Snefru

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

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

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

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

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

Криптоанализ SnefruПравить

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

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

Описание атакиПравить

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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