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

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

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

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

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

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

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

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

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

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

• Стойкость к поиску первого прообраза — отсутствие эффективного полиномиального алгоритма вычисления обратной функции , то есть нельзя восстановить текст ${\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})}$ .

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

Вероятность встретить одинаковые хеши для сообщений из двух разных наборов, содержащих ${\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. Атака требует большого объёма памяти для хранения текстов и эффективных методов сортировки.

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

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

Наиболее широко используются хеш-функции, основанные на этой конструкции в 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 ⁿ .

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

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

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

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

${\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)}$ .

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

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

Это версия схемы Девиса — Мейера: блоки сообщения применяются как ключи криптосистемы . Схема может быть использована, если блоки данных и ключ шифрования имеют один и тот же размер. Например, 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}}$ ).

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

${\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}}$ определяется уравнением :

${\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 // . — 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.

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

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