Алгоритмы TEA, ХТЕА и их варианты

Одно из наиболее интересных семейств алгоритмов блочного симметричного шифрования — это алгоритмы семейства TEA (Tiny Encryption Algorithm, «крошечный алгоритм шифрования»). Они разработаны в 1990-х гг. Дэвидом Уилером (David J. Wheeler) и Роджером Нидэмом (Roger М. Needham) из компьютерной лаборатории Кембриджского Университета.

Все алгоритмы семейства TEA отличает простота реализации и относительно высокая криптостойкость. Начнем рассмотрение этих алгоритмов с описания алгоритма TEA.

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

Как видно из описания, алгоритм действительно максимально прост в реализации; он основан только на операциях XOR, циклического сдвига на фиксированное число битов, а также модульного сложения и вычитания. Все эти операции могут быть легко реализованы на любой платформе. Авторы алгоритма признают, что есть и более простые, и более скоростные алгоритмы шифрования, однако, по их мнению, алгоритм TEA является «лучшим компромиссом между стойкостью, простотой реализации ... и производительностью». Криптоанализ алгоритма TEA
Алгоритм TEA вызвал достаточно большой интерес у криптологического сообщества. До сих пор периодически появляются различные работы, посвященные его криптоанализу.

Одна из первых таких работ — известная работа Джона Келси, Брюса Шнай-ера и Дэвида Вагнера, посвященная криптоанализу ряда алгоритмов с помощью связанных ключей. Ее авторы предложили 3 атаки на полнораун-довый алгоритм TEA методом дифференциального криптоанализа на связанных ключах. Наиболее эффективная из них требует наличия 223 выбранных открытых текстов и соответствующих им шифртекстов (зашифрованных на искомом ключе и одном связанном с ним ключе). Алгоритм вскрывается вы-полнением около 2 операций шифрования.

Кроме того, для алгоритма TEA обнаружены классы эквивалентных ключей: каждый ключ имеет по 3 эквивалентных ключа, полученных инверсией старших битов К[0] и/или К[1]. Таким образом, вместо 2 различных ключей TEA имеет 2126 классов эквивалентных ключей. Благодаря этому алгоритм не может быть использован для построения функций хэширования. Данное свойство алгоритма было успешно использовано хакерами при взломе игровой консоли Microsoft Xbox, в которой TEA использовался именно в качестве основы для хэш-функции.

Ряд исследований статистических свойств алгоритма выполнила группа специалистов из Университета г. Мадрид; в частности, работа посвящена методике, позволяющей отличить от случайной последовательности шифртекст, полученный с помощью алгоритма TEA.

Группа корейских специалистов из Университета г. Сеул предложила несколько атак на алгоритм TEA с уменьшенным количеством раундов:
11-раундовый TEA вскрывается методом невозможных дифференциалов при наличии 252,5 выбранных открытых текстов путем применения 285 операций шифрования;
несколько позже атака была распространена и на 12-раундовый TEA. Были исследованы и некоторые модификации алгоритма TEA.

Фаузан Мирза (Fauzan Mirza) из Университета Royal Holloway (Лондон) предложил в работе крайне упрощенный вариант алгоритма TEA — Simplified TEA (STEA), функция раунда которого выполняет лишь операцию XOR над обрабатываемым субблоком и используемым фрагментом ключа; алгоритм STEA оказался подвержен множеству атак, что никак не распространяется на алгоритм TEA, поскольку его функция раунда несравнимо сложнее.

Роджер Флеминг (Roger Fleming) исследовал вариант алгоритма TEA, в котором отсутствовала модификация переменной Г, т. е. Т была константой (конкретное значение не важно). Данный вариант вскрывается с помощью сдвиговой атаки (впоследствии предложенной для ряда алгоритмов), для которой требуется 232 известных открытых текстов и 298 операций шифрования. Данная атака также не применима к оригинальному алгоритму TEA.

Интересный обзор алгоритмов семейства TEA и атак на них, а также исследование статистических свойств этих алгоритмов выполнил студент Университета штата Алабама Викрам Редди Андем (Vikram Reddy Andem). Не менее интересный обзор можно найти на Web-странице Мэтью Рассела (Matthew Russell). Выводы исследователей таковы: за исключением атак на связанных ключах, TEA не имеет серьезных проблем с криптостойкостью. Тем не менее, авторы алгоритма предложили алгоритм ХТЕА (Extended TEA), в котором усилена процедура расширения ключа с целью противодействия подобным атакам.