Почему Keccak настолько крут и почему его выбрали в качестве нового SHA-3

Привет, %username%!
Мне, как ни разу не профессиональному математику и криптографу, редко бывает сразу понятно как устроен тот или иной алгоритм. И тем более, почему его выбирают.
Так и с новым стандартом SHA-3. Выбрали какой-то Keccak, спасибо камраду NeverWalkAloner, привел его описание. Но лично мне так и не стало понятно как он работает и в чем его фишка. Давайте разбираться.

В конце статьи будет небольшой бонус параноикам в виде информации к размышлению о стойкости SHA-2


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

Случайный оракул — это абстрактный черный ящик, обладающий бесконечной памятью и работающий по следующему алгоритму:

• Получает на вход строку и смотрит, работал ли он с ней ранее.
• Если нет, то генерирует истинно случайное число и сохраняет в себе пару строка-число.
• Если да, то выдает ранее сохраненное число для этой строки.

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

Еще один бич всех хэш функций — это коллизии. Не те, что могут по определению быть, потому что у хэша размер фиксированный, а те которые случаются гораздо раньше, плохии коллизии (1 и 2 рода). У большинства современных реализаций хэшей используются различные т.н. функции сжатия, преобразующие блок текста размером, скажем, n, в блок размером, скажем, n/2. И пока что никто не доказал, что можно построить функцию сжатия, устойчивую к коллизиям.

И тут авторы Keccak пошли другим путем. Они решили использовать псевдослучайные перестановки, в которых коллизий не может быть по определению. Остановимся на этом моменте подробнее.

Вспомним как работает любой блочный шифр.

Он берет блок открытого текста фиксированной длины, ключ, и сопоставляет им шифротекст такой же длины. Это сопоставление однозначно, иначе мы бы не смогли расшифровать блок обратно. Таким образом, идеальный блочный шифр(скажем, с размером блока 128 бит) можно представить как нефиговых размеров таблицу, в первой строке которой будут все возможные ключи(2¹²⁸), в первой колонке — все возможные открытые тексты(тоже 2¹²⁸), а на пересечении строк и столбцов будут стоять истинно случайным образом сгенерированные шифроблоки, причем отношение открытый блок-ключ-зашифрованный блок будет однозначным.

В математике такое взаимно однозначное отношение называется биекцией.

Заметьте, что в любой строке и любой колонке можно встретить все возможные комбинации бит (длины 2¹²⁸ для нашего случая) в случайном порядке, причем каждая комбинация будет встречаться единожды. Это и есть перестановки. Ну а в реальной жизни используются псевдослучайные перестановки, описываемые алгоритмами. Потому что такую вот таблицу сгенерировать нереально.

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

А каким местом тут хэши и Keccak?

Авторы Keccak придумали простую (если разобраться) схему, т.н. Sponge функцию, или по-русски губку.
Внутри этой «губки» имеется состояние(размером в 1600 бит для SHA-3), к которому на каждом раунде применяется одна и та же функция, реализующая псевдо-случайную перестановку.

То есть, это по сути, блочный шифр без ключа с размером блока 1600 бит. И если мы заполним состояние нулями, выполним 10 раундов (10 раз применим их функцию f) в одну сторону, а потом столько же в обратную(с функцией, обратной f), то опять получим нули. Биекция во всей красе. Но это еще не всё.

Чтобы захэшировать строку, нужно сначала разбить её на куски определенного размера и на каждом раунде ксорить(подмешивать) их не ко всему 1600 битному состоянию, а только к его началу размера r. Тут уж я вставлю ту самую картинку, теперь она имеет смысл.


То есть, на каждом раунде очередной кусок строки подмешивается только к части состояния, тогда как псевдо-случайная перестановка f обрабатывает всё состояние целиком, размазывая таким образом строку по состоянию и делая его зависимым от всей строки.

Это так называемый этап «впитывания». И теперь понятно, почему он так называется. Надеюсь, вам тоже. Осталось чуть-чуть!

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

Из-за того, что мы используем не всё состояние, а лишь его часть, мы не можем ничего сказать о связи входных и выходных данных. И авторы Keccak доказали, что стойкость такой конструкции неотличима от случайного оракула с размером «ответа», равным с/2 (всё состояние имеет размер с+r) при условии, что f — идеальная функция перестановки(та табличка из идеального блочного шифра, только из двух столбцов, потому, что ключа нет). То есть, чтобы получить хэш с доказанной математически стойкостью в 512 бит, нужно сделать размер параметра с (независимой части состояния) 512*2=1024 бита. Таким образом, при состоянии размером 1600 бит для 512 битного хэша мы 1024 бита не трогаем, а к первым 576 подмешиваем часть хэшируемой строки на каждом раунде.

Не обошлось без ложки дёгтя:
функция f у авторов хорошо описана, она состоит из пяти довольно простых обратимых операций(даже анимашки есть), внешне хорошая и её пока не поломали, но нет гарантий, что её не поломают в будущем. Зато, если это произойдет, нужно будет заменить лишь f(например на нормальный блочный шифр вроде AES, только без ключа), а «губку» можно оставить, т.к. она (доказано) стойкая при стойкой f.

На этом у меня всё, надеюсь, получилось более-менее разложить всё по полочкам. Спасибо ребятам с pgpru за консультацию про биекции, а авторам keccak за код обратных функций, из которых состоит функция f(есть в пакете keccak-tools на их сайте).