FROG

FROG
Создатель:	Д. Георгудис, Д. Леру и Б. Шаве
Создан:	1998 г.
Опубликован:	1992 г.
Размер ключа:	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. Было показано, что ключ шифра FROG можно вскрывать при трудозатратах около 2⁵⁷. Для DES, к примеру, с его 56-разрядным ключом это стало бы прекрасным показателем стойкости (поскольку на его лобовое вскрытие путем тотального перебора требуется 2⁵⁶ опробования), однако для шифра с длиной ключа по меньшей мере 128 бит этого уже слишком мало.

Испытания на скорость шифрования/расшифрования (компилятор Borland) выявили 6 более-менее очевидных лидеров, продемонстрировавших скорость свыше 25 Мбит/сек: Crypton (40 Мбит/сек); Rijndael; RC6; E2; Twofish и Mars (26 Мбит/сек). На последних местах оказались Magenta и HPC со скоростью около 2 Мбит/сек, остальные алгоритмы показали результаты от 6 до 10 Мбит/сек. Сразу же было отмечено, что при других компиляторах показатели могут сильно отличаться. Например, при компиляторе DJGPP алгоритм MARS демонстрирует скорость свыше 60 Мбит/сек, а лидер Crypton — менее 30 Мбит/сек. Что же касается скорости формирования ключей, то здесь разброс оказался значительно шире: от 500 000 кл/мсек (Crypton) до 100 кл/мсек (HPC и FROG). Среди лидеров в этом разряде можно отметить алгоритмы Magenta, E2, Safer+, RC6, Rijndael, Mars, Serpent, Twofish.

Что же касается стойкости шифров, то этот показатель проверить значительно сложнее. В ходе этапа предварительной оценки первого круга на 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. Значение текущего (/-го) байта складывается по модулю 2 со значением того же байта 1-й части ключа раунда (процедура расширения ключа описана далее).
2. Вторая часть ключа раунда представляет собой таблицу перестановок. Из данной таблицы выбирается байт, порядковый номер которого равен значению, вычисленному на первом шаге. Значение выбранного байта замещает значение текущего байта шифруемого блока данных.
3. Значение следующего байта (/ +1 -перекладывается по модулю 2 со значением, выбранным на шаге 2. Полученный результат замещает старое значение / +1 -го байта шифруемого блока данных.
4. Третья часть ключа раунда представляет собой таблицу индексов. Значение /-го байта таблицы индексов определяет еще один модифицируемый байт шифруемого блока данных, который изменяется полностью аналогично i + 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-байтная таблица индексов.
• Выполняется анализ цепочек ссылок таблицы индексов; если таблица состоит из нескольких цепочек, производится изменение таблицы с целью получения одной цепочки ссылок, длина которой будет равна размеру таблицы.

• Таблица снова анализируется с целью поиска индексов, удовлетворяющих следующему условию:

$I[i]=i+1$

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

$I[i]=i+2$

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

21,247,199,108,66,239

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

$I[i]=U[(index[i-1]+A[i])mod L]$

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

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

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, позволяет объединить несколько цепочек в одну.

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

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

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

• довольно большая часть множества возможных ключей алгоритма оказалась слабой (благодаря очень сложной процедуре расширения ключа) к различным видам атак;
• алгоритм оказался весьма медленным, причем даже по сравнению с алгоритмами, известными до конкурса AES, например, Blowfish и RC5
• алгоритм FROG оказался очень требовательным к оперативной памяти — ему необходимо около 2500 байтов в случае, если ключи раундов сформированы заранее, а для работы полнофункционального алгоритма, включающего процедуру расширения ключа, необходимо около 5000 байтов; эти требования очень велики (особенно в сравнении с другими алгоритмами — участниками конкурса AES) для реализации данного алгоритма в смарт-картах.
• Существует ряд слабых ключей для данного алгоритма. Процедура установки ключа сравнительно медленна по причине сложного механизма генерации таблиц трансформации. Сам шифр имеет сравнительно низкую производительность, хотя после установки ключа 8 раундов преобразования выполняются довольно быстро — реализованный на 8086 ассемблере FROG выполняется на скорости 2.2 МБайт/с на ПК с процессором Pentium 200.
• Криптоаналитики также обратили внимание на уязвимость функции расшифрования и ее довольно медленную диффузию.
• Другими участниками AES было показано, что ключ шифра Frog вскрывается при помощи 2⁵⁷ операций, что было бы прекрасно для DES с ключом 56 бит, но не шифров со 128-битным и выше ключом по мнению криптоаналитиков.

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

Литература

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