Функция одностороннего сжатия

В криптографии функция одностороннего сжатия — это функция, которая преобразует два входных сигнала фиксированной длины в выходные данные фиксированной длины. Преобразование является «односторонним» , что означает, что для конкретного вывода сложно вычислить входные данные, которые сжимаются до этого вывода. Функции одностороннего сжатия не связаны с обычными алгоритмами сжатия данных , которые вместо этого могут быть инвертированы точно (сжатие без потерь) или приблизительно (сжатие с потерями) к исходным данным.

Функция одностороннего сжатия

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

Функции одностороннего сжатия часто создаются на основе блочных шифров . Некоторые методы превращения любого обычного блочного шифра в функцию одностороннего сжатия: Дэвис-Мейер , Матьяс-Мейер-Осеас , Миягути-Пренель (функции сжатия единичного блока) и MDC-2/Meyer-Shilling , MDC-4. , Hirose (функции сжатия двухблочной длины). Эти методы подробно описаны далее. ( MDC-2 — это также название хэш-функции, запатентованной IBM .)

Другой метод - 2BOW (или NBOW в целом), который представляет собой «высокоскоростную хеш-функцию с несколькими блоками, основанную на блочных шифрах». и обычно достигает (асимптотических) показателей от 1 до 2 независимо от размера хеша (только с небольшими постоянными издержками). Этот метод еще не подвергался серьезному анализу безопасности, поэтому с ним следует обращаться осторожно.

Сжатие

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

Например, вход A может иметь 128 бит, вход B — 128 бит, и они вместе сжимаются до одного выхода в 128 бит. Это эквивалентно сжатию одного 256-битного входного сигнала в один выходной 128-битный.

Некоторые функции сжатия сжимают не наполовину, а сжимают с некоторым другим коэффициентом. Например, вход A может иметь 256 бит, а вход B — 128 бит, которые сжимаются до одного выхода в 128 бит. То есть всего 384 входных бита сжимаются до 128 выходных битов.

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

В одну сторону

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

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

• Легко вычислить: если у вас есть входные данные, вычислить результат легко.
• Устойчивость к прообразу: если злоумышленник знает только выходные данные, вычислить входные данные будет невозможно. Другими словами, учитывая результат $h$, должно быть невозможно вычислить входные данные $m$ такой, что $\operatorname {hash} (m)=h$.
• Второе сопротивление прообразу: при наличии входных данных $m_{1}$ чей вывод $h$, должно быть невозможно найти другой вход $m_{2}$ у которого такой же вывод $h$, то есть $\operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})$.
• Устойчивость к коллизиям: должно быть сложно найти два разных входа, которые сжимаются до одного и того же выхода, т.е. злоумышленник не должен иметь возможности найти пару сообщений. $m_{1}\neq m_{2}$ такой, что $\operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})$. Из-за парадокса дня рождения (см. также «Атака дня рождения ») существует 50%-ная вероятность того, что столкновение можно будет обнаружить примерно через $2^{n/2}$ где $n$ — количество битов на выходе хэш-функции. Таким образом, атака на хеш-функцию не должна позволять обнаруживать коллизии менее чем с $2^{n/2}$ работа.

В идеале хотелось бы, чтобы «неосуществимость» сопротивления прообразу и сопротивления второму прообразу означала работу примерно $2^{n}$ где $n$ — количество битов на выходе хэш-функции. Однако, особенно для устойчивости ко второму прообразу, это представляет собой сложную проблему.

Конструкция Меркле-Дамгорда

Основная статья: Строительство Меркла – Дамгорда

Хэш-конструкция Меркла-Дамгорда. Поля с надписью [f] представляют собой функцию одностороннего сжатия.

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

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

Когда применяется заполнение длины (также называемое усилением MD), атаки не могут обнаружить коллизии быстрее, чем парадокс дня рождения ( $2^{n/2}$, $n$ размер блока в битах), если используемая функция $f$ устойчив к столкновениям. Следовательно, хэш-конструкция Меркла-Дамгорда сводит проблему поиска правильной хеш-функции к поиску правильной функции сжатия.

Вторая атака по прообразу (при сообщении $m_{1}$ злоумышленник находит другое сообщение $m_{2}$ удовлетворить $\operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})$ можно сделать по Келси и Шнайеру для $2^{k}$-message-блокировать сообщение вовремя $k\times 2^{n/2+1}+2^{n-k+1}$. Сложность этой атаки достигает минимума $2^{3n/4+2}$ для длинных сообщений, когда $k=2^{n/4}$ и подходы $2^{n}$ когда сообщения короткие.

Построение из блочных шифров

Типичный современный блочный шифр

Функции одностороннего сжатия часто создаются на основе блочных шифров.

Блочные шифры принимают (как и функции одностороннего сжатия) два входных сигнала фиксированного размера ( ключ и открытый текст ) и возвращают один выходной сигнал ( зашифрованный текст ), размер которого равен входному открытому тексту.

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

Некоторые методы превращения любого обычного блочного шифра в функцию одностороннего сжатия: Дэвис-Мейер, Матьяс-Мейер-Осеас, Миягути-Пренел (функции сжатия единичного блока) и MDC-2, MDC-4, Hirose (двойное сжатие). -функции сжатия по длине блока).

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

Если блочный шифр имеет размер блока , скажем, 128 бит, методы с одинарной длиной блока создают хеш-функцию с размером блока 128 бит и создают хеш из 128 бит. Методы двойной длины блока создают хеши с размером вдвое большим по сравнению с размером блока используемого блочного шифра. Таким образом, 128-битный блочный шифр можно превратить в 256-битную хеш-функцию.

Эти методы затем используются внутри конструкции Меркла-Дамгорда для построения фактической хеш-функции. Эти методы подробно описаны далее.

Использование блочного шифра для построения функции одностороннего сжатия для хеш-функции обычно несколько медленнее, чем использование специально разработанной функции одностороннего сжатия в хеш-функции. Это связано с тем, что все известные конструкции безопасности выполняют планирование ключей для каждого блока сообщения. Блэк, Кокран и Шримптон показали, что невозможно построить функцию одностороннего сжатия, которая выполняет только один вызов блочного шифра с фиксированным ключом. На практике разумные скорости достигаются при условии, что планирование ключа выбранного блочного шифра не является слишком сложной операцией.

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

Таким образом, скорость хеширования или скорость дают представление об эффективности хеш-функции, основанной на определенной функции сжатия. Скорость повторной хеш-функции определяет соотношение между количеством операций блочного шифрования и выходным результатом. Точнее, скорость представляет собой соотношение между количеством обработанных бит входных данных. $m$, выходная разрядность $n$ блочного шифра и необходимые операции блочного шифра. $s$ производить эти $n$ выходные биты. Как правило, использование меньшего количества операций блочного шифрования приводит к повышению общей производительности всей хеш-функции, но также приводит к меньшему хеш-значению, что может быть нежелательно. Ставка выражается формулой:

$R_{h}={\frac {\left|m_{i}\right|}{s\cdot n}}$

Хэш-функция может считаться безопасной только в том случае, если выполняются как минимум следующие условия:

• Блочный шифр не имеет особых свойств, отличающих его от идеальных шифров, таких как слабые ключи или ключи, которые приводят к идентичному или связанному шифрованию (фиксированные точки или коллизии ключей).
• Полученный размер хеша достаточно велик. По дню рождения атака уровень безопасности 2. ⁸⁰ (обычно считается, что сегодня невозможно вычислить) желательно при этом размер хеша должен быть не менее 160 бит.
• Последний блок правильно дополняется по длине перед хешированием. (См. конструкцию Меркла – Дамгарда .) Заполнение длины обычно реализуется и обрабатывается внутри специализированных хеш-функций, таких как SHA-1 и т. д.

Представленные ниже конструкции: Дэвис-Мейер, Матьяс-Мейер-Осеас, Миягути-Пренель и Хиросе оказались безопасными при анализе черного ящика . Цель состоит в том, чтобы показать, что любая обнаруженная атака при определенных предположениях не менее эффективна, чем атака на день рождения . Модель черного ящика предполагает, что используется блочный шифр, случайно выбираемый из набора, содержащего все подходящие блочные шифры. В этой модели злоумышленник может свободно шифровать и расшифровывать любые блоки, но не имеет доступа к реализации блочного шифра. Функция шифрования и дешифрования представлена ​​оракулами, которые получают пару: открытый текст и ключ или зашифрованный текст и ключ. Затем оракулы отвечают случайно выбранным открытым текстом или зашифрованным текстом, если пара задается впервые. Они оба используют общую таблицу для этих троек, пары из запроса и соответствующего ответа, и возвращают запись, если запрос был получен во второй раз. Для доказательства существует алгоритм поиска коллизий, который делает случайно выбранные запросы к оракулам. Алгоритм возвращает 1, если два ответа приводят к конфликту с участием хеш-функции, построенной на основе функции сжатия с применением этого блочного шифра (иначе 0). Вероятность того, что алгоритм вернет 1, зависит от количества запросов, определяющих уровень безопасности.

Дэвис-Мейер

Функция одностороннего сжатия Дэвиса – Мейера.

Функция сжатия одного блока Дэвиса-Мейера подает каждый блок сообщения ( $m_{i}$) как ключ к блочному шифру. Он передает предыдущее значение хеш-функции ( $H_{i-1}$) в качестве открытого текста для шифрования. Затем выходной зашифрованный текст также подвергается операции XOR (⊕) с предыдущим значением хеш-функции ( $H_{i-1}$), чтобы получить следующее хеш-значение ( $H_{i}$). В первом раунде, когда предыдущего хеш-значения нет, используется постоянное заранее заданное начальное значение ( $H_{0}$).

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

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

Схема имеет скорость (k — размер ключа):

$R_{DM}={\frac {k}{1\cdot n}}={\frac {k}{n}}$

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

Вариации этого метода заменяют XOR любой другой групповой операцией, например сложением 32-битных целых чисел без знака.

Примечательным свойством конструкции Дэвиса-Мейера является то, что даже если базовый блочный шифр полностью безопасен, можно вычислить фиксированные точки для конструкции: для любого $m$, можно найти значение $h$ такой, что $E_{m}(h)\oplus h=h$: нужно просто установить $h=E_{m}^{-1}(0)$. Это свойство, которым случайные функции определенно не обладают. До сих пор на этом свойстве не было основано ни одной практической атаки, но об этой «особенности» следует знать. Фиксированные точки могут быть использованы во второй атаке на прообраз (при наличии сообщения $m_{1}$, злоумышленник находит другое сообщение $m_{2}$ удовлетворить $\operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})$) Келси и Шнайера для $2^{k}$-message-блокировать сообщение вовремя $3\times 2^{n/2+1}+2^{n-k+1}$. Если конструкция не позволяет легко создавать фиксированные точки (например, Матьяс-Мейер-Осеас или Миягути-Пренель), то эту атаку можно выполнить в $k\times 2^{n/2+1}+2^{n-k+1}$ время. В обоих случаях сложность выше $2^{n/2}$ но ниже $2^{n}$ когда сообщения длинные и когда сообщения становятся короче, сложность атаки возрастает $2^{n}$.

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

Матиас-Мейер-Осия

Функция одностороннего сжатия Матьяса – Мейера – Осеаса

Функцию одностороннего сжатия Матьяса – Мейера – Осеаса с длиной одного блока можно считать двойственной (противоположной) функции Дэвиса – Мейера.

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

Если блочный шифр имеет разные размеры блока и ключа, хеш-значение ( $H_{i-1}$) будет иметь неправильный размер для использования в качестве ключа. Шифр также может иметь другие особые требования к ключу. Затем хэш-значение сначала передается через функцию $g$ быть преобразованным/дополненным, чтобы соответствовать ключу для шифра.

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

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

Схема имеет тариф:

$R_{MMO}={\frac {n}{1\cdot n}}=1$

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

Миягути-Пренель

Функция одностороннего сжатия Миягути – Пренеля

Функция одностороннего сжатия Миягути-Пренеля с длиной одного блока представляет собой расширенный вариант функции Матьяса-Мейера-Осеаса. Его независимо предложили Сёдзи Миягути и Барт Пренил .

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

Если блочный шифр имеет разные размеры блока и ключа, хеш-значение ( $H_{i-1}$) будет иметь неправильный размер для использования в качестве ключа. Шифр также может иметь другие особые требования к ключу. Затем хэш-значение сначала передается через функцию $g$ быть преобразованным/дополненным, чтобы соответствовать ключу для шифра.

В математических обозначениях Миягути – Пренеля можно описать как:

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

Схема имеет тариф:

$R_{MP}={\frac {n}{1\cdot n}}=1$

Роли $m_{i}$ и $H_{i-1}$ можно переключить, так что $H_{i-1}$ зашифрован под ключом $m_{i}$, что делает этот метод расширением метода Дэвиса – Мейера.

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

Хиросе

Функция сжатия двухблочной длины Hirose

Хиросе Функция одностороннего сжатия с двойной длиной блока состоит из блочного шифра и перестановки. $p$. Он был предложен Сёичи Хиросе в 2006 году и основан на работе Мридул Нанди .

Он использует блочный шифр, длина ключа которого $k$ больше длины блока $n$и создает хэш размером $2n$. Например, любой из кандидатов AES со 192- или 256-битным ключом (и 128-битным блоком).

Каждый раунд принимает часть сообщения $m_{i}$ то есть $k-n$ бит и использует его для обновления двух $n$-битные значения состояния $G$ и $H$.

Первый, $m_{i}$ объединяется с $H_{i-1}$ изготовить ключ $K_{i}$. Затем два значения обратной связи обновляются в соответствии с:

• $G_{i}=E_{K_{i}}(G_{i-1})\oplus G_{i-1}$
• $H_{i}=E_{K_{i}}(p(G_{i-1}))\oplus p(G_{i-1})$

$p(G_{i-1})$ — произвольная перестановка без неподвижных точек на $n$-битовое значение, обычно определяемое как $p(x)=x\oplus c$ для произвольной ненулевой константы $c$ (все могут быть удобным выбором).

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

Окончательный результат $H_{t}||G_{t}$. Схема имеет тариф ${\textstyle R_{Hirose}={\frac {k-n}{2n}}}$ относительно шифрования сообщения с помощью шифра.

Хиросе также предоставляет доказательство в модели идеального шифра.

Губка строительная

Губчатую конструкцию можно использовать для создания функций одностороннего сжатия.

См. также

• Whirlpool — криптографическая хэш-функция, построенная с использованием конструкции Миягути-Пренеля и блочного шифра, аналогичного Square и AES .
• CBC-MAC , OMAC и PMAC — методы преобразования блочных шифров в коды аутентификации сообщений (MAC).

Ссылки

Источники

• Менезес; ван Оршот; Ванстон (2001). «Хеш-функции и целостность данных» (PDF) . Справочник по прикладной криптографии .