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]

Принцип работы

Можно обозначить состояние как ${\displaystyle A}$, а 17 слов, которые определяют состояния, обозначить как ${\displaystyle a0...a16}$. Буфер обозначается как ${\displaystyle B}$, ${\displaystyle j}$-я его ячейка — как ${\displaystyle b^{j}}$, а одно из слов, лежащих внутри этой ячейки, — как ${\displaystyle b_{i}^{j}}$. Изначально и состояние, и буфер заполнены только нулями. При режиме «Push» «Panama» получает на вход некоторое 8-битовое слово, в режиме «Pull» на выход формируется 8-битовое слово.^[7]

Если обозначить функцию, которая обновляет буфер, как ${\displaystyle \lambda }$, то, если принять, что ${\displaystyle d=\lambda (b)}$, можно получить следующие правила обновления буфера:

${\displaystyle d^{j}=b^{j-1}}$ при ${\displaystyle j\notin {0...25}}$,

${\displaystyle d^{0}=b^{31}\oplus q}$,

${\displaystyle d_{i}^{25}=b_{i}^{24}\oplus b_{i+2mod8}^{31}}$ для ${\displaystyle 0<i<8}$

где в режиме «Push» ${\displaystyle q}$ есть входной блок ${\displaystyle p}$, а в «Pull» — это часть состояния ${\displaystyle A}$, т. е. 8 его компонент, определяемые как

${\displaystyle q_{i}=a_{i+1}}$ для ${\displaystyle 0<i<8}$

Обновление состояния происходит по следующему правилу ${\displaystyle \rho }$, которое является суперпозицией 4 различных преобразований:

${\displaystyle \rho ={\sigma }+\theta +\pi +\gamma }$

где ${\displaystyle \theta }$ — это обратное линейное преобразование, ${\displaystyle \gamma }$ — это, опять же, обратное линейное преобразование, ${\displaystyle \pi }$ — это комбинация циклического сдвига битов слова и перемешивания позиций слов и преобразование ${\displaystyle \sigma }$ — это поразрядное сложение буфера и входного слова.

В данном случае ${\displaystyle +}$ будет определять сумму операций, где сначала выполняется та, что стоит правее.

Теперь можно рассмотреть каждую из этих операций. ${\displaystyle \theta }$ определяется следующим образом:

${\displaystyle c=\theta (a)\Leftrightarrow c_{i}=a_{i}\oplus a_{i+1}\oplus a_{i+4}}$ для ${\displaystyle i\in {0...17}}$,

где все индексы берутся по модулю ${\displaystyle 17}$. Заметим, что обратимость данного преобразования следует из того факта, что ${\displaystyle 1\oplus x\oplus x^{4}}$ является взаимно простым с ${\displaystyle 1\oplus x^{17}}$.

${\displaystyle \gamma }$ можно определить как:

${\displaystyle c=\gamma (a)\Leftrightarrow c_{i}=a_{i}\oplus (a_{i+1}OR\neg a_{i+2})}$ для ${\displaystyle i\in {0...17}}$,

где все индексы берутся по модулю ${\displaystyle 17}$.

Если для преобразования ${\displaystyle \pi }$ определить, что ${\displaystyle t_{k}}$ есть смещение на ${\displaystyle k}$ позиций от младшего бита к старшему, то:

${\displaystyle c=\pi (a)\Leftrightarrow c_{i}=t_{k}(a_{j})}$,

причем ${\displaystyle j=7i{}{\pmod {17}}}$, а ${\displaystyle k=i(i+1)/2{\pmod {32}}}$

Если для преобразования ${\displaystyle \sigma }$ будет выполняться, что ${\displaystyle c=\sigma (a)}$, то

${\displaystyle c_{0}=a_{0}\oplus 00000001_{hex}}$,

${\displaystyle c_{i+1}=a_{i+1}\oplus l_{i}}$ для ${\displaystyle 0\leqslant i<8}$,

${\displaystyle c_{i+9}=a_{i+9}\oplus b_{i}^{16}}$ для ${\displaystyle 0\leqslant i<8}$

В режиме «Push» ${\displaystyle l}$ является входным сообщением ${\displaystyle p}$, а в «Pull» режиме — ${\displaystyle l=b^{4}}$.

Выходное слово ${\displaystyle z}$ в «Pull» режиме определяется следующим образом:

${\displaystyle z_{i}=a_{i+9}}$ ${\displaystyle 0\leqslant i<8}$.^[11]

«Panama» как хеш-функция

«Panama» как хеш-функция сопоставляет сообщению произвольной длины ${\displaystyle M}$ хеш-результат в 256 бит.^[11] При этом хеширование происходит в 2 этапа

• ${\displaystyle M}$ преобразуется в строку ${\displaystyle M'}$ с длиной, которая кратна 256, путем добавления единиц.
• Соответствующая строка ${\displaystyle M'}$ загружается в «Panama».

Можно обозначить ${\displaystyle M'}$ как последовательность из числа ${\displaystyle V}$ входных блоков ${\displaystyle p}$. Тогда в нулевой момент времени генерируется режим Reset, затем в течение ${\displaystyle V}$ тактов загружаются входные блоки. После этого производится 32 пустых «Pull»-итераций. И затем на 33-ю «Pull»-итерацию возвращается результат хеширования ${\displaystyle h}$.

Основной задачей разработки хеш-функции «Panama» было нахождение «герметичной» хеш-функции^[11], то есть такой функции, для которой (если результат хеширования состоит из ${\displaystyle n}$ бит):

• для задачи поиска коллизии ожидаемая сложность равна ${\displaystyle 2^{n/2}}$
• для задачи вычисления образа ожидаемая сложность равна ${\displaystyle 2^{n}}$
• для задачи вычисления второго образа ожидаемая сложность равна ${\displaystyle 2^{n}}$

Кроме того, невозможно выявить систематические корреляции между любой линейной комбинацией входных битов и любой линейной комбинацией битов результата хеширования.^[11]

Поиск коллизий

Данная хеш-функция подвергалась успешным атакам дважды. Уже в 2001 году было показано, что данная хеш-функция не является криптостойкой, так как были найдены коллизии за ${\displaystyle 2^{82}}$ операций. Более того, Йоан Даймен показал, что можно найти коллизии уже за ${\displaystyle 2^{6}}$ операций, а для удовлетворения параметрам надежности необходимо, чтобы коллизии находились хотя бы за ${\displaystyle 2^{128}}$ операций.^[12]

Примечания

1. «Fast Hashing and Stream Encryption with Panama» Joan Daemen, Craig Clapp
2. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition  (неопр.). Дата обращения: 5 ноября 2016. Архивировано 5 октября 2012 года.
3. J. Daemen, «Cipher and hash function design strategies based on linear and differential cryptanalysis»
4. Fast Hashing and Stream Encryption with Panama" Joan Daemen, Craig Clapp
5. Архивированная копия  (неопр.). Дата обращения: 16 декабря 2016. Архивировано из оригинала 15 августа 2011 года.
6. SHA1 version 1.0  (неопр.). Дата обращения: 16 декабря 2016. Архивировано 14 мая 2017 года.
7. Panama  (неопр.). Дата обращения: 4 ноября 2016. Архивировано 26 декабря 2016 года.
8. The Panama Cryptographic Function | Dr Dobb’s  (неопр.). Дата обращения: 4 ноября 2016. Архивировано из оригинала 23 февраля 2016 года.
9. * «Fast Hashing and Stream Encryption with Panama» Joan Daemen, Craig Clapp
10. Шифр PANAMA | Блог о шифровании  (неопр.). Дата обращения: 5 ноября 2016. Архивировано 5 ноября 2016 года.
11. «Fast Hashing and Stream Encryption with Panama» Joan Daemen, Craig Clapp
12. 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., Рузин А. В., Сланин А. В., Тютвин А. Н. «Поточные шифры».

Ссылки