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

В Криптографии, односторонняя функция сжатии - это такая функция, которая образует значение длиной 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}.$

См. также

• Whirlpool (криптография)
• Блочный шифр

Литература

Книги

• 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. — Springer, 2005. — С. 474–490.
• R. Winternitz. A secure one-way hash function built from DES. — IEEE Press, Springer, 2005. — С. 88-90.

Научные статьи

• Авезова Яна Эдуардовна. СОВРЕМЕННЫЕ ПОДХОДЫ К ПОСТРОЕНИЮ ХЭШ-ФУНКЦИЙ НА ПРИМЕРЕ ФИНАЛИСТОВ КОНКУРСА SHA-3. — Москва, 2015.
• А.В. Антонов. [www.hups.mil.gov.ua/periodic-app/article/1988/soivt_2012_2_23.pdf РАЗВИТИЕ МЕТОДА ПОСТРОЕНИЯ ХЕШ-ФУНКЦИИ]. — Харьков, 2012.