Поиск второго прообраза хэш-значения Hamsi-256

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:21, 21 декабря 2015.
Finding Second Preimages of Short Messages for Hamsi-256
Finding Second Preimages of Short Messages for.png
Авторы Thomas Fuhr [@: 1]
Опубликован 2010 г.
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал


__NUMBEREDHEADINGS__

Содержание

Аннотация В данной работе мы изучили стойкость второго прообраза Hamsi-256, возможного значения на втором цикле SHA-3. Мы показали, что существует возможность нахождения аффинных уравнений между некоторыми входными битами и некоторыми выходными битами для 3-циклической функции сжатия. Это свойство позволяет злоумышленнику найти псевдо прообраз для функции сжатия Hamsi-256. Этот алгоритм псевдо прообраза можно использовать для нахождения вторых прообразов резюмирующей информации сообщений М со сложностью , которая в свою очередь меньше, чем в случае с наилучшими универсальными атаками при коротком М.
Ключевые слова: хэш функции, Hamsi, второй прообраз.


Введение

Hamsi это семейство хэш функций, которые были представлены на NIST SHA-3 Кучуком [1]. Оно включает в себя 4 версии, с соответствующим выходным значением в 224, 256, 384 и 512 бит. Оно основывается на метода расширения допустимого значения Меркла-Дамгарда однако, в данном случаем его схема более подходит в нашем случае т.к. здесь не используется блочных шифров в режиме Давиеса-Меера. Функция сжатия Hamsi использует короткие блоки сообщения, а её безопасность зависит от сложности раскрытия сообщения. Вместо ключевой перестановки, применяется фиксированная перестановка для объединения входящей цепочки переменных и раскрытого сообщения. Данная новая цепочка переменных получается путём предварительного вычисления выходных значений перестановки и упреждающий расчёт предыдущей цепочки переменных.

Предыдущие работы

До этого уже были исследованы несколько устройств различения по признакам применительно к функции сжатия Hamsi. Некоторые из них используют тот факт, что алгебраическая степень начальной перестановки достаточно мала. В [2] Аумассон отмечает, что алгебраическая степень функции сжатия с 5 циклами, рассматриваемой как функция входящей цепочки переменный, будет не более 243. Аумассон и Мейер в последствии расширили эту методику для нахождения устройств различения по признакам с нулевым суммарным значением для 6-ти цикловой версии функции сжатия [3]. Также в публикациях можно встретить некоторые результаты дифференциального криптоанализа функции сжатия. Т.к. различия в сообщениях будут иметь малую вероятность распространения, то это вызовет псевдо коллизии функции сжатия [4][5]. Калик и Туран выяснили, что для некоторой заданной разности во входящей цепочке переменных, разницу выходных битов функции сжатия можно выявить с вероятностью 1, согласно атаке с псевдо прообразом [6].

Наш вклад

В данной статье мы определим пробелы в безопасности функции сжатия Hamsi, которые можно использовать для нахождения вторых прообраза Hamsi-256 со сложностью эквивалентной оценкам сжатия, усилив тем самым наилучшую на текущий период атаку на короткие сообщения. Это первая атака, которая вычисляет общие границы одного из кандидатов SHA-3 на втором цикле. Наш метод можно отнести к кубическим атакам [7] и AIDA [8]. Он основывается на точном выборе переменных и для некоторого набора начальных условий на фазе инициализации контролировании распределения этих переменных и уходе от роста алгебраической степени в вычислениях. Нашей целью является разрешение системы полиномиальных уравнений, и для этого мы устанавливаем значения некоторых переменных как константы и пытаемся решить систему относительно оставшихся переменных. Основная идея заключается в том, что устанавливаются некоторые условия для блока сообщения и цепочки переменных для того, чтобы найти аффинные отношения между выходными значениями функции сжатия и некоторыми битами входящей цепочки переменных. Эти отношения можно использовать для нахождения прообразов общей хэш функции.

Схожие работы

Шимар и Динур независимо от данной работы показали алгебраическую атаку на второй прообраз Hamsi-256 основывающуюся на кубических методиках. Их атака была показана на Crypto 2010, и превосходила универсальные атаки на хэш функции Меркла-Дамгарда для малого исходного сообщения [9] .

План статьи

В разделе 2 мы кратко описали хэш функцию Hamsi-256. В разделе 3 показаны два алгебраических свойства S-box использованные в Hamsi, и то, как их использовать для записи результата для первых двух циклов функции сжатия, взятой как аффинная функция для некоторых бит цепочки переменных. После этого в Разделе 4 описывается, как расширить это свойство для нахождения аффинных уравнений общей функции сжатия Hamsi-256. При некоторых условиях на блок сообщения и входную цепочку переменных, есть возможность найти 14 (соответственно, 11) выходных биты функции сжатия, которые можно записать как аффинную функцию 7 (соотв. 8) бит входной цепочки переменных, для данного блока сообщения и фиксированной оставшейся части цепочки переменных. В разделе 5, показывается как эти уравнения используются для нахождения псевдо прообразов общей функции сжатия Hamsi-256, а также некоторые оптимизированные способы и оценка сложности. Затем, в Разделе 6, выявляется как использовать алгоритм псевдо прообраза для определения вторых прообразов общей хэш функции со сложностью равной оценкам сжатия, что в свою очередь, является нашим основным результатом. Наконец, в Разделе 7, изучается применение универсальных определённых методов расширения области определения Меркла-Дамгарда в Hamsi. Результирующая сложность получилась немного больше, чем для случая обычной вариации расширения области определения Меркла-Дамгарда, из-за того, что блоки сообщений там имеют меньшую энтропию, чем требуется для конкретной реализации универсальных методик. Поэтому наша атака с использованием второго прообраза более эффективна, чем данные методики при условии, что начальное сообщение короткое.

Обозначения

Во всей данной работе переменные представленные малыми буквами – это 32-битные переменные, а заглавными используются в обозначениях начальной фазы или сообщений. j-ая переменная LSB обозначается . представляет собой дайджест сообщения Hamsi-256. есть выходное значение функции сжатия Hamsi-256 применительно к цепочке переменных и блоку сообщения , а процесс взаимодействия функции сжатия для некоторых блоков сообщения будет определяться рекурсивно следующим образом:

Описание Hamsi-256

В данной статье мы сконцентрировали наше внимание на Hamsi-256. Наш метод также применим для Hamsi-224, однако, в отличие от Hamsi-256, с его помощью нельзя получить универсальные граничные значения.

Hamsi-256 использует функцию сжатия, которая отображает 256-битную цепочку переменных и 32-битный блок сообщения в 256-битную цепочку переменных. Он состоит из следующих операций:

Расширение сообщения

Сперва 32-битный блок сообщения расширяется в 256-битную переменную . Функция расширения является линейным кодом над .

Сцепление

Расширенное сообщение затем сцепляется с входящей цепочкой переменных для получения 512 значения , представленной матрицей 32-битных регистров. Функция сцепления представляется следующим образом:

Циклическая функция

После сцепления следующая циклическая перестановка выполняется три раза (восемь раз для последнего блока сообщения):

где включает в себя добавление константы и счётчика для данной фазы, является подстановкой данного уровня основанной на использовании вторых 4-бит для 4-битного S-box Serpent, а - уровень распространения, оперирующий с 4 наборами 4 32-битных переменных параллельно.

Более точно, заключается в реализации для всех и S-box для битов слов . Другими словами, тот же S-box применяется параллельно для 128 столбцов на стадии инициализации.

Таблица 1. S-box использующийся в Hamsi.
Входы и выходы представлены в шестнадцатеричной системе счисления, lsb x соответствует словам.
0 1 2 3 4 5 6 7 8 9 A B C D E F
8 6 7 9 3 C A F D 1 E 4 0 B 5 2


На уровне распространения происходит следующее. На входе принимается (соотв. ) и он включает в себя следующие операции:

Отсечение

После третьего цикла, выходное значение функции сжатия получается путём применения функции отсечения на данной фазе и выполнения сложения по модулю 2 полученного результата для выявления цепочки значений.

Расширение области определения

Для построения хэш функции с длинной равной длине переменных, в Hamsi используется схема Меркла-Дамгарда. Она состоит в сцеплении сообщений «1» и стольких «0», сколько понадобиться для получения целого числа блоков, а затем дальнейшим сцеплением длина сообщения кодируется 64 битами. Для последнего блока перестановка состоит из 8 циклов (вместо 3).

Описание двухциклической функции сжатия Hamsi-256

В данной раздел мы посветили уменьшенной версии функции сжатия Hamsi-256, где начальная перестановка выполняется за 2 цикла. Полученный результат используется в последующих разделах для реализации взлома полной версии Hamsi-256. Мы показали как найти псевдо прообраза для данной версии функции сжатия с уменьшенным количеством циклов.

Изучение Hamsi S-box

Для Hamsi S-box отметим следующих свойства.

Мы используем и для того, чтобы получить

(1)

В результате, только один бит выходного значения зависит от . Аналогично для и , получается, что

(2)

Если вход S-box зависит только от одного переменного бита, то выход S-box можно представить как аффинную функцию от этого бита. Постпредством этого, свойства (1) и (2) можно найти соответственно при следующих критериях. Во-первых, только один выходной бит S-box должен зависеть от . Во-вторых, входные биты 0 и 2 или 1 и 3 не должны зависеть от , т.о. эот означает, что для соответствующего выбора первого цикла S-box, зависят от только входные биты из цепочки переменных.

Конкретный набор переменных

Давайте возьмем любое значение блока сообщения . Без знания входного значения цепочки, можно вычислить после первого цикла сложения констант. Теперь предположим, что j-ый бит будет . Тогда независимо от значения , если и , только первых выходной бит j-ого S-box 3-его столбца будет зависеть от (согласно уравнению 1). Пусть J будет набором переменных, который удовлетворяет данному свойству.

Тогда мы можем определить переменный бит для каждого таким образом, чтобы . После первого уровня S-box, только слово зависит от переменного набора , посредством аффинных отношений. После первого цикла уровня распределения и второго цикла сложения констант, слова и будут линейно зависеть от , что означает, что только один входной бит каждого S-box второго уровня подстановки может зависеть от . Как следствие из этого, выход данного уровня есть также аффинная функция от . Для второго уровня распределения, отсечение и упреждение, нельзя увеличить степень, т.к. весь выход функции сжатия является аффинной функцией от .

Построение и решение линейной системы

Теперь постараемся инвертировать 2-циклическую функцию сжатия для того, чтобы найти блок сообщения и значение цепочки , которое отображает заданное значение . Идея в том, чтобы выразить выход функции сжатия в виде аффинной системы заданного набора переменных и решить эту систему. Для соответствующего выбора переменных, нам известно, что система будет аффинной, но сперва необходимо вычислить её коэффициенты. Чтобы сделать это выполним следующее:

  1. Выберем блок сообщения и вычислим результирующее значение до перехода на уровень подстановки.
  2. Вычислим результирующий набор переменных . Если ,выберем другое значение .
  3. Выберем значение цепочки такое, что для всех после выполнения первого сложения констант. затем разбивается на переменную часть (биты и для ) и постоянную часть (оставшиеся биты).
  4. Вычислим для получения постоянных коэффициентов системы.
  5. Для каждого извлечём из путём добавления значений и . Вычислим для получения коэффициентов используя метод интерполяции.
  6. Решим аффинную систему 256 уравнений при неизвестных для нахождения прообраза . Если у неё нет решения, выберем другое значение постоянной части . Если перепробовали все значения, увеличиваем .

Затем полагаем, что сложность решения результирующей системы уравнений меньше, чем сложность оценки функции сжатия. Во избегании не нужных вычислений, можно, например, найти решения подсистем и прерваться при нахождении несоответствия. Каждая система позволяет проверить значений со сложностью менее чем оценок функции сжатия. Т.к. , общая сложность этого алгоритма будет около оценок сжатия.

Линейные уравнения для полной функции сжатия Hamsi-256

В данном разделе мы покажем как применить схожие методики для нахождения линейных уравнений полной функции сжатия Hamsi-256.

Если попробовать использовать то же свойство для S-box, что и в предыдущем разделе, то мы не сможем найти какой-либо большой набор переменных, который приведёт впоследствии к линейным уравнениям. В таком случае, более подходящим будет свойство (2). Если блок сообщения будет таким, что перед первым уровнем подстановки и , при том, что мы установим и , только j-ый бит будет зависеть от после уровня S-box. Тоже самое и для с .

По сравнению с методом из Раздела 3, здесь используется более свободная степень (для каждой переменной, два бита сообщения и один бит цепочки переменной). Однако, т.к. является d входом для уровня распределения, зависимость от не имеет быстрого распространения на первом цикле.

Стадию инициализации S перед перестановкой циклов можно т.о. разбить на три части:

  • Переменные биты: Наборы переменных X, Y.
  • Условные биты: Биты в стадии инициализации, которые принимают заданные значения т.о. чтобы зависимость от начальной фазы для переменных после первого уровня подстановки описывалась уравнением (2). Каждому переменному биту требуется определение трёх условных битов: двух для блока сообщения и одного для входной переменной цепочки.
  • Постоянные биты: Оставшиеся биты в стадии инициализации.

Эти биты не обязательно должны быть непосредственно битами из входящего блока сообщения или переменной цепочки: они могут быть линейными функциями от этих битов. К примеру, при рассмотрении уравнения 2, Условные биты значения входящей цепочки будут двумя конкретными битами ( и , или и ). Соответствующий переменный бит можно потом взять как значение одного из этих двух битов.

В результате, можно найти наборы переменных и такие, что некоторые выходные биты всей функции сжатия будет линейно зависеть от Переменных битов X, Y, представляющие Условные биты как заданное значение и Постоянные биты как набор.

Алгебраические свойства S-box Hamsi-256. Для нахождения данного набора переменных необходимо принять во внимание следующие свойства.

  1. Любая функция f от 1 до n бита является аффинной. Это можно определить как . Поэтому, если все входные биты 4-битного S-box постоянны, кроме одного, то выход S-box будет аффинной функцией оставшегося входного бита. Если этот входной бит является аффинной функцией от переменных в , это будет такой же случай для 4 выходных бит, как и для композиции аффинных функций.
  2. Аналогично, если вход S-box зависит только от одной из переменных, его выходом будет аффинная функция этой переменной.
  3. Если является выходом S-box со входом  : только нелинейный одночлен в представлении будет , и будет зависеть только от нелинейных одночленов и . В следствии этого, если одночлен является аффинной функцией , то является и . Аналогично, если одночлены и являются аффинными в , то тоже самое и для .

Используем данные свойства в автоматизированном поиске допустимых коэффициентов для гарантии, что некоторые конечные и начальные биты будут участвующие в расчёте функции сжатия будут аффинными функциями набора переменных.

Оптимальные наборы переменных. Для нашей атаки на второй прообраз необходимо сперва определить оптимальные наборы переменных битов. В нашей атаке будут две ёмкие по времени фазы: генерация аффинной системы уравнений, и проверка решений. Сложности в общем случае зависят от числа переменных и числа результирующих аффинных уравнений . Для заданного числа переменных , мы рассматриваем выбор набора переменных, который приводит к наибольшей системе аффинных уравнений, используя полный перебор. Ресурсоёмкость генерации системы уменьшается с увеличением числа переменных, тогда как затраты на проверку решений в основном уменьшает увеличение числа уравнений. Точная оценка сложности данной атаки представлена в Разделе 5. Оптимальные значения и можно найти путём выявления компромисса затрат между этими двумя алгоритмами.

Более того, оценка сгенерированной системы может использоваться повторно для попытки нахождения псевдо прообраза нескольких значений, что реализуется частично в нашей атаке. Поэтому, оптимальные наборы уравнений будут различными в разных частях нашей атаки.

Нахождение оптимального набора переменных. Для заданного значения определим набор переменных, который приводит к получению максимального значения . Сделаем это с помощью полного перебора всех наборов переменных , которые содержат в точности элементов.

Рассмотрим теперь фиксированный набор . Попробуем определить какие из выходных битов можно всегда выразить как аффинную функцию от Переменных , при допущении, что все Условные биты приняли корректные константы, а Постоянные биты зафиксированы. Затем выполним следующее:

Для каждой пары переменных , определим набор выходных битов , которые всегда будут аффинными функциями от и , при том, что Условные биты приняли корректные константы, а Постоянные биты зафиксированы. Как получить эти наборы будет описано ниже. Когда это сделано, биты в наборе будут аффинными функциями набора переменных . Если алгебраическое представление выходного бита b как функции от переменных содержит в себе одночлен 2 степени или более, то пусть z и z’ будут двумя переменными этого одночлена. Тогда b не будет в т.к. для некоторого распределения всех остальных переменных представление b содержит одночлен zz’.

Теперь объясним, как найти . После первого уровня S-box, только один бит зависит от каждой переменной z и z’. Рассмотрим распределение этих переменных для функции сжатия. Данное распределение не всегда будет определённым – это вероятностный процесс относительно уровней S-box. Для каждого начального бита фазы инициализации, определим является ли он независимым от z и z’, либо линейно зависит от z и/или z’, либо квадратично зависит от z и z’. Уровень распределения является линейным. Поэтому бит начальной фазы после уровня распределения всегда будет аффинным для z,z’ тогда и только тогда, когда все его входные биты также находятся в зависимости и всегда аффинны в z,z’. не изменяет степень каждого бита на начальной стадии. не линейно и не увеличивает степень. Более точно, если два различных входных бита заданного S-box могут зависеть от соответствующих z,z’, то некоторые выходные биты могут иметь квадратичную зависимость. В завершении, для функции сжатия и не увеличивают степень.

Давайте теперь рассмотрим фиксированный набор . Попробуем определить который из выходных битов можно всегда представить как аффинную функцию от Переменных , при том, что Условные биты приняли корректные константы, а Постоянные биты зафиксированы. Эквивалентно, попробуем определить выходные биты , полиномиально представимые как функции от переменных битов содержащих одночлены степени . Это означает, что для некоторого выбора и некоторого предположения для других переменных, полиномиальное представление может содержать одночлен z,z’. Поэтому для каждого выбора , вычисляем какие биты на начальной фазе могут содержать одночлены z,z’ и zz’ в процессе предвычисления и нахождении результирующего значения цепочки.

Используя этот метод установим следующие свойства для 7 и 8 переменных. При данном блоке сообщения и всей цепочке переменных кроме x и y, а также предположении о том, что есть условия на блок сообщения и значение цепочки, эти условия определяются:

  • Выходными битами 9, 18, 44, 88, 144, 152, 183, 185, 188, 193, 219, 221, 228 и 246 зависящими линейно от , которые используют 14 выходных битов и 7 переменных с .
  • Выходными битами 11, 39, 46, 185, 188, 195, 218, 220, 230, 248 и 255 зависящими от , которые используют 11 выходных битов и 8 переменных с .

Когда Условные биты перестают быть значащими для верного значения и Постоянные биты также перестают быть значащими для любого значения, то отношение между некоторыми выходными битами (обозначим их как биты уравнения) и переменными битами можно представить как систему линейных уравнений.

Псевдо прообраз для функции сжатия Hamsi-256

В данном разделе мы попробуем найти псевдо прообраз для заданного значения цепочки переменных. Определим нашей основной задачей нахождение , таких, что . В первом подпункте мы рассмотрим оптимизированный алгоритм, который выполняет следующие операции с более меньшей сложностью. Т.к. нам известно, что выходные биты являются аффинными функциями переменных битов , вычисление инверсии функции сжатия можно выполнить следующим образом. Также здесь мы зададим соответствие между рассмотренными операциями и этапами данного алгоритма, на которых они выполняются.

  • Установим начальное значение цепочки переменных и блока сообщения таких, что условия удовлетворяются (шаг 1 и 2).
  • Вычислим выходные биты при (шаги от 3 до 7).
  • Выходные биты функции сжатия будут аффинными функциями от переменных. Вычислим коэффициенты данных функций (шаг 8).
  • Решим результирующую систему аффинных уравнений (шаг 9). Если у неё нет решений - начнём заново.
  • Если линейная система имеет решение , вычислим будет ли для функции сжатия (шаг 10). Это будет с вероятностью . Если нет – начинаем с начала.

Построение и решение систем уравнений

Основная идея. Основная идея заключается в том, что для вычисления коэффициентов системы уравнений используется методика из Раздела 3. Говоря более точно, можно оценить функцию сжатия со всеми переменными равными 0 для получения коэффициентов-констант, а также отдельно для каждой переменной чтобы выявить её коэффициенты, с помощью повторного вызова функции сжатия. Но для определения коэффициентов, необходимо только вычислить те части общей процедуры решения, в которых непосредственно просматривается зависимость от Переменных битов воздействие на биты Уравнения, что в свою очередь потребует меньше вычислений, чем выполнение всей функции сжатия. Более того, некоторые малые изменения во входящей цепочке переменных не повлияют непосредственно на весь этап инициализации. Некоторые стадии вычисления можно т.о. использовать повторно при расчёте коэффициентов-констант различных систем уравнений. Мы распишем метод вычисления таких систем наже.

Более эффективный метод. Для более эффективного вычисления коэффициентов используем следующие ухищрения:

  • Коэффициенты каждой переменной зависят только от распределения переменной на втором и третьем уровне распределения. Поэтому их можно получить из входных значений соответствующих S-box’ов.
  • В первых двух циклах функция сжатия Hamsi-256 будет аффинной функцией от переменных определённых в Разделе 3.

Затем используем набор из 8 переменных как показано в разделе 3, обозначающих вспомогательные переменные, для вычисления более эффективных систем уравнений. Как известно из анализа раздела 3, на всём начальном этапе, вплоть до получения входного значения на третьем уровне S-box, будут использоваться аффинные функции от этих переменных, что в свою очередь означает, что некоторые Условные биты будут иметь соответствующие значения. Вместо того, чтобы вычислять всю функцию сжатия для получения коэффициентов-констант для каждой системы, мы всего лишь модифицируем вспомогательную переменную первой системы для второй. Поэтому некоторые значения на среднем этапе процесса вычисления не нужно повторно рассчитывать.

Когда мы рассчитали данные промежуточные значения на начальной стадии для всех основных и вспомогательных переменных равных 0, можно вывести все значения для начального этапа при возможных переменных значения, с помощью выявления распределения 8 вспомогательных переменных на S-box уровне второго цикла.

Т.о. мы можем улучшить атаку следующим способом.

  1. Установить значения Условных битов из цепочки переменных соответствующим образом.
  2. Выбрать Постоянные биты переменной цепочки и блок сообщения m так, чтобы все условия выполнялись.
  3. Выбрать набор из 8 вспомогательных переменных т.о., чтобы выполнялись результирующие вспомогательные условия. Для случайного значения на начальном этапе инициализации мы можем найти 8 вспомогательных значений с большой вероятностью. Если нет, то возвращаемся в шагу 2.
  4. Вычислим первые два цикла функции сжатия для всех Переменных и вспомогательных переменных равных 0. Сохраним результаты полученные при расчёте начальных операций.
  5. Вычислим распределение вспомогательных переменных в первых двух циклах.
  6. Для каждого значения набор вспомогательных переменных выявим входные значения S-box’ов использующих Переменные во 2 и 3 циклах.
  7. Определим коэффициеты-константы с помощью части третьего цикла, в которая влияет на биты Уравнения.
  8. Определим другие коэффициенты системы рассмотрев распределения Переменных на 2 и 3 циклах.
  9. Решим результирующую систему линейных уравнений. Если у неё нет решения – возвращаемся к шагу 2.
  10. Установим Переменные биты равными одному из решений системы кравнений, и вычислим функцию сжатия. Если результат не удовлетворяет нашему , то идём опять на шаг 2.

Сложность оценки данной атаки

Здесь мы оценим сложность различных этапов данной атаки. Т.к. мы стараемся избежать лишних вычислительных операций, то, в основном, используем операции на битах, а не на 32-битных регистрах. Можно воспользоваться параллелизмом для создания нескольких систем одновременно, с различными значениями Постоянных битов входящей цепочки переменных. Поэтому отметим, что верное измерение для оценки сложности данной атаки будет числом элементарных побитовых операций (AND, OR, XOR) которые в неё входят. В отличие от общих атак, мы используем анализ Шамира и Динура [10] и оцениваем число побитовых операций в функции сжатия Hamsi-256 примерно в 10500.

Шаги от 1 к 3 являются установочными шагами и имеют пренебрежимо малую сложность по сравнению с другими. Также заметим, что выбор вспомогательных переменных может быть таким же и для больших систем, поэтому можно выявить этапы начальной стадии на которых всё рассчитывается предварительно и вследствие этого сложностью которых можно пренебречь.

Шаг 4 включает в себя вычисления 2 из 3 циклов функции сжатия. Тщательный анализ того, какие именно биты S-box’ов необходимы для расчёта и какие этапы линейного распределения уровней необходимо выполнить приводит нас к 5248 операциям для систем из 7-переменных и 4852 операциям для систем из 8-переменных.

На шаге 5 выполняется вычисление крайних 7 циклов S-box’ов для каждого вспомогательного значения, и максимум 7 х 20 = 140 XOR операций для каждой переменной второго цикла уровня распределения, что в свою очередь будет 1120 элементарными операциями для систем.

Шаг 6 состоит из выполнения сложения по модулю 2 значений входов некоторых S-box’ов перед циклами 2 и 3 для различных значений вспомогательных переменных. Такие значения данных переменных можно выбрать с помощью кодирования Грея, для минимизации этапов фазы, которая будет рассчитываться вновь. Поэтому, только 7 входных битов второго S-box уровня можно задействовать. Для третьего S-box уровня, будут действенны только некоторые S-box’ы (45 для систем с 7-переменными, 34 для систем с 8-переменными). Этому шагу требуется наличие 7 + 4 х 45 = 187 (соотв. 7 + 4 ч 34 = 143) XOR’ов для систем с 7-переменными (соотв. 8-переменными).

На шаге 7 выполняется оценка коэффициентов-констант данной системы. Эти коэффициенты можно получить путём вычисления некоторых промежуточных этапов расчёта выходов функции сжатия, при известном выходе второго цикла. Это включает в себя применение распределительных операций и упреждения. Для вычисления упреждения необходимо инвертировать битов первого цикла сложения констант. Этому шагу необходимо выполнить 473 + 54 + 28 = 555 (соотв. 328 + 37 + 22 = 387) операций на каждую систему.

Шаг 8 включает в себя получение коэффициентов одночленов первой степени. Это можно получить с помощью выявления распределения переменных по S-box’ам. Для систем с 7-переменными (соотв. 8 переменными) входы 17 (соотв. 20) S-box’ов зависят от переменных полученных перед вторым уровнем подстановки. Для некоторых из них, необходимо вычислить только несколько выходных битов. Для каждой системы из 7-переменных (соотв. 8-переменных), требуется на это 210 (соотв. 200) операций. Для распределения на втором уровне для входов применяемых на третьем цикле S-box’ов требуется 60 (соотв. 46) XOR’ов. На третьем цикле, выходы 45 (соотв. 34) S-box’ов влияют на биты Уравнения. Для оценки коэффициентов данных переменных рассмотрим 3 возможных случая для третьего цикла S-box уровня:

  1. Вход S-box не зависит от Переменных. Тогда выход также не будет зависеть от Переменных, и не требуется никаких вычислений. Это характерно для 5 (соотв. 9) S-box’ов.
  2. Один входной бит может изначально зависеть от одной или нескольких Переменных. Тогда выход будет зависеть от тех же Переменных что и вход, а вычисление коэффициентов будет эквивалентно оценке одного S-box’а. Это характерно для 31 (соотв. 17) S-box’ов, и приводит к сложности в 364 (соотв. 155) операций.
  3. Два входных бита могут изначально зависеть от Переменных. Т.к. зависимость не детерминированная, получаем три различных случая зависимостей в процессе вычисления системы. Каждый из них приводит к разному распределению и т.п. Если злоумышленник использует параллелизм, ему необходимо вычислить зависимости для всех трёх случаев, что приводит к сложности эквивалентной 3 вычислениям S-box’а. Это характерно для 6 (соотв. 8) S-box’ов со сложностью 221 (соотв. 213).

Данные линейные коэффициенты можно получить с помощью простых операций для битов представляющих распределение переменных на втором и третьем уровнях S-box. Полная сложность выявления коэффициентов из этих битов будет максимально равна 125 (соотв. 101) операциям.

Сложив всё это вместе, средние затраты на вычисление этих коэффициентов системы уравнений будут:

операций для систем с 7-переменными

операций для систем с 8-переменными

Более того, затраты для построения данной системы с 7 переменными будут около оценок сжатия. Сложность же построения системы с 8 переменными будет оценок сжатия.

На шаге 9 идёт решение системы уравнений, сложность которых меньше по сравнению с оценкой функции сжатия. Используем алгоритм Гаусса. Из этого следует, что сложность будет: для каждой переменной, для каждой оценки, мы вычисляем максимум , и в среднем число XOR’ов будет . Это приводит к тому, что общая сложность будет операций на каждую систему, что в свою очередь характеризуется 392 операциями для системы с 7-переменными и 396 операциями для системы с 8-переменными. Следовательно можн оценить сложность данного шага как и .

Вероятность успеха 10-ого шага , что в совокупности будет означать сложность оценок сжатия (сложность проверена для наличия одного решения ). Для каждой системы уравнений можно проверить значений цепочки переменных, значит необходимо рассчитать около систем. Наилучшим алгоритмом псевдо прообраза в таком случаем для 8 переменных будет:

Изменчивость. Также необходимо увериться, что у нас есть необходимое пространство для поиска вторых прообразов. Мы можем определить только определённый тип псевдо прообразов для заданного выхода, который определяется с помощью условий, налагаемых на входной блок сообщения и цепочку переменных. Для 8 переменных получаем 24 таких битовых условия (16 на блок сообщения и 8 на цепочку переменных). Исходное пространство поиска будет размером , мы в свою очередь имеем пары (C,m) для покрытия этих условий. Также необходимо найти 8 вспомогательных переменных. Вспомогательную переменную можно определить, когда существуют и допустимы одно условие на блок сообщения и ещё одно на цепочку переменных (согласно Разделу 3). Т.к. мы имеем 32 потенциальных вспомогательных переменных, вероятность что хотя бы 8 из них можно выбрать будет ½. Поэтому ожидается наличие не менее кандидатов, среди которых будет псевдо прообразов заданного значения. Это подтверждает что для реализации атаки необходимо наличие достаточного места для поиска данных прообразов.

Вторые прообразы для полной Hamsi-256

Как было показано в Разделе 5 псевдо прообраза для Hamsi-256 функции сжатия можно найти со сложностью около оценок сжатия. Это угрожает безопасности Hamsi-256, т.к. можно использовать алгоритм псевдо прообраза для построения алгоритма нахождения второго прообраза путём применения основной методике схождения посередине. В данном разделе мы расписали эти два основных метода и показали как их улучшить. Основная идея заключается в следующем: сложность атаки псевдо прообраза определяется сложностью построения систем уравнений, и в особенности сложностью получения коэффициентов этих уравнений. Для установки основного второго прообраза можно попробовать инвертировать одну из промежуточных цепочек переменных. Т.к. коэффициенты линейной системы одни и те же, каким бы ни было значение цепочки переменных инвертируемой нами, некоторые вычисления можно скомпоновать.

Основной алгоритм второго прообраза

Основная идея здесь заключается в том, чтобы сгенерировать вторые прообразы используя наш алгоритм псевдо прообраза включающий в себя основную методику схождения посередине. Алгоритм можно представить следующим образом:

  1. Вычислим псевдо прообразов значений цепочки после девятого блока сообщения.
  2. Вычислим промежуточные хэш значения для последовательностей 8 блоков сообщений пока не получим одно из значений выявленных на шаге 1. Ожидаемое число таких сообщений будет около .

Это приводит нас ко второй атаке на прообраз со сложностью около . Однако, исходное сообщение должно содержать не менее 9 блоков, т.о. мы должны быть уверены, что имеем достаточную изменчивость для получения второго прообраза равной длины. Улучшение нашего метода приводит к улучшению самых популярных на сегодняшний день атак на Hamsi-256.

Псевдо прообразы в наборе отображений

На первом шаге обычной атаки большое количество вычислительного времени идёт на генерацию систем. Если оно многоцелевое, то вычисление можно произвести только единожды. В этом разделе мы покажем другой алгоритм, который использует данное примечание.

Теперь опишем, как найти псевдо прообраз элемента набора N отображений, что в свою очередь является более простой задачей, чем нахождение псевдо прообраза заданного элемента. В нашем методе вычисление коэффициентов системы линейных уравнений зависит только от значений которые складываются по модулю 2 с этими коэффициентами. Т.о. мы используем аналогичный метод для расчёта прообраза элемента набора при помощи однократного вычисления коэффициентов, и пытаемся решить систему уравнений для всех N элементов данного набора.

Начало анализа системы оценки можно записать в общем виде для всех значений. Сперва определим оценку , где постоянные бинарные векторы размером , x неизвестный бинарный вектор размером , а А фиксированная бинарная матрица. Затем начнём с вычисления алгоритма Гаусса для базиса размером y. Сложность этой части обозначим за . По тому же принципу, что использовался в предыдущем разделе оцениваем её как . В заключении анализа проверяем корректны ли оставшиеся уравнения. Другими словами, проверка не максимум линейных отношений выходных битов приведёт к максимальной сложности в элементарных операций. В связи с этим данный шаг можно пересмотреть для некоторых конкретных приложений.

В результате, сложность нового алгоритма получится из уравнения 3 и будет:

Получаем опять же операций, и операций, что в свою очередь приводит к и оценкам сжатия.

Вторые прообразы для коротких сообщений

Теперь рассмотрим следующий алгоритм. Требуется, чтобы исходное сообщение состояло не менее чем из 10 блоков. Если это условие выполняется, то сложность не зависит от длины сообщения. Т.о. это более эффективная атака на короткие сообщения, чем атака Келси и Шнеера.

Рассмотрим сообщение и попробуем найти второй прообраз с дайджестом М. Следовательно нам надо принять во внимание цепочку переменных . Сперва постараемся найти x псевдо прообразов , а именно . Используем набор из 8-неизвестных. Сложность данного шага будет примерно (5):

На втором шаге начиная с где мы ищем y псевдо прообразов одного элемента из данного набора . Для этого шага мы используем оценку систем с 7-неизвестными. Сложность второго шага будет (6):

И наконец, используя вероятностный подход, мы пытаемся найти такой, что результирующая цепочка переменных вызывает противоречие для одного из переменных с . Сложность данного шага будет (7):

Обозначим и . Для j указанного выше, существует такое i, что . В результате, и (8)

Это позволяет получить второй прообраз для со сложностью (9)

Для Hamsi-256 наилучшим компромиссом будет тот случай, когда сложность всех шагов примерно равна. Для x = 11 и y =71 получаем:

Что приводит к сложности примерно в оценок сжатия.

Атака на второй прообраз Келси-Шнаера

В предыдущих разделах мы описали атаку на второй прообраз реализующуюся быстрее чем общие атаки на хэш функции. Для полноты картины, также отметим, что она даже быстрее чем универсальные атаки на устройство расширения области определения использующееся в схеме Hamsi.

В [10] Келси и Шнаер предложили общую атаку на простые хэш функции Меркла-Дамгарда. Для этого они использовали либо алгоритм нахождения мультиколлизий созданный Джоуксом [11], либо фиксированные точки. Т.к. Hamsi-256 основывается на устройстве расширения области определения Меркла-Дамгарда, то данную атаку также можно применять для Hamsi-256. Однако, использовать можно только в случае очень коротких сообщений, что не даём злоумышленнику свободы в выборе степеней для реализации атаки на Hamsi-256. Более того, специфическая схема функции сжатия не позволяет злоумышленнику легко сгенерировать фиксированные точки.

В данном разделе мы покажем модифицированную версию данной атаки, применимую непосредственно к Hamsi-256. Модификация тривиально, но сложность новой атаки значительно отличается от сложности исходного её аналога. Целью данного раздела является нахождение оценки сложности наилучшей универсальной атаки на Hamsi-256.

Описание данной атаки

TemplateDifinitionIcon.svg Определение «Определение 1. »
(p, q) сообщение для хэш функции Меркла-Дамгарда будет набором (q – p + 1) сообщений таких, что
  1. .
  2. содержит в точности i блока после процесса наполнения.

Атака на исходный второй прообраз реализуется следующим образом. Давайте предположим, что нам необходимо найти второй прообраз дайджеста Hamsi-256 l-блочного сообщения . Для этого найдём сообщение M’ такое, что . Мы ищем M’ такое, чтобы M и M’ были одинаковой длины.

  1. Генерируем (p, q) сообщение для при некоторых соответствующих значениях p и q, о которых будет рассказано в последствии.
  2. Выберем значение общего дайджеста h в виде цепочки переменных и вычислим функцию сжатия для случайно последовательности 8 блоков сообщения, чтобы найти такие, что является одним из значений цепочки встречающимся в вычислении для .
  3. Вычислим . Сообщение будет вторым прообразом .

Расширенные сообщения для Hamsi-256

Расширенные сообщения генерируются путём использования алгоритма мультиколлизий [11]. Расширенные сообщения размером генерируются с помощью выполнения следующего поиска. Установим (вектор инициализации Hamsi-256). Для всех i в {0,…,k – 1}, найдём две последовательности блоков сообщения и таких, что:


Пусть и . Можно записать с . Тогда последовательность будет длинной j и . В общем случае, Келси и Шнаер берут для всех i. Затраты на каждый шаг данного поиска будет около в связи с парадоксом дней рождения, что приводит к общей сложности примерно в . Hamsi-256 обладает определённым свойством, которое заключается в том, что блоки сообщения малы по сравнению с цепочками переменных. Поэтому, если злоумышленник выбирает , он может сгенерировать только значений для последовательности . На первой итерации, вероятность нахождения коллизии очень мала, и затраты на итерации для будут около . Это сохраняет равную сложность, при которой необходимо выбрать для каждого значения i что соответствует расширенному сообщению после примерно оценок сжатия.

Оценка сложности

В случае Hamsi-256 мы выбираем p = 4k и такие, что . Две последние функции сжатия вычисления используют блоки сообщения представленные битовой длинной m и блоком находящимся перед включающими битами т.е. т.о. мы не принимаем во внимание результирующее значение цепочки.

Затраты на генерацию расширенного сообщения будут примерно оценок функции сжатия. Среднее число возможных значений для второго шага будет около . Сообщение можно легко вычислить. Общая сложность данной атаки будет (10):

Сложность данной атаки аналогична атаке Келси и Шнаера, но условие на длину сообщения значительно отличаются ( вместо ). В результате, наша атака рассмотренная в предыдущем разделе является более эффективной чем эта универсальная атака на сообщения длинна которых варьируется от 10 до 96 блоков.

Возможные улучшения

Некоторые улучшения нашей атаки на второй прообраз можно реализовать с помощью применения атаки Келси Шнаера на устройство расширения области определения вместе с нашим алгоритмом нахождения псевдо прообраза. К примеру, можно попробовать инвертировать некоторые промежуточные цепочки переменных в вычислении между двумя шагами универсальной атаки, т.о. увеличивая потенциальное число целевых значений для второго этапа. Такая атака, однако, может быть эффективна только для коротких сообщений, тогда как основной особенностью нашего алгоритма псевдо прообраза как раз таки является исключение некоторых значений (С, m) с помощью линейных отношений. Если пространство целевых значений становиться больше , то практически каждое значение будет вычисляться в любом случае и применение нашей методики нецелесообразно.

Заключение и подведение итогов

В данной статье мы показали первую атаку на Hamsi-256, реализуемую быстрее, чем универсальные атаки на хэш функции. Хоть в ней присутствуют схожие элементы из дифференциальных атак, такие как анализ распределения переменных или уменьшение пространства поиска путём установки определённых условий, всё же данная атака больше алгебраическая. Для коротких сообщений, наш алгоритм работает быстрее, чем универсальные атаки на устройство расширения области определения Меркла-Дамгарда, использующегося в Hamsi. Хоть сложность атаки и не представляет достаточной угрозы для использования Hamsi-256, она показывает некоторые огрехи в её конструкции.


Благодарности

Мы хотели бы поблагодарить Генри Гилберта и анонимные рецензии представленные на Asiacrypt 2010 за полезные комментарии на ранней стадии данной работы. Хотелось бы особенно отметить Ади Шамира и Итаи Динура за их предложения касательно Hamsi-256.

Контакты авторов материала

  1. ANSSI, Paris, France and TELECOM-ParisTech, Paris, France E-mail:[1]

Литература

  1. Kucuk, O.: The hash function hamsi. Submission to NIST (updated) (2009)
  2. Aumasson, J.-P.: On the pseudorandomness of hamsi. NIST mailing list (local link)(2009)
  3. Aumasson, J.-P., Meier, W.: Zero-sum distinguishers for reduced keccak-f and for the core functions of luffa and hamsi. NIST mailing list (2009)
  4. Wang, K.J.M., Wang, X., Wang, W.: New pseudo-near-collision attack on reducedround of hamsi-256. Cryptology ePrint Archive, Report 2009/484 (2009),http://eprint.iacr.org/
  5. Nikolic, I.: Near collisions for the compression function of hamsi-256. In: CRYPTO rump session (2009)
  6. Calik, C., Turan, M.S.: Message recovery and pseudo-preimage attacks on the compression function of hamsi-256. Cryptology ePrint Archive, Report 2010/057
  7. Dinur, I., Shamir, A.: Cube attacks on tweakable black box polynomials. In:EUROCRYPT, pp. 278–299 (2009)
  8. Vielhaber, M.: Aida algebraic iv differential attack breaking one.fivium by aida an algebraic iv differential attack (2007)
  9. Shamir, A., Dinur, I.: An algebraic attack on hamsi-256 (to appear)
  10. Kelsey, J., Schneier, B.: Second preimages on n-bit hash functions for much less than 2n work. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp.474–490. Springer, Heidelberg (2005)
  11. 11,0 11,1 Joux, A.: Multicollisions in iterated hash functions. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 306–316. Springer, Heidelberg (2004)