Алгоритм RC5

Алгоритм RC5 интересен по многим причинам.

Алгоритм разработан известнейшим криптологом Рональдом Ривестом — одним из разработчиков асимметричной системы RSA и одним из основателей одноименной фирмы (RSA Data Security), которая, несомненно, является одним из мировых лидеров рынка средств криптографической защиты информации. Аббревиатура RC обозначает, по разным источникам, либо Rivest Cipher, либо Ron's Code, т. е., в совокупности, «шифр Рона Ривеста». Аналогично предыдущим алгоритмам шифрования Рона Ривеста RC2 и RC4 (является потоковым шифром, поэтому в данной книге не описан), алгоритм RC5 получил весьма широкое распространение;
по количеству пользователей в мире он стоит в одном ряду с такими известными алгоритмами, как IDEA и Blowfish.

На преобразованиях, используемых в RC5, основана последующая разработка компании RSA — алгоритм RC6, который стал финалистом конкурса AES по выбору нового стандарта шифрования США; алгоритм RC6 не победил в конкурсе, но, видимо, превзойдет своего предка по широте использования.

Структура алгоритма
Аналогично, например, алгоритму SHARK, часть основных параметров алгоритма RC5 являются переменными. Как пишет автор алгоритма «RC5 — это несколько различных алгоритмов», поскольку, помимо секретного ключа, параметрами алгоритма являются следующие:
размер слова w (в битах); RC5 шифрует блоками по два слова; допустимыми значениями w являются 16, 32 или 64, причем 32 является рекомендуемым; количество раундов алгоритма R — в качестве значения допустимо любое целое число от 0 до 255 включительно;
размер секретного ключа в байтах любое целое значение от 0 до 255 включительно.

По мнению автора алгоритма, переменные параметры расширяют сферу использования алгоритма, а также позволяют сильно сократить издержки при необходимости перехода на более сильный вариант алгоритма — в отличие от DES (основная проблема которого — короткий 56-битный ключ), в программной или аппаратной реализации RC5, поддерживающей переменные параметры, легко было бы заменить ключ более длинным, таким образом устранив проблему. Вот что пишет об этом Рон Ривест: «Фиксированные параметры могут быть не менее опасны [переменных], поскольку они не могут быть улучшены при необходимости. Рассмотрим проблему DES: его ключ слишком короток и нет простого способа увеличить его».

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

Стоит отметить, что под словом «раунд» в описании алгоритма Ривест понимает преобразования, соответствующие двум раундам обычных алгоритмов, структура которых является сетью Фейстеля. То есть раунд алгоритма RC5 обрабатывает блок целиком, тогда как типичный раунд сети Фейстеля обрабатывает только один субблок — обычно половину блока.

Алгоритм поразительно прост— в нем используются только операции сложения по модулю 2, а также сдвиги на переменное число битов. Последняя из операций представляется автором алгоритма как революционное решение, не использованное в более ранних алгоритмах шифрования (до алгоритма RC5 такие использовались только в алгоритме Madryga, не получившем широкого распространения), — сдвиг на переменное число битов является весьма просто реализуемой операцией, которая, однако, существенно усложняет дифференциальный и линейный криптоанализ алгоритма. Простота алгоритма может рассматриваться как его важное достоинство — простой алгоритм легче реализовать и легче анализировать на предмет возможных уязвимостей.

Криптоанализ алгоритма
Считается, что именно революционные сдвиги на переменное число битов привлекли внимание криптоаналитиков к алгоритму RC5 — RC5 стал одним из наиболее изученных алгоритмов на предмет возможных уязвимостей.

Начало криптоанализу алгоритма RC5 было положено сотрудниками RSA Laboratories — научного подразделения фирмы RSA Data Security — Берто-ном Калиски (Burton S. Kaliski Jr.) и Икван Лайзой Ин (Yiqun Lisa Yin). В период с 1995 по 1998 гг. они опубликовали ряд отчетов, в которых подробно проанализировали криптостойкость алгоритма RC5. Выводы таковы.

Алгоритм RC5 почти невозможно вскрыть методом линейного криптоанализа. Во многом это свойство алгоритма предопределило наличие операции циклического сдвига на переменное число битов. Однако дальнейшие исследования показали, что существует класс ключей, при использовании которых алгоритм может быть вскрыт линейным криптоанализом.

Дифференциальный криптоанализ существенно более эффективен при атаках на алгоритм RC5. Калиски и Ин предложили атаку на алгоритм RC5-32/12/16, для которой требовалось наличие 263 пар выбранных открытых текстов и соответствующих им шифртекстов. Этот результат улучшили Ларе Кнудсен и Уилли Мейер (Willi Meier), для атаки которых требовалось 254 выбранных открытых текстов. Они же нашли несколько классов слабых ключей, использование которых упрощает дифференциальный криптоанализ. А наилучшим результатом является криптоаналитический метод, предложенный криптологами Алексом Бирюковым и Эйялом Кушилевицем (Eyal Kushilevitz), которым необходимо 244 выбранных открытых текстов для успешной атаки. Тем не менее, все описанные выше атаки являются непрактичными — для их выполнения требуется наличие огромного количества выбранных открытых текстов. Бирюков и Кушилевиц считают, что для обеспечения полной невскрываемости алгоритма дифференциальным криптоанализом достаточно выполнения 18-20 раундов вместо 12.

На основании того факта, что на ряде платформ операция циклического сдвига на переменное число битов выполняется за различное число тактов процессора, изобретатель метода вскрытия алгоритмов шифрования по времени исполнения Пол Кохер высказал предположение о возможности атаки по времени исполнения на алгоритм RC5 на таких платформах. Два варианта подобной атаки были сформулированы криптоанали-тиками Говардом Хейзом (Howard М. Heys) и Хеленой Хандшух (Helena Handschuh), которые показали, что секретный ключ можно вычислить путем выполнения около 220 операций шифрования с высокоточными замерами времени исполнения и последующим выполнением от 228 до 240 тестовых операций шифрования. Однако Калиски и Ин предложили весьма простое «противоядие» против этой атаки — принудительно выполнять все сдвиги за одинаковое число тактов (т. е. как наиболее медленный из возможных сдвигов — это, несомненно, несколько снизит среднюю скорость шифрования). Аналогичную методику противодействия атакам по времени исполнения советует и сам Кохер.

Таким образом, наиболее реальным методом взлома алгоритма RC5 (не считая варианты с небольшим количеством раундов и с коротким ключом) является полный перебор возможных вариантов ключа шифрования. Что означает, что у алгоритма RC5 практически отсутствуют недостатки с точки зрения его стойкости. Это косвенно подтверждается тем, что достаточно много исследований стойкости алгоритма было направлено против вариантов с усеченным количеством раундов: такие варианты обычно исследуются в случае отсутствия серьезных уязвимостей у полноценных вариантов исследуемого алгоритма. Было немало и других исследований данного алгоритма. Причем их подавляющее большинство применялось к 64-битной версии алгоритма (т. е. для w = 32). Это не означает, что RC5 со 128-битным блоком шифруемых данных является существенно менее изученным — результаты исследований показывают, что 128-битный вариант RC5 с достаточным количеством раундов вскрыть существенно сложнее 64-битного. Например, Бирюков и Кушилевиц предложили атаку на алгоритм RC5-64/16/16 на основе 263 выбранных открытых текстов, что достаточно нереально для практического применения. Варианты RC5
Структура алгоритма RC5, несмотря на свою простоту, представлялась многим криптологам как поле для возможных усовершенствований. Соответственно, появилось множество известных вариантов алгоритма RC5, в которых преобразования в «пол-раундах» классического RC5 несколько изменены:
Алгоритм RC5XOR, в котором сложение с ключом раунда по модулю 2W заменено операцией XOR.

Данный алгоритм оказался менее стоек, чем RC5, как к линейному, так и к дифференциальному криптоанализу. В частности, Бирюков и Кушилевиц предложили атаку методом дифференциального криптоанализа, вскрывающую алгоритм RC5XOR-32/12/16 на основе 228 выбранных открытых текстов.
Алгоритм RC5P, в котором сложение левого и правого обрабатываемых субблоков операцией XOR заменено сложением по модулю 2.
Алгоритм оказался так же стоек, как и RC5, против линейного криптоанализа, но значительно слабее против дифференциального.
Здесь и далее в качестве примера приведено только преобразование для вычисления левого субблока; правый вычисляется в следующей половине раунда аналогичным образом.
Алгоритм RC5KFR, в котором число битов сдвига является функцией ключа шифрования КС, т. е. для каждого ключа шифрования число битов сдвига является фиксированным (может быть различным для разных раундов алгоритма).
Алгоритм RC5KFR также не является хорошо изученным алгори+мом, однако считается, что во многих случаях (особенно при недостаточно большом количестве раундов) криптоанализ данного варианта алгоритма RC5 сводится к анализу алгоритма RC5PFR, что не внушает уверенности в его стойкости. Алгоритм RC5RA, в котором выполняется циклический сдвиг на переменное число битов, определяемое не значением младших log2 w битов другого субблока, а некоей функцией, обрабатывающей в качестве входного значения все биты другого субблока.
И этот вариант алгоритма еще недостаточно изучен (и, видимо, уже не будет достаточно изучен, поскольку можно утверждать, что RC5 и его варианты сейчас представляют лишь исторический интерес), но существует мнение, что алгоритм RC5RA может быть еще сильнее, чем RC5, против известных методов криптоанализа.

Продолжение истории алгоритма
Как было сказано выше, на основе алгоритма RC5 в 1998 г. был разработан алгоритм RC6, который также основан на циклических сдригах на переменное число битов. Подавляющее большинство криптоаналитических исследований алгоритма RC5 могут быть в различной мере применены и к RC6. У RC6 уже своя богатая история, которая заслуживает отдельного описания.

По материалам книги Сергея Панасенко «Алгоритмы шифрования»