HPC (шифр)

HPC (Hasty Pudding Cipher) — блочный симметричный криптоалгоритм, созданный известным американским криптологом и математиком Ричардом Шреппелем^[англ.] из Университета штата Аризона в 1998 году. Первые два слова названия криптоалгоритма можно перевести как «мучной заварной пудинг». Столь странное название HPC получил, по всей видимости, из-за обилия «хитрых» числовых преобразований, что существенно затрудняет его анализ.

Общая структура

HPC основан на ячейке Фейстеля и имеет интересную особенность — размер как шифруемого блока, так и ключа шифрования не ограничен ничем. Фактически, алгоритм HPC состоит из пяти различных(но взаимосвязанных) субалгоритмов, каждый из которых предназначен для шифрования блоков различной длины:

Название	Размер блока в битах
HPC-Tiny	0 — 35
HPC-Short	36 — 64
HPC-Medium	65 — 128
HPC-Long	129 — 512
HPC-Extended	513 и более

Структура раунда HPC-Medium[1][2]

Раунд алгоритма HPC-Medium

Шифрование выполняется в 8 раундов. Шифруемый 128-битный блок записывается в два 64-битных регистра ${\displaystyle S_{1}}$ и ${\displaystyle S_{2}}$, после чего над ними производится огромное число различных математических операций:

Обозначение	Операция
${\displaystyle \oplus }$	сложение по модулю 2
${\displaystyle +}$	сложение по модулю ${\displaystyle 2^{64}}$
${\displaystyle -}$	вычитание по модулю ${\displaystyle 2^{64}}$
${\displaystyle <<n}$	циклический сдвиг влево на n разрядов
${\displaystyle >>n}$	циклический сдвиг вправо на n разрядов
${\displaystyle t()}$	обнуление младшего байта 64-битного блока
${\displaystyle \And }$	побитовое логическое "и"

Кроме того,в раунде также принимают участие некоторые константы:

• ${\displaystyle C_{1}=b+PI19}$
  • ${\displaystyle b}$ - размер шифруемого блока в битах
  • ${\displaystyle PI19=3141592653589793238}$ - "псевдослучайная" константа
• ${\displaystyle X_{n}}$ - значения, определяющие количество бит циклического сдвига:
  • ${\displaystyle X_{1}=22+(<S_{0}>\And 31)}$
  • ${\displaystyle X_{2}=33+i}$
    • ${\displaystyle <S_{0}>}$ - текущее на момент выполнения значение регистра ${\displaystyle S_{0}}$
    • ${\displaystyle i}$ - номер текущего раунда, начиная с нуля
• ${\displaystyle k_{n}}$ - фрагмент расширенного ключа:
  • ${\displaystyle k_{1}=K[<S_{0}>\And 255]}$
  • ${\displaystyle k_{2}=K[<S_{0}>\And 255]}$[3]
  • ${\displaystyle k_{3}=K[(<S_{0}>\And 255)+3*i+1]}$
  • ${\displaystyle k_{4}=K[b+16+i]}$
    • ${\displaystyle K}$ - расширенный ключ(массив из 256 64-битных слов)
• ${\displaystyle Sp_{n}}$ - фрагменты дополнительного ключа:
  • ${\displaystyle Sp_{1}=Spice[i\oplus 4]}$
  • ${\displaystyle Sp_{2}=Spice[i]}$
  • ${\displaystyle Sp_{3}=Spice[i\oplus 7]}$
  • ${\displaystyle Sp_{4}=Spice[i\oplus 2]}$
  • ${\displaystyle Sp_{5}=Spice[i\oplus 1]}$
    • ${\displaystyle Spice}$ - дополнительный ключ(массив из 8 64-битных слов)

По завершении 8 раундов преобразования производится ещё 2 операции:

• ${\displaystyle S_{0res}'=S_{0}'+K[b+8]}$
• ${\displaystyle S_{1res}'=S_{1}'+K[b+9]}$

Расшифровка производится посредством выполнения обратных операций в обратном порядке.

Процедура расширения ключа

Задача процедуры расширения ключа - формирование расширенного ключа, являющегося массивом из 256 64-битных слов. Понятно, что для каждого из субалгоритмов должна быть своя процедура. Знание одного из массивов расширенного ключа не позволяет вычислить ни другие массивы, ни сам ключ шифрования. Однако, при фиксированном размере шифруемых блоков достаточно один раз сформировать расширенный ключ для данного субалгоритма.

Этап 1: Инициализация

• ${\displaystyle K[0]=PI19+Nc}$
• ${\displaystyle K[1]=E19+L}$
• ${\displaystyle K[2]=R220<<Nc}$
  • ${\displaystyle E19=2718281828459045235}$, ${\displaystyle R220=14142135623730950488}$ - аналогичные ${\displaystyle PI19}$ "псевдослучайные" константы
  • ${\displaystyle L}$ - размер ключа шифрования в битах
  • ${\displaystyle Nc}$ - номер субалгоритма(3 для HPC-Medium)

Остальные 253 слова ключа инициализируются следующим образом:

• ${\displaystyle K[i]=K[i-1]+(K[i-2]\oplus (K[i-3]>>23)\oplus (K[i-3]<<41))mod2^{64}}$

Этап 2: Сложение

Производится побитовое сложение по модулю 2 ключа шифрования и проинициализированного массива расширенного ключа, но не более 128 слов.

Этап 3: Перемешивание

Раунд перемешивания ключа

Выполняется функция перемешивания данных расширенного ключа, которая обеспечивает влияние каждого бита ключа на каждый бит расширенного ключа:

Шаг 1

Выполняется инициализация регистров ${\displaystyle S_{0},...,S_{7}}$:

• ${\displaystyle S_{0}=K[255],S_{1}=K[254],...,S_{7}=K[248]}$

Шаг 2

Для каждого слова расширенного ключа выполняется операция, приведённая на рисунке. Для усиления эффекта автор алгоритма рекомендует проводить 3 раунда перемешивания.

• ${\displaystyle |}$ - побитовое логическое "или"
• ${\displaystyle i}$ - номер вычисляемого слова расширенного ключа
• ${\displaystyle j}$ - номер раунда перемешивания
• ${\displaystyle kc_{n}}$ - текущие значения слов расширенного ключа:
  • ${\displaystyle kc_{1}=K[i]}$
  • ${\displaystyle kc_{2}=K[(i+83)\And 255]}$
  • ${\displaystyle kc_{3}=K[<R_{0}>\And 255]}$

Этап 4: Добавление

Если размер ключа превышает 128 64-битных слов, то для каждого блока из 128 слов повторяются Этапы 2 и 3. Таким образом, процедура перемешивания ключей по порядку сложности примерно похожа на саму процедуру шифрования.

Дополнительный ключ

Его назначение - модифицировать результат шифрования при одинаковых входных блоках и ключах. Дополнительный ключ может быть секретным, что увеличивает фактический объём ключевой информации, однако в алгоритме с неограниченной длиной ключа такая возможность может быть лишней. В таких случаях можно просто обнулить дополнительный ключ.

Достоинства и недостатки

1. Один раунд шифрования алгоритма HPC состоит из очень большого количества элементарных операций. В сравнении, например, с отечественным алгоритмом ГОСТ 28147-89, который состоит всего из 4 элементарных операций, HPC представляется чрезвычайно сложным и громоздким. Тем не менее, из-за того, что все операции проводятся над 64-битными словами, HPC показал удивительно высокую скорость работы на 64-битных платформах. На конкурсе стандартов шифрования AES по скорости шифрования 128-битных блоков HPC уступил только алгоритму DFC, а 512- и 1024-битные блоки HPC шифровал в 2-3 раза быстрее всех своих конкурентов.
2. К явным недостаткам алгоритма можно отнести, кроме сложности, невозможность распараллеливания процессов шифрования и перемешивания, а также огромные требования, предъявляемые алгоритмом к энергонезависимой и оперативной памяти, что достаточно затрудняет его применение в смарт-картах.
3. Алгоритм не попал во второй этап AES. В своей статье[4] автор обрушился с критикой на экспертов AES, считая, что на конкурсе приоритеты были расставлены неправильно. По мнению Ричарда Шреппеля^[англ.], в качестве мирового стандарта необходимо выбирать алгоритмы, приспособленные под 64-битные платформы, так как именно за ними будущее. Кроме того, автор HPC утверждал, что нельзя разработать алгоритм, работающий одинаково хорошо как на мощных многоядерных 64-битных серверах, так и на слабых и дешевых 8-битных смарт-картах. Однако, на результаты конкурса эта позиция никак не повлияла.

Криптоанализ

• Чтобы стимулировать интерес к криптоанализу своего изобретения, автор обязался награждать каждого криптоаналитика бутылкой знаменитого шампанского "Дом Периньон". Награждения будут проходить до тех пор, пока шифр не будет вскрыт, либо пока не опустеет ящик(10 бутылок).[5]
• По словам автора шифра, HPC имеет уровень защищённости в 400 бит, то есть, для успешной атаки на шифр потребуется ${\displaystyle 2^{400}}$ испытаний. Такое утверждение основано на подсчёте количества промежуточных состояний в процессе шифрования, а также на размере расширенного ключа[6].

Уязвимости

Дэвид Вагнер^[англ.] обнаружил уязвимость в шифре HPC[7], а позднее Carl D’Halluin, Gert Bijnens, Барт Пренель и Винсент Рэймен опубликовали статью[8], подтверждающую это. Оказалось, что примерно каждый 256-й ключ алгоритма имеет 230 эквивалентных ключей. Однако, этот недостаток был оперативно исправлен автором ещё до подведения итогов первого раунда конкурса.

Атака "Chosen Spice"

При таком виде атаки злоумышленник, имея доступ к парам открытых и шифрованных текстов, может, манипулируя массивом дополнительного ключа "Spice", смотреть, как при этом меняется открытый или шифрованный текст в последующих шифрованиях. Однако, по словам автора, атак такого вида ещё не наблюдалось, а для работ в этой области нужны усилия криптоаналитического сообщества.[2]

Примечания

1. Панасенко С. П. Алгоритмы шифрования. Специальный справочник — СПб.: BHV-СПб, 2009. — 576 с. — ISBN 978-5-9775-0319-8
2. Richard Schroeppel,«Hasty Pudding Cipher Specification», May 1999  (неопр.). Дата обращения: 31 октября 2010. Архивировано из оригинала 17 июля 2011 года.
3. ${\displaystyle k_{1}}$ и ${\displaystyle k_{2}}$ имеют одинаковый вид, но, вообще говоря, это будут разные числа, так как они зависят от текущего значения ${\displaystyle S_{0}}$.
4. Rich Schroeppel, Puddingmeister, «The Hasty Pudding Cipher: One Year Later», June 12, 1999  (неопр.). Дата обращения: 31 октября 2010. Архивировано из оригинала 30 ноября 2021 года.
5. «СИСТЕМЫ БЕЗОПАСНОСТИ связи и телекоммуникаций», 1999  (неопр.). Дата обращения: 30 октября 2010. Архивировано 3 июля 2011 года.
6. Rich Schroeppel, Hilarie Orman, «An Overview of the Hasty Pudding Cipher», July 1998  (неопр.). Дата обращения: 31 октября 2010. Архивировано из оригинала 30 ноября 2021 года.
7. Richard Schroeppel, «Tweaking the Hasty Pudding Cipher» May 14, 1999  (неопр.). Дата обращения: 31 октября 2010. Архивировано из оригинала 30 ноября 2021 года.
8. «Equivalent Keys of HPC»,1999