WikiSort.ru - Не сортированное

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}}$ . Изначально и состояние, и буфер заполнены только ${\displaystyle 0}$ -ми. При режиме «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]

Примечания

Литература

• «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., Рузин А. В., Сланин А. В., Тютвин А. Н. «Поточные шифры».

Ссылки