Криптоанализ алгоритма

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

Начало криптоанализу алгоритма RC5 было положено сотрудниками RSA Laboratories Бертоном Калиски и Икван Лайзой Ин. В период с 1995 по 1998 гг. они опубликовали ряд отчетов, в которых подробно проанализировали криптостойкость алгоритма RC5. Выводы таковы.

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

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

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

Было немало и других исследований данного алгоритма. Причем их подавляющее большинство применялось к 64-битной версии алгоритма (т.е. для w=32). Это не означает, что RC5 со 128-битным блоком шифруемых данных является существенно менее изученным – результаты исследований показывают, что 128-битный вариант RC5 с достаточным количеством раундов вскрыть существенно сложнее 64-битного.

Варианты RC5

Структура алгоритма RC5, несмотря на свою простоту, представлялась многим криптологам как поле для возможных усовершенствований. Соответственно, появилось множество известных вариантов алгоритма RC5, в которых преобразования в «пол-раундах» классического RC5 несколько изменены:

1. Алгоритм RC5XOR, в котором сложение с ключом раунда по модулю заменено операцией XOR (рис.4):

. (38)

Данный алгоритм оказался менее стоек, чем RC5, как к линейному, так и к дифференциальному криптоанализу.

2. Алгоритм RC5P, в котором сложение левого и правого обрабатываемых субблоков операцией XOR заменено сложением по модулю (рис. 4):

. (39)

Алгоритм оказался так же стоек, как и RC5, против линейного криптоанализа, но значительно слабее против дифференциального.

Рис.4. Раунды алгоритмов RC5XOR и RC5P

3. Алгоритм RC5PFR, отличающийся от RC5 циклическим сдвигом на фиксированное, а не переменное число битов (рис.5):

, (40)

где – число битов циклического сдвига, которое может быть различным в различных раундах алгоритма; в этом случае последовательность является дополнительным параметром алгоритма.

Данный вариант алгоритма RC5 не является хорошо изученным, однако эксперты предполагают, что алгоритм RC5PFR нестоек против дифференциального криптоанализа.

4. Алгоритм RC5KFR, в котором число битов сдвига является функцией ключа шифрования KC, т.е. для каждого ключа шифрования число битов сдвига является фиксированным (может быть различным для разных раундов алгоритма) (рис. 5):

, (41)

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

Рис. 5. Раунды алгоритмов RC5PFR и RC5KFR

Алгоритм RC5RA, в котором выполняется циклический сдвиг на переменное число битов, определяемое не значением младших битов другого субблока, а некоей функцией f(), обрабатывающей в качестве входного значения все биты другого субблока:

. (42)

И этот вариант алгоритма еще недостаточно изучен, но существует мнение, что алгоритм RC5RA может быть еще сильнее, чем RC5, против известных методов криптоанализа.

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