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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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)$.Шаблон:Sfn

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

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

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

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

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

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

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

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

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

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

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

Литература

Книги

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

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

• Шаблон:Статья
• Шаблон:Статья