Функция одностороннего сжатия - One-way compression function

В криптография, а функция одностороннего сжатия - это функция, которая преобразует два входа фиксированной длины в выход фиксированной длины.^[1] Преобразование "в одну сторону", что означает, что для конкретного выхода сложно вычислить входные данные, которые сжимаются до этого выхода. Функции одностороннего сжатия не относятся к обычным Сжатие данных алгоритмы, которые вместо этого можно точно инвертировать (сжатие без потерь) или приблизительно (сжатие с потерями) к исходным данным.

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

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

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

Сжатие

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

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

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

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

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

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

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

• Легко вычислить: если у вас есть какие-то входные данные, легко вычислить выход.
• Сопротивление прообразу: если злоумышленник знает только выходные данные, вычислить входные данные будет невозможно. Другими словами, на выходе час, должно быть невозможно вычислить вход м такой, что хэш(м)=час.
• Сопротивление второго прообраза: задан вход m1 чей выход час, должно быть невозможно найти другой вход m2 который имеет такой же вывод час т.е. ${displaystyle hash(m1)eq hash(m2)}$.
• Сопротивление столкновению: Должно быть трудно найти любые два разных входа, которые сжимаются до одного и того же выхода, то есть злоумышленник не должен быть в состоянии найти пару сообщений m1 ≠ m2 таких, что хэш(m1) = хэш(m2). Из-за парадокс дня рождения (смотрите также атака на день рождения ) вероятность столкновения составляет 50% примерно за 2 секунды.^{п / 2} где n - количество бит на выходе хэш-функции. Таким образом, атака на хеш-функцию не должна найти коллизию менее чем с 2^{п / 2} работай.

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

Строительство Меркла-Дамгарда

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

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

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

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

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

Когда применяется дополнение по длине (также называемое MD-усилением), атаки не могут находить коллизии быстрее, чем парадокс дня рождения (2^п/2, п размер блока в битах), если используется ж-функция устойчива к столкновениям.^[3][4] Следовательно, конструкция хеширования Меркла – Дамгарда сводит проблему поиска подходящей хеш-функции к поиску подходящей функции сжатия.

Вторая атака на прообраз (с сообщением м₁ злоумышленник находит другое сообщение м₂ чтобы удовлетворить хэш (м₁) = хеш (м₂)) можно сделать по Келси и Шнайеру^[5] для 2^k-message-block сообщение вовремя k × 2^п/2+1 + 2^п−k+1. Обратите внимание, что сложность этой атаки достигает минимум 2^3п/4+2 для длинных сообщений, когда k = 2^п/4 и подходов 2^п когда сообщения короткие.

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

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

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

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

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

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

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

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

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

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

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

Следовательно, хеш-скорость или скорость дают представление об эффективности хеш-функции на основе определенной функции сжатия. Скорость повторной хеш-функции показывает соотношение между количеством операций блочного шифрования и выходными данными. Точнее, если n обозначает длину выходных битов блочного шифра, то скорость представляет собой отношение между количеством обработанных битов входных m, n выходных битов и необходимыми операциями блочного шифра s для создания этих n выходных битов. Как правило, использование меньшего количества операций с блочным шифрованием может привести к лучшей общей производительности всей хеш-функции, но это также приводит к меньшему хэш-значению, что может быть нежелательным. Ставка выражается формулой ${displaystyle R_{h}={frac {left|m_{i}ight|}{scdot n}}}$.

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

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

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

Дэвис-Мейер

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

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

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

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

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

${displaystyle R_{DM}={frac {k}{1cdot n}}={frac {k}{n}}.}$

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

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

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

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

Матиас – Мейер – Осеас

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

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

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

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

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

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

Схема имеет курс:

${displaystyle R_{MMO}={frac {n}{1cdot n}}=1.}$

Вторая атака на прообраз (для сообщения m1 злоумышленник находит другое сообщение m2, удовлетворяющее hash (m1) = hash (m2)) может быть проведена согласно Келси и Шнайеру.^[5] для 2^k-message-block сообщение за время k × 2^{п / 2 + 1}+2^{п-к + 1}. Обратите внимание, что сложность выше 2^{п / 2} но ниже 2^п когда сообщения длинные, а когда сообщения становятся короче, сложность атаки приближается к 2^п.

Миягути – Пренил

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

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

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

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

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

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

Схема имеет курс:

${displaystyle R_{MP}={frac {n}{1cdot n}}=1.}$

Роли м_я и H_я-1 можно переключить, так что H_я-1 зашифрован под ключом m_я. Таким образом, вместо этого этот метод является расширением метода Дэвиса-Мейера.

Вторая атака по прообразу (для сообщения m1 злоумышленник находит другое сообщение m2, удовлетворяющее hash (m1) = hash (m2)) может быть проведена согласно Келси и Шнайеру.^[5] для 2^k-message-block сообщение за время k × 2^{п / 2 + 1}+2^{п-к + 1}. Обратите внимание, что сложность выше 2^{п / 2} но ниже 2^п когда сообщения длинные, а когда сообщения становятся короче, сложность атаки приближается к 2^п.

Хиросе

Функция сжатия двойного блока по длине Хиросе

Хиросе^[8] Функция одностороннего сжатия двойной длины состоит из блочного шифра и перестановки p. Он был предложен Шоичи Хиросе в 2006 году и основан на работе^[11] к Мридул Нанди.

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

Каждый раунд принимает часть сообщения м_я то есть k−п бит, и использует его для обновления двух п-битовые значения состояния грамм и ЧАС.

Первый, м_я соединяется с ЧАС_я−1 изготовить ключ K_я. Затем два значения обратной связи обновляются в соответствии с:

• грамм_я = E_Kя(ГРАММ_я−1) ⊕ G_я−1
• ЧАС_я = E_Kя(п(ГРАММ_я−1)) ⊕ п(ГРАММ_я−1).

п(ГРАММ_я−1) - произвольная перестановка без неподвижных точек на п-битовое значение, обычно определяемое как

• п(Икс) = Икс ⊕ c

для произвольной ненулевой постоянной c. (Все единицы могут быть удобным выбором.)

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

Окончательный результат ЧАС_т||грамм_т. Схема имеет ставку р_Хиросе = (k−п)/2п относительно шифрования сообщения с помощью шифра.

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

Конструкция из губки

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

Смотрите также

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

Рекомендации

1. Справочник по прикладной криптографии Альфреда Дж. Менезеса, Пола К. ван Оршота, Скотта А. Ванстоуна. Пятое издание (август 2001 г.), стр. 328.
2. "Объявление о первом конфликте SHA1". Блог Google Online Security. Получено 2020-01-12.
3. Иван Дамгард. Принцип построения хеш-функций. Жиль Брассар, редактор CRYPTO, том 435 LNCS, страницы 416–427. Спрингер, 1989.
4. Ральф Меркл. Односторонние хэш-функции и DES. Жиль Брассар, редактор CRYPTO, том 435 LNCS, страницы 428–446. Спрингер, 1989.
5. Джон Келси и Брюс Шнайер. Вторые прообразы на п-битные хеш-функции для гораздо меньше 2^п работай. В Рональде Крамере, редакторе EUROCRYPT, том 3494 LNCS, страницы 474–490. Спрингер, 2005.
6. Джон Блэк, Мартин Кокран и Томас Шримптон. О невозможности создания высокоэффективных хеш-функций на основе блочного шифрования. Достижения в криптологии - EUROCRYPT '05, Орхус, Дания, 2005. Авторы определяют хеш-функцию «высокоэффективной, если ее функция сжатия использует только один вызов блочного шифра с фиксированным ключом».
7. Джон Блэк, Филлип Рогавей и Том Шримптон. Анализ методом черного ящика построений хэш-функций на основе блочного шифра из PGV. Достижения в криптологии - CRYPTO '02, Lecture Notes in Computer Science, vol. 2442, pp. 320–335, Springer, 2002. См. Таблицу на стр. 3, Дэвис-Мейер, Матиас-Мейер-Осис и Миягути-Пренель пронумерованы в первом столбце как хэш-функции 5, 1 и 3.
8. С. Хиросе, Некоторые правдоподобные конструкции хеш-функций двойной длины. В: Робшоу, М. Дж. Б. (ред.) FSE 2006, LNCS, vol. 4047, стр. 210–225, Springer, Heidelberg 2006.
9. Справочник по прикладной криптографии Альфреда Дж. Менезеса, Пола К. ван Оршота, Скотта А. Ванстоуна. Пятое издание (август 2001 г.), стр. 375.
10. Р. Винтерниц. Безопасная односторонняя хеш-функция, построенная на DES. В материалах симпозиума IEEE по информационной безопасности и конфиденциальности, стр. 88-90. IEEE Press, 1984.
11. М. Нанди, На пути к оптимальным хэш-функциям двойной длины, В: Материалы 6-й Международной конференции по криптологии в Индии (INDOCRYPT 2005), Lecture Notes in Computer Science 3797, pages 77–89, 2005.

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