|
Достоинствами шифра являются его простота в реализации, небольшой размер кода и довольно высокая скорость выполнения, а также возможность оптимизации выполнения на стандартных 32-битных процессорах, так как в качестве основных операций используются операции [[Сложение по модулю 2|исключающего «ИЛИ» (XOR)]], [[битовый сдвиг|побитового сдвига]] и сложения по модулю 2<sup>32</sup>. Поскольку алгоритм не использует таблиц подстановки и раундовая функция довольно проста, алгоритму требуется не менее 16 циклов (32 раундов) для достижения эффективной диффузии, хотя полная диффузия достигается уже за 6 циклов (12 раундов).<ref name="teasite" />
Алгоритм имеет отличную устойчивость к [[Линейный криптоанализ|линейному криптоанализу]] и довольно хорошую к [[Дифференциальный криптоанализ|дифференциальному криптоанализу]]. Главным недостатком этого алгоритма шифрования является его уязвимость к атакам "«на связанных ключах"» ({{lang-en|Related-key attack}}). Из-за простого расписания ключей каждый ключ имеет 3 эквивалентных ключа. Это означает, что эффективная длина ключа составляет всего 126 бит<ref name="kelsey1996">{{cite journal |
first = John |
last = Kelsey |
Исходный текст разбивается на блоки по 64 бита каждый. 128-битный ключ К делится на четыре 32-битных подключа K[0], K[1], K[2] и K[3]. На этом подготовительный процесс заканчивается, после чего каждый 64-битный блок шифруется на протяжении 32 циклов (64 раундов) по нижеприведённому алгоритму.<ref name="differential">Seokhie Hong, Deukjo Hong, Youngdai Ko, Donghoon Chang, Wonil Lee, Sangjin Lee, (2003). [http://www.springerlink.com/content/n4exvw35x7g8t6pb/fulltext.pdf Differential Cryptanalysis of TEA and XTEA] </ref>
Предположим, что на вход n-го раунда (для 1 ≤ n ≤ 64) поступают правая и левая часть (L<sub>n</sub>, R<sub>n</sub>), тогда на выходе n-го раунда будут левая и правая части (L<sub>n+1</sub>, R<sub>n+1</sub>), которые вычисляются по следующим правилам:
L<sub>n+1</sub> = R<sub>n</sub>.
Если n = 2 * i - — 1 для 1 ≤ i ≤ 32 (нечётные раунды), то
R<sub>n+1</sub> = L<sub>n</sub> <math>\boxplus</math> ( { [ R<sub>n</sub> <math>\ll</math> 4 ] <math>\boxplus</math> K[0] } <math>\oplus</math> { R<sub>n</sub> <math>\boxplus</math> i * δ } <math>\oplus</math> { [ R<sub>n</sub> <math>\gg</math> 5 ] <math>\boxplus</math> K[1] } )
Если n = 2 * i для 1 ≤ i ≤ 32 (чётные раунды), то
R<sub>n+1</sub> = L<sub>n</sub> <math>\boxplus</math> ( { [ R<sub>n</sub> <math>\ll</math> 4 ] <math>\boxplus</math> K[2] } <math>\oplus</math> { R<sub>n</sub> <math>\boxplus</math> i * δ } <math>\oplus</math> { [ R<sub>n</sub> <math>\gg</math> 5 ] <math>\boxplus</math> K[3] } )
Где
* X <math>\boxplus</math> Y – — операция сложения чисел X и Y по модулю 2<sup>32</sup>.
* X <math>\oplus</math> Y – — побитовое [[Сложение по модулю 2|исключающее «ИЛИ» (XOR)]] чисел X и Y, которое в [[Си (язык программирования)|языке программирования Си]] обозначается как X ^ Y
* X <math>\ll</math> Y и X <math>\gg</math> Y - — операции [[битовый сдвиг|побитового сдвига]] числа X на Y бит влево и вправо соответственно.
* Константа δ была выведена из [[Золотое сечение|Золотого сечения]] δ = (<math>\sqrt{5}</math> + 1) * 2<sup>31</sup> = 2654435769 = 9E3779B9<sub>h</sub><ref name="tea" />. В каждом раунде константа умножается на номер цикла i. Это было сделано для предотвращения простых атак, основанных на симметрии раундов.
Также очевидно, что в алгоритме шифрования TEA нет как такового алгоритма расписания ключей. Вместо этого в нечётных раундах используются подключи К[0] и К[1], в чётных – — К[2] и К[3].
Т.к.Так как это блочный шифроалгоритм, где длина блока 64-бит, а длина данных может быть не кратна 64-битам, значения всех байтов дополняющих блок до кратности в 64-бит устанавливается в 0x01 .
== Реализация ==
Комментарии:
* v — исходный текст состоящий из двух частей по 32 бита
* k — ключ состоящий из четырёх 32-битных частей
Изменения по сравнению с оригинальным кодом:
=== Атаки на связанных ключах ===
Алгоритм наиболее уязвим к "«атакам на связанных ключах"» ({{lang-en|Related-key attack}}), из-за простого расписания ключей (в т.ч.том числе отсутствия алгоритма расписания ключей как такового). Существуют как минимум три известные атаки данного типа, они были представлены в работе Джона Келси (''John Kelsea''), Брюса Шнайера (''Bruce Sсhneier'') и Дэвида Вагнера (''David Wagner'') в [[1997 год]]у <ref name="kelsey1997">{{cite journal |
first = John |
last = Kelsey |
journal = Lecture Notes in Computer Science |
volume = 1334 | pages = 233–246 | date = 1997 |
doi = 10.1007/BFb0028479}}</ref>. Наиболее простые из них дают дифференциальную характеристику с вероятностью 2<sup>-32−32</sup> после 32 циклов алгоритма, поэтому требуется не менее 2<sup>34</sup> выбранных открытых текстов для нахождения [[Дифференциальный криптоанализ|дифференциальной характеристики]] с вероятностью 1 и определения всех бит ключа. Более сложная в реализации атака, сочетающая в себе идеи "«атаки на связанных ключах"» Эли Бихама (''Eli Biham'') <ref name="relatedkey">Eli Biham, Computer Science Department, Technion - — Israel Institute of Technology, Haifa 32000, Israel, (1992). [http://www.springerlink.com/content/r1381780l1466637/fulltext.pdf "«New Types of Cryptanalytic Attacks Using Related Keys"»]</ref> и [[Дифференциальный криптоанализ|дифференциальной атаки]] даёт дифференциальную характеристику с вероятностью 2<sup>-11−11</sup>, требует всего 2<sup>23</sup> выбранных открытых текстов и время порядка 2<sup>32</sup> времён шифрования (т.е.то есть требует количество битовых операций порядка 2<sup>32</sup>).
=== Дифференциальный криптоанализ ===
Было обнаружено, что TEA довольно устойчив к [[Дифференциальный криптоанализ|дифференциальному криптоанализу]]. Атака на 10 раундов TEA требует 2<sup>52.5</sup> выбранных открытых текстов и имеет временную сложность 2<sup>84</sup> <ref name="impossible">{{cite journal | first = Dukjae | last = Moon | coauthors = Hwang, Kyungdeok; Lee, Wonil; Lee, Sangjin; Lim, Jongin | title = Impossible differential cryptanalysis of reduced round XTEA and TEA | journal = Lecture Notes in Computer Science | volume = 2365 | pages = 49–60 | date = 2002 | url = http://www.iacr.org/archive/fse2002/23650050/23650050.pdf | doi = 10.1007/3-540-45661-9_4}}</ref>. Лучший результат – — криптоанализ 17 раундов TEA<ref name=autogenerated1>{{cite journal | first = Seokhie | last = Hong | coauthors = Hong, Deukjo; Ko, Youngdai; Chang, Donghoon; Lee, Wonil; Lee, Sangjin | title = Differential cryptanalysis of TEA and XTEA | url = http://www.springerlink.com/content/n4exvw35x7g8t6pb/fulltext.pdf |journal = In Proceedings of ICISC 2003 | date = 2003}}</ref>. Данная атака требует всего 1920 выбранных открытых текстов, однако имеет временную сложность 2<sup>123.37</sup>.
=== Эквивалентные ключи ===
Ещё одна проблема алгоритма TEA – — наличие эквивалентных ключей. Было показано, что каждый ключ имеет три ему эквивалентных<ref name="cryptoanalisys" />. Это означает, что эффективная длина ключа имеет всего 126 бит вместо 128, задуманных разработчиками, поэтому TEA нежелательно использовать в качестве [[Хеширование|хэш-функции]], что было отражено в книге Эндрю Хуанга (''Andrew Huang'') ''"«Hacking the Xbox: an introduction to reverse engineering"»'' на примере взлома игровой приставки ''Microsoft Xbox''.
Таблица эквивалентных ключей:
== Расширения алгоритма ==
Выявление ряда серьезных уязвимостей и слабых мест в исходном алгоритме TEA привело к скорому созданию его расширений. Основными отличиями всех этих алгоритмов являются усовершенствованное расписание ключей, динамическая зависимость ключа от текста, а также другой размер ключа, входного блока и/или количество раундов сети Фейстеля.
==== XTEA ====
[[XTEA]] имеет размер блока, равный 64 битам, размер ключа – — 128 битам, количество раундов [[Сеть Фейстеля|сети Фейстеля]] равно 64. Алгоритм был разработан Дэвидом Уилером и Роджером Нидхэмом и опубликован в [[1997 год]]у. Главное отличие от исходного алгоритма TEA – — наличие алгоритма расписания ключей, что позволило устранить критическую уязвимость к "«атакам на связанных ключах"», но привело к ухудшению стойкости к [[Дифференциальный криптоанализ|дифференциальному криптоанализу]]<ref name=autogenerated1 />. Существуют три модификации этого алгоритма, разработанные Томом Дэнисом (''Tom Denis'')<ref name="extended">Tom St Denis. [http://tomstdenis.tripod.com/xtea.pdf Extended TEA Algorithms]</ref>: [[XTEA]]-1 (размер блока – — 64 бита, размер ключа – — 128 бит, количество раундов [[Сеть Фейстеля|сети Фейстеля]] – — 32), [[XTEA]]-2 (размер блока – — 128 бит, размер ключа – — 128 бит, количество раундов [[Сеть Фейстеля|сети Фейстеля]] - — 64) и [[XTEA]]-3 (размер блока – — 128 бит, размер ключа – — 256 бит, количество раундов [[Сеть Фейстеля|сети Фейстеля]] - — 64).
==== XXTEA ====
В [[1998 год]]у было опубликовано следующее расширение алгоритма, получившее название [[XXTEA]]. Размер ключа – — 128 бит. Отличительной особенностью является возможность шифрования любых блоков, длина которых кратна 64 битам, количество раундов равно 52 + 6*(количество 32-битных слов в блоке) или 52 + 12*M при длине блока 64*M бит. Практическая эффективность опубликованной анонимно дифференциальной атаки не доказана<ref>[http://cipherdev.org/break-xxtea.c.txt Исходная статья с реализацией атаки на XXTEA и примером кода]</ref>.
==== RTEA ====
Существует так же альтернативная модификация алгоритма TEA, получившая наименование [[RTEA]], разработанная в [[2007 год]]у ''“Marcos«Marcos el Ruptor”Ruptor»''. Размер блока – — 64 бита; для 128-битного ключа число раундов [[Сеть Фейстеля|сети Фейстеля]] равно 48, для 256-битного - — 64. По заявлениям разработчиков этот алгоритм производительнее и более устойчив к криптоанализу<ref name="rteatests">[http://defectoscopy.com/results.html Сравнительные результаты устойчивости симметричных криптоалгоритмов]{{lang-en|}}</ref>, чем XTEA, однако и на этот алгоритм уже существует "«атака на связанных ключах"»<ref name="rka">[http://0x9e3779b9.org/break-rtea-2.c.txt A related key attack for RTEA.]</ref>.
==== Raiden ====
! Название алгоритма || Стандартное количество раундов сети Фейстеля|| Размер блока || Размер ключа
|-
| TEA || 64 || 64 бита || 128 бит
|-
| XTEA || 64 || 64 бита || 128 бит
|-
| XTEA-1 || 32 || 64 бита || 128 бит
|-
| XTEA-2 || 64 || 128 бит || 128 бит
|-
| XTEA-3 || 64 || 128 бит || 256 бит
|-
| XXTEA || 52 + 12 * M || 64 * M бит || 128 бит
|-
| RTEA || 48 или 64 || 64 бита || 128 или 256 бит
|-
| Raiden || 32 || 64 бита || 128 бит
|}
* В то же время, авторы алгоритма TEA на своей официальной странице<ref name="teasite" /> обращают внимание на то, что в реальных условиях практического использования алгоритм TEA все еще остается довольно надежным и все найденные уязвимости, как правило, не являются критичными, к примеру, при передаче данных в реальном времени.
== Ссылки ==
* [http://143.53.36.235:8080/tea.htm Страница алгоритма шифрования TEA]
* Roger M. Needham and David J. Wheeler. "«TEA, a Tiny Encryption Algorithm"»[http://www.cix.co.uk/~klockstone/tea.pdf (PDF)]
* Andew Hang. "«Hacking the Xbox: an introduction to reverse engineering"»[http://books.google.ru/books?id=FdPNE6beKcMC&pg=PA109&dq=Tiny+TEA+algorithm&lr=#v=onepage&q=Tiny%20TEA%20algorithm&f=false]
* Журнал "«Хакер Онлайн"», TEA: блочный шифр своими руками, (2004)[http://www.xakep.ru/post/22086/default.asp]
* Paris Kitsos,Yan Zhang. "«RFID Security: Techniques, Protocols and System-On-Chip Design"»[http://books.google.ru/books?id=WIF7h9OYT34C&pg=PA426&dq=Tiny+TEA+implementation#v=onepage&q=Tiny%20TEA%20implementation&f=false]
* David J. Wheeler and Roger M. Needham. «Correction to xtea.» Technical report, Computer Laboratory, University of Cambridge, October 1998 [http://www.movable-type.co.uk/scripts/xxtea.pdf (PDF)].
* Roger M. Needham and David J. Wheeler. «Tea extensions.» Technical report, Computer Laboratory, University of Cambridge, October 1997 [http://www.movable-type.co.uk/scripts/xtea.pdf (PDF)].
| 