Snefru

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

В данное время Меркл советует применять функцию 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.