информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
За кого нас держат?Spanning Tree Protocol: недокументированное применениеВсе любят мед
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 С наступающим 
 Серьезная уязвимость в Apache Log4j 
 Крупный взлом GoDaddy 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
легко сгенерировать самому 05.12.02 09:39  Число просмотров: 3682
Автор: RElf <M> Статус: Member
Отредактировано 05.12.02 10:16  Количество правок: 1
<"чистая" ссылка>
> Собственно проблема состоит в том, что нужно много (хотя бы
> штук 20) разных хэш функций. CRC вполне устраивает, только
> я не могу найти ни одного полинома в 32 бита, кроме того,
> что в ГОСТе, ISO и CCITT. Если есть другие идеи или другие
> полиномы, очень был бы благодарен...

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

CRC64 и не только
<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-2022 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach