РегистрацияХэш-функция Keccak и конструкция Sponge как универсальный криптопримитив
Кризис в области криптографии, связанный со стойкостью хэш-функций, наиболее ярко проявившийся в середине 2000-х годов, вынудил американский институт стандартов и технологий (НИСТ) объявить конкурс на создание нового стандарта хэширования — SHS (Secure Hash Standart). Победитель конкурса алгоритмов хэширования получит имя хэш-функции SHA-3.
В ходе конкурса получили распространение, широкое обсуждение и значительное принятие различные идеи, связанные с дизайном как самих хэш-функций, так и симметричных криптопримитивов в целом.
Особенно интересным явлением стало то, что в финале конкурса из пяти финалистов, двое оказались универсальными криптопримитивами, которые могут использоваться не только для хэширования, но и для выполнения множества других криптографических операций. Это может привести на практике к значительному упрощению криптографических протоколов, как уже существующих, так и вновь проектируемых.
О другом универсальном криптопримитиве Skein было подробно написано ранее. Тем интереснее также подробно разобрать Keccak и сравнить его со Skein. Следует сразу отметить, что Keccak (в отличие от Skein) не содержит в своей основе блочный шифр и поэтому не является совсем универсальным. Однако, в других областях его гибкость и универсальность проявляются достаточно полно. В ряде случаев он может например использоваться в таких протоколах, в которых нужно использование блочного шифра в режиме счётчика.
Традиционный дизайн хэш-функций основан на использовании функции сжатия. Эта функция отображает значение m → n (m > n) псевдослучайным образом. При этом значение n должно быть до 512 бит, а m порядка 2n. Повторяя эту функцию в течении нескольких раундов с различными константами, достигают нужного значения стойкости. Дополняя и сцепляя между собой блоки от разных фрагментов исходного текста, получают возможность вычислить хэш от сообщения произвольной длины. При этом возникает существенная проблема: сконструировать функцию сжатия трудно. Многораундовые повторения сгладят её дефектность, но заведомое наличие быстрой возможности найти частичную коллизию в исходной функции сжатия ставит под вопрос стойкость всей конструкции. Авторы алгоритма Keccak (Guido Bertoni, Joan Daemen, Michaёl Peeters и Gilles Van Assche) утверждают, что сконструировать надёжную функцию сжатия вида m → n (m > n) как однораундовый блок криптопримитива, крайне сложно (или невозможно вообще).
Авторы алгоритма Skein (и Whirlpool, который не участвует в конкурсе, но вошёл в некоторые промежуточные стандарты) считают, что в качестве функции сжатия можно использовать блочный шифр. Действительно, в отличие от псевдослучайных функций (Pseudo Random Function — PRF), псевдослучайные перестановки (Pseudo Random Permutation — PRP), создавать проще. А блочный шифр является такой перестановкой, зависимой от ключа. Достаточно сконструировать шифр с размером блока и размером ключа 512 бит и можно будет получить функцию сжатия m → n (m > n), подавая на вход такого шифра эти значения. Проблема однако в том, что хотя блочные шифры и считаются самыми доверяемыми в плане стойкости симметричными криптопримитивами, они часто имеют облегчённое или слабое ключевое расписание (функцию разворачивания подключей раунда из основного ключа). Это приводит к атакам со связанными ключами, которые хотя и не представляют практической угрозы в большинстве протоколов, но ставят под удар функцию сжатия на основе блочного шифра. Более того — идеальное ключевое расписание для идеального блочного шифра само по себе должно обладать свойствами идеальной псевдослучайной функции. То есть для создания идеальной хэш-функции нужно использовать … идеальную хэш-функцию. Получается замкнутый круг, который лишь отчасти можно победить некоторыми конструкторскими уловками и некоторыми натяжками в доказательствах. Так, можно использовать фиксированный ключ, но изменяющийся твик-вектор или использовать лишь часть выхода шифра.
Авторы хэш-функции Keccak (произносится как "Ketchak") приняли ряд радикальных решений. Они решили не использовать функцию сжатия в виде отдельного строительного блока, а в качестве стойкого криптопреобразования решили сконструировать бесключевую PRP. Всё это упаковано в очень простую конструкцию Sponge ("Губка"). Авторами этой конструкции являются непосредственные создатели алгоритма Keccak, которые впервые представили её на симпозиуме ECRYPT Hash function – 2007 в качестве альтернативы традиционному дизайну Дамгарда-Меркла.
Атаки на нахождение коллизий (двух произвольных сообщений, дающих одинаковый хэш) и вторых прообразов (сообщения, дающего такой же хэш, что и имеющееся) имеют важное практическое и теоретическое значение, но наряду с неинвертируемостью не обеспечивают полной оценки стойкости хэш-функции. Существует целый ряд экзотических атак — на удлинение сообщения, атаки на частичные коллизии с подобранным префиксом и др. Чтобы доказать стойкость конструкции Sponge ко всем возможным атакам, авторы приняли ещё одно радикальное решение: считать единственным и достаточным общим критерием стойкости неразличимость хэш-функции от случайного оракула.
Случайный оракул (Random Oracle) — это идеализированная функция, описывающая работу машины с практически бесконечным объёмом памяти, которая на любой запрос может выдать идеально случайное число и запомнить пару "запрос-ответ". Если такой же запрос будет когда-либо повторён, то ответ будет не генерироваться заново, а взят из запомненного списка. Если перестановка f, лежащая в основе Sponge идеальна, то и хэш-функция доказуемо неразличима от RO, значит никакие из возможных атак действовать не будут. Конечно, есть оговорка на наличие универсального тривиального различителя для всех возможных хэш-функций: построение случайного оракула на алгоритме с конечным числом состояний невозможно. Например коллизия внутреннего состояния приведёт к неслучайному выходу, что было бы невозможно в RO, у которого никаких внутренних состояний нет. Однако, авторы доказывают, что такая конструкция обеспечивает стойкость для N запросов к функции f или f-1, равную N2 • 2-(c+1), что при обычной длине выхода укладывается в 2c/2 и невозможно без наличия различителя в используемой PRP.
Именно эти теоретические результаты, основанные на одном из самых строгих доказательств неразличимости от случайного оракула в конкурсе SHA-3, дают удивительные практические возможности для простого использования хэш-функции Keccak в качестве практически универсального криптопримитива.
Ещё одной интересной особенностью конструкции Sponge является лёгкость персонализации данных. Предположим, один и тот же пароль используется как для генерации симметричного ключа, так и для ключа MAC — для предотвращения изменения сообщения. Нежелательно, чтобы они были одинаковыми. Например, в хэш-функции Skein для этого предусмотрен ограниченный набор битов для переключения режимов использования. А в конструкции Sponge хэш-функции Keccak это не требуется. Любая персонализация данных может быть добавлена на вход функции, например, по рекомендации авторов, в XML-формате и кодировке UTF, что делает число возможных вариантов персонализации и режимов использования практически неограниченным.
 | Кроме конструкции Sponge, интересна также и сама функция перестановки хэш-функции Keccak. Текущее внутреннее состояние представлено в ней в виде набора битов, сгруппированных в виде виртуального объекта в трёхмерном пространстве (трёхмерного массива). Сам объект можно разбить на плоскости или точнее слои вдоль трёх осей координат, а элементы каждого слоя — на фрагменты в виде столбцов или векторов. При этом для обработки внутренних состояний не используются S-блоки или операции, параметры которых менялись бы в зависимости от данных. Для создания нелинейных преобразований используется набор простейших логических операций (XOR, AND, NOT), которые существуют в любом процессоре и минимальный набор констант. А трёхмерное представление текущего внутреннего состояния помогает применить эти операции оптимальным образом. Функции Chi, Theta, Pi, Rho и Iota последовательно обрабатывают внутреннее состояние на каждом раунде. На странице Олденбургского университета имени Карла фон Осиетски представлено описание этих функций на немецком языке и анимированные диаграммы состояний. Чтобы не разбирать подробно процесс их работы, можно посмотреть по приведённой ссылке анимированные изображения в gif-формате, которые позволяют понять работу алгоритма наглядным образом. |
Таким образом, хэш функция Keccak является почти таким же универсальным криптопримитивом, как и Skein, за исключением возможности использования в режиме блочного шифра. Режим блочного шифра остаётся незаменимым в прозрачном шифровании данных на дисках компьютеров, но в этой области нет существенного ограничения по ресурсам, поэтому для шифрования можно использовать отдельный блочный шифр в соответствующем режиме. Для решения же многих других задач Keccak также универсален, как и Skein, а фактически его область применения может быть шире. При необходимости этот алгоритм мог бы быть легко внедрён как в миниатюрные устройства с ограниченными ресурсами, так и на высокопроизводительные серверы, работающие с большим объёмом соединений. Оба алгоритма имеют самую сильную доказательную базу среди всех финалистов, но по некоторым оценкам, Keccak имеет более строгие доказательства в модели RO. В частности он неподвержен атакам на функции конструкции Narrow Pipe.
В случае принятия любого из этих достойных кандидатов (как Keccak, так и Skein) в качестве стандарта алгоритма хэширования, на практическое использование симметричных алгоритмов и смешанных протоколов, а также и на теоретические исследования в различных областях криптографии будет оказано заметное стимулирующее влияние.
См. также: Перспективные режимы Sponge-шифрования.
комментариев: 11558 документов: 1036 редакций: 4118
На официальном сайте читаем:
комментариев: 9796 документов: 488 редакций: 5664
Это обзорная статья-компиляция по разным публикациям разработчиков, а не перевод какого-то одного готового материала. Если вопрос в этом.
комментариев: 9796 документов: 488 редакций: 5664
Эти примеры ещё более обширные, а перспективы ещё более захватывающие, чем это виделось в 2011 году. Возможно кому-то будет интересно, как дополнение к данной статье.
[humor]
На 4-ой странице слайдов показан хэш, изображение которого может быть не одобрено наркоконтролем.
[/humor]
комментариев: 1515 документов: 44 редакций: 5786
Да, смутно припоминаю, что был анонос FOSDEM'а, но я решил не ходить, т.к. оно показалось собранием, ориентированном больше на тех, кто занимается исключительно программированием и СПО. Возможно, стоило сходить.
Я не очень понял мотив сравнений, приведённых на 22-ой стр. слайдов. На них можно было бы ограничиться общими словами «брутфорс по понятным причинам нефизичен». Вместо этого авторы расписали в красках, что значат числа типа 2128, подавая их так, как будто keccak сломать столь же невероятно, сколь перебрать все варианты из этих больших чисел.
комментариев: 9796 документов: 488 редакций: 5664
Там сказано перед этим, что можно разменивать ресурсоёмкость на стойкость в пределах 2128 … 2256. А дальше напоминание, скорее всего только для того, что не надо пытаться компенсировать стойкость завышением этих параметров. Если выяснится, что есть что-то серьёзное, кроме брутфорса, то надо объявлять SHA-4.
Не будут же они пытаться объяснять как у нас в схожем топике, почему алгоритмов с неоптимизированной избыточной защитой не создают, а сосредотачиваются вместо этого на теоретических исследованиях. Программерам лучше про нефизичность на примитивном уровне напомнить.
комментариев: 1515 документов: 44 редакций: 5786
Вот несмотря на объяснения в том топике, в голове связную картинку мне уложить трудно. :) Всё-таки одно дело — кратковременная секретность и практичность, на которые ориентирован НИСТ, и совсем другое дело — секретность долговременная. Возможно, это не совсем про то, но в общем виде я бы перечислил следующие причины для завышения длин ключей выше нефизичного порога:
RSA-1024 вряд ли будет скоро факторизован, но стандарты советуют выбирать хотя бы RSA-2048. Одна из причин — вера в закон Мура, другая — вера в появление КК (чем больше длина ключа, тем сложнее будет соорудить КК, его ломающий), третья — вера в то, что даже если появится алгоритм быстрой факторизации, его применение для ключей большой длины всё же останется для противника непрактичным или нефизичным. Т.е. мы делаем попытку покрыть себя защитой от тех атак, про которые мы пока ничего не знаем, но экстраполируем на них то, что знаем про другие атаки. Грубо говоря, нет проблем с вычислительной мощностью — делаем RSA-ключ 4096 и не думаем.
Конечно, если что-то стрясётся серьёзное, новый конкурс (SHA-4) будет жизненно необходим (весь мир не может играть в уловки). Тем не менее, каждый сам для себя может иметь некоторые мотивы (типа вышеперечисленных), чтобыТолько это будет не компенсацией теоретический стойкости, а компенсацией стойкости практической — я бы так охарактеризовал.
комментариев: 9796 документов: 488 редакций: 5664
Здесь основа хэша не шифр, а бесключевая перестановка. Функции сжатия нет, поэтому коллизий в самой перестановке нет по определению. Коллизии будут возникать, как и положено в любой стойкой хэш-функции, и совпадать с идеальной моделью (при условии идеальности этой перестановки — PRP), поскольку в фазе отжатия из перестановки отрезается кусок (так получается PRP → PRF). Но реальный (или самый фатальный по последствиям) способ найти коллизию, атакуя стойкость в губчатой конструкции — это получить цикл в перестановке.
Т.е. здесь всё зависит не от ключа, а от размера внутреннего состояния. Если использовать Keccak в режиме шифрования, а не хэширования, то делать ключ больше части внутреннего состояния (части блока перестановки) смысла нет — это не повысит стойкость. А внутреннее состояние трудно сделать нефиксированным кроме каких-то предопределённых значений или масштабируемым в слишком широких пределах.
Безопасно масштабируемые по всем параметрам и без существенного роста накладных расходов, но с ростом безопасности алгоритмы — дело будущего. Дойдут скорее всего и до такого, но не на тех конструкциях, что используются сейчас.
комментариев: 1515 документов: 44 редакций: 5786
комментариев: 9796 документов: 488 редакций: 5664
Кстати, универсальный Sponge-протокол для каналов связи уже разработан — Blinker. Работа,
слайды. Его удобно встроить прямо в железку.
Тот ужас, из которого сейчас состоят SSH, SSL, VPN, IPSec и пр. имеет всё больше оснований уйти в историю.
комментариев: 9796 документов: 488 редакций: 5664
Keccak — это уже вчерашний день. Авторы предлагают использовать Keyak. Или облегчённую версию — Ketje для миниатюрных устройств.
При этом на выбор предлагают River Keyak, Lake Keyak, Sea Keyak и Ocean Keyak. Авторы сделали ещё более удобным и гибким сочетание шифрования с аутентификацией и двигаются в сторону всё большей объект-ориентированности: когда разные объекты протокола (ключ, вектор инициализации, тэги, заголовки, коды аутентификации) подаются на вход и снимаются с выхода Keyak (в соответствии со своей принадлежностью) как объекты. Что позволяет широко использовать объектный подход для форматирования данных.
В конце июля конструкции из Keyak (параллельный дуплекс – помимо обычного и Sponge) внесли в код Keccak.