Схема построения криптографических хеш-функций Sponge
Схема построения криптографических хеш-функций Sponge
В 2007 году Bertoni G., Daemen J., Peeters M., Van Assche G. в работе [1] представили понятие “Sponge” хеш-функций (sponge hash functions) в качестве альтернативы схемы Merkle-Damgard. Конструкция “Sponge” хеш-функции начинается с «фазы впитывания», в которой сообщение сжимается итеративно, и заканчивается «фазой выжимания», в которой хеш-дайджест сообщения извлекается, возможно, итеративным образом. Идея дизайна “Sponge” состоит в том, чтобы получить безопасную криптографическую хеш-функцию путем итерации функции сжатия, которая не обязательно удовлетворяет основным свойствам безопасности хеш-функции.
Схема “Sponge” (“криптографическая губка”) [1], [2] - это простая итерационная схема для построения функции с входом переменной длины и выходом произвольной длины на основе функции f, являющейся преобразованием фиксированной длины или перестановкой, оперирующей с фиксированным числом b битов, составляющих так называемое внутреннее состояние S. b = r + с. Значение r называется битовой скоростью, а значение с — мощностью. Функцию f будем в дальнейшем называть внутренней функцией. Внутреннее состояние S сначала инициализируется некоторым фиксированным значением. Затем, после соответствующего дополнения и разделения сообщения на r-битные фрагменты, просто и итеративно обрабатываются все r-битные фрагменты сообщения, путем побитового сложения их r битам внутреннего состояния, а затем применяя b-битную функцию f. После того, как все блоки сообщений обрабатываются этим процессом «впитывания», последовательно выводятся r битов конечного хеш-значения путем извлечения r битов из внутреннего состояния и последующего применения к нему функции f (процесс «выжимания»). В работе [3] было показано, что когда внутренняя функция f моделируется как случайное преобразование или перестановка, “Sponge” функция индифферентна от случайного оракула с точность до 2c/2 вызовов f.
Cхема “Sponge” является перспективной и популярной конструкцией построения криптографических хеш-функций. С её помощью кроме хеш-функций можно создавать такие криптопримитивы, как блочные симметричные шифры, коды аутентификации сообщения и поточные шифры. Более того, по этой схеме был спроектирован алгоритм Keccak [4], ставший победителем конкурса SHA-3.
Согласно схеме “Sponge” для вычисления хеш-значения заданного сообщения выполняются следующие преобразования:
1. Дополнение (padding).
Это преобразование заключается в следующем. Входное сообщение дополняется некоторым количеством битов так, чтобы длина дополненного сообщения была кратна заданной длине блока сообщения. При чем, если длина входного сообщения изначально кратна длине блока, то либо дополнение выполняется, в результате увеличивая входное сообщение на дополнительный целый блок, либо может не осуществляться. Существуют алгоритмы, в которых дополнение не выполняется, и к последнему неполному блоку применяются отдельные преобразования, отличающиеся от преобразований, выполняемых над “полными” блоками.
2. Инициализация состояния.
Преобразование инициализации состояния состоит в следующем. В криптографическом алгоритме хеширования используется переменная S, битовая последовательность некоторой определенной длины. Переменная S называют состоянием (state). Начальное значение состояния S, т.е. все биты этой переменной, называют корневым состоянием (root state). Оно определяется алгоритмом и имеет фиксированное значение, и никогда не должно рассматриваться как входное. Это имеет решающее значение для безопасности схемы “Sponge”.
3. “Фаза впитывания” (absorbing phase).
Это преобразование можно описать следующим образом:
1) Выполняется побитово операция XOR между первыми r битами состояния S и первым блоком. И затем первые r бит состояния S заменяем на результат этой операции.
2) К состоянию S применяем внутреннюю функцию f.
3) Выполняется побитово операция XOR между первыми r битами состояния S и следующим блоком. И затем первые r бит состояния S заменяем на результат этой операции.
4) К состоянию S применяем функцию f.
5) Повторяются шаги 3 и 4 до тех пор, пока не будут обработаны таким образом все блоки сообщения.
4. “Фаза выжимания” (squeezing phase).
Это преобразование можно описать следующим образом:
1) Первые r бит состояния S возвращаются в качестве первого блока.
2) К состоянию S применяем функцию f.
3) Первые r бит состояния S возвращаются в качестве следующего блока.
4) Повторяются шаги 2 и 3 до тех пор, пока общая длина всех возвращенных блоков не будет больше или равна требуемой длине хэш-значения.
5) Полученный результат усекается до требуемой длины.
1. Bertoni, G.M. & Daemen, Joan & Peeters, Michael & Assche, Gilles. (2007). Sponge Functions. ECRYPT Hash Workshop 2007, https://keccak.team/files/SpongeFunctions.pdf
2. Bertoni G., Daemen J, Peeters M., Van Assche G. Cryptographic sponge functions. Version 0.1, January 14, 2011, https://keccak.team/files/CSF-0.1.pdf
3. Bertoni G., Daemen J., Peeters M., Van Assche G. On the Indifferentiability of the Sponge Construction // Advances in Cryptology - EUROCRYPT 2008, LNCScience, Springer. - 2008. - V.4965. - P.181-197, https://www.researchgate.net/publication/221348054_On_the_Indifferentiability_of_the_Sponge_Construction
4. Bertoni G., Daemen J, Peeters M., Van Assche G. The Keccak reference. SHA-3 competition (round 3), 2011, https://keccak.team/files/Keccak-reference-3.0.pdf