Хеш-функция 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]

Принцип работы[ | ]

Можно обозначить состояние как , а 17 слов, которые определяют состояния обозначить как . Буфер обозначается как , -я его ячейка как , а одно из слов, лежащих внутри этой ячейки как . Изначально и состояние, и буфер заполнены только -ми. При режиме «Push» «Panama» получает на вход некоторое 8-битовое слово, в режиме «Pull» на выход формируется 8-битовое слово.[7]

Если обозначить функцию, которая обновляет буфер как , то если принять что , можно получить следующие правила обновления буфера:

при ,
,
для

где в режиме «Push» есть входной блок , а в «Pull» это часть состояния , т.е 8 его компонент, определяемые как

для

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

,где  — это обратное линейное преобразование,  — это, опять же, обратное линейное преобразование,  — это комбинация циклического сдвига битов слова и перемешивания позиций слов и преобразование  — это поразрядное сложение буфера и входного слова.

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

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

для ,

где все индексы берутся по модулю . Заметим, что обратимость данного преобразования следует из того факта, что является взаимно простым с .

можно определить как:

для ,

где все индексы берутся по модулю .

Если для преобразования определить, что есть смещение на позиций от младшего бита к старшему, то:

,

причем , а

Если для преобразования будет выполняться, что , то

,
для ,
для

В режиме «Push» является входным сообщением , а в «Pull» режиме — .

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

.[11]

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

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

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

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

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

  • для задачи поиска коллизии ожидаемая сложность равна
  • для задачи вычисления образа ожидаемая сложность равна
  • для задачи вычисления второго образа ожидаемая сложность равна

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

Поиск коллизий[ | ]

Данная хеш-функция подвергалась успешным атакам дважды. Уже в 2001 году было показано, что данная хеш-функция не является криптостойкой, так как были найдены коллизии за операций. Более того, Йоан Даймен показал, что можно найти коллизии уже за операций, а для удовлетворения параметрам надежности необходимо, чтобы коллизии находились хотя бы за операций.[12]

Примечания[ | ]

  1. «Fast Hashing and Stream Encryption with Panama» Joan Daemen, Craig Clapp
  2. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition
  3. 1 2 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
  7. 1 2 Panama
  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 | Блог о шифровании
  11. 1 2 3 4 «Fast Hashing and Stream Encryption with Panama» Joan Daemen, Craig Clapp
  12. Producing Collisions for Panama, Instantaneously

Литература[ | ]

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

Ссылки[ | ]