Хэш-функция 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-шифрования.
ппцкесссак одному из алгоритмов? А окончательно когда утвердят новый стандарт? Только через 2 года? Я что-т в море этой информации запутался, потому вопросы:- Когда будет известен победитель?
- Когда он станет новым AES?
Если пробел по времени между 2 и 1 большой (год и более), то что будет делать НИСТ, еслинеожиданныеВНЕЗАПНЫЕ события в криптоанализе покажут, что "финалист скорей дыряв чем хорош"?комментариев: 9796 документов: 488 редакций: 5664
Например, Rijndael был самым слабым по криптостойкости из пяти финалистов на AES, но победителем выбрали его. Посчитали, что различия в стойкости несущественны, а вот практичность на его стороне.
Летом 2012 года и полгода ещё будут формально утверждать стандарт.
Официально это никогда не планировалось. НИСТ заявил желательным иметь дополнительные свойства для хэшей, но не ставил целью разработку именно универсального криптопримитива для вытеснения других алгоритмов. Победитель станет SHA-3 и заменит SHA-2. Попытка заменить одним алгоритмом другие алгоритмы, не относящиеся к хэшам — на совести амбициозных разработчиков.
неожиданныеВНЕЗАПНЫЕ события в криптоанализе покажут, что "финалист скорей дыряв чем хорош"?НИСТ оставляет за собой право перенести сроки завершения конкурса в случае
ВНЕЗАПНЫХнепредвиденных ситуаций.комментариев: 9796 документов: 488 редакций: 5664
Ну это вы загнули!
И вы тоже :)
Хорошо, давайте сбоку подойдём. Полагаю, что форумчанам будет небезынтересно узнать сколько из участников этого НИСТ-конкурса говорят по-русски, и какие алгоритмы представляют. Есть ли такие, кстати? Наверняка кто-то из израильской школы, нет? Если да, было бы интересно взглянуть на фамилии.
комментариев: 9796 документов: 488 редакций: 5664
комментариев: 9796 документов: 488 редакций: 5664
комментариев: 9796 документов: 488 редакций: 5664
Продолжение обсуждения из /comment48059.
Что касается SHA-3, то совершенно случайно я недавно переписывался с командой разработчиков Keccak, правда ответил мне Guido Bertoni.
Дело вот в чём: кандидаты Skein и Keccak — универсальные криптопримитивы, но Skein содержит в основе ещё и блочный шифр Threefish, а Keccak — только бесключевую перестановку.
С точки зрения дизайна — это ИМХО плюс Keccak, но некоторый минус к будущей возможной практической универсальности за пределами требований SHA-3.
Я предложил им простейший способ переделки Keccak в блочный шифр (точнее режим использования Sponge-конструкции в режиме блочного шифра). Они ответили, что непосредственно Keccak не проектировался на эффективное исполнение инвертирующей перестановки, поэтому такой блочный шифр будет медленным.
Зато они отметили, что разработанные ими новые режимы поточного шифрования с аутентификацией (duplexing mode) сделают в большинстве применений блочные шифры ненужными.
Хотя сам Keccak, кажется, балансирует на грани небольшого запаса прочности (как в своё время AES), но теоретический вклад от разработки Sponge-подобных конструкций очень велик. Лично я хотел бы видеть его победителем конкурса.
В том же SSL, используя один криптопримитив, можно было бы убрать кашу из хэшей, MAC'ов, разных режимов шифров с ошибками при реализации дополнений блоков, поместив туда один Keccak в нужном режиме. Также можно забыть про все эти непонятно как сделанные /dev/urandom, потоковые режимы для мобильной связи — в самом Keccak всё это уже рассмотрено и доказано (с оговорками на полноту доказательств в криптографии).
Наконец, если даже сам Keccak окажется слаб, функцию бесключевой перестановки в нём можно будет и заменить, зато сама идея Sponge-функций будет актуальной со всеми наработками.
комментариев: 1515 документов: 44 редакций: 5786
Он первый соавтор по статьям. Обычно сортировка идёт либо по вкладу в работу, либо по алфавиту. Впрочем, алфавитный порядок там тоже соблюдён.
Так было же ранее утверждение, что с потоковыми шифрами (типа RC4) всё предельно плохо, трудно создать стойкий потоковый шифр и т.д.? Или я что-то путаю? И эти "режимы поточного шифрования" — какая-то отдельная работа, не имеющая никакого прямого отношения к самому Keccak?
"Один Keccak" — это что из
- Keccak как хэш SHA-3
- Keccak как хэш SHA-3 + "способ переделки Keccak в блочный шифр"
- Keccak как хэш SHA-3 + "разработанные ими новые режимы поточного шифрования с аутентификацией"
А то я что-то запутался.В целом ясно. Т.е. Keccak хорош именно своими концептуальными теоретическими наработками, которые будут полезны криптографии в любом случае (независимо от того выберут ли его победителем).
комментариев: 9796 документов: 488 редакций: 5664
А с Keccak всё будет якобы предельно хорошо. По крайней мере, это достаточно хорошо обосновано.
Основанная именно на самом Keccak. Или на всех его возможных Sponge-аналогах.
“1.” Было бы неинтеренсно. Про “2” пока забудьте (это была моя личная фантазия, которую не одобрили разработчики), а вот “3” – самое оно.
Блочный шифр – это псевдослучайная перестановка, управляемая ключом. И на каждом раунде у него производится такая же операция, только с подключом, выведенным из основного ключа. На вход подают открытый текст, с выхода снимают шифртекст. При расшифровке в обычных режимах – тоже самое в обратном порядке.
Потоковый шифр берёт на вход только ключ и продуцирует бесконечно (ну или там два в такой-то степени) большой поток псевдослучайных бит – гамму, которую достаточно поксорить с открытым текстом. На вход самого шифра открытый текст не поступает. Атаки с подобранными текстами отпадают. Зато можно пытаться восстановить внутреннее состояние шифра по гамме.
Проблема с традиционными потоковыми шифрами (и кстати хэшами) в том, что там пытались использовать небиективные преобразования. А Keccak (Sponge) основан на перестановке, которая является внутренним состоянием и из которой отрезают нужную часть после определённого числа раундов для получения выхода гаммы. Т.е. cтойкость по идее такая же, как и у блочных шифров, плюс фантастические возможности для универсализации (многие из которых возможно даже ещё не рассмотрены) при простоте реализации и доказательства стойкости.
Другая проблема традиционных потоковых шифров (да и для блочных это отчасти актуально) – необходимость аутентификации. В потоковом шифре инвертирование бита шифртекста тривиально инвертирует бит открытого текста (там ведь всего лишь ксорят гамму). Значит, необходимо запустить параллельно два процесса: генерацию гаммы с ксором (шифрование или расшифрование) и подсчёт аутентификационного MAC-значения. Мало того, что это разные алгоритмы, они требуют ещё и разных ключей. Или потребуется третий алгоритм для разворачивания двух ключей из одного.
В Keccak-Sponge duplexing-mode используется потоковое шифрование с вычислением аутентификации за один проход и из одного ключа, причём со всякими дополнительными возможностями.
В своё время у команды Шнайера не получилось создать такой шифр (он оказался нестойким, хотя и не в совсем реалистичных сценариях атак).
Если бы Keccak-duplexing mode встроить в OpenSSL, то его было бы легко использовать в шифровании ячеек цепочек Tor, где для этого используется AES-counter в потокового режиме (счётчик) + MAC и также Keccak мог бы стать заменой во многих других шифрованных сетевых протоколах.
Единственное для чего я наивно пытался предложить исследователям попробовать сделать на основе Keccak ещё и блочный шифр – это охватить сферу дискового шифрования. Но думаю, что если Keccak победит, то там есть различные варианты проработки и этого вопроса.
А во время конкурса у них дел и так хватает по основному вопросу — хэшированию.
Ну и да, я пожелал именно им победы в конкурсе!
комментариев: 1515 документов: 44 редакций: 5786
А что можно сказать что скорость Keccak в таких режимах применения по сравнению с другими хэшами/блочными шифрами? Может ли он занять ту нишу, в которой традиционно жил RC4? Насколько он требователен к ресурсам? И будет ли он быстрее AES?
комментариев: 9796 документов: 488 редакций: 5664
Вот многочисленные и регулярно обновляемые тесты: http://bench.cr.yp.to/results-sha3.html
А здесь есть AES в потоковом режиме (aRC4 уже нигде в актуальном тестировании нет).
Что можно сказать? Keccak-512 уже медленнее SHA-512 и по скорости сравним с AES-128-stream и обгоняет на некоторых платформах почти в два раза AES-256-stream (с которым его корректнее сравнивать по запасу прочности). Но это всё-таки сравнение хэширования в SHA-3 и шифрования потоковых шифров, что не совсем корректно.
Среди финалистов SHA-3 по скорости Keccak — середнячок, даже ближе к медленным. А вот Skein заметно обгоняет всех по быстродействию. Skein-1024 почти в два раза быстрее Keccak-1024 на многих платформах. Также, оба алгоритма используют стандартные инструкции процессоров, так что особой потребности в криптоускорителях не будет и будет возможность компактного исполнения.
Но вот про сравнение Skein и Keccak именно в режиме шифрования, конкретных данных нет. Кроме давнего упоминания Шнайера о том, что Threefish-Skein в два раза быстрее AES.
Вообще, не очень честно по сравнению к остальным кандидатам — конкурс подразумевал создание только хэшей, а некоторые разработчики продвинули универсальные криптоалгоритмы, чем потенциально ставят НИСТ в сложное положение.