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