Русская Википедия:Snefru
Snefru — криптографическая хеш-функция, предложенная Ральфом Мерклом. (Само название Snefru, продолжая традиции блочных шифров Khufu и Khafre, также разработанных Ральфом Мерклом, представляет собой имя египетского фараона). Функция Snefru преобразует сообщения произвольной длины в хеш длины <math>m</math> (обычно <math>m=128</math> или <math>m=256</math>).
Описание алгоритма хеширования
Входное сообщение разбивается на блоки длиной <math>512-m</math> битов. Основой алгоритма является функция <math>H</math>, принимающая на входе <math>512</math> — разрядное значение и вычисляющая <math>m</math> — разрядное значение. Каждый новый блок сообщения конкатенируется с хешем, вычисленным для предыдущего блока, и поступает на вход функции <math>H</math>. Первый блок объединяется со строкой нулей. Хеш последнего блока конкатенируется с двоичным представлением длины сообщения (MD – усиление), и полученная конкатенация хешируется последний раз.
Функция <math>H</math> основана на (обратимой) функции блочного шифрования <math>E</math>, принимающей и вычисляющей <math>512</math> — битные значения. <math>H</math> возвращает XOR — комбинацию первых <math>m</math> битов входа функции <math>E</math> и последних <math>m</math> битов выхода функции <math>E</math>. Функция <math>E</math> смешивает входные данные в несколько шагов. Каждый шаг состоит из 64 раундов. В ходе одного раунда берется слово сообщения и младший значащий байт этого слова подается на <math>S</math> блок, выходом которого также является слово. Далее выполняется операция XOR полученного слова с двумя соседними словами в сообщении. Таким образом, в одном раунде, используя один байт слова, изменяются два соседних с ним слова в сообщении. В конце раунда байты используемого слова перемешиваются так, чтобы в следующий раз на вход <math>S</math> блока попал другой байт (происходит ряд циклических сдвигов на 8, 16 или 24 разряда). Так как раундов 64, а слов 16, то каждое слово используется четыре раза, следовательно, каждый байт сообщения используется в качестве входа <math>S</math> блока. Построение <math>S</math> блока аналогично построению в алгоритме Khafre.
Если число шагов в функции <math>E</math> равно <math>2</math> (<math>128</math> раундов), то функция Snefru называется двухпроходной, если число шагов равно <math>3</math> (<math>192</math> раунда) то Snefru трехпроходная, и так далее.
Криптоанализ Snefru
В марте 1990 года была назначена награда в 1000$ первому, кто сможет взломать двухпроходный вариант Snefru, найдя два сообщения с одинаковым хеш-кодом (то есть показать, что Snefru не является стойкой к коллизиям 2-го рода). Аналогичная награда была объявлена позже за взлом четырехпроходного варианта Snefru.
Используя средства дифференциального анализа, Эли Бихам и Ади Шамир показали, что двухпроходная функция Snefru (с <math>128</math> — разрядным хешем) не является стойкой к коллизиям 1-го рода и 2-го рода.
Описание атаки
Стандартная атака на хеш-функции основана на парадоксе «дней рождения». Если подвергнуть хешированию <math>2^{m/2}</math> (<math>2^{64}</math>, когда <math>m=128</math>) различных сообщений, то с высокой вероятностью получится найти пару с одинаковым хешем. Такая атака применима к любой хеш-функции, вне зависимости от её реализации.
Для Snefru Бихам и Шамир разработали метод дифференциального криптоанализа, который не зависит от выбора <math>S</math> блоков и даже может быть использован в том случае, когда <math>S</math> блоки не известны криптоаналитику.
При длине хеша <math>m=128</math> длина блоков, на которые делится входное сообщение равно <math>512-m=384</math>. В данной атаке был применен алгоритм, отыскивающий два входных значения функции <math>H</math> (<math>512</math> — разрядные значения), отличающиеся только в первых <math>384</math> разрядах, формируемых из блоков входного сообщения, но при этом, имеющих один и тот же хеш.
Шаги алгоритма:
- Выбирается произвольный блок длиной <math>384</math> бита. К нему приписывается строка нулей (или любой другой <math>128</math> — битный вектор, например, хеш предыдущего блока), формируя <math>512</math> — разрядный входной блок для функции <math>H</math>. Вычисляется <math>H</math>.
- Создается второй входной блок для функции <math>H</math> путём изменения по одному байту в <math>8</math> и <math>9</math> словах первого блока. При этом меняется именно часть, содержащаяся в первых <math>384</math> битах, приписанная строка не меняется. Изменяемые байты в <math>8</math> и <math>9</math> словах — те, которые будут использованы в качестве входных значениях <math>S</math> блока в <math>56</math> и <math>57</math> раундах соответственно. Вычисляется <math>H</math>.
- Сравниваются значения функции <math>H</math> от входных блоков, полученных в шагах 1) и 2). С вероятностью <math>2^{-40}</math> будет найдена пара с одинаковым хешем.
Таким образом, вычисляя функцию <math>H</math> от приблизительно <math>2^{41}</math> пар блоков, можно найти коллизию 2-го рода для Snefru.
Пояснение алгоритма атаки
Так как изменения, применяемые на шаге <math>2</math>, касаются только байтов, которые используются в <math>56</math> и <math>57</math> раундах, то значения блоков после раундов с номером < <math>56</math> на шагах <math>1</math> и <math>2</math> будут одинаковы.
В <math>56</math>-м раунде байт из <math>8</math>-го слова используется для изменения <math>7</math>-го и <math>9</math>-го слов. Байт подается на вход <math>S</math> блока, на выходе которого — слово. Далее выполняется операция XOR с <math>7</math>-м и <math>9</math>-м словами. При изменении этого байта (в шаге <math>2</math>), а также байта <math>9</math>-го слова, который используется как вход <math>S</math> блока в <math>57</math>-м раунде, с вероятностью <math>1/256</math> после выполнения операции XOR байт в <math>9</math>-м слове окажется таким же, как этот же байт в блоке в шаге <math>1</math> после <math>56</math>-и раундов. Тогда, подавая этот байт в <math>57</math>-м раунде на вход <math>S</math> блока, на выходе получим то же значение, что и в <math>57</math>-м раунде, осуществляемом над блоком из шага <math>1</math>. Следовательно, <math>10</math>-е слово будет одинаково после <math>57</math> раунда для обоих шагов. Одинаковым окажется также и <math>11</math>-е слово после <math>58</math> раунда, <math>12</math>-е слово после <math>59</math> раунда, …, <math>16</math>-е слово после <math>64</math> раунда, <math>1</math>-е слово после <math>65</math> раунда, …, <math>6</math>-е слово после <math>69</math> раунда, так как вход <math>S</math> блока для обоих шагов в этих раундах один и тот же.
<math>7</math>-е слово разное для шагов уже после <math>56</math>-го раунда. Поэтому на <math>71</math>-м раунде оно станет причиной того, что станут различными для двух этапов значения <math>6</math>-го и <math>8</math>-го слов. То же самое произойдет и на <math>72</math>-м раунде для слов <math>7</math> и <math>9</math>. И снова, с вероятностью <math>1/256</math>, байт в <math>9</math>-м слове, который будет использоваться в качестве входа <math>S</math> блока в <math>73</math>-м раунде, будет одинаков для шагов <math>1</math> и <math>2</math>. А значит, одинаковыми будут <math>10</math>-е, …, <math>16</math>-е, <math>1</math>-е, …, <math>5</math>-е слова. Изменения начнутся, когда будет использовано <math>6</math>-е слово в <math>86</math>-м раунде.
Таким образом, если после <math>56</math>, <math>72</math>, <math>88</math>, <math>104</math> и <math>120</math>-го раундов байт в <math>9</math>-м слове, который будет использоваться в качестве входа для <math>S</math> блока в следующих за указанными раундах, будет одинаков для обоих шагов, то одинаковы после полных <math>128</math> раундов окажутся слова <math>10</math>, <math>11</math>, …, <math>16</math>. Вероятность этого события <math>(1/256)^5=2^{-40}</math>. Так как в качестве хеша блока берется значение операции XOR от первых 4-х слов входного блока функции <math>E</math> и первых 4-х слов выходного блока функции <math>E</math>, то хеши, вычисленные на обоих шагах окажутся одинаковыми.
Сравнение атаки с известными методами криптоанализа
Метод был применен также к трехпроходной и четырехпроходной функции Snefru, показав лучшие результаты по сравнению с методом «дней рождения».
| Количество проходов функции Snefru |
Длина хеша, <math>m</math> | Сложность атаки | Метод «дней рождения» |
|---|---|---|---|
| 2 | 128 — 192 | <math>2^{12.5}</math> | <math>2^{64}</math> — <math>2^{96}</math> |
| 224 | <math>2^{12.5}</math> | <math>2^{112}</math> | |
| 3 | 128 — 192 | <math>2^{28.5}</math> | <math>2^{64}</math> — <math>2^{96}</math> |
| 224 | <math>2^{33}</math> | <math>2^{112}</math> | |
| 4 | 128 — 192 | <math>2^{44.5}</math> | <math>2^{64}</math> — <math>2^{96}</math> |
| 224 | <math>2^{81}</math> | <math>2^{112}</math> |
С помощью этой атаки можно найти множество пар, у которых одинаковый хеш, и, кроме того, разыскать несколько сообщений, хеш которых равен хешу данного сообщения (коллизия 1-го рода). Количество операций, требующееся для отыскания коллизии 1-го рода, в данной атаке меньше, чем в методе «грубой силы».
| Количество проходов функции Snefru |
Длина хеша, <math>m</math> | Сложность атаки | Метод «грубой силы» |
|---|---|---|---|
| 2 | 128 — 224 | <math>2^{24}</math> | <math>2^{128}</math> — <math>2^{224}</math> |
| 3 | 128 — 224 | <math>2^{56}</math> | <math>2^{128}</math> — <math>2^{224}</math> |
| 4 | 128 — 192 | <math>2^{88}</math> | <math>2^{128}</math> — <math>2^{192}</math> |
Примечания
В данное время Меркл советует применять функцию Snefru с не менее чем восемью проходами. Однако с таким количеством проходов вычисление функции Snefru в значительной степени замедляется, сравнительно с функциями MD5 или SHA.
Литература
- Eli Biham, Adi Shamir. Differential cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer (Extended Abstract).
- Шаблон:Книга
