Snefru

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В $56$-м раунде байт из $8$-го слова используется для изменения $7$-го и $9$-го слов. Байт подается на вход $S$ блока, на выходе которого — слово. Далее выполняется операция XOR с $7$-м и $9$-м словами. При изменении этого байта (в шаге $2$), а также байта $9$-го слова, который используется как вход $S$ блока в $57$-м раунде, с вероятностью $1/256$ после выполнения операции XOR байт в $9$-м слове окажется таким же, как этот же байт в блоке в шаге $1$ после $56$-и раундов. Тогда, подавая этот байт в $57$-м раунде на вход $S$ блока, на выходе получим то же значение, что и в $57$-м раунде, осуществляемом над блоком из шага $1$. Следовательно, $10$-е слово будет одинаково после $57$ раунда для обоих шагов. Одинаковым окажется также и $11$-е слово после $58$ раунда, $12$-е слово после $59$ раунда, …, $16$-е слово после $64$ раунда, $1$-е слово после $65$ раунда, …, $6$-е слово после $69$ раунда, так как вход $S$ блока для обоих шагов в этих раундах один и тот же.

$7$-е слово разное для шагов уже после $56$-го раунда. Поэтому на $71$-м раунде оно станет причиной того, что станут различными для двух этапов значения $6$-го и $8$-го слов. То же самое произойдет и на $72$-м раунде для слов $7$ и $9$. И снова, с вероятностью $1/256$, байт в $9$-м слове, который будет использоваться в качестве входа $S$ блока в $73$-м раунде, будет одинаков для шагов $1$ и $2$. А значит, одинаковыми будут $10$-е, …, $16$-е, $1$-е, …, $5$-е слова. Изменения начнутся, когда будет использовано $6$-е слово в $86$-м раунде.

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

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

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

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

Количество проходов функции Snefru	Длина хеша, $m$	Сложность атаки	Метод «дней рождения»
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	Длина хеша, $m$	Сложность атаки	Метод «грубой силы»
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.