информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Где водятся OGRыАтака на Internet
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
... или...сrc_start=0xfffffffe,0xfffffffd...или число раундов... 05.12.02 09:37  Число просмотров: 4287
Автор: Chingachguk <Chingachguk> Статус: Member
<"чистая" ссылка>
> Собственно проблема состоит в том, что нужно много (хотя бы
> штук 20) разных хэш функций. CRC вполне устраивает, только
> я не могу найти ни одного полинома в 32 бита, кроме того,
> что в ГОСТе, ISO и CCITT. Если есть другие идеи или другие
> полиномы, очень был бы благодарен...
> Спасибо.

Все зависит от задачи. Насколько криптостойкой тебе нужна подпись.
Если просто контроль данных, то можно и crc с разными стартовыми значениями (не FFFFFFFFh, а FFFFFFFE и т.д.)

А вообще можно хоть 4xDES, 5xDES - есть же трайпл DES.
Увеличь число раундовых преобразований в каком-нибудь хэше,
<theory>
полиномы для CRC32 или... 05.12.02 00:47  
Автор: SemenU Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Собственно проблема состоит в том, что нужно много (хотя бы штук 20) разных хэш функций. CRC вполне устраивает, только я не могу найти ни одного полинома в 32 бита, кроме того, что в ГОСТе, ISO и CCITT. Если есть другие идеи или другие полиномы, очень был бы благодарен...
Спасибо.
легко сгенерировать самому 05.12.02 09:39  
Автор: RElf <M> Статус: Member
Отредактировано 05.12.02 10:16  Количество правок: 1
<"чистая" ссылка>
> Собственно проблема состоит в том, что нужно много (хотя бы
> штук 20) разных хэш функций. CRC вполне устраивает, только
> я не могу найти ни одного полинома в 32 бита, кроме того,
> что в ГОСТе, ISO и CCITT. Если есть другие идеи или другие
> полиномы, очень был бы благодарен...

Я тут как-то исследованием CRC64 занимался - много чего интересного нарыл. Посмотри на страничке и дальше по ссылкам:

CRC64 и не только
попробуем... 07.12.02 03:06  
Автор: SemenU Статус: Незарегистрированный пользователь
<"чистая" ссылка>
За ссылку спасибо... Почитал и решил обойтись простыми полиномами...

Сгенерировать их в домашних условиях не получилось (долго это, разве нет?), а вот готовых нашелся список из 2000 шт!

Если интересно, зачем было нужно: Bloom фильтры нужно сделать. На деле, я думаю функциями 6-8 обойдется. Альтернативно, я видел, люди делали так: брали MD5 шириной 128 бит, и резали на 4 куска (по 32, соответственно). Однако, оптимальный случай для 4-х хэш функций дает >5% false positive rate. Мне кажется с CRC32 выдет быстрее и экономнее.

Спасибо, на деле оказался единственный форум из 6, где ответили; помогло, а то я неуверенно седя ощущал.
попробуем... 07.12.02 07:41  
Автор: RElf <M> Статус: Member
<"чистая" ссылка>
> За ссылку спасибо... Почитал и решил обойтись простыми
> полиномами...
>
> Сгенерировать их в домашних условиях не получилось (долго
> это, разве нет?),

Вовсе нет. Например, см. ниже по ссылке.

> а вот готовых нашелся список из 2000 шт!

Тоже вариант.

> Если интересно, зачем было нужно: Bloom фильтры нужно
> сделать. На деле, я думаю функциями 6-8 обойдется.
> Альтернативно, я видел, люди делали так: брали MD5 шириной
> 128 бит, и резали на 4 куска (по 32, соответственно).
> Однако, оптимальный случай для 4-х хэш функций дает >5%
> false positive rate. Мне кажется с CRC32 выдет быстрее и
> экономнее.

Что-то я все равно не понял, что дано и что нужно получить.


A fast algorithm for listing all degree n irreducible and primitive polynomials over GF(2)
bloom filter это... 07.12.02 15:00  
Автор: SemenU Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> > Сгенерировать их в домашних условиях не получилось (долго
> > это, разве нет?),
> Вовсе нет. Например, см. ниже по ссылке.
>
Спасибо, почитаю...

> > [skiped про bloom фильтр]
> Что-то я все равно не понял, что дано и что нужно получить.Вот ссылка про эти самые фильтры, там все просто...

http://www.cs.wisc.edu/~cao/papers/summary-cache/node8.html
... или...сrc_start=0xfffffffe,0xfffffffd...или число раундов... 05.12.02 09:37  
Автор: Chingachguk <Chingachguk> Статус: Member
<"чистая" ссылка>
> Собственно проблема состоит в том, что нужно много (хотя бы
> штук 20) разных хэш функций. CRC вполне устраивает, только
> я не могу найти ни одного полинома в 32 бита, кроме того,
> что в ГОСТе, ISO и CCITT. Если есть другие идеи или другие
> полиномы, очень был бы благодарен...
> Спасибо.

Все зависит от задачи. Насколько криптостойкой тебе нужна подпись.
Если просто контроль данных, то можно и crc с разными стартовыми значениями (не FFFFFFFFh, а FFFFFFFE и т.д.)

А вообще можно хоть 4xDES, 5xDES - есть же трайпл DES.
Увеличь число раундовых преобразований в каком-нибудь хэше,
... или...сrc_start=0xfffffffe,0xfffffffd...или число раундов... 07.12.02 03:32  
Автор: SemenU Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> Все зависит от задачи. Насколько криптостойкой тебе нужна
> подпись.
Криптостойкость мне совсем не нужна... Хотя я не совсем понимаю, что это значит.

Нужно несколько таких функций H[i], 1<=i<=N, чтоб на разных данных X и Y
значения функций H[i](X) и H[j](Y) были (по возможности) не равны для любых i и j, 1<=i,j<=N.

> Если просто контроль данных, то можно и crc с разными
> стартовыми значениями (не FFFFFFFFh, а FFFFFFFE и т.д.)
>
Согласен с утверждением, что получится H[i](X) = H[i+1](X) + C[i]. Не подходит.

> А вообще можно хоть 4xDES, 5xDES - есть же трайпл DES.
> Увеличь число раундовых преобразований в каком-нибудь хэше,
Если я правильно понял, предлагается что-то типа:

Пусть H(X) - хэш функция. Положим тогда H[i] = H^i.

А не получится ли так, что если для каких-то i0 и j0 H[i0](X) == H[j0](Y), то
H[i0+n](X) == H[j0+n](Y) для всех n, 1<=n<=min(N-i0, N-j0). Помоему, получится именно так. Это не есть хорошо...

Спасибо.
Предлагал про хэш я другое. С CRC был не прав. 09.12.02 16:57  
Автор: Chingachguk <Chingachguk> Статус: Member
<"чистая" ссылка>
> > А вообще можно хоть 4xDES, 5xDES - есть же трайпл DES.
> > Увеличь число раундовых преобразований в каком-нибудь
> хэше,
> Если я правильно понял, предлагается что-то типа:

Нет. Я предлагал видоизменить алгоритм какого-нибудь хэша, например MD5. Во многих (которые я видел, я не знаток криптографии) хэш-функциях есть понятие "раундового преобразования". Те на самом деле хэш-функцию можно представить в виде:

h = MD5(text);

h1 = MD5_r(text1) (раундовая функция хэша, text1 - часть text или целая),

h2 = MD5_r(h1),
...
и тд.

Например, в алгоритме MD5 есть часть, которую называют "подбитие дайджеста" - используется, когда входные данные достигают определенной кратности, например 512-ти битам:

;static void MDTransformF (UINT4 s[4, UINT4 x16])
PFF s0,s1,s2,s3,x0,S11,0d76aa478h ; // 1
PFF s3,s0,s1,s2,x1,S12,0e8c7b756h ; // 2
...
PFF s1,s2,s3,s0,x15,S14,049b40821h ; // 16
; static void MDTransformG (UINT4 s[4, UINT4 x16])
PGG s0,s1,s2,s3,x1,S21, 0f61e2562h ; // 17
PGG s3,s0,s1,s2,x6,S22, 0c040b340h ; // 18
...
PGG s1,s2,s3,s0,x12,S24,08d2a4c8ah ; // 32
; static void MDTransformH (UINT4 s[4, UINT4 x16])
PHH s0,s1,s2,s3,x5,S31, 0fffa3942h ; // 33
PHH s3,s0,s1,s2,x8,S32, 08771f681h ; // 34
...
PHH s1,s2,s3,s0,x2,S34, 0c4ac5665h ; // 48
; static void MDTransformI (UINT4 s[4, UINT4 x16])
PII s0,s1,s2,s3,x0,S41, 0f4292244h ; // 49
PII s3,s0,s1,s2,x7,S42, 0432aff97h ; // 50
...
PII s1,s2,s3,s0,x9,S44, 0eb86d391h ; // 64

Если выкинуть(изменить) часть таких преобразований, то можно получить (в ущерб стойкости ?) совершенно другой хэш.

Про трайпл-дез - совершенно другая была мысль. Собственно, смотри сам трайпл. Можно сделать трайпл-MD5 или дабл-DES.

боюсь с другими алгоритмами получится, как с CRC 10.12.02 08:17  
Автор: SemenU Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> Нет. Я предлагал видоизменить алгоритм какого-нибудь хэша,
> например MD5. Во многих (которые я видел, я не знаток
> криптографии) хэш-функциях есть понятие "раундового
> преобразования". Те на самом деле хэш-функцию можно
> представить в виде:
>
> [skiped]
>
Я это, боюсь не стандартизованный полином для CRC32 использовать, а вы мне алгоритм менять предлагаете! Не, чур меня, чур... Меня же кошмары по ночам замучают.

Вобшем, поразному портить входные данные к, скажем, MD5 кажется лучше. Например,
H(1)= MD5(X),
H(2) = MD5(X*H(2))
...
H(i) = MD5(X*H(i-1))

где * - XOR, напрмер...
а что если... 07.12.02 07:36  
Автор: RElf <M> Статус: Member
<"чистая" ссылка>
> Нужно несколько таких функций H[i], 1<=i<=N, чтоб на
> разных данных X и Y
> значения функций H[i](X) и H[j](Y) были (по возможности) не
> равны для любых i и j, 1<=i,j<=N.

А почему бы просто не положить H[i](X) = f(i||X), где f какая-нибудь фиксированная хэш-функция нужной размерности?
Т.е. приписываем i к данным X слева ("конкатинируем" i и X), и от всего этого считаем значение f.
а доказательство? 07.12.02 15:45  
Автор: SemenU Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> А почему бы просто не положить H[i](X) = f(i||X), где f
> какая-нибудь фиксированная хэш-функция нужной размерности?
> Т.е. приписываем i к данным X слева ("конкатинируем" i и
> X), и от всего этого считаем значение f.

Да, подобная идея была в моей голове. Но я не такой спец в этом вопросе, и боюсь я, что не сработает это. Тут все начинает зависеть от f, не так ли?

Например, пусть f(X) = X % P (остаток от деления X на P). Пусть все X одной длины.
i|X обобщим как A*i + B*X.

H[i](X) = (A*i + B*X) % P

Поищем H[n](X) - H[m](X) по модулю P:
((A*n + B*X) % P - (A*m +B*X) % P) = (A*(n-m)) mod P, т.е.
H[n](X) == H[m](X) + (A*(n-m) % P) + t*P, где t 0, 1 или -1

Вобщем нужны функции, которые бы друг через друга очень сложно выражались...
А лучше никак :), только не понятно, что это значит...
Но, определенно, если взять H[i](X) := A % Pi, и Pi попарно различные простые, тогда все намного лучше! Правильно?

Кто нибудь представляет себе, что будет, если f - это MD5? Можно ли выразить
значение MD5(A*x + B) через MD5(x)? Хмм... Сам подумал и кажется, что нет... Или да?
спасет collision-resistant hash-function 08.12.02 00:35  
Автор: RElf <M> Статус: Member
Отредактировано 08.12.02 00:36  Количество правок: 1
<"чистая" ссылка>
> > А почему бы просто не положить H[i](X) = f(i||X), где f
> > какая-нибудь фиксированная хэш-функция нужной размерности?
> > Т.е. приписываем i к данным X слева ("конкатинируем" i и
> > X), и от всего этого считаем значение f.
>
> Да, подобная идея была в моей голове. Но я не такой спец в
> этом вопросе, и боюсь я, что не сработает это. Тут все
> начинает зависеть от f, не так ли?
>
> Например, пусть f(X) = X % P (остаток от деления X на P).

Это плохой пример. Нужно смотреть в сторону collision-resistant (collision-free) хэш-фукнций. Ссылка внизу.

> Пусть все X одной длины. i|X обобщим как A*i + B*X.
>
> H[i](X) = (A*i + B*X) % P
>
> Поищем H[n](X) - H[m](X) по модулю P:
> ((A*n + B*X) % P - (A*m +B*X) % P) = (A*(n-m)) mod P, т.е.
> H[n](X) == H[m](X) + (A*(n-m) % P) + t*P, где t 0, 1 или -1
>
> Вобщем нужны функции, которые бы друг через друга очень
> сложно выражались...
> А лучше никак :), только не понятно, что это значит...
> Но, определенно, если взять H[i](X) := A % Pi, и Pi попарно
> различные простые, тогда все намного лучше! Правильно?

Не факт. Если например положить P равным произведению Pi (или простому числу того же порядка), то получиться примерно тоже самое.

> Кто нибудь представляет себе, что будет, если f - это MD5?
> Можно ли выразить значение MD5(A*x + B) через MD5(x)?

Вряд ли. По крайней мере это криптографический хэш, что, в частности, подразумевает отсутствие функциональных закономерностей между MD5(A*x+B) и MD5(x). Хотя это не доказано.

Посмотри Chapter 9 "Hash Functions and Data Integrity" в

Handbook of Applied Cryptography
спасет collision-resistant hash-function 09.12.02 15:45  
Автор: SemenU Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> > Например, пусть f(X) = X % P (остаток от деления X на P).
>
> Это плохой пример. Нужно смотреть в сторону
> collision-resistant (collision-free) хэш-фукнций. Ссылка
> внизу.
>
Пример-то, конечно, плохой... Хотя, разве CRC не есть остаток от деления? Правда полиномы там, но все же.

Почитаю... может пойму чего лишнего.

> > Но, определенно, если взять H[i](X) := X % Pi, и Pi попарно
> > различные простые, тогда все намного лучше! Правильно?
>
> Не факт. Если например положить P равным произведению Pi
> (или простому числу того же порядка), то получиться
> примерно тоже самое.
>
Гмм... Да нет же... Видимо я туплю, но:

пусть X == A1 mod P1 и X == A2 mod P2. Я утверждаю, что A1 и A2 не связанны
никаким уравнением не включающим X.

другими словами: Для любых A1 и A2 существует X, что выполняются два вышепривенных равенства. X, например, (A2-A1)P1^(P2-1) + A1

> > Кто нибудь представляет себе, что будет, если f - это MD5?
> > Можно ли выразить значение MD5(A*x + B) через MD5(x)?
>
> Вряд ли. По крайней мере это
> криптографический хэш, что, в частности,
> подразумевает отсутствие функциональных закономерностей
> между MD5(A*x+B) и MD5(x). Хотя это не доказано.
>
Да-аа... Я так и думал.

MD5 - это круто. Может и правда, закрыть глаза на то, что он в несколько раз
медленнее CRC. За то 128 бит сразу! За то можно линейно портить данные, и получать другие хэш функции...

Правда немножечко я еще сомневаюсь... Разве может быть все так просто?
выбор богатый 10.12.02 00:00  
Автор: RElf <M> Статус: Member
<"чистая" ссылка>
> Пример-то, конечно, плохой... Хотя, разве CRC не есть
> остаток от деления? Правда полиномы там, но все же.

Это верно.

> > > Но, определенно, если взять H[i](X) := X % Pi, и
> > > Pi попарно различные простые, тогда все намного лучше!
> > > Правильно?

> > Не факт. Если например положить P равным произведению Pi
> > (или простому числу того же порядка), то получиться
> > примерно тоже самое.
> >
> Гмм... Да нет же... Видимо я туплю, но:
>
> пусть X == A1 mod P1 и X == A2 mod P2. Я утверждаю, что A1
> и A2 не связанны никаким уравнением не включающим X.

Тоже самое справедливо для приведенного мной примера.

> другими словами: Для любых A1 и A2 существует X, что
> выполняются два вышепривенных равенства.

Но заметь, что такое X не единственное: X+P1*P2 тоже удовлетворяет равенствам.

[...]

> MD5 - это круто. Может и правда, закрыть глаза на то, что
> он в несколько раз медленнее CRC.

Если нужна большая скорость и разрядность, то возможно лучше использовать CRC64 в качестве компромиса.

> За то 128 бит сразу! За то можно линейно
> портить данные, и получать другие хэш функции...

> Правда немножечко я еще сомневаюсь... Разве может быть все
> так просто?

Проверено электроникой ;-)
и точно, выбор богатый. Но ничего точно пока не выяснилось... 10.12.02 08:07  
Автор: SemenU Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> > Пример-то, конечно, плохой... Хотя, разве CRC не есть
> > остаток от деления? Правда полиномы там, но все же.
>
> Это верно.
>
Угу, только там не все так, как у целых чисел. Напрмер, если я не ошибаюсь, существуют неразложимые, но и не простые полиномы. Ну да ладно.

> > > > Но, определенно, если взять H[i](X) := X % Pi, и
> > > > Pi попарно различные простые, тогда все намного лучше!
> > > > Правильно?
>
> > другими словами: Для любых A1 и A2 существует X, что
> > выполняются два вышепривенных равенства.
>
> Но заметь, что такое X не единственное: X+P1*P2 тоже
> удовлетворяет равенствам.
>
Это - да... Другими словами, CRC не является ни "preimage resistant", ни "2nd preimage resistant" ни "collision resistant". CRC вообще не OWF ("One Way Function"). CRC - это просто "hash function", def. 9.1 из той самой книги, на которую была ссылка.

> > MD5 - это круто. Может и правда, закрыть глаза на то, что
> > он в несколько раз медленнее CRC.
>
> Если нужна большая скорость и разрядность, то возможно
> лучше использовать CRC64 в качестве компромиса.
>
А я думаю, это еще вопрос для исследования, что быстрее CRC64 или два разных CRC32, чтобы получить 64 бита. Хотя CRC64 должен иметь большую эффективную ширину (есть такой термин?), чем пара < CRC32, CRC32>.

> > За то 128 бит сразу! За то можно линейно
> > портить данные, и получать другие хэш функции...
> > Правда немножечко я еще сомневаюсь... Разве может быть все
> > так просто?
>
> Проверено электроникой ;-)
:-) Я другое имел в виду...
фиолетово 10.12.02 11:17  
Автор: RElf <M> Статус: Member
<"чистая" ссылка>
> > Если нужна большая скорость и разрядность, то возможно
> > лучше использовать CRC64 в качестве компромиса.
> >
> А я думаю, это еще вопрос для исследования, что быстрее
> CRC64 или два разных CRC32, чтобы получить 64 бита. Хотя
> CRC64 должен иметь большую эффективную ширину (есть такой
> термин?), чем пара < CRC32, CRC32>.

На самом деле CRC64 или два CRC32 - не суть важно. Если CRC32 построены на двух различных неприводимых полиномах p,q 32-й степени, а CRC64 на полиноме r 64-й степени, то между каждое CRC32 есть проекция на F_{2^32} (поле из 2^32 элементов), а CRC64 проекция на F_{2^64}. При этом F_{2^32}xF_{2^32} и F_{2^64} равномощны.
По скорости выигрывает та CRC, чья разрядность совпадает с разрядностью процессора, хотя этот выигрыш незначителен.

В общем, если тебе не важна криптостойкость, наверное, все-таки лучше использовать набор из нескольких CRC-R, где R разрядность процессора.
Использование криптографических хэш-фукнций здесь необосновано и ведет к значительному проигрышу в скорости. Всякой функции - своя область применения ;-)
стартовое значение особой роли не играет 05.12.02 09:47  
Автор: RElf <M> Статус: Member
<"чистая" ссылка>
> Если просто контроль данных, то можно и crc с разными
> стартовыми значениями (не FFFFFFFFh, а FFFFFFFE и т.д.)

Можно показать, что CRC подсчитанные таким образом отличаются (xor) на константу, которая не зависит от данных, а только от начальных значений. Таким образом, использование другого начального значения с тем же полиномом не дает абсолютно ничего.

> А вообще можно хоть 4xDES, 5xDES - есть же трайпл DES.
> Увеличь число раундовых преобразований в каком-нибудь хэше,

Тогда уж лучше использовать хеш-функции типа MD5, SHA-1 и т.д. Но все они сильно проигрывают CRC по скорости.
не обольщайтсь 23.01.03 18:34  
Автор: Persicum Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Не все неприводимые многочлены
являются многочленами максимальной длины!!!
Я вот скачал недавно таблицу 5-битовых 32-разрядных полиномов.
Стал проверять, из них набралось тока сто штук с периодом FFFFFFFF,
из огромного числа.
Не обольщайтесь!!! 23.01.03 18:31  
Автор: Guest Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Не все неприводимые многочлены
являются многочленами максимальной длины!!!
Я вот скачал недавно таблицу 5-битовых 32-разрядных полиномов.
Стал проверять, из них набралось тока сто штук с периодом FFFFFFFF,
из огромного числа.
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach