Мне, как ни разу не профессиональному математику и криптографу, редко бывает сразу понятно как устроен тот или иной алгоритм. И тем более, почему его выбирают.
Так и с новым стандартом SHA-3. Выбрали какой-то Keccak, спасибо камраду NeverWalkAloner, привел его описание. Но лично мне так и не стало понятно как он работает и в чем его фишка. Давайте разбираться.
В конце статьи будет небольшой бонус параноикам в виде информации к размышлению о стойкости SHA-2
Для начала, скажу, что все хэши стремятся быть максимально похожими на так называемый «Случайный оракул». Поэтому, для начала немного про него.
Случайный оракул — это абстрактный черный ящик, обладающий бесконечной памятью и работающий по следующему алгоритму:
- Получает на вход строку и смотрит, работал ли он с ней ранее.
- Если нет, то генерирует истинно случайное число (м.б. фиксированной длины, а может и вообще любое в диапазоне 0 -бесконечность, тут формулировки разнятся) и сохраняет в себе пару строка-число.
- Если да, то выдает ранее сохраненное число для этой строки.
Похоже на хэш, да? Только с тем фундаментальным отличием, что связь между хешируемой строкой и результатом вычислить в принципе невозможно. Идем дальше.
Еще один бич всех хэш функций — это коллизии. Не те, что могут по определению быть, потому что у хэша размер фиксированный, а те которые случаются гораздо раньше, плохии коллизии (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 на их сайте).
На 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 32×32 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 Hamming 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-блоки размером 32×32, описанные простой комбинацией операций. Как их точно подбирали — непонятно.
Вот такие пироги. Напихали каких то констант, протолкнули свой алгоритм как стандарт и ничего никому не объяснили. И чем черт не шутит, может тот псевдопериод, который я нашел, позволяет дядькам из АНБ подделывать хэши как два пальца. А может и не позволяет.
ссылка на оригинал статьи http://habrahabr.ru/post/168707/
Добавить комментарий