Введение

Блок-шифр, алгоритм блочного шифрования.

В криптографии FROG — это блок-шифр, разработанный Джорджудисом, Леру и Чавесом. Алгоритм может работать с любым размером блока от 8 до 128 байт и поддерживает размеры ключей от 5 до 125 байт. Алгоритм состоит из 8 раундов и имеет очень сложный алгоритм формирования ключа. В 1998 году он был представлен компанией TecApro, костариканской компанией-разработчиком программного обеспечения, на конкурс AES в качестве кандидата на статус расширенного стандарта шифрования (Advanced Encryption Standard). Вагнер и др. (1999) выявили несколько слабых классов ключей для FROG. Другие проблемы включали очень медленную подготовку ключа и относительно медленное шифрование. FROG не был отобран в число финалистов.

Философия дизайна

Обычно блочный шифр применяет фиксированную последовательность примитивных математических или логических операций (таких как сложение, исключающее ИЛИ и т.п.) к открытому тексту и секретному ключу для получения зашифрованного текста. Злоумышленник использует эти знания для поиска уязвимостей в шифре, которые могут позволить восстановить исходный текст. Философия разработки FROG заключается в сокрытии точной последовательности примитивных операций, даже если сам шифр известен. В то время как другие шифры используют секретный ключ только как данные (которые комбинируются с открытым текстом для получения зашифрованного текста), FROG использует ключ как данные и как инструкции о том, как эти данные комбинировать. По сути, расширенная версия ключа используется FROG в качестве программы. Сам FROG функционирует как интерпретатор, который применяет эту программу, зависящую от ключа, к открытому тексту для создания зашифрованного текста. Расшифровка выполняется путем применения той же программы в обратном порядке к зашифрованному тексту.

Описание

FROG-ключ (или внутренний ключ) имеет длину 2304 байта. Он генерируется рекурсивно путем итеративного применения функции FROG к пустому открытому тексту. Полученный блок обрабатывается для формирования хорошо структурированного внутреннего ключа, состоящего из 8 записей. FROG состоит из 8 раундов, операции каждого раунда кодируются одной записью во внутреннем ключе. Все операции выполняются на уровне байта и состоят из операций XOR и подстановок. FROG очень прост в реализации (опорная реализация на C содержит всего около 150 строк кода). Большая часть кода, необходимого для реализации FROG, используется для генерации секретного внутреннего ключа; сам внутренний шифр представляет собой очень короткий код. Возможно написать ассемблерную подпрограмму всего из 22 машинных инструкций, выполняющую полное шифрование и расшифрование FROG. Реализация будет эффективно работать на 8-битных процессорах, поскольку использует только инструкции байтового уровня. Не используются побитовые операции. После вычисления внутреннего ключа алгоритм достаточно быстрый: версия, реализованная на ассемблере 8086, достигает скорости обработки более 2,2 мегабайта в секунду на ПК Pentium с частотой 200 МГц.

Безопасность

Философия разработки FROG призвана защищать от непредвиденных/неизвестных типов атак. Однако, сам факт использования ключа в качестве программы шифрования означает, что некоторые ключи могут соответствовать слабым алгоритмам шифрования. Дэвид Вагнер и другие обнаружили, что 2−33 ключей являются слабыми, и в этих случаях ключ может быть взломан, используя 258 выбранных открытых текстов. Другим недостатком FROG является то, что функция дешифрования обладает значительно меньшей диффузией, чем функция шифрования. В этом случае 2−29 ключей являются слабыми и могут быть взломаны, используя 236 выбранных шифротекстов.