Panama (хеш-функция)
Panama[1] — криптографический примитив, который может быть использован либо в виде криптографической хеш-функции, либо как потоковый шифр. Был разработан в 1998 году Йоаном Дайменом и Крейгом Клепом для повышения эффективности в программном обеспечении для 32-битных архитектур. Является одним из прародителей алгоритма хеширования «Keccak», ставшим победителем конкурса криптографических примитивов от Национального института стандартов и технологий США[2]. Во многом основывается на StepRightUp потоковом хеш-модуле.[3]
Особенности
По утверждениям разработчиков, «Panama» на момент разработки имела высокий уровень безопасности, однако это достигалось ценой огромной вычислительной нагрузки. Поэтому, как выяснилось, «Panama» как хеш-функция оказалась менее подходящей для хеширования сообщений, нежели её соперники. Если говорить о «Panama» как о потоковом шифре, то отличительной особенностью его применения оказалось долгая процедура инициализации. Поэтому, применяя его в задачах, требующих высоких скоростей, необходимо предоставить все условия, которые будут направлены на уменьшение количества разсинхронизаций.[4]
Предполагалось, что «Panama» будет применяться в шифровании или дешифровании видео для доступа к некоторым приложениям, в частности, «pay-TV».[5] Логика разработчиков заключалась в том, что приставки и цифровые телевизоры будут применять высокоскоростные процессоры, и «Panama» при дешифровании не будет слишком сильно загружать эти процессоры.
Структура
«Panama» основана на машине с конечными состояниями, состоящей из двух больших блоков: 544 бита состояний и 8192-битовый буфер, работающий по принципу регистра сдвига с обратной связью. Обратная связь обеспечивает то, что входные биты после входа проходят через несколько итераций, что, в свою очередь, обеспечивает побитовую диффузию. Надо сказать, что подобный буфер применяется в функции сжатия SHA.[6] Объектом работы «Panama» является 32-битовое слово и состояние состоит из 17 таких слов, в то время как буфер имеет 32 ячейки, в каждой из которых лежит по 8 таких слов.[7]
Операции
«Panama» может обновлять буфер и состояния, выполняя итерации. И для итерационной функции реализовано три режима: «Reset», «Push» и «Pull». В режиме «Push» машина получает некоторые входные данные, но ничего не выдает на выход. В режиме «Pull», наоборот, формируются выходные данные, но ничего не принимается на вход. Также «пустая Pull-итерация» означает, что выходные данные при этой итерации удаляются. При режиме «Reset» состояние и буфер сбрасываются в ноль.[8]
Изменение состояния характеризуется высокой диффузией и распределенной нелинейностью.[9] Это означает, что для того, чтобы достичь хорошего рассеивания, достаточно небольшого числа итераций. Это осуществляется при помощи 4 блоков, каждый из которых решает свою собственную задачу.
- Первый решает задачу нелинейности.
- Второй обеспечивает побитовую дисперсию.
- Третий создает побитовую диффузию.
- Четвёртый вводит буфер и входные данные.[10]
Если рассмотреть «Panama» как хеш-функцию, то алгоритм её работы следующий. Изначально хеш-функция принимает все блоки сообщений. После этого проводится ещё несколько «Push»-итераций, что позволяет последним принятым блокам сообщений быть рассеяными внутри буфера и состояния. После этого производится последняя «Pull»-итерация, что позволяет получить итог хеширования. Схема потокового шифрования инициализируется следующим образом: cначала проходит две «Push»-итерации для получения ключа и параметра диверсификации. После этого происходит некоторое количество «Pull»-итераций для того, чтобы рассеять ключ и параметр внутри буфера и состояний. На этом инициализация заканчивается и «Panama» готова к созданию битов выходной последовательности, выполняя «Pull»-итерации.[3]
Принцип работы
Можно обозначить состояние как [math]\displaystyle{ A }[/math], а 17 слов, которые определяют состояния, обозначить как [math]\displaystyle{ a0...a16 }[/math]. Буфер обозначается как [math]\displaystyle{ B }[/math], [math]\displaystyle{ j }[/math]-я его ячейка — как [math]\displaystyle{ b^j }[/math], а одно из слов, лежащих внутри этой ячейки, — как [math]\displaystyle{ b^j_i }[/math]. Изначально и состояние, и буфер заполнены только нулями. При режиме «Push» «Panama» получает на вход некоторое 8-битовое слово, в режиме «Pull» на выход формируется 8-битовое слово.[7]
Если обозначить функцию, которая обновляет буфер, как [math]\displaystyle{ \lambda }[/math], то, если принять, что [math]\displaystyle{ d=\lambda(b) }[/math], можно получить следующие правила обновления буфера:
- [math]\displaystyle{ d^j = b^{j-1} }[/math] при [math]\displaystyle{ j \notin {0...25} }[/math],
- [math]\displaystyle{ d^0 = b^{31} \oplus q }[/math],
- [math]\displaystyle{ d^{25}_i = b^{24}_i \oplus b^{31} _ {i+2 mod 8} }[/math] для [math]\displaystyle{ 0\lt i\lt 8 }[/math]
где в режиме «Push» [math]\displaystyle{ q }[/math] есть входной блок [math]\displaystyle{ p }[/math], а в «Pull» — это часть состояния [math]\displaystyle{ A }[/math], т. е. 8 его компонент, определяемые как
- [math]\displaystyle{ q_i = a_{i+1} }[/math] для [math]\displaystyle{ 0\lt i\lt 8 }[/math]
Обновление состояния происходит по следующему правилу [math]\displaystyle{ \rho }[/math], которое является суперпозицией 4 различных преобразований:
- [math]\displaystyle{ \rho = {\sigma} + \theta + \pi + \gamma }[/math]
где [math]\displaystyle{ \theta }[/math] — это обратное линейное преобразование, [math]\displaystyle{ \gamma }[/math] — это, опять же, обратное линейное преобразование, [math]\displaystyle{ \pi }[/math] — это комбинация циклического сдвига битов слова и перемешивания позиций слов и преобразование [math]\displaystyle{ \sigma }[/math] — это поразрядное сложение буфера и входного слова.
В данном случае [math]\displaystyle{ + }[/math] будет определять сумму операций, где сначала выполняется та, что стоит правее.
Теперь можно рассмотреть каждую из этих операций. [math]\displaystyle{ \theta }[/math] определяется следующим образом:
- [math]\displaystyle{ c=\theta(a) \Leftrightarrow c_i = a_i \oplus a_{i+1} \oplus a_{i+4} }[/math] для [math]\displaystyle{ i\in {0...17} }[/math],
где все индексы берутся по модулю [math]\displaystyle{ 17 }[/math]. Заметим, что обратимость данного преобразования следует из того факта, что [math]\displaystyle{ 1 \oplus x \oplus x^4 }[/math] является взаимно простым с [math]\displaystyle{ 1 \oplus x^{17} }[/math].
[math]\displaystyle{ \gamma }[/math] можно определить как:
- [math]\displaystyle{ c=\gamma(a) \Leftrightarrow c_i = a_i \oplus (a_{i+1} OR \neg a_{i+2}) }[/math] для [math]\displaystyle{ i\in {0...17} }[/math],
где все индексы берутся по модулю [math]\displaystyle{ 17 }[/math].
Если для преобразования [math]\displaystyle{ \pi }[/math] определить, что [math]\displaystyle{ t_k }[/math] есть смещение на [math]\displaystyle{ k }[/math] позиций от младшего бита к старшему, то:
- [math]\displaystyle{ c=\pi(a) \Leftrightarrow c_i=t_k(a_j) }[/math],
причем [math]\displaystyle{ j=7i{ } \pmod {17} }[/math], а [math]\displaystyle{ k=i(i+1)/2 \pmod {32} }[/math]
Если для преобразования [math]\displaystyle{ \sigma }[/math] будет выполняться, что [math]\displaystyle{ c=\sigma(a) }[/math], то
- [math]\displaystyle{ c_0=a_0 \oplus 00000001_{hex} }[/math],
- [math]\displaystyle{ c_{i+1}=a_{i+1} \oplus l_i }[/math] для [math]\displaystyle{ 0 \leqslant i\lt 8 }[/math],
- [math]\displaystyle{ c_{i+9}=a_{i+9} \oplus b^{16}_i }[/math] для [math]\displaystyle{ 0 \leqslant i\lt 8 }[/math]
В режиме «Push» [math]\displaystyle{ l }[/math] является входным сообщением [math]\displaystyle{ p }[/math], а в «Pull» режиме — [math]\displaystyle{ l=b^4 }[/math].
Выходное слово [math]\displaystyle{ z }[/math] в «Pull» режиме определяется следующим образом:
- [math]\displaystyle{ z_i=a_{i+9} }[/math] [math]\displaystyle{ 0 \leqslant i\lt 8 }[/math].[11]
«Panama» как хеш-функция
«Panama» как хеш-функция сопоставляет сообщению произвольной длины [math]\displaystyle{ M }[/math] хеш-результат в 256 бит.[11] При этом хеширование происходит в 2 этапа
- [math]\displaystyle{ M }[/math] преобразуется в строку [math]\displaystyle{ M' }[/math] с длиной, которая кратна 256, путем добавления единиц.
- Соответствующая строка [math]\displaystyle{ M' }[/math] загружается в «Panama».
Можно обозначить [math]\displaystyle{ M' }[/math] как последовательность из числа [math]\displaystyle{ V }[/math] входных блоков [math]\displaystyle{ p }[/math]. Тогда в нулевой момент времени генерируется режим Reset, затем в течение [math]\displaystyle{ V }[/math] тактов загружаются входные блоки. После этого производится 32 пустых «Pull»-итераций. И затем на 33-ю «Pull»-итерацию возвращается результат хеширования [math]\displaystyle{ h }[/math].
Основной задачей разработки хеш-функции «Panama» было нахождение «герметичной» хеш-функции[11], то есть такой функции, для которой (если результат хеширования состоит из [math]\displaystyle{ n }[/math] бит):
- для задачи поиска коллизии ожидаемая сложность равна [math]\displaystyle{ 2^{n/2} }[/math]
- для задачи вычисления образа ожидаемая сложность равна [math]\displaystyle{ 2^n }[/math]
- для задачи вычисления второго образа ожидаемая сложность равна [math]\displaystyle{ 2^n }[/math]
Кроме того, невозможно выявить систематические корреляции между любой линейной комбинацией входных битов и любой линейной комбинацией битов результата хеширования.[11]
Поиск коллизий
Данная хеш-функция подвергалась успешным атакам дважды. Уже в 2001 году было показано, что данная хеш-функция не является криптостойкой, так как были найдены коллизии за [math]\displaystyle{ 2^{82} }[/math] операций. Более того, Йоан Даймен показал, что можно найти коллизии уже за [math]\displaystyle{ 2^6 }[/math] операций, а для удовлетворения параметрам надежности необходимо, чтобы коллизии находились хотя бы за [math]\displaystyle{ 2^{128} }[/math] операций.[12]
Примечания
- ↑ «Fast Hashing and Stream Encryption with Panama» Joan Daemen, Craig Clapp
- ↑ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition . Дата обращения: 5 ноября 2016. Архивировано 5 октября 2012 года.
- ↑ 3,0 3,1 J. Daemen, «Cipher and hash function design strategies based on linear and differential cryptanalysis»
- ↑ Fast Hashing and Stream Encryption with Panama" Joan Daemen, Craig Clapp
- ↑ Архивированная копия (недоступная ссылка). Дата обращения: 16 декабря 2016. Архивировано 15 августа 2011 года.
- ↑ SHA1 version 1.0 . Дата обращения: 16 декабря 2016. Архивировано 14 мая 2017 года.
- ↑ 7,0 7,1 Panama . Дата обращения: 4 ноября 2016. Архивировано 26 декабря 2016 года.
- ↑ The Panama Cryptographic Function | Dr Dobb’s (недоступная ссылка). Дата обращения: 4 ноября 2016. Архивировано 23 февраля 2016 года.
- ↑ * «Fast Hashing and Stream Encryption with Panama» Joan Daemen, Craig Clapp
- ↑ Шифр PANAMA | Блог о шифровании . Дата обращения: 5 ноября 2016. Архивировано 5 ноября 2016 года.
- ↑ 11,0 11,1 11,2 11,3 «Fast Hashing and Stream Encryption with Panama» Joan Daemen, Craig Clapp
- ↑ Producing Collisions for Panama, Instantaneously . Дата обращения: 13 ноября 2016. Архивировано 10 октября 2019 года.
Литература
- «Fast Hashing and Stream Encryption with Panama» Joan Daemen, Craig Clapp
- A. Bosselaers, R. Govaerts, J. Vandewalle, «Fast Hashing on the Pentium»
- J. Daemen, «Cipher and hash function design strategies based on linear and differential cryptanalysis»
- C.S.K. Clapp «Optimizing a fast stream cipher for VLIW, SIMD, and superscalar processors»
- Acoсков А. В., Иванов М. A., Мирский А. A., Рузин А. В., Сланин А. В., Тютвин А. Н. «Поточные шифры».