Snefru

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Количество проходов функции Snefru	Длина хеша, ${\displaystyle m}$	Сложность атаки	Метод «грубой силы»
2	128 — 224	${\displaystyle 2^{24}}$	${\displaystyle 2^{128}}$ — ${\displaystyle 2^{224}}$
3	128 — 224	${\displaystyle 2^{56}}$	${\displaystyle 2^{128}}$ — ${\displaystyle 2^{224}}$
4	128 — 192	${\displaystyle 2^{88}}$	${\displaystyle 2^{128}}$ — ${\displaystyle 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.