Snefru | это... Что такое Snefru? (original) (raw)

Snefru — это криптографическая однонаправленная хеш-функция, предложенная Ральфом Мерклом. (Само название Snefru, продолжая традиции блочных шифров Khufu и Khafre, также разработанных Ральфом Мерклом, представляет собой имя египетского фараона). Функция Snefru преобразует сообщения произвольной длины в хеш длины (обычно m=128 или m=256 ).

Описание алгоритма хеширования

Входное сообщение разбивается на блоки длиной 512-m битов. Основой алгоритма является функция , принимающая на входе 512 — разрядное значение и вычисляющая — разрядное значение. Каждый новый блок сообщения конкатенируется с хешем, вычисленным для предыдущего блока, и поступает на вход функции . Первый блок объединяется со строкой нулей. Хеш последнего блока конкатенируется с двоичным представлением длины сообщения (MD – усиление), и полученная конкатенация хешируется последний раз.

Функция основана на (обратимой) функции блочного шифрования , принимающей и вычисляющей 512 — битные значения. возвращает XOR — комбинацию первых битов входа функции и последних битов выхода функции . Функция смешивает входные данные в несколько шагов. Каждый шаг состоит из 64 раундов. В ходе одного раунда берется слово сообщения и младший значащий байт этого слова подается на блок, выходом которого также является слово. Далее выполняется операция XOR полученного слова с двумя соседними словами в сообщении. Таким образом, в одном раунде, используя один байт слова, изменяются два соседних с ним слова в сообщении. В конце раунда байты используемого слова перемешиваются так, чтобы в следующий раз на вход блока попал другой байт (происходит ряд циклических сдвигов на 8, 16 или 24 разряда). Так как раундов 64, а слов 16, то каждое слово используется четыре раза, следовательно, каждый байт сообщения используется в качестве входа блока. Построение блока аналогично построению в алгоритме Khafre.

Если число шагов в функции равно ( 128 раундов), то функция Snefru называется двухпроходной, если число шагов равно ( 192 раунда) то Snefru трехпроходная, и так далее.

Криптоанализ Snefru

В марте 1990 года была назначена награда в 1000$ первому, кто сможет взломать двухпроходный вариант Snefru, найдя два сообщения с одинаковым хеш-кодом (то есть показать, что Snefru не является стойкой к коллизиям 2-го рода). Аналогичная награда была объявлена позже за взлом четырехпроходного варианта Snefru.

Используя средства дифференциального анализа, Эли Бихам и Ади Шамир показали, что двухпроходная функция Snefru (с 128 — разрядным хешем) не является стойкой к коллизиям 1-го рода и 2-го рода.

Описание атаки

Стандартная атака на хеш-функции основана на парадоксе «дней рождения». Если подвергнуть хешированию $2^{m/2}$ ( $2^{64}$ , когда m=128 ) различных сообщений, то с высокой вероятностью получится найти пару с одинаковым хешем. Такая атака применима к любой хеш-функции, вне зависимости от ее реализации.

Для Snefru Бихам и Шамир разработали метод дифференциального криптоанализа, который не зависит от выбора блоков и даже может быть использован в том случае, когда блоки не известны криптоаналитику.

При длине хеша m=128 длина блоков, на которые делится входное сообщение равно 512-m=384 . В данной атаке был применен алгоритм, отыскивающий два входных значения функции ( 512 — разрядные значения), отличающиеся только в первых 384 разрядах, формируемых из блоков входного сообщения, но при этом, имеющих один и тот же хеш.

Шаги алгоритма:

Выбирается произвольный блок длиной бита. К нему приписывается строка нулей (или любой другой — битный вектор, например, хеш предыдущего блока), формируя — разрядный входной блок для функции . Вычисляется .
Создается второй входной блок для функции путем изменения по одному байту в и словах первого блока. При этом меняется именно часть, содержащаяся в первых битах, приписанная строка не меняется. Изменяемые байты в и словах — те, которые будут использованы в качестве входных значениях блока в и раундах соответственно. Вычисляется .
Сравниваются значения функции от входных блоков, полученных в шагах 1) и 2). С вероятностью $2^{-40}$ будет найдена пара с одинаковым хешем.

Таким образом, вычисляя функцию от приблизительно $2^{41}$ пар блоков, можно найти коллизию 2-го рода для Snefru.

Пояснение алгоритма атаки

Так как изменения, применяемые на шаге , касаются только байтов, которые используются в и раундах, то значения блоков после раундов с номером < на шагах и будут одинаковы.

В -м раунде байт из -го слова используется для изменения -го и -го слов. Байт подается на вход блока, на выходе которого — слово. Далее выполняется операция XOR с -м и -м словами. При изменении этого байта (в шаге ), а также байта -го слова, который используется как вход блока в -м раунде, с вероятностью 1/256 после выполнения операции XOR байт в -м слове окажется таким же, как этот же байт в блоке в шаге после -и раундов. Тогда, подавая этот байт в -м раунде на вход блока, на выходе получим то же значение, что и в -м раунде, осуществляемом над блоком из шага . Следовательно, -е слово будет одинаково после раунда для обоих шагов. Одинаковым окажется также и -е слово после раунда, -е слово после раунда, …, -е слово после раунда, -е слово после раунда, …, -е слово после раунда, так как вход блока для обоих шагов в этих раундах один и тот же.

-е слово разное для шагов уже после -го раунда. Поэтому на -м раунде оно станет причиной того, что станут различными для двух этапов значения -го и -го слов. То же самое произойдет и на -м раунде для слов и . И снова, с вероятностью 1/256 , байт в -м слове, который будет использоваться в качестве входа блока в -м раунде, будет одинаков для шагов и . А значит, одинаковыми будут -е, …, -е, -е, …, -е слова. Изменения начнутся, когда будет использовано -е слово в -м раунде.

Таким образом, если после , , , 104 и 120 -го раундов байт в -м слове, который будет использоваться в качестве входа для блока в следующих за указанными раундах, будет одинаков для обоих шагов, то одинаковы после полных 128 раундов окажутся слова , , …, . Вероятность этого события $(1/256)^5=2^{-40}$ . Так как в качестве хеша блока берется значение операции XOR от первых 4-х слов входного блока функции и первых 4-х слов выходного блока функции , то хеши, вычисленные на обоих шагах окажутся одинаковыми.

Сравнение атаки с известными методами криптоанализа

Метод был применен также к трехпроходной и четырехпроходной функции Snefru, показав лучшие результаты по сравнению с методом «дней рождения».

Сравнение атаки Шамира и Бихама с атакой «дней рождения»

Количество проходовфункции Snefru	Длина хеша,	Сложность атаки	Метод «дней рождения»
2	128 — 192	$2^{12.5}$	$2^{64}$ — $2^{96}$
224	$2^{12.5}$	$2^{112}$
3	128 — 192	$2^{28.5}$	$2^{64}$ — $2^{96}$
224	$2^{33}$	$2^{112}$
4	128 — 192	$2^{44.5}$	$2^{64}$ — $2^{96}$
224	$2^{81}$	$2^{112}$

С помощью этой атаки можно найти множество пар, у которых одинаковый хеш, и, кроме того, разыскать несколько сообщений, хеш которых равен хешу данного сообщения (коллизия 1-го рода). Количество операций, требующееся для отыскания коллизии 1-го рода, в данной атаке меньше, чем в методе «грубой силы».

Сравнение атаки Шамира и Бихама с методом «грубой силы»

Количество проходовфункции Snefru	Длина хеша,	Сложность атаки	Метод «грубой силы»
2	128 — 224	$2^{24}$	$2^{128}$ — $2^{224}$
3	128 — 224	$2^{56}$	$2^{128}$ — $2^{224}$
4	128 — 192	$2^{88}$	$2^{128}$ — $2^{192}$

Примечания

В данное время Меркл советует применять функцию Snefru с не менее чем восемью проходами. Однако с таким количеством проходов вычисление функции Snefru в значительной степени замедляется, сравнительно с функциями MD5 или SHA.

Литература

Eli Biham, Adi Shamir. Differential cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer (Extended Abstract).
Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. — М.: ТРИУМФ, 2003. — 816 с. — ISBN 5-89392-055-4

Хеш-функции
Общего назначения	Adler-32 • CRC • FNV • Murmur2 • PJW-32 • TTH • Jenkins hash
Криптографические	JH • HAVAL • Keccak (SHA-3) • LM-хеш • MD2 • MD4 • MD5 • MD6 • N-Hash • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 • SHA-1 • SHA-2 • Skein • Snefru • Tiger • Whirlpool • ГОСТ Р 34.11-94