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

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

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

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

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

Функция сжатия

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

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

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

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

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

Основная статья: Односторонняя функция

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

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

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

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

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

Структура Меркла — Дамгора

Основная статья: Структура Меркла — Дамгора

Структура Меркла — Дамгора, где IV — начальное значение свертки (фиксированный вектор), $f$ — функция сжатия.

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

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

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

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

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

Структура Дэвиса — Мейера

Схема Дэвиса — Мейера

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

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

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

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

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

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

Структура Матиса — Мейера — Осеаса

Схема Матиса-Мейера-Осеаса

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

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

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

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

Структура Миагути — Пренеля

Основная статья: Функция Миагути — Пренеля

Схема Миагучи-Пренеля

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

$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.