HPC (шифр)

Поделись знанием:
Перейти к: навигация, поиск




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

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

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

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

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

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

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

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

  • <math>C_{1}=b+PI19</math>
  • <math>X_{n}</math> - значения, определяющие количество бит циклического сдвига:
    • <math>X_{1}=22+(<S_{0}>\And31)</math>
    • <math>X_{2}=33+i</math>
      • <math><S_{0}></math> - текущее на момент выполнения значение регистра <math>S_{0}</math>
      • <math>i</math> - номер текущего раунда, начиная с нуля
  • <math>k_{n}</math> - фрагмент расширенного ключа:
    • <math>k_{1}=K[<S_{0}>\And255]</math>
    • <math>k_{2}=K[<S_{0}>\And255]</math>[3]
    • <math>k_{3}=K[(<S_{0}>\And255)+3*i+1]</math>
    • <math>k_{4}=K[b+16+i]</math>
  • <math>Sp_{n}</math> - фрагменты дополнительного ключа:
    • <math>Sp_{1}=Spice[i\oplus4]</math>
    • <math>Sp_{2}=Spice[i]</math>
    • <math>Sp_{3}=Spice[i\oplus7]</math>
    • <math>Sp_{4}=Spice[i\oplus2]</math>
    • <math>Sp_{5}=Spice[i\oplus1]</math>

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

  • <math>S_{0res}'=S_{0}'+K[b+8]</math>
  • <math>S_{1res}'=S_{1}'+K[b+9]</math>

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


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

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

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

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

  • <math>K[i]=K[i-1]+(K[i-2]\oplus(K[i-3]>>23)\oplus(K[i-3]<<41))mod 2^{64}</math>

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

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

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

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

Шаг 1

Выполняется инициализация регистров <math>S_{0},...,S_{7}</math>:

  • <math>S_{0}=K[255],S_{1}=K[254],...,S_{7}=K[248]</math>

Шаг 2

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

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

Этап 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 бит, то есть, для успешной атаки на шифр потребуется <math>2^{400}</math> испытаний. Такое утверждение основано на подсчёте количества промежуточных состояний в процессе шифрования, а также на размере расширенного ключа[6].

Уязвимости

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

Атака "Chosen Spice"

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

Напишите отзыв о статье "HPC (шифр)"

Примечания

  1. [www.all4web.ru/art.aspx?id=41 Сергей Панасенко, «Алгоритмы шифрования», 2009]
  2. 1 2 [richard.schroeppel.name:8015/hpc/hpc-spec Richard Schroeppel,«Hasty Pudding Cipher Specification», May 1999]
  3. <math>k_{1}</math> и <math>k_{2}</math> имеют одинаковый вид, но, вообще говоря, это будут разные числа, так как они зависят от текущего значения <math>S_{0}</math>.
  4. [richard.schroeppel.name:8015/hpc/hpc-oneyearlater Rich Schroeppel, Puddingmeister, «The Hasty Pudding Cipher: One Year Later», June 12, 1999]
  5. [kiwibyrd.chat.ru/aes/aes1.htm «СИСТЕМЫ БЕЗОПАСНОСТИ связи и телекоммуникаций», 1999]
  6. [richard.schroeppel.name:8015/hpc/hpc-overview Rich Schroeppel, Hilarie Orman, «An Overview of the Hasty Pudding Cipher», July 1998]
  7. [richard.schroeppel.name:8015/hpc/tweak Richard Schroeppel, «Tweaking the Hasty Pudding Cipher» May 14, 1999]
  8. [www.google.ru/url?sa=t&source=web&cd=1&ved=0CBkQFjAA&url=https%3A%2F%2Fwww.cosic.esat.kuleuven.be%2Fpublications%2Farticle-74.pdf&rct=j&q=Equivalent%20Keys%20in%20HPC&ei=84LNTLnvMMWgOoLYsKQB&usg=AFQjCNFxBuApPMGHnb6T8tem8-mgp0UpdA&sig2=EA9Lg_TTUMAlWAncQ56xaw&cad=rjt| «Equivalent Keys of HPC»,1999]

Отрывок, характеризующий HPC (шифр)



Анатоль последнее время переселился к Долохову. План похищения Ростовой уже несколько дней был обдуман и приготовлен Долоховым, и в тот день, когда Соня, подслушав у двери Наташу, решилась оберегать ее, план этот должен был быть приведен в исполнение. Наташа в десять часов вечера обещала выйти к Курагину на заднее крыльцо. Курагин должен был посадить ее в приготовленную тройку и везти за 60 верст от Москвы в село Каменку, где был приготовлен расстриженный поп, который должен был обвенчать их. В Каменке и была готова подстава, которая должна была вывезти их на Варшавскую дорогу и там на почтовых они должны были скакать за границу.
У Анатоля были и паспорт, и подорожная, и десять тысяч денег, взятые у сестры, и десять тысяч, занятые через посредство Долохова.
Два свидетеля – Хвостиков, бывший приказный, которого употреблял для игры Долохов и Макарин, отставной гусар, добродушный и слабый человек, питавший беспредельную любовь к Курагину – сидели в первой комнате за чаем.
В большом кабинете Долохова, убранном от стен до потолка персидскими коврами, медвежьими шкурами и оружием, сидел Долохов в дорожном бешмете и сапогах перед раскрытым бюро, на котором лежали счеты и пачки денег. Анатоль в расстегнутом мундире ходил из той комнаты, где сидели свидетели, через кабинет в заднюю комнату, где его лакей француз с другими укладывал последние вещи. Долохов считал деньги и записывал.
– Ну, – сказал он, – Хвостикову надо дать две тысячи.
– Ну и дай, – сказал Анатоль.
– Макарка (они так звали Макарина), этот бескорыстно за тебя в огонь и в воду. Ну вот и кончены счеты, – сказал Долохов, показывая ему записку. – Так?
– Да, разумеется, так, – сказал Анатоль, видимо не слушавший Долохова и с улыбкой, не сходившей у него с лица, смотревший вперед себя.
Долохов захлопнул бюро и обратился к Анатолю с насмешливой улыбкой.
– А знаешь что – брось всё это: еще время есть! – сказал он.
– Дурак! – сказал Анатоль. – Перестань говорить глупости. Ежели бы ты знал… Это чорт знает, что такое!
– Право брось, – сказал Долохов. – Я тебе дело говорю. Разве это шутка, что ты затеял?
– Ну, опять, опять дразнить? Пошел к чорту! А?… – сморщившись сказал Анатоль. – Право не до твоих дурацких шуток. – И он ушел из комнаты.
Долохов презрительно и снисходительно улыбался, когда Анатоль вышел.
– Ты постой, – сказал он вслед Анатолю, – я не шучу, я дело говорю, поди, поди сюда.
Анатоль опять вошел в комнату и, стараясь сосредоточить внимание, смотрел на Долохова, очевидно невольно покоряясь ему.
– Ты меня слушай, я тебе последний раз говорю. Что мне с тобой шутить? Разве я тебе перечил? Кто тебе всё устроил, кто попа нашел, кто паспорт взял, кто денег достал? Всё я.
– Ну и спасибо тебе. Ты думаешь я тебе не благодарен? – Анатоль вздохнул и обнял Долохова.
– Я тебе помогал, но всё же я тебе должен правду сказать: дело опасное и, если разобрать, глупое. Ну, ты ее увезешь, хорошо. Разве это так оставят? Узнается дело, что ты женат. Ведь тебя под уголовный суд подведут…
– Ах! глупости, глупости! – опять сморщившись заговорил Анатоль. – Ведь я тебе толковал. А? – И Анатоль с тем особенным пристрастием (которое бывает у людей тупых) к умозаключению, до которого они дойдут своим умом, повторил то рассуждение, которое он раз сто повторял Долохову. – Ведь я тебе толковал, я решил: ежели этот брак будет недействителен, – cказал он, загибая палец, – значит я не отвечаю; ну а ежели действителен, всё равно: за границей никто этого не будет знать, ну ведь так? И не говори, не говори, не говори!
– Право, брось! Ты только себя свяжешь…
– Убирайся к чорту, – сказал Анатоль и, взявшись за волосы, вышел в другую комнату и тотчас же вернулся и с ногами сел на кресло близко перед Долоховым. – Это чорт знает что такое! А? Ты посмотри, как бьется! – Он взял руку Долохова и приложил к своему сердцу. – Ah! quel pied, mon cher, quel regard! Une deesse!! [О! Какая ножка, мой друг, какой взгляд! Богиня!!] A?
Долохов, холодно улыбаясь и блестя своими красивыми, наглыми глазами, смотрел на него, видимо желая еще повеселиться над ним.
– Ну деньги выйдут, тогда что?
– Тогда что? А? – повторил Анатоль с искренним недоумением перед мыслью о будущем. – Тогда что? Там я не знаю что… Ну что глупости говорить! – Он посмотрел на часы. – Пора!
Анатоль пошел в заднюю комнату.
– Ну скоро ли вы? Копаетесь тут! – крикнул он на слуг.
Долохов убрал деньги и крикнув человека, чтобы велеть подать поесть и выпить на дорогу, вошел в ту комнату, где сидели Хвостиков и Макарин.
Анатоль в кабинете лежал, облокотившись на руку, на диване, задумчиво улыбался и что то нежно про себя шептал своим красивым ртом.
– Иди, съешь что нибудь. Ну выпей! – кричал ему из другой комнаты Долохов.
– Не хочу! – ответил Анатоль, всё продолжая улыбаться.
– Иди, Балага приехал.
Анатоль встал и вошел в столовую. Балага был известный троечный ямщик, уже лет шесть знавший Долохова и Анатоля, и служивший им своими тройками. Не раз он, когда полк Анатоля стоял в Твери, с вечера увозил его из Твери, к рассвету доставлял в Москву и увозил на другой день ночью. Не раз он увозил Долохова от погони, не раз он по городу катал их с цыганами и дамочками, как называл Балага. Не раз он с их работой давил по Москве народ и извозчиков, и всегда его выручали его господа, как он называл их. Не одну лошадь он загнал под ними. Не раз он был бит ими, не раз напаивали они его шампанским и мадерой, которую он любил, и не одну штуку он знал за каждым из них, которая обыкновенному человеку давно бы заслужила Сибирь. В кутежах своих они часто зазывали Балагу, заставляли его пить и плясать у цыган, и не одна тысяча их денег перешла через его руки. Служа им, он двадцать раз в году рисковал и своей жизнью и своей шкурой, и на их работе переморил больше лошадей, чем они ему переплатили денег. Но он любил их, любил эту безумную езду, по восемнадцати верст в час, любил перекувырнуть извозчика и раздавить пешехода по Москве, и во весь скок пролететь по московским улицам. Он любил слышать за собой этот дикий крик пьяных голосов: «пошел! пошел!» тогда как уж и так нельзя было ехать шибче; любил вытянуть больно по шее мужика, который и так ни жив, ни мертв сторонился от него. «Настоящие господа!» думал он.
Анатоль и Долохов тоже любили Балагу за его мастерство езды и за то, что он любил то же, что и они. С другими Балага рядился, брал по двадцати пяти рублей за двухчасовое катанье и с другими только изредка ездил сам, а больше посылал своих молодцов. Но с своими господами, как он называл их, он всегда ехал сам и никогда ничего не требовал за свою работу. Только узнав через камердинеров время, когда были деньги, он раз в несколько месяцев приходил поутру, трезвый и, низко кланяясь, просил выручить его. Его всегда сажали господа.
– Уж вы меня вызвольте, батюшка Федор Иваныч или ваше сиятельство, – говорил он. – Обезлошадничал вовсе, на ярманку ехать уж ссудите, что можете.
И Анатоль и Долохов, когда бывали в деньгах, давали ему по тысяче и по две рублей.
Балага был русый, с красным лицом и в особенности красной, толстой шеей, приземистый, курносый мужик, лет двадцати семи, с блестящими маленькими глазами и маленькой бородкой. Он был одет в тонком синем кафтане на шелковой подкладке, надетом на полушубке.
Он перекрестился на передний угол и подошел к Долохову, протягивая черную, небольшую руку.
– Федору Ивановичу! – сказал он, кланяясь.
– Здорово, брат. – Ну вот и он.
– Здравствуй, ваше сиятельство, – сказал он входившему Анатолю и тоже протянул руку.
– Я тебе говорю, Балага, – сказал Анатоль, кладя ему руки на плечи, – любишь ты меня или нет? А? Теперь службу сослужи… На каких приехал? А?
– Как посол приказал, на ваших на зверьях, – сказал Балага.
– Ну, слышишь, Балага! Зарежь всю тройку, а чтобы в три часа приехать. А?
– Как зарежешь, на чем поедем? – сказал Балага, подмигивая.
– Ну, я тебе морду разобью, ты не шути! – вдруг, выкатив глаза, крикнул Анатоль.
– Что ж шутить, – посмеиваясь сказал ямщик. – Разве я для своих господ пожалею? Что мочи скакать будет лошадям, то и ехать будем.
– А! – сказал Анатоль. – Ну садись.
– Что ж, садись! – сказал Долохов.
– Постою, Федор Иванович.
– Садись, врешь, пей, – сказал Анатоль и налил ему большой стакан мадеры. Глаза ямщика засветились на вино. Отказываясь для приличия, он выпил и отерся шелковым красным платком, который лежал у него в шапке.
– Что ж, когда ехать то, ваше сиятельство?
– Да вот… (Анатоль посмотрел на часы) сейчас и ехать. Смотри же, Балага. А? Поспеешь?
– Да как выезд – счастлив ли будет, а то отчего же не поспеть? – сказал Балага. – Доставляли же в Тверь, в семь часов поспевали. Помнишь небось, ваше сиятельство.
– Ты знаешь ли, на Рожество из Твери я раз ехал, – сказал Анатоль с улыбкой воспоминания, обращаясь к Макарину, который во все глаза умиленно смотрел на Курагина. – Ты веришь ли, Макарка, что дух захватывало, как мы летели. Въехали в обоз, через два воза перескочили. А?
– Уж лошади ж были! – продолжал рассказ Балага. – Я тогда молодых пристяжных к каурому запрег, – обратился он к Долохову, – так веришь ли, Федор Иваныч, 60 верст звери летели; держать нельзя, руки закоченели, мороз был. Бросил вожжи, держи, мол, ваше сиятельство, сам, так в сани и повалился. Так ведь не то что погонять, до места держать нельзя. В три часа донесли черти. Издохла левая только.