В криптографии , A функция сжатия односторонний является функцией , которая преобразует два входа фиксированной длиной в выходной сигнал с фиксированной длиной. [1] Преобразование является «односторонним» , что означает, что для конкретного выхода трудно вычислить входные данные, которые сжимаются до этого выхода. Функции одностороннего сжатия не связаны с традиционными алгоритмами сжатия данных , которые вместо этого могут быть инвертированы точно (сжатие без потерь) или приблизительно (сжатие с потерями) исходных данных.
Функции одностороннего сжатия, например, используются в конструкции Меркла – Дамгарда внутри криптографических хеш-функций .
Функции одностороннего сжатия часто строятся из блочных шифров . Некоторые методы для преобразования любого нормального блочного шифра в функцию одностороннего сжатия: Дэвис-Мейер , Матьяс-Мейер-Осис , Миягути-Пренель (функции сжатия по длине одного блока) и MDC-2 / Мейер-Шиллинг , MDC-4 , Хиросе (функции сжатия двойной длины блока). Эти методы подробно описаны ниже. ( MDC-2 - это также название хеш-функции, запатентованной IBM .)
Сжатие
Функция сжатия смешивает два входа фиксированной длины и производит один выходной сигнал фиксированной длины того же размера, что и один из входов. Это также можно увидеть как то, что функция сжатия преобразует один большой ввод фиксированной длины в более короткий вывод фиксированной длины.
Например, вход A может быть 128 бит, вход B 128 бит, и они сжимаются вместе до одного выхода 128 бит. Это эквивалентно сжатию одного 256-битного входа до одного 128-битного выхода.
Некоторые функции сжатия сжимаются не наполовину, а с помощью другого фактора. Например, вход A может быть 256 бит, а вход B 128 бит, которые сжимаются до одного выхода из 128 бит. То есть всего 384 входных бита сжимаются вместе до 128 выходных бит.
Перемешивание производится таким образом, что достигается полный лавинный эффект . То есть каждый выходной бит зависит от каждого входного бита.
В одну сторону
Односторонняя функция является функцией , которая легко вычислить , но трудно инвертировать. Функция одностороннего сжатия (также называемая хеш-функцией) должна иметь следующие свойства:
- Легко вычислить: если у вас есть ввод (ы), легко вычислить вывод.
- Сопротивление прообразу: если злоумышленник знает только выходные данные, вычислить входные данные будет невозможно. Другими словами, на выходе, должно быть невозможно вычислить ввод такой, что .
- Второй прообраз-сопротивление: задан вход чей выход , должно быть невозможно найти другой вход который имеет такой же вывод , т.е. .
- Устойчивость к коллизиям: должно быть трудно найти любые два разных входа, которые сжимаются в один и тот же выход, т.е. злоумышленник не должен быть в состоянии найти пару сообщений. такой, что . Из-за парадокса дня рождения (см. Также « Атака дня рождения» ) существует 50% -ная вероятность, что столкновение может быть обнаружено примерно через где - количество бит в выводе хеш-функции. Таким образом, атака на хеш-функцию не должна обнаруживать коллизию с менее чем примерно Работа.
В идеале нужно, чтобы «неосуществимость» в сопротивлении прообразу и сопротивлению второму прообразу означала работу примерно где - количество бит в выводе хеш-функции. Однако, особенно для сопротивления второму прообразу, это является сложной проблемой. [ необходима цитата ]
Строительство Меркла-Дамгарда
Обычно функции одностороннего сжатия используются в конструкции Меркла – Дамгарда внутри криптографических хеш-функций. Эта конструкция используется в наиболее широко используемых хэш-функциях, включая MD5 , SHA-1 (устарел [2] ) и SHA-2 .
Хеш-функция должна иметь возможность обрабатывать сообщение произвольной длины в вывод фиксированной длины. Этого можно добиться, разбив входные данные на серию блоков одинакового размера и последовательно работая с ними, используя функцию одностороннего сжатия. Функция сжатия может быть либо специально разработана для хеширования, либо построена на основе блочного шифра.
Последний обработанный блок также должен быть дополнен по длине , это важно для безопасности этой конструкции. Эта конструкция называется конструкцией Меркла – Дамгарда . Эту форму принимают наиболее широко используемые хэш-функции, включая SHA-1 и MD5 .
Когда применяется дополнение по длине (также называемое MD-усилением), атаки не могут находить коллизии быстрее, чем парадокс дня рождения (, размер блока в битах), если используемая функция устойчив к столкновениям. [3] [4] Следовательно, конструкция хеширования Меркла – Дамгарда сводит проблему поиска подходящей хеш-функции к поиску подходящей функции сжатия.
Вторая атака на прообраз (с сообщением злоумышленник находит другое сообщение удовлетворить можно сделать согласно Келси и Шнайеру [5] для-сообщение-блокировка сообщения вовремя . Обратите внимание, что сложность этой атаки достигает минимум для длинных сообщений, когда и подходы когда сообщения короткие.
Построение из блочных шифров
Функции одностороннего сжатия часто строятся из блочных шифров.
Блочные шифры принимают (как функции одностороннего сжатия) два входа фиксированного размера ( ключ и открытый текст ) и возвращают один единственный выход ( зашифрованный текст ), который имеет тот же размер, что и входной открытый текст.
Однако современные блочные шифры только частично односторонние. То есть, учитывая открытый текст и зашифрованный текст, невозможно найти ключ, который шифрует открытый текст в зашифрованный текст. Но, учитывая зашифрованный текст и ключ, соответствующий открытый текст можно найти, просто используя функцию дешифрования блочного шифра. Таким образом, чтобы превратить блочный шифр в функцию одностороннего сжатия, необходимо добавить некоторые дополнительные операции.
Некоторые методы превращения любого нормального блочного шифра в функцию одностороннего сжатия: Дэвис-Мейер, Матяс-Мейер-Осис, Миягути-Пренель (функции сжатия по длине одного блока) и MDC-2, MDC-4, Hirose (двойная функции сжатия длины блока).
Функции сжатия с одноблочной длиной выводят то же количество битов, которое обрабатывается базовым блочным шифром. Следовательно, функции сжатия с двойной длиной блока выводят вдвое больше битов.
Если блочный шифр имеет размер блока, скажем, 128 битов, методы с одинарной длиной блока создают хеш-функцию, которая имеет размер блока 128 бит и создает хэш 128 бит. Методы с двойной длиной блока создают хеши с размером в два раза больше, чем размер блока используемого блочного шифра. Таким образом, 128-битный блочный шифр можно превратить в 256-битную хеш-функцию.
Затем эти методы используются внутри конструкции Меркла – Дамгарда для построения фактической хэш-функции. Эти методы подробно описаны ниже.
Использование блочного шифра для построения функции одностороннего сжатия для хеш-функции обычно несколько медленнее, чем использование специально разработанной функции одностороннего сжатия в хеш-функции. Это связано с тем, что все известные безопасные конструкции выполняют планирование ключей для каждого блока сообщения. Блэк, Кокран и Шримптон показали, что невозможно построить функцию одностороннего сжатия, которая делает только один вызов блочного шифра с фиксированным ключом. [6] На практике приемлемые скорости достигаются при условии, что планирование ключей для выбранного блочного шифра не является слишком тяжелой операцией.
Но в некоторых случаях это проще, потому что одна реализация блочного шифра может использоваться как для блочного шифра, так и для хеш-функции. Он также может сэкономить место для кода в очень крошечных встроенных системах, таких как, например, смарт-карты или узлы в автомобилях или других машинах.
Следовательно, хеш-скорость или скорость дают представление об эффективности хеш-функции, основанной на определенной функции сжатия. Скорость повторной хеш-функции описывает соотношение между количеством операций блочного шифрования и выходными данными. Точнее, скорость представляет собой соотношение между количеством обработанных битов ввода., длина вывода в битах блочного шифра и необходимые операции блочного шифра производить эти выходные биты. Как правило, использование меньшего количества операций с блочным шифрованием приводит к лучшей общей производительности всей хеш-функции, но это также приводит к меньшему хэш-значению, что может быть нежелательным. Ставка выражается формулой:
Хеш-функцию можно считать безопасной только при соблюдении хотя бы следующих условий:
- Блочный шифр не имеет особых свойств, которые отличают его от идеальных шифров, таких как слабые ключи или ключи, которые приводят к идентичным или связанным шифрам (фиксированные точки или конфликты ключей).
- В результате размер хэша достаточно велик. В соответствии с днем рождения нападают на уровень безопасности из 2 80 ( как правило , предполагается, что неосуществимо вычислительном сегодня) [ править ] Желательно , таким образом , размер хэш должен быть по меньшей мере 160 битов.
- Последний блок правильно дополняется по длине перед хешированием. (См. Конструкцию Меркла – Дамгарда .) Заполнение длины обычно реализуется и обрабатывается внутри специализированных хэш-функций, таких как SHA-1 и т. Д.
Представленные ниже конструкции: Дэвис-Мейер, Матиас-Мейер-Осис, Миягути-Пренель и Хиросе оказались безопасными при анализе черного ящика . [7] [8] Цель состоит в том, чтобы показать, что любая атака, которая может быть обнаружена, не более эффективна, чем атака дня рождения при определенных предположениях. Модель черного ящика предполагает, что используется блочный шифр, который выбирается случайным образом из набора, содержащего все подходящие блочные шифры. В этой модели злоумышленник может свободно шифровать и расшифровывать любые блоки, но не имеет доступа к реализации блочного шифра. Функции шифрования и дешифрования представлены оракулами, которые получают пару из открытого текста и ключа или зашифрованного текста и ключа. Затем оракулы отвечают случайным образом выбранным открытым текстом или зашифрованным текстом, если пара была запрошена в первый раз. Они оба используют таблицу для этих триплетов, пару из запроса и соответствующего ответа, и возвращают запись, если запрос был получен во второй раз. Для доказательства существует алгоритм поиска коллизий, который делает случайно выбранные запросы к оракулам. Алгоритм возвращает 1, если два ответа приводят к конфликту с участием хэш-функции, которая построена из функции сжатия, применяющей этот блочный шифр (0 else). Вероятность того, что алгоритм вернет 1, зависит от количества запросов, определяющих уровень безопасности.
Дэвис-Мейер
Функция сжатия единичного блока Дэвиса-Мейера подает каждый блок сообщения () как ключ к блочному шифру. Он передает предыдущее значение хеш-функции () как открытый текст, который нужно зашифровать. Затем выходной зашифрованный текст также подвергается операции XOR (⊕) с предыдущим значением хеш-функции () для получения следующего хеш-значения (). В первом раунде, когда нет предыдущего хеш-значения, он использует постоянное заранее заданное начальное значение ().
В математических обозначениях Дэвиса-Мейера можно описать как:
Схема имеет скорость (k - размер ключа):
Если блочный шифр использует, например, 256-битные ключи, тогда каждый блок сообщения () - это 256-битный фрагмент сообщения. Если один и тот же блочный шифр использует размер блока 128 бит, тогда значения хеш-функции на входе и выходе в каждом раунде составляют 128 бит.
Варианты этого метода заменяют XOR любой другой групповой операцией, например сложением 32-битных целых чисел без знака.
Примечательным свойством конструкции Дэвиса – Мейера является то, что даже если лежащий в основе блочный шифр полностью безопасен, можно вычислить фиксированные точки для конструкции: для любого, можно найти значение такой, что : нужно просто установить . [9] Это свойство, которым, конечно, не обладают случайные функции . До сих пор на этом свойстве не было основано никаких практических атак, но об этой «особенности» следует помнить. Фиксированные точки могут использоваться во второй атаке прообраза (при наличии сообщения, злоумышленник находит другое сообщение удовлетворить Келси и Шнайера [5] для-сообщение-блокировка сообщения вовремя . Если конструкция не позволяет легко создать фиксированные точки (например, Матяс – Мейер – Осис или Миягути – Пренель), то эту атаку можно выполнить ввремя. Обратите внимание, что в обоих случаях сложность выше но ниже когда сообщения длинные, а когда сообщения становятся короче, сложность атаки приближается .
Безопасность конструкции Дэвиса – Мейера в идеальной модели шифра впервые была доказана Р. Винтерницем. [10]
Матиас – Мейер – Осеас
Одноблочную функцию одностороннего сжатия Матяса – Мейера – Осиса можно рассматривать как двойственную (противоположную) функцию Дэвиса – Мейера.
Он скармливает каждому блоку сообщения () как открытый текст, который нужно зашифровать. Затем выходной зашифрованный текст также подвергается операции XOR (⊕) с тем же блоком сообщения () для получения следующего хеш-значения (). Предыдущее значение хеш-функции () подается как ключ к блочному шифру. В первом раунде, когда нет предыдущего хеш-значения, он использует постоянное заранее заданное начальное значение ().
Если блочный шифр имеет разные размеры блока и ключа, значение хеш-функции () будет иметь неправильный размер для использования в качестве ключа. У шифра также могут быть другие особые требования к ключу. Затем хеш-значение сначала передается через функцию для преобразования / дополнения в качестве ключа для шифра.
В математических обозначениях Матяс – Мейер – Осеас можно описать как:
Схема имеет курс:
Вторая атака на прообраз (с сообщением злоумышленник находит другое сообщение удовлетворить можно сделать согласно Келси и Шнайеру [5] для-сообщение-блокировка сообщения вовремя . Обратите внимание, что сложность выше но ниже когда сообщения длинные, и когда сообщения становятся короче, сложность атаки приближается .
Миягути – Пренель
Функция одностороннего сжатия по длине одного блока Миягути – Пренеля является расширенным вариантом метода Матьяса – Мейера – Осиса. Его независимо предложили Сёдзи Миягути и Барт Пренил .
Он скармливает каждому блоку сообщения () как открытый текст, который нужно зашифровать. Затем выходной зашифрованный текст подвергается операции XOR (⊕) с тем же блоком сообщения (), а затем также XOR с предыдущим значением хеш-функции () для получения следующего хеш-значения (). Предыдущее значение хеш-функции () подается как ключ к блочному шифру. В первом раунде, когда нет предыдущего хеш-значения, он использует постоянное заранее заданное начальное значение ().
Если блочный шифр имеет разные размеры блока и ключа, значение хеш-функции () будет иметь неправильный размер для использования в качестве ключа. У шифра также могут быть другие особые требования к ключу. Затем хеш-значение сначала передается через функцию для преобразования / дополнения в качестве ключа для шифра.
В математических обозначениях Миягути – Пренеля можно описать как:
Схема имеет курс:
Роли а также можно переключить, так что зашифровано под ключом , что делает этот метод расширением метода Дэвиса-Мейера.
Вторая атака на прообраз (с сообщением злоумышленник находит другое сообщение удовлетворить можно сделать согласно Келси и Шнайеру [5] для-сообщение-блокировка сообщения вовремя . Обратите внимание, что сложность выше но ниже когда сообщения длинные, и когда сообщения становятся короче, сложность атаки приближается .
Хиросе
Функция одностороннего сжатия двойной длины по Хиросе [8] состоит из блочного шифра и перестановки. Он был предложен Шоичами Hirose в 2006 году и базируется на работе [11] по Mridul Нанди .
Он использует блочный шифр, длина ключа которого больше длины блока , и производит хэш размера . Например, любой из кандидатов AES со 192- или 256-битным ключом (и 128-битным блоком).
Каждый раунд принимает часть сообщения это бит, и использует его для обновления двух -битовые значения состояния а также .
Первый, соединяется с изготовить ключ . Затем два значения обратной связи обновляются в соответствии с:
- произвольная перестановка без неподвижных точек на -битовое значение, обычно определяемое как для произвольной ненулевой константы (все могут быть удобным выбором).
Каждое шифрование напоминает стандартную конструкцию Дэвиса – Мейера. Преимущество этой схемы перед другими предложенными схемами с двойной длиной блока состоит в том, что оба шифрования используют один и тот же ключ, и, таким образом, усилия по планированию ключей могут быть разделены.
Окончательный результат . Схема имеет ставку относительно шифрования сообщения шифром.
Хиросе также предоставляет доказательство в идеальной модели шифра.
Конструкция из губки
Конструкция из губки может использоваться для создания функций одностороннего сжатия.
Смотрите также
- Whirlpool - криптографическая хеш-функция, построенная с использованием конструкции Миягути – Пренеля и блочного шифра, подобного Square и AES .
- CBC-MAC , OMAC и PMAC - методы преобразования блочных шифров в коды аутентификации сообщений (MAC).
Рекомендации
Цитаты
- ^ Справочник по прикладной криптографии Альфреда Дж. Менезеса, Пола К. ван Оршота, Скотта А. Ванстона. Пятое издание (август 2001 г.), стр. 328.
- ^ "Объявление о первом столкновении SHA1" . Блог Google по онлайн-безопасности . Проверено 12 января 2020 .
- ^ Иван Дамгард. Принцип построения хеш-функций . Жиль Брассар, редактор CRYPTO, том 435 LNCS, страницы 416–427. Спрингер, 1989.
- ^ Ральф Меркл. Односторонние хэш-функции и DES . Жиль Брассар, редактор CRYPTO, том 435 LNCS, страницы 428–446. Спрингер, 1989.
- ^ а б в г Джон Келси и Брюс Шнайер. Второй прообразы на п битовых хэш - функций для гораздо меньше , чем 2 л работы . В Рональде Крамере, редакторе EUROCRYPT, том 3494 LNCS, страницы 474–490. Спрингер, 2005.
- ↑ Джон Блэк, Мартин Кокран и Томас Шримптон. О невозможности создания высокоэффективных хеш-функций на основе блочного шифрования. Достижения в криптологии - EUROCRYPT '05, Орхус, Дания, 2005. Авторы определяют хеш-функцию «высокоэффективной, если ее функция сжатия использует ровно один вызов блочного шифра с фиксированным ключом».
- ↑ Джон Блэк, Филип Рогэвей и Том Шримптон. Анализ методом черного ящика построений хеш-функций на основе блочного шифра из PGV. Достижения в криптологии - CRYPTO '02, Lecture Notes in Computer Science, vol. 2442, pp. 320–335, Springer, 2002. См. Таблицу на странице 3, Дэвис-Мейер, Матиас-Мейер-Осис и Миягути-Пренель пронумерованы в первом столбце как хэш-функции 5, 1 и 3.
- ^ a b С. Хиросе, Некоторые правдоподобные конструкции хеш-функций двойной длины . В: Робшоу, MJB (ред.) FSE 2006, LNCS, т. 4047, стр. 210–225, Springer, Heidelberg 2006.
- ^ Справочник по прикладной криптографии Альфреда Дж. Менезеса, Пола К. ван Оршота, Скотта А. Ванстона. Пятое издание (август 2001 г.), стр. 375.
- ^ Р. Винтерниц. Безопасная односторонняя хеш-функция, построенная на DES. В материалах симпозиума IEEE по информационной безопасности и конфиденциальности, стр. 88-90. IEEE Press, 1984.
- ^ М. Нанди, На пути к оптимальным хэш-функциям двойной длины , В: Труды 6-й Международной конференции по криптологии в Индии (INDOCRYPT 2005), Конспект лекций по информатике 3797, страницы 77–89, 2005.
Источники
- Менезеш; ван Оршот; Ванстон (2001). «Хеш-функции и целостность данных» (PDF) . Справочник по прикладной криптографии .