Системный архитектор, криптоманьяк
32,9
рейтинг
8 февраля 2013 в 09:57

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


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

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


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

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


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

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

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

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

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

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

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

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

А каким местом тут хэши и 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 на их сайте).

Бонус
Когда ковырял потоковый HC-128 заметил 2 интересных функции, которые перексоривали одно и тоже число, 2 раза крутанув его на разное кол-во бит + еще один ксор с им же, сдвинутым вправо. 3 разных константы (6 для обоих функций)
На java выглядит примерно так

int func(int x, int a, int b, int c)
{
return (ror(x, a) ^ ror(x, b) ^ (x >>> c));
}


Потом выяснилось, что это 2 функции sigma1 и sigma2 из SHA-2.

И я чего то заморочился, потому что выглядят они красиво, а как работают – хз.

Оригинальные a,b, с из SHA-2 и HC-128
{7, 18, 3} и {17, 19, 10}

Я решил посчитать хитрый период, взяв бесконечный цикл f(f(f(f...(1)))) и ища повтор. Оказалось, что у функции с оригинальными константами такой «период» был равен 49146, а мне удалось найти кучу пар, у которых «период» был 131070. И, как и у оригинальных констант, множества, которые генерировались при таком цикле, не пересекались. Например

{22, 13, 3} и {18, 4, 9},
{24, 15, 2} и {18, 3, 4}

Так вот, функция func, если посчитать период нормально, пробегая от 0 до 232-1 имеет период 232, то есть опять же, биективна.

Далее цитата из топика с pgpru:
Вот даже известные криптографы пытались исследовать этот АНБ-шный трюк, но к какому-то определённому мнению вроде не пришли.

The σ0 and σ1 GF(2)- linear mappings are one to one (in order to check this property, we computed the 32x32 GF(2) matrices representing σ0 and σ1, and checked that the kernel of this matrix was restricted to the null vector).


«Evaluation Report Security Level of Cryptography – SHA-256» © Dr. Helena Handschuh, Dr. Henri Gilbert

σ0 and σ1 have both the property to increase the Ham­ming weight of low-weight inputs. This increase is upper bounded by a factor of 3. The average increase of Hamming weight for low-weight inputs is even higher if three rotations are used instead of two rotations and one bit-shift. However, a reason for this bit-shift is given by the next observation. In contrast to all other members of the MD4-family including SHA-1, rotating expanded message words to get new expanded message words is not possible anymore (even in the XOR-linearized case). This is due to the bitshift being used in σ0 and σ1.


«Preliminary Analysis of the SHA-256 Message Expansion» © Norbert Pramstaller, Christian Rechberger, Vincent Rijmen

We show that the disturbance-correction strategy is applicable to the SHA-256 architecture and we prove that functions Σ, σ are vital for the security of SHA-256 by showing that for a variant without them it is possible to find collisions with complexity 264 hash operations


The S-boxes σ0 and σ1 play a similar role: they provide nonlinearity and better diffusion for the message expansion.


«Analysis of simplified variants of SHA-256» © Krystian Matusiewicz, Josef Pieprzyk, Norbert Pramstaller, Christian Rechberger, Vincent Rijmen.

В общем, это линейные или слабонелинейные S-блоки размером 32x32, описанные простой комбинацией операций. Как их точно подбирали — непонятно.


Вот такие пироги. Напихали каких то констант, протолкнули свой алгоритм как стандарт и ничего никому не объяснили. И чем черт не шутит, может тот псевдопериод, который я нашел, позволяет дядькам из АНБ подделывать хэши как два пальца. А может и не позволяет.
@Scratch
карма
101,7
рейтинг 32,9
Системный архитектор, криптоманьяк
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (19)

  • +4
    У случайной перестановки размера n средний размер цикла имеет порядок корня из n. Поэтому нет ничего плохого в периоде 49146 у перестановки размера 232.
    • +2
      Ну и хорошего нет ) Ведь можно было сделать лучше, а не сделали. Правда это просто паранойя, не стоит воспринимать её в серьёз.
  • +2
    Дополнение. Для понимания математического доказательства о неотличимости конкструкции sponge от случайного оракула имеет смысл послушать лекции class.coursera.org/crypto/lecture/. На русском аналогичные материалы в свободном доступе найти сложно, наши учебники содержат несколько иную тематику.
    • 0
      А разве в этом курсе про случайный оракул упоминается? Я что то пропустил такое.
      • +1
        И про доказательство криптостойкости губки — тоже, что-то не помню. Сам этот же курс сейчас, первую часть, прохожу.

        А оракл — да, не используется эта терминология совсем. Dan использует другие способы определения, PRF, PRP, итп ;)
        • 0
          Тут сам объект оракула не имеет значения, имхо. Тем более что он уж сильно абстрактен. Гораздо более важно понятие «неотличимости». Криптостойкость губки рассматривается как раз-таки в статьях товарщей, разрабатывавших Keccak (ну и другие исследователи в дальнейшем похожие конструкции рассматривали).
  • +2
    Идея конечно чертовски красивая. Коллизии в функции сжатия говорите, да кому они вообще нужны эти функции сжатия!
    Ну и стоит отдать дань уважения модели случайного оракула без нее ничего бы этого не было. Точнее было бы конечно, но без особых причин отказываться от SHA2 в пользу SHA3. Ну только если вас смущают всякие левые S-блоки 32*32 :)
    • +2
      Модель типа оракула сама напрашивается когда начинаешь задумываться как может выглядеть идеальный хэш. Ну во всяком случае, так кажется, когда о ней узнаешь )
      • 0
        В принципе да, но насколько все-таки мощный инструмент. Универсальный практически для любой области криптографии.
        Это явно большой шаг для криптографии, как самостоятельной науки.
        Но с другой стороны мне тоже, как ни разу не криптографу, очень сложно принимать доказательства вида, «этот протокол безопасен, пока хэш-функция неотличима от RO». И то что благодаря Keccak, у этой формулировки появилось продолжение «а эта хэш-функция неотличима от RO, т.к....» это конечно вселяет оптимизм.
  • 0
    Только одно но: шех в принципе не может не давать коллизий, т.к. размер простанство возможных сообщений — на много-много-много порядков больше размера пространства возможных хешей. (Ну и про birthday paradox забывать не стоит).

    Стоит говорить пожалуй о том, что максимально минимизирована «алгоритмическая часть», которая могла бы увеличить шансы на коллизию.
    • 0
      Я указал это (читайте с «Еще один бич всех хэш функций — это коллизии»). Ну и про минимизацию да, теперь не надо париться и свои схемы придумывать. Только PRP
  • 0
    Насколько я понял, случайный оракул для практического применения не годится. Дело не в том, что на практике даже самый чёрный ящик можно вскрыть и заглянуть в его память. Предположим, что у Алисы есть случайный оракул, а у Боба другой случайный оракул. До 1 ноября оба оракула ни разу не получали на вход строку «Хабрахабр». А 1 ноября и Боб, и Алиса скормили эту строку своим оракулам. Где гарантия, что на выходе Алиса и Боб получат одно и то же? Получается, что для того, чтобы стать похожими на реальные хэш-функции, все случайные оракулы во Вселенной должны иметь связь с каким-то единым высшим разумом. Или я что-то неправильно понял?
    • +3
      Вы путаете тепл^H^H^H^H абстрактную модель и реальную реализацию, а заодно и уровни где они применяются. У Боба и Алисы нет случайных оракулов, у них есть только хеш-функция. И базовое требование к любой хеш-функции — это чтобы она при одних и тех же входных данных выдавала одни и те же выходные (иначе это не хеш-функция).

      А к идеальной хеш-функции предъявляется еще одно требование — чтобы для тех входных данных, которые внешний наблюдатель еще не видел проходящими через хеш-функцию, никак нельзя было предугадать результат хеш-функции. Такой способностью обладает абстрактная модель «случайный оракул». Случайный оракул в свою очередь представляется абстрактной моделью «черный ящик». Абстрактный черный ящик нельзя «вскрыть» по определению (иначе это не черный ящик). Это как бесконечность — сколько на пальцах не считай, до нее не досчитаешь, а она все равно существует.

      Ну и наконец, идеальных хеш-функций нет, но чем ближе конкретная реальная функция подбирается к абстрактному идеалу — тем лучше.
      • 0
        Спасибо.
      • 0
        > иначе это не хеш-функция
        иначе это не функция
        просто не функция
  • 0
    И пока что никто не доказал, что можно построить функцию сжатия, устойчивую к коллизиям.

    еще бы: отразить счетное множество в конечное без коллизий.

    псевдослучайные перестановки, в которых коллизий не может быть по определению

    ого.

    будут стоять истинно случайным образом

    вы употребляете выражение «истинная случайность» так, будто это не абстракция
    • 0
      а вы имеете какое то отношение к enrupt?
      • 0
        у меня такой же ник
        • 0
          я заметил, спасибо

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.