K
Kelvin
Модератор
- Регистрация
- 12 Ноя 2018
- Сообщения
- 4,053
все хэши стремятся быть максимально похожими на так называемый «Случайный оракул». Поэтому, для начала немного про него.
Случайный оракул — это абстрактный черный ящик, обладающий бесконечной памятью и работающий по следующему алгоритму:
Похоже на хэш, да? Только с тем фундаментальным отличием, что связь между хешируемой строкой и результатом вычислить в принципе невозможно. Идем дальше.
Еще один бич всех хэш функций — это коллизии. Не те, что могут по определению быть, потому что у хэша размер фиксированный, а те которые случаются гораздо раньше, плохии коллизии (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 на их сайте).
источник:https://habr.com/post/168707/
Случайный оракул — это абстрактный черный ящик, обладающий бесконечной памятью и работающий по следующему алгоритму:
- Получает на вход строку и смотрит, работал ли он с ней ранее.
- Если нет, то генерирует истинно случайное число и сохраняет в себе пару строка-число.
- Если да, то выдает ранее сохраненное число для этой строки.
Похоже на хэш, да? Только с тем фундаментальным отличием, что связь между хешируемой строкой и результатом вычислить в принципе невозможно. Идем дальше.
Еще один бич всех хэш функций — это коллизии. Не те, что могут по определению быть, потому что у хэша размер фиксированный, а те которые случаются гораздо раньше, плохии коллизии (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 на их сайте).
источник:https://habr.com/post/168707/
