Односторонняя функция сжатия

Односторонняя функция сжатия в криптографии — функция, которая образует значение длиной ${\displaystyle n}$ на выходе при задании двух входных значений длиной ${\displaystyle n}$^[1]. Одностороннее преобразование означает, что легко вычислить значение хеш-функции по прообразу, но трудно создать прообраз, значение хеш-функции которого равно заданной величине^[2][3].

Односторонняя функция сжатия используется, например, в структуре Меркла — Дамгора внутри криптографических хеш-функций.

Односторонние функции сжатия часто построены из блочных шифров. Для того, чтобы превратить любой стандартный блочный шифр в одностороннюю функцию сжатия существуют схемы Дэвиса — Мейера, Матиса — Мейера — Осеаса, Миагути — Пренеля (функции сжатия одноблочной длины)^[4].

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

Например, если вход А имеет длину в 128 бит, вход B в 128 бит, и они сжаты вместе в один выход в 128 бит. Это то же самое, как если бы один-единственный 256-битовый вход сжимался вместе в один выход в 128 бит.

Некоторые функции сжатия имеют различный размер двух входов, но выход, как правило, имеет такой же размер, как и один из входов. Например, вход А может быть 256 бит, вход B 128 бит, и они сжаты вместе с одним выходом в 128 бит. То есть, в общей сложности 384 входных битов сжимаются вместе до 128 выходных битов.^[5]

Таким образом, смешивание выполняется за счет достижения лавинного эффекта.То есть, каждый выходной бит зависит от каждого входного бита.^[6]

Функция сжатия в одну сторону должна обладать следующими свойствами:

• Стойкость к поиску первого прообраза — отсутствие эффективного полиномиального алгоритма вычисления обратной функции, то есть нельзя восстановить текст ${\displaystyle m}$ по известной его свертке ${\displaystyle H(m)}$ за реальное время (необратимость). Это свойство эквивалентно тому, что хеш-функция является односторонней функцией.
• Стойкость к поиску второго прообраза (коллизиям первого рода). Зная входное сообщение ${\displaystyle m_{1}}$ и его свёртку ${\displaystyle H(m_{1})}$, вычислительно невозможно найти другой вход ${\displaystyle m_{2}}$, чтобы ${\displaystyle H(m_{1})=H(m_{2})}$.
• Стойкость к коллизиям (коллизиям второго рода). Должно быть вычислительно невозможно подобрать пару сообщений ${\displaystyle m_{1}}$ и ${\displaystyle m_{2}}$ , что ${\displaystyle H(m_{1})=H(m_{2})}$.^[7]

Сведём задачу криптоанализа хеш-функций к задаче поиска коллизии: сколько сообщений надо просмотреть, чтобы найти сообщения с двумя одинаковыми хешами.

Вероятность встретить одинаковые хеши для сообщений из двух разных наборов, содержащих ${\displaystyle n_{1}}$ и ${\displaystyle n_{2}}$ текстов, равна ${\displaystyle P\thickapprox 1-e^{-{\frac {n_{1}\cdot n_{2}}{2^{l}}}}}$. Если ${\displaystyle n_{1}=n_{2}=2^{l/2}}$, то вероятность успеха атаки ${\displaystyle P\thickapprox 1-e^{-1}\thickapprox 0,63}$, а сложность проведения атаки ${\displaystyle 2^{l/2+1}}$ операций.

Чтобы найти коллизию, надо сгенерировать два псевдослучайных множества сообщений (в каждом множестве ${\displaystyle 2^{n/2}}$ сообщений) и найти для них хеши. Тогда, согласно парадоксу дней рождения (см. также атака «дней рождения»), вероятность того, что среди них найдется пара сообщений с одинаковыми хешами, больше 0,5. Атака требует большого объёма памяти для хранения текстов и эффективных методов сортировки.^[8]

Суть конструкции заключается в итеративном процессе последовательных преобразований, когда на вход каждой итерации поступает блок исходного текста и выход предыдущей итерации^[9].

Наиболее широко используются хеш-функции, основанные на этой конструкции в MD5, SHA-1 и SHA-2.

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

Атака нахождения второго прообраза (учитывая сообщение ${\displaystyle m_{1}}$, злоумышленник находит ещё одно сообщение ${\displaystyle m_{2}}$, чтобы удовлетворить ${\displaystyle H(m_{1})=H(m_{2})}$) может быть выполнена в соответствии с Килси и Шнайером, для сообщения из 2^k блоков может быть выполнена за время k × 2^n/2+1 + 2^n-k+1. Важно отметить, если сообщения длинные, то сложность атаки находится между 2^n/2 и 2ⁿ, а когда длина сообщения становится меньше, сложность приближается к 2ⁿ.^[10]

Роль функции сжатия может осуществлять любой блочный шифр E. Данная идея легла в основу развития конструкции Меркла — Дамгора в схемах Дэвиса — Мейера, Матиса — Мейера — Осеаса, Миагути — Пренеля^[11].

В данной схеме блок сообщения ${\displaystyle m_{i}}$ и предыдущее значение хеш-функции ${\displaystyle H_{i-1}}$ поступают в качестве ключа и блока открытого текста соответственно на вход блочного шифра ${\displaystyle E}$. Получившийся в результате шифрования блок закрытого текста суммируется (операция XOR) с результатом предыдущей итерации хеширования (${\displaystyle H_{i-1}}$) для получения следующего значения хеш-функции (${\displaystyle H_{i}}$).^[11]

В математических обозначениях схему Дэвиса — Мейера можно записать как:

${\displaystyle H_{i}=E_{m_{i}}{(H_{i-1})}\oplus {H_{i-1}}.}$

Если блочный шифр использует, например, 256-битный ключ, то каждый блок сообщений (${\displaystyle m_{i}}$) представляет собой 256-битный фрагмент сообщения. Если же блочный шифр использует размер блока в 128 бит, то входные и выходные значения хеш-функции в каждом раунде составляют 128 бит.

Важным свойством конструкции Дэвиса — Мейера является то, что даже если базовый блок шифрования является полностью безопасным, можно вычислить неподвижные точки для построения: для любого ${\displaystyle m}$ можно найти значение ${\displaystyle h}$ такое что ${\displaystyle E_{m}(h)\oplus h=h}$ : просто нужно установить ${\displaystyle h=E_{m}^{-1}(0)}$.^[12]

Безопасность структуры Дэвиса — Мейера была впервые доказана Винтерницом^[13].

Это версия схемы Девиса — Мейера: блоки сообщения применяются как ключи криптосистемы. Схема может быть использована, если блоки данных и ключ шифрования имеют один и тот же размер. Например, AES хорошо подходит для этой цели.

В данной конструкции блок сообщения ${\displaystyle m_{i}}$ и предыдущее значение хеш-функции ${\displaystyle H_{i-1}}$ поступают в качестве ключа и блока открытого текста соответственно на вход блочного шифра ${\displaystyle E}$. Но уже значение ${\displaystyle H_{i-1}}$ подвергается предварительной обработке функцией ${\displaystyle g}$ из-за возможных различий в размерах хеш-суммы и размере ключа шифра ${\displaystyle E}$. Эта функция реализует отображение n-битного значения хеш- функции в k-битный ключ шифра ${\displaystyle E}$. В результате применения операции шифрования, получается блок закрытого текста, который суммируется с соответствующим ему блоком открытого текста (${\displaystyle m_{i}}$).^[14]

В математических обозначениях схему Матиса — Мейера — Осеаса можно записать как:

${\displaystyle H_{i}=E_{g(H_{i-1})}(m_{i})\oplus m_{i}.}$

Схема Миагути — Пренеля — расширенная версия схемы Матиса — Мейера — Осеаса. Отличие в том, что блок закрытого текста суммируется не только с соответствующим ему блоком открытого текста (${\displaystyle m_{i}}$), но и с результатом предыдущей итерации хеширования (${\displaystyle H_{i-1}}$). Чтобы сделать алгоритм более устойчивым к атаке, исходный текст, ключ шифра и зашифрованный текст складываются с помощью операции XOR и создают новый дайджест. Эта схема используется в Whirlpool для создания хеш-функции. Результат суммирования ${\displaystyle H_{i}}$ определяется уравнением^[15]:

${\displaystyle H_{i}=E_{g(H_{i-1})}(m_{i})\oplus H_{i-1}\oplus m_{i}.}$

• Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Chapter 9 // Hash Functions and Data Integrity. — 5-e изд. — August 2001. — С. 328.
• Брюс Шнайер. Прикладная криптография. — 2-e изд. — 2006. — С. 37—38. — 610 с.
• В.В.Ященко. Введение в криптографию. — 1999. — С. 30. — 271 с.
• С.Баричев, Р.Серов. Основы современной криптографии. — Москва, 2001. — С. 106—108. — 122 с.
• С.В.Дубров. Основы современной криптографии. — Новосибирск, 2012. — С. 65—67. — 260 с.
• John Kelsey and Bruce Schneier. Second preimages on n-bit hash functions for much less than 2n work. — 2005. — С. 474–490.
• R. Winternitz. A secure one-way hash function built from DES. — IEEE Press, 1984. — С. 88—90.

• Авезова Яна Эдуардовна. Современные подходы к построению хеш-функций на примере финалистов конкурса sha-3. — Москва, 2015.
• А. В. Антонов. [www.hups.mil.gov.ua/periodic-app/article/1988/soivt_2012_2_23.pdf Развитие метода построения хеш-функции]. — Харьков, 2012.