FROG

Поделись знанием:
Перейти к: навигация, поиск
Это статья об алгоритме шифрования. О методе измерения огибающей и фазы сверхкоротких лазерных импульсов смотрите статью Frequency-resolved optical gating.
FROG
Создатель:

Д. Георгудис, Д. Леру и Б. Шаве

Создан:

1998 г.

Размер ключа:

128/192/256 бит

Размер блока:

128 бит

Число раундов:

8

Тип:

Собственный

FROG — алгоритм симметричного блочного шифрования c неортодоксальной структурой, один из участников американского конкурса AES, разработка костариканской компании TecApro Internacional.





История создания

Алгоритм FROG был создан в 1998 тремя специалистами компании Tecnologia Apropriada (ТесАрго) из небольшого латиноамериканского государства Коста-Рика (неизвестного ранее своими разработками в области криптографии): Дианелосом Георгоудисом (Dianelos Georgoudis), Дамианом Jlepy (Damian Leroux) и Билли Симоном Чавесом (Billy Simon Chaves)

Заявленный на конкурс вариант шифра соответствует требованиям AES, имея блок, равный 128 бит и ключ длиной 128, 192 или 256 бит. Сам алгоритм, теоретически, допускает ключи длиной от 40 до 1000 бит.

Конкурс AES

Шифр FROG выставила на конкурс международная компания TecApro Internacional, зарегистрированная в Коста-Рике. Разработчики алгоритма — Д. Георгудис (D. Georgoudis), Д. Леру (D. Leroux) и Б. Шаве (B. Chaves) — люди, мягко говоря, мало известные в криптографическом мире. Как утверждают авторы, FROG — это «новый шифр с неортодоксальной структурой». Основу стойкости шифра составляет секретный внутренний ключ сложной конструкции, сами же операции шифрования/дешифрования чрезвычайно просты.

В августе команда TWOFISH (Вагнер, Фергюсон и Шнайер) показали, что ключ шифра FROG можно вскрывать при трудозатратах около 257.

Что же касается стойкости шифров, то этот показатель проверить значительно сложнее. В ходе этапа предварительной оценки первого круга на web-сайте НИСТ и непосредственно на конференции AES2 было представлено значительное количество криптоаналитических результатов, так или иначе «подмочивших» репутацию практически всех шифров-кандидатов. Однако, если не говорить о явных аутсайдерах LOKI, FROG, MAGENTA и HPC, то никаких очевидных слабостей в алгоритмах не обнаружено.

Основные характеристики и структура алгоритма

Конкурс AES устанавливал для алгоритмов-участников конкурса обязательность поддержки 128-битного размера блока шифруемых данных, а также 128- , 192- и 256-битных ключей шифрования. Однако, разработчики алгоритма FROG предложили более широкий набор значений этих параметров:

  • допустимо использовать ключи размером от 5 до 125 байтов (то есть от 40 до 1000 битов);
  • размер блока может варьироваться от 8 до 128 байтов, то есть от 64 до 1024 битов (однако в авторском описании алгоритма в соответствии с требованиями AES фигурирует 16-байтный размер блока).

Независимо от размера ключа и блока, шифрование выполняется в 8 раундов. В каждом раунде над каждым байтом шифруемого блока (считая, что блоки имеют размер 16 байтов) производятся следующие действия:

  1. Значение текущего (N-го) байта складывается по модулю 2 со значением того же байта 1-й части ключа раунда (процедура расширения ключа описана далее).
  2. Вторая часть ключа раунда представляет собой таблицу перестановок. Из данной таблицы выбирается байт, порядковый номер которого равен значению, вычисленному на первом шаге. Значение выбранного байта замещает значение текущего байта шифруемого блока данных.
  3. Значение следующего байта (N+1 -перекладывается по модулю 2 со значением, выбранным на шаге 2. Полученный результат замещает старое значение N+1-го байта шифруемого блока данных.
  4. Третья часть ключа раунда представляет собой таблицу индексов. Значение N-го байта таблицы индексов определяет еще один модифицируемый байт шифруемого блока данных, который изменяется полностью аналогично N + 1 -му байту (то есть складывается по модулю 2 со значением, полученным на шаге 2).

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

Эта процедура должна получить из ключа шифрования 8 ключей раундов — по одному на каждый раунд алгоритма. Ключ раунда состоит из трех подключей:

  • 16-байтная 1-я часть;
  • 256-байтная таблица перестановок;
  • 16-байтная таблица индексов.

Таким образом, для работы алгоритма необходимо выработать 2304 байтов ключевой информации.

  1. Путём «размножения» ключа шифрования (то есть значение ключа шифрования повторяется необходимое количество раз, а ключ шифрования этого алгоритма, как было сказано выше, имеет размер от 5 до 125 байтов) вырабатывается первый 2304-байтный временный массив данных. Байты последней из «размноженных» копий ключа, выходящие за границу требуемого 2304-байтного массива (например, последний 71 байт 125-байтного ключа — ключа максимального размера), отбрасываются.
  2. Аналогичным «размножением» 251-байтного фрагмента мастер-ключа формируется второй 2304-байтный временный массив данных. Мастер- ключ представляет собой специально подобранную константу размером 251 байт. Побайтное значение мастер-ключа (начиная с младшего байта) приведено в таблице.
  3. Путём применения операции сложения по модулю 2 к соответствующим битам двух массивов, выработанных на шагах 1 и 2, получается временный расширенный ключ.
  4. Форматирование ключа, полученного на шаге 3 (то есть его разбиение на 8 отрезков— по числу раундов— размером 16 + 256 + 16 байтов, а также дополнительная обработка, которая будет описана далее), дает предварительный расширенный ключ алгоритма.
  5. Предварительный расширенный ключ используется для зашифровывания 2304-байтного массива, заполненного нулями. Шифрование выполняется в режиме сцепления блоков шифра, где в качестве вектора инициализации (IV) используются первые 16 байтов исходного ключа шифрования, самый первый из которых еще и складывается по модулю 2 с числом, равным размеру ключа шифрования в байтах (это необходимо для получения различных IV для ключей разного размера, но с совпадающими первыми 16 байтами). Результат операции — расширенный ключ, заполненный псевдослучайной информацией.
  6. Аналогично шагу 4, выполняется форматирование расширенного ключа для получения восьми ключей раундов с необходимой структурой.

Форматирование ключа

Шаги 4 и 6 алгоритма расширения ключа представляют собой форматирование 2304-байтной псевдослучайной последовательности с целью получения 8 ключей раундов. Если 1-я часть ключа раунда, используемая для сложения по модулю 2, может иметь абсолютно случайную структуру, то корректная таблица перестановок должна состоять из 256 неповторяющихся значений от 0 до 255, а к 16-байтной таблице индексов, кроме того, предъявляются дополнительные требования.

Таким образом, при форматировании производятся следующие действия:

  • Разбиение 2304-байтного массива на 8 фрагментов по 16 + 256 + 16 байтов.
  • Первые 16 байтов фрагмента становятся первой частью ключа раунда без изменений.
  • Следующие 256 байтов (обозначим этот фрагмент А) обрабатываются специальной процедурой с целью получения корректной таблицы перестановок. Данная процедура выглядит так:
  • создается 256-байтный массив t/, содержащий последовательно расположенные значения от 0 до 255;
  • в цикле от 0 до 255 /-й байт таблицы перестановок Т определяется по формуле:
  • index[i-l] — номер элемента массива t/, использованного на предыдущем шаге (для нулевого шага принимается равным 0), a L — текущий размер массива U\
  • использованный байт массива U выбрасывается, а расположенные после него элементы массива U сдвигаются на 1 байт к началу массива; таким образом, значение L в каждом проходе данного цикла уменьшается на 1;
  • если таблица перестановок создается для операции расшифровывания, то выполняется её инвертирование.
  • Аналогично шагу 3 создается 16-байтная таблица индексов.
  • Выполняется анализ цепочек ссылок таблицы индексов; если таблица состоит из нескольких цепочек, производится изменение таблицы с целью получения одной цепочки ссылок, длина которой будет равна размеру таблицы.
  • Таблица снова анализируется с целью поиска индексов, удовлетворяющих следующему условию:

<math>I[i]=i+1</math>

если такие элементы таблицы существуют, их значение меняется на

<math>I[i]=i+2</math>

Шаги 3-5 процедуры форматирования стоит рассмотреть на примере. Предположим, создается 6-байтная таблица индексов из следующего 6-байтного фрагмента псевдослучайной последовательности:

21,247,199,108,66,239

В цикле от 0 до 5 (шаг 4) /-й байт таблицы индексов I определяется по формуле:

<math>I[i]=U[(index[i-1]+A[i])mod L]</math>

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

Результат — таблица индексов:

3,2,5,1,0,4

3,0,5,1,2,4

Анализ таблицы (шаг 5) позволяет выяснить, что данная таблица состоит из двух цепочек ссылок:

3→1→2→5→4→2→0→3

3→1→0→3 и 5→4→2→5

Однако для достижения максимальной криптостойкости алгоритма таблица индексов должна содержать одну цепочку максимального размера. Алгоритм, выполняемый на шаге 5, позволяет объединить несколько цепочек в одну.

Достоинства и недостатки алгоритма

Как и многие другие алгоритмы, например AES (Rijndael) или SAFER+, FROG является байт-ориентированным. Однако, в отличие от объяснимых и объясненных авторами Rijndael и SAFER+ преобразований, применённых в этих алгоритмах, авторы алгоритма FROG ограничились пояснением, что такая необычная структура раунда выбрана с целью обеспечить максимально быстрое рассеивание входных данных (то есть обеспечение влияния каждого бита шифруемых данных на каждый бит шифртекста в пределах блока).

Тем не менее, FROG был признан одним из наиболее слабых участников конкурса AES; в нем было найдено множество недостатков, в частности:

  • довольно большая часть множества возможных ключей алгоритма оказалась слабой (благодаря очень сложной процедуре расширения ключа) к различным видам атак;
  • алгоритм оказался медленным, причем даже по сравнению с алгоритмами, известными до конкурса AES, например, Blowfish и RC5;
  • алгоритм FROG оказался очень требовательным к оперативной памяти — ему необходимо около 2500 байтов в случае, если ключи раундов сформированы заранее, а для работы полнофункционального алгоритма, включающего процедуру расширения ключа, необходимо около 5000 байтов; эти требования очень велики (особенно в сравнении с другими алгоритмами — участниками конкурса AES) для реализации данного алгоритма в смарт-картах;
  • существует ряд слабых ключей для данного алгоритма. Процедура установки ключа сравнительно медленна по причине сложного механизма генерации таблиц трансформации. Сам шифр имеет сравнительно низкую производительность, хотя после установки ключа 8 раундов преобразования выполняются довольно быстро — реализованный на 8086 ассемблере FROG выполняется на скорости 2.2 Мбайт/с на ПК с процессором Pentium 200;
  • криптоаналитики также обратили внимание на уязвимость функции расшифрования и её довольно медленную диффузиюК:Википедия:Статьи без источников (тип: не указан)[источник не указан 4020 дней];
  • другими участниками AES было показано, что ключ шифра Frog вскрывается при помощи 257 операций.

Таким образом, алгоритм FROG не вышел в финал конкурса AES.

Напишите отзыв о статье "FROG"

Литература

  • Курс «Защита информации», кафедра радиотехники, Московский физико-технический институт (МФТИ), эссе «Review of AES Candidates», Lipatiev, 2004
  • crypto.pp.ua/2010/12/algoritm-frog/

Отрывок, характеризующий FROG

В это время позади Кутузова послышались вдали звуки здоровающихся полков, и голоса эти стали быстро приближаться по всему протяжению растянувшейся линии наступавших русских колонн. Видно было, что тот, с кем здоровались, ехал скоро. Когда закричали солдаты того полка, перед которым стоял Кутузов, он отъехал несколько в сторону и сморщившись оглянулся. По дороге из Працена скакал как бы эскадрон разноцветных всадников. Два из них крупным галопом скакали рядом впереди остальных. Один был в черном мундире с белым султаном на рыжей энглизированной лошади, другой в белом мундире на вороной лошади. Это были два императора со свитой. Кутузов, с аффектацией служаки, находящегося во фронте, скомандовал «смирно» стоявшим войскам и, салютуя, подъехал к императору. Вся его фигура и манера вдруг изменились. Он принял вид подначальственного, нерассуждающего человека. Он с аффектацией почтительности, которая, очевидно, неприятно поразила императора Александра, подъехал и салютовал ему.
Неприятное впечатление, только как остатки тумана на ясном небе, пробежало по молодому и счастливому лицу императора и исчезло. Он был, после нездоровья, несколько худее в этот день, чем на ольмюцком поле, где его в первый раз за границей видел Болконский; но то же обворожительное соединение величавости и кротости было в его прекрасных, серых глазах, и на тонких губах та же возможность разнообразных выражений и преобладающее выражение благодушной, невинной молодости.
На ольмюцком смотру он был величавее, здесь он был веселее и энергичнее. Он несколько разрумянился, прогалопировав эти три версты, и, остановив лошадь, отдохновенно вздохнул и оглянулся на такие же молодые, такие же оживленные, как и его, лица своей свиты. Чарторижский и Новосильцев, и князь Болконский, и Строганов, и другие, все богато одетые, веселые, молодые люди, на прекрасных, выхоленных, свежих, только что слегка вспотевших лошадях, переговариваясь и улыбаясь, остановились позади государя. Император Франц, румяный длиннолицый молодой человек, чрезвычайно прямо сидел на красивом вороном жеребце и озабоченно и неторопливо оглядывался вокруг себя. Он подозвал одного из своих белых адъютантов и спросил что то. «Верно, в котором часу они выехали», подумал князь Андрей, наблюдая своего старого знакомого, с улыбкой, которую он не мог удержать, вспоминая свою аудиенцию. В свите императоров были отобранные молодцы ординарцы, русские и австрийские, гвардейских и армейских полков. Между ними велись берейторами в расшитых попонах красивые запасные царские лошади.
Как будто через растворенное окно вдруг пахнуло свежим полевым воздухом в душную комнату, так пахнуло на невеселый Кутузовский штаб молодостью, энергией и уверенностью в успехе от этой прискакавшей блестящей молодежи.
– Что ж вы не начинаете, Михаил Ларионович? – поспешно обратился император Александр к Кутузову, в то же время учтиво взглянув на императора Франца.
– Я поджидаю, ваше величество, – отвечал Кутузов, почтительно наклоняясь вперед.
Император пригнул ухо, слегка нахмурясь и показывая, что он не расслышал.
– Поджидаю, ваше величество, – повторил Кутузов (князь Андрей заметил, что у Кутузова неестественно дрогнула верхняя губа, в то время как он говорил это поджидаю ). – Не все колонны еще собрались, ваше величество.
Государь расслышал, но ответ этот, видимо, не понравился ему; он пожал сутуловатыми плечами, взглянул на Новосильцева, стоявшего подле, как будто взглядом этим жалуясь на Кутузова.
– Ведь мы не на Царицыном лугу, Михаил Ларионович, где не начинают парада, пока не придут все полки, – сказал государь, снова взглянув в глаза императору Францу, как бы приглашая его, если не принять участие, то прислушаться к тому, что он говорит; но император Франц, продолжая оглядываться, не слушал.
– Потому и не начинаю, государь, – сказал звучным голосом Кутузов, как бы предупреждая возможность не быть расслышанным, и в лице его еще раз что то дрогнуло. – Потому и не начинаю, государь, что мы не на параде и не на Царицыном лугу, – выговорил он ясно и отчетливо.
В свите государя на всех лицах, мгновенно переглянувшихся друг с другом, выразился ропот и упрек. «Как он ни стар, он не должен бы, никак не должен бы говорить этак», выразили эти лица.
Государь пристально и внимательно посмотрел в глаза Кутузову, ожидая, не скажет ли он еще чего. Но Кутузов, с своей стороны, почтительно нагнув голову, тоже, казалось, ожидал. Молчание продолжалось около минуты.
– Впрочем, если прикажете, ваше величество, – сказал Кутузов, поднимая голову и снова изменяя тон на прежний тон тупого, нерассуждающего, но повинующегося генерала.
Он тронул лошадь и, подозвав к себе начальника колонны Милорадовича, передал ему приказание к наступлению.
Войско опять зашевелилось, и два батальона Новгородского полка и батальон Апшеронского полка тронулись вперед мимо государя.
В то время как проходил этот Апшеронский батальон, румяный Милорадович, без шинели, в мундире и орденах и со шляпой с огромным султаном, надетой набекрень и с поля, марш марш выскакал вперед и, молодецки салютуя, осадил лошадь перед государем.
– С Богом, генерал, – сказал ему государь.
– Ma foi, sire, nous ferons ce que qui sera dans notre possibilite, sire, [Право, ваше величество, мы сделаем, что будет нам возможно сделать, ваше величество,] – отвечал он весело, тем не менее вызывая насмешливую улыбку у господ свиты государя своим дурным французским выговором.
Милорадович круто повернул свою лошадь и стал несколько позади государя. Апшеронцы, возбуждаемые присутствием государя, молодецким, бойким шагом отбивая ногу, проходили мимо императоров и их свиты.
– Ребята! – крикнул громким, самоуверенным и веселым голосом Милорадович, видимо, до такой степени возбужденный звуками стрельбы, ожиданием сражения и видом молодцов апшеронцев, еще своих суворовских товарищей, бойко проходивших мимо императоров, что забыл о присутствии государя. – Ребята, вам не первую деревню брать! – крикнул он.
– Рады стараться! – прокричали солдаты.
Лошадь государя шарахнулась от неожиданного крика. Лошадь эта, носившая государя еще на смотрах в России, здесь, на Аустерлицком поле, несла своего седока, выдерживая его рассеянные удары левой ногой, настораживала уши от звуков выстрелов, точно так же, как она делала это на Марсовом поле, не понимая значения ни этих слышавшихся выстрелов, ни соседства вороного жеребца императора Франца, ни всего того, что говорил, думал, чувствовал в этот день тот, кто ехал на ней.
Государь с улыбкой обратился к одному из своих приближенных, указывая на молодцов апшеронцев, и что то сказал ему.


Кутузов, сопутствуемый своими адъютантами, поехал шагом за карабинерами.
Проехав с полверсты в хвосте колонны, он остановился у одинокого заброшенного дома (вероятно, бывшего трактира) подле разветвления двух дорог. Обе дороги спускались под гору, и по обеим шли войска.
Туман начинал расходиться, и неопределенно, верстах в двух расстояния, виднелись уже неприятельские войска на противоположных возвышенностях. Налево внизу стрельба становилась слышнее. Кутузов остановился, разговаривая с австрийским генералом. Князь Андрей, стоя несколько позади, вглядывался в них и, желая попросить зрительную трубу у адъютанта, обратился к нему.
– Посмотрите, посмотрите, – говорил этот адъютант, глядя не на дальнее войско, а вниз по горе перед собой. – Это французы!
Два генерала и адъютанты стали хвататься за трубу, вырывая ее один у другого. Все лица вдруг изменились, и на всех выразился ужас. Французов предполагали за две версты от нас, а они явились вдруг, неожиданно перед нами.
– Это неприятель?… Нет!… Да, смотрите, он… наверное… Что ж это? – послышались голоса.
Князь Андрей простым глазом увидал внизу направо поднимавшуюся навстречу апшеронцам густую колонну французов, не дальше пятисот шагов от того места, где стоял Кутузов.
«Вот она, наступила решительная минута! Дошло до меня дело», подумал князь Андрей, и ударив лошадь, подъехал к Кутузову. «Надо остановить апшеронцев, – закричал он, – ваше высокопревосходительство!» Но в тот же миг всё застлалось дымом, раздалась близкая стрельба, и наивно испуганный голос в двух шагах от князя Андрея закричал: «ну, братцы, шабаш!» И как будто голос этот был команда. По этому голосу всё бросилось бежать.
Смешанные, всё увеличивающиеся толпы бежали назад к тому месту, где пять минут тому назад войска проходили мимо императоров. Не только трудно было остановить эту толпу, но невозможно было самим не податься назад вместе с толпой.
Болконский только старался не отставать от нее и оглядывался, недоумевая и не в силах понять того, что делалось перед ним. Несвицкий с озлобленным видом, красный и на себя не похожий, кричал Кутузову, что ежели он не уедет сейчас, он будет взят в плен наверное. Кутузов стоял на том же месте и, не отвечая, доставал платок. Из щеки его текла кровь. Князь Андрей протеснился до него.
– Вы ранены? – спросил он, едва удерживая дрожание нижней челюсти.
– Раны не здесь, а вот где! – сказал Кутузов, прижимая платок к раненой щеке и указывая на бегущих. – Остановите их! – крикнул он и в то же время, вероятно убедясь, что невозможно было их остановить, ударил лошадь и поехал вправо.
Вновь нахлынувшая толпа бегущих захватила его с собой и повлекла назад.
Войска бежали такой густой толпой, что, раз попавши в середину толпы, трудно было из нее выбраться. Кто кричал: «Пошел! что замешкался?» Кто тут же, оборачиваясь, стрелял в воздух; кто бил лошадь, на которой ехал сам Кутузов. С величайшим усилием выбравшись из потока толпы влево, Кутузов со свитой, уменьшенной более чем вдвое, поехал на звуки близких орудийных выстрелов. Выбравшись из толпы бегущих, князь Андрей, стараясь не отставать от Кутузова, увидал на спуске горы, в дыму, еще стрелявшую русскую батарею и подбегающих к ней французов. Повыше стояла русская пехота, не двигаясь ни вперед на помощь батарее, ни назад по одному направлению с бегущими. Генерал верхом отделился от этой пехоты и подъехал к Кутузову. Из свиты Кутузова осталось только четыре человека. Все были бледны и молча переглядывались.
– Остановите этих мерзавцев! – задыхаясь, проговорил Кутузов полковому командиру, указывая на бегущих; но в то же мгновение, как будто в наказание за эти слова, как рой птичек, со свистом пролетели пули по полку и свите Кутузова.