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

Шифрование выполняется в 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]}$
  • ${\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 . В своей статье автор обрушился с критикой на экспертов AES , считая, что на конкурсе приоритеты были расставлены неправильно. По мнению , в качестве мирового стандарта необходимо выбирать алгоритмы, приспособленные под 64- битные платформы, так как именно за ними будущее. Кроме того, автор HPC утверждал, что нельзя разработать алгоритм, работающий одинаково хорошо как на мощных многоядерных 64- битных серверах, так и на слабых и дешевых 8- битных смарт-картах . Однако, на результаты конкурса эта позиция никак не повлияла.

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

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

Уязвимости

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

Атака "Chosen Spice"

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

Примечания