Меню Главная Случайная статья Настройки XXTEA Материал из https://ru.wikipedia.org XXTEA — криптографический алгоритм, реализующий блочное симметричное шифрование и представляющий собой сеть Фейстеля. Является расширение алгоритма Block TEA. Разработан и опубликован Дэвидом Уилером[англ.] и Роджером Нидхемом в 1998 году. Выполнен на простых и быстрых операциях: XOR, подстановка, сложение.[1][2] Содержание 1 История 2 Особенности 3 Описание работы алгоритма 4 Криптоанализ 4.1 Первый подход 4.2 Второй подход 4.3 Восстановление ключа 5 Примечания 6 Литература История На симпозиуме Fast Software Encryption в декабре 1994 года Дэвид Уилер и Роджер Нидхэм, профессора Компьютерной Лаборатории Кембриджского Университета[англ.], представили новый криптографический алгоритм TEA. Данный алгоритм проектировался как альтернатива DES, который к тому моменту уже считался устаревшим.[3][4] Позже в 1996 году в ходе личной переписки Дэвида Уилера с Дэвидом Вагнером была выявлена уязвимость для атаки на связанных ключах, которая была официально представлена в 1997 году на Первой Международной Конференции ICIS группой учёных, состоявшей из Брюса Шнайера, Джона Келси и Дэвида Вагнера.[5][6] Данная атака послужила основанием для улучшения алгоритма TEA, и в октябре 1996 года Уилер и Нидхэм опубликовали внутренний отчет лаборатории, в котором приводилось два новых алгоритма: XTEA и Block TEA.[7] 10 октября 1998 года группа новостей sci.crypt.research опубликовала статью Маркку-Юхани Сааринена, в которой была найдена уязвимость Block TEA на стадии дешифрования[4]. В том же месяце Дэвид Уилер и Роджер Нидхэм опубликовали внутренний отчёт лаборатории, в котором приводилось улучшение алгоритма Block TEA — XXTEA.[8] Особенности XXTEA, как и остальные шифры семейства TEA, обладает рядом отличительных особенностей по сравнению с аналогичными шифрами: Высокая скорость работы Малое потребление памяти Простая программная реализация Относительно высокая надёжность.[9][10][11][4] Описание работы алгоритма Исходный текст разбивается на слова по 32 бита каждый, из полученных слов формируется блок. Ключ также разбивают на 4 части, состоящие из слов по 32 бита каждый, и формируют массив ключей. В ходе одного раунда работы алгоритма шифруется одно слово из блока. После того, как были зашифрованы все слова, заканчивается цикл, и начинается новый. Количество циклов зависит от количества слов и равно ${\displaystyle 6+52/n}$, где ${\displaystyle n}$ — количество слов. Шифрование одного слова состоит в следующем: Над левым соседом выполняется операция битового сдвига влево на два, а над правым операция битового сдвига вправо на пять. Над полученными значениями выполняют операцию побитового сложения по модулю 2. Над левым соседом выполняется операция битового сдвига вправо на три, а над правым операция битового сдвига влево на 4. Над полученными значениями выполняют операцию побитового сложения по модулю 2 Полученные числа складывают по модулю 232. Константа , выведенная из Золотого сечения = (${\displaystyle {\sqrt {5}}}$ — 1) * 231 = 2654435769 = 9E3779B9h[3], умножается на номер цикла(это было сделано для предотвращения простых атак, основанных на симметрии раундов). Полученное в предыдущем пункте число складывают побитово по модулю 2 с правым соседом. Полученное в 4 пункте число сдвигают побитово направо на 2, складывают побитово по модулю два с номером раунда и находят остаток от деления на 4. С помощью полученного числа выбирают ключ из массива ключей. Выбранный в предыдущем раунде ключ складывают побитово по модулю 2 с левым соседом. Числа, полученные в предыдущем и 4 пунктах, складывают по модулю 232. Числа, полученные в предыдущем и 3 пунктах, складывают побитово по модулю 2, данную сумму складывают с шифруемым словом по модулю 232. Криптоанализ На данный момент существует атака на основе адаптивно подобранного открытого текста, опубликованная Элиас Яаррков в 2010 году. Существует два подхода, в которых используется уменьшение количества циклов за счет увеличения количества слов. Первый подход Пусть у нас есть некий открытый текст. Возьмем из него 5 неких слов, начиная с ${\displaystyle r}$, которые мы шифруем с ${\displaystyle r+1}$. Прибавим какое-нибудь число к ${\displaystyle r+2}$, и получим новый открытый текст. Теперь выполним первый цикл шифрования для этих текстов. Если после шифрования разница осталась только в данном слове, то продолжаем шифрование. Если начали появляться разницы в других словах, то начинаем поиск заново либо меняя исходный, либо пытаясь подобрать другую разницу. Сохранение разницы только в одном слове возможно, так как функция шифрования не биективна для каждого соседа. Элиас Яаррков провел ряд экспериментов и выяснил, что вероятность прохождения разности ${\displaystyle \Delta =13}$ 5 полных циклов давала вероятность между ${\displaystyle 2}$${\displaystyle -109}$ и ${\displaystyle 2}$${\displaystyle -110}$ для большинства ключей, то есть если пара текстов прошла 5 из 6 полных циклов, то её можно считать верной, так как если поместить разницу в конец блока, будут возникать разницы в большинстве слов. Данная атака была проведена и был восстановлен ключ для алгоритма с количеством циклов уменьшенным до трёх. Второй подход Второй подход отличается от первого тем, что после первого раунда шифрования ${\displaystyle r+1}$ слова, разница должна перейти в него самого из ${\displaystyle r+2}$ слова, при этом разница может измениться, а после следующего раунда шифрования разница вернется в ${\displaystyle r+2}$ слово и станет равна изначальному, но изменит знак. После проведения оценки данного метода, Элиас Яаррков получил, что для успешного нахождения правильной пары достаточно 259 текстов, причем разница должна лежать в интервале ${\displaystyle [-d;d]}$, где ${\displaystyle d=32}$, причем увеличение d не улучшило результатов. После была проведена успешная атака на XXTEA с количеством циклом, уменьшенным до 4, и правильная пара была получена с помощью 235 пар текстов, а предыдущая оценка даёт необходимость в 234.7 пар текстов. Восстановление ключа Зная правильную пару текстов, достаточно прогнать алгоритм в обратном порядке, так как теперь нам известно все кроме ключа. [2][12] Примечания Wheeler et al, 1998. 1 2 Yarrkov, 2010. 1 2 Wheeler et al, 1994. 1 2 3 Saarinen, 1998. Kelsey et al, 1997. ICIS, 1997. Wheeler et al, 1996. Wheeler et al, 1998. Sima et al, 2012. Cenwei, 2008. Yarrkov, 2010. Sima et al, 2012. Литература David J. Wheeler, Roger M. Needham. Correction to XTEA (англ.). — 1998. — Октябрь. E. Yarrkov. Cryptanalysis of XXTEA (англ.). — 2010. — 4 Май. Saarinen M.-J. Cryptanalysis of Block Tea (англ.). — 1998. — 20 Октябрь. David J. Wheeler, Roger M. Needham. TEA, a tiny encryption algorithm (англ.). — 1994. — Декабрь. David J. Wheeler, Roger M. Needham. TEA extensions (англ.). — 1996. — Октябрь. J. Kelsey, B. Schneier and D. Wagner. Related-key cryptanalysis of 3-WAY, Biham-DES,CAST, DES-X, NewDES, RC2, and TEA (англ.). — 1997. — Ноябрь. Mao Cenwei. Comparison of a Few Small Ciphers Applicable to RFID (англ.). — 2008. — Июнь. I. Sima, D. Tarmurean и V. Greu. XXTEA, an alternative replacement of KASUMI cipher algorithm in A5/3 GSM and f8, f9 UMTS data security functions (англ.). — 2012. — Июнь. First International Conference, ICIS'97, Beijing, China, November 11-14, 1997, Proceedings / Editors: Yongfei Han, Tatsuaki Okamoto, Sihan Quing. — 1. — Springer-Verlag Berlin Heidelberg, 1997. — (Lecture Notes in Computer Science). — ISBN 978-3-540-63696-0.