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. Дата обращения: 5 ноября 2016. Архивировано 5 октября 2012 года.
  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. Дата обращения: 16 декабря 2016. Архивировано 14 мая 2017 года.
  7. 1 2 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. 1 2 3 4 «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., Рузин А. В., Сланин А. В., Тютвин А. Н. «Поточные шифры».