Эта статья является кандидатом в добротные статьи

XXTEA

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
XXTEA
Создатель:

Дэвид Вилер и Роджер Ниидхэм

Создан:

1998 г.

Опубликован:

1998 г.

Размер ключа:

128 бит

Размер блока:

бит, где - количество слов, не меньшее 2

Число раундов:

, где - количество слов

Тип:

Сеть Фейстеля

XXTEA — криптографический алгоритм, реализующий блочное симметричное шифрование и представляющий собой сеть Фейстеля. Является расширение алгоритма Block TEA. Разработан и опубликован Дэвид Уилер[en] и Роджером Ниидхэмом в 1998 году. Выполнен на простых и быстрых операциях: XOR, подстановка, сложение.[1][2]

История[править | править вики-текст]

На симпозиуме Fast Software Encryption[en] в декабре 1994 года Дэвид Уилер и Роджер Нидхэм, профессоры Компьютерной Лаборатории Кембриджского Университета[en], представили новый криптографический алгоритм TEA. Данный алгоритм проектировался как альтернатива DES, который к тому моменту уже считался устаревшим.[3][4]

Позже в 1996 году в ходе личной переписки Дэвида Уилера с Дэвидом Вагнером была выявлена уязвимость к атаке на связанных ключах, которая была официально представлена в 1997 году на Первой Международной Конференции ICIS группой ученых, состоявшей из Брюса Шнайера, Джона Келси и Дэвида Вагнера.[5][6] Данная атака послужила основанием для улучшения алгоритма TEA, и в октябре 1996 года Уилер и Нидхэм опубликовали внутренний отчет лаборатории, в котором приводилось два новых алгоритма: XTEA и Block TEA.[7]

10 октября 1998 года группа новостей sci.crypt.research опубликовала статью Маркку-Юхани Сааринена, в которой была найдена уязвимость Block TEA на стадии дешифрования[4]. В том же месяце Дэвид Уилер[en] и Роджер Нидхэм опубликовали внутренний отчет лаборатории[en], в котором приводилось улучшение алгоритма Block TEA - XXTEA.[8]

Особенности[править | править вики-текст]

XXTEA, как и остальные шифры семейства TEA, обладает рядом отличительных особенностей по сравнению с аналогичными шифрами:

  • Высокая скорость работы
  • Малое потребление памяти
  • Простая программная реализация
  • Относительно высокая надежность[9][10][11][4]

Описание работы алгоритма[править | править вики-текст]

Схема алгоритма шифрования XXTEA

Исходный текст разбиваается на слова по 32 бита каждый, из полученных слов формируется блок. Ключ также разбивают на 4 части, состоящие из слов по 32 бита каждый, и формируют массив ключей. В ходе одного раунда работы алгоритма шифруется одно слово из блока. После того, как были зашифрованы все слова, заканчивается цикл, и начинается новый. Количество циклов зависит от количества слов и равно , где - количество слов. Шифрование одного слова состоит в следующем:

  1. Над левым соседом выполняется операция битового сдвига влево на два, а над правым операция битового сдвига вправо на пять. Над полученными значениями выполняют операцию побитового сложения по модулю 2.
  2. Над левым соседом выполняется операция битового сдвига вправо на три, а над правым операция битового сдвига влево на 4. Над полученными значениями выполняют операцию побитового сложения по модулю 2
  3. Полученные числа складывают по модулю 232.
  4. Константа δ, выведенную из Золотого сечения δ = ( - 1) * 231 = 2654435769 = 9E3779B9h[3] умножается на номер цикла(это было сделано для предотвращения простых атак, основанных на симметрии раундов).
  5. Полученное в предыдущем пункте число складывают побитово по модулю 2 с правым соседом.
  6. Полученное в 4 пункте число сдвигают побитово направо на 2, складывают побитово по модулю два с номером раунда, и находят остаток от деления на 4. С помощью полученного числа выбирают ключ из массива ключей.
  7. Выбранный в предыдущем раунде ключ складывают побитово по модулю 2 с левым соседом.
  8. Числа, полученные в предыдущем и 4 пунктах складывают по модулю 232.
  9. Числа, полученные в предыдущем и 3 пунктах складывают побитово по модулю 2, данную сумму складывают с шифруемым словом по модулю 232.

Криптоанализ[править | править вики-текст]

На данный момент существует атака на основе адаптивно подобранного открытого текста, опубликованная Элиас Яаррков в 2010 году. Существует два подхода, в которых используется уменьшение количества циклов за счет увеличения количества слов.

Первый подход[править | править вики-текст]

Схема первого подхода дифференциального криптоанализа XXTEA

Пусть у нас есть некий открытый текст. Возьмем из него 5 неких слов, начиная с , которые мы шифруем с . Прибавим какое-нибудь число к , и получим новый открытый текст. Теперь выполним первый цикл шифрования для этих текстов. Если после шифрования разница осталась только в данном слове, то продолжаем шифрование. Если начали появляться разницы в других словах, то начинаем поиск заново либо меняя исходный, либо пытаясь подобрать другую разницу. Сохранение разницы только в одном слове возможно, т.к. функция шифрования не биективна для каждого соседа. Элиас Яаррков провел ряд экспериментов и выяснил, что вероятность прохождения разности 5 полных циклов давала вероятность между и для большинства ключей, то есть если пара текстов прошла 5 из 6 полных циклов, то её можно считать верной, т.к. если поместить разницу в конец блока, будут возникать разницы в большинстве слов. Данная атака была проведена и был восстановлен ключ для алгоритма с количеством циклов уменьшенным до трёх.

Второй подход[править | править вики-текст]

Схема второго подхода дифференциального криптоанализа XXTEA

Второй подход отличается от первого тем, что после первого раунда шифрования слова, разница должна перейти в него самого из слова, при этом разница может изменится, а после следующего раунда шифрования разница вернется в слово и станет равна изначальному, но изменит знак. После проведения оценки данного метода, Элиас Яаррков получил, что для успешного нахождения правильной пары достаточно 259 текстов, причем разница должна лежать в интервале , где , причем увеличение d не улучшило результатов. После была проведена успешная атака на XXTEA с количеством циклом уменьшенным до 4, и правильная пара была получена с помощью 235 пар текстов, а предыдущая оценка даёт необходимость в 234.7 пар текстов.

Восстановление ключа[править | править вики-текст]

Зная правильную пару текстов, достаточно прогнать алгоритм в обратном порядке, т.к. теперь нам известно все кроме ключа. [2][12]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]