TEA

У этого термина существуют и другие значения, см. TEA (значения).

TEA

Создатель |  Дэвид Уилер и Роджер Нидхэм
Создан |  1994 г.
Опубликован |  1994 г.
Размер ключа |  128 бит
Размер блока |  64 бит
Число раундов |  64 (32 цикла)
Тип |  Сеть Фейстеля

В криптографии Tiny Encryption Algorithm (TEA)[1] — блочный алгоритм шифрования типа «Сеть Фейстеля». Алгоритм был разработан на факультете компьютерных наук Кембриджского университета Дэвидом Уилером[англ.] (David Wheeler) и Роджером Нидхэмом (Roger Needham) и впервые представлен в 1994 году[2] на симпозиуме по быстрым алгоритмам шифрования в Лёвене (Бельгия).

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

## Содержание

* 1 Свойства
* 2 Описание алгоритма
* 3 Реализация
* 4 Криптоанализ
* 4.1 Атаки на связанных ключах
* 4.2 Дифференциальный криптоанализ
* 4.3 Эквивалентные ключи
* 5 Расширения алгоритма
* 5.1 XTEA
* 5.2 XXTEA
* 5.3 RTEA
* 5.4 Raiden
* 5.5 Сравние различных версий расширения алгоритма TEA
* 6 См. также
* 7 Примечания
* 8 Ссылки

## Свойства

[править | править код]

Алгоритм шифрования TEA[1] основан на битовых операциях с 64-битным блоком, имеет 128-битный ключ шифрования. Стандартное количество раундов сети Фейстеля равно 64 (32 цикла), однако, для достижения наилучшей производительности или шифрования, число циклов можно варьировать от 8 (16 раундов) до 64 (128 раундов). Сеть Фейстеля несимметрична из-за использования в качестве операции наложения сложения по модулю 232.

Достоинствами шифра являются его простота в реализации, небольшой размер кода и довольно высокая скорость выполнения, а также возможность оптимизации выполнения на стандартных 32-битных процессорах, так как в качестве основных операций используются операции исключающего «ИЛИ» (XOR), побитового сдвига и сложения по модулю 232. Поскольку алгоритм не использует таблиц подстановки и раундовая функция довольно проста, алгоритму требуется не менее 16 циклов (32 раундов) для достижения эффективной диффузии, хотя полная диффузия достигается уже за 6 циклов (12 раундов).[1]

Алгоритм имеет отличную устойчивость к линейному криптоанализу и довольно хорошую к дифференциальному криптоанализу. Главным недостатком этого алгоритма шифрования является его уязвимость для атак «на связанных ключах» (англ. Related-key attack). Из-за простого расписания ключей каждый ключ имеет 3 эквивалентных ключа. Это означает, что эффективная длина ключа составляет всего 126 бит[3][4], поэтому данный алгоритм не следует использовать в качестве хеш-функции.

## Описание алгоритма

[править | править код]

Исходный текст разбивается на блоки по 64 бита каждый. 128-битный ключ К делится на четыре 32-битных подключа K[0], K[1], K[2] и K[3]. На этом подготовительный процесс заканчивается, после чего каждый 64-битный блок шифруется на протяжении 32 циклов (64 раундов) по нижеприведённому алгоритму.[5]

Предположим, что на вход n-го раунда (для 1 ≤ n ≤ 64) поступают правая и левая часть (Ln, Rn), тогда на выходе n-го раунда будут левая и правая части (Ln+1, Rn+1), которые вычисляются по следующим правилам:

Ln+1 = Rn.

Если n = 2 * i — 1 для 1 ≤ i ≤ 32 (нечётные раунды), то Rn+1 = Ln ⊞ {\displaystyle \boxplus } ({ [ Rn ≪ {\displaystyle \ll } 4 ]  ⊞ {\displaystyle \boxplus } K[0] }  ⊕ {\displaystyle \oplus } { Rn ⊞ {\displaystyle \boxplus } i * δ }  ⊕ {\displaystyle \oplus } { [ Rn ≫ {\displaystyle \gg } 5 ]  ⊞ {\displaystyle \boxplus } K[1] })

Если n = 2 * i для 1 ≤ i ≤ 32 (чётные раунды), то Rn+1 = Ln ⊞ {\displaystyle \boxplus } ({ [ Rn ≪ {\displaystyle \ll } 4 ]  ⊞ {\displaystyle \boxplus } K[2] }  ⊕ {\displaystyle \oplus } { Rn ⊞ {\displaystyle \boxplus } i * δ }  ⊕ {\displaystyle \oplus } { [ Rn ≫ {\displaystyle \gg } 5 ]  ⊞ {\displaystyle \boxplus } K[3] })

Где

* X  ⊞ {\displaystyle \boxplus } Y — операция сложения чисел X и Y по модулю 232.
* X  ⊕ {\displaystyle \oplus } Y — побитовое исключающее «ИЛИ» (XOR) чисел X и Y, которое в языке программирования Си обозначается как X ^ Y
* X  ≪ {\displaystyle \ll } Y и X  ≫ {\displaystyle \gg } Y — операции побитового сдвига числа X на Y бит влево и вправо соответственно.
* Константа δ была выведена из Золотого сечения δ = ( 5 {\displaystyle {\sqrt {5}}} — 1) * 231 = 2654435769 = 9E3779B9h[2]. В каждом раунде константа умножается на номер цикла i. Это было сделано для предотвращения простых атак, основанных на симметрии раундов.

Также очевидно, что в алгоритме шифрования TEA нет как такового алгоритма расписания ключей. Вместо этого в нечётных раундах используются подключи К[0] и К[1], в чётных — К[2] и К[3].

Так как это блочный шифроалгоритм, где длина блока 64-бит, а длина данных может быть не кратна 64-битам, значения всех байтов дополняющих блок до кратности в 64-бит устанавливается в 0x01 .

## Реализация

[править | править код]

Реализация на языке программирования Си (адаптированный вариант кода, представленного в статье Дэвида Уилера и Роджера Нидхэма[2]) функций шифрования и расшифрования с использованием алгоритма TEA:

#include <stdint.h>

void encrypt( uint32_t* v, const uint32_t* k )

/* set up */
uint32_t v0 = v[0];
uint32_t v1 = v[1];
uint32_t sum = 0;
uint32_t i;

/* a key schedule constant */
uint32_t delta = 0x9e3779b9;

/* cache key */
uint32_t k0 = k[0];
uint32_t k1 = k[1];
uint32_t k2 = k[2];
uint32_t k3 = k[3];

/* basic cycle start */
for( i = 0; i < 32; ++i )

sum += delta;
v0 += ( ( v1 << 4 ) + k0 ) ^ ( v1 + sum ) ^ ( ( v1 >> 5 ) + k1 );
v1 += ( ( v0 << 4 ) + k2 ) ^ ( v0 + sum ) ^ ( ( v0 >> 5 ) + k3 );

/* end cycle */

v[0] = v0;
v[1] = v1;

void decrypt( uint32_t* v, const uint32_t* k )

/* set up */
uint32_t v0 = v[0];
uint32_t v1 = v[1];
uint32_t sum = 0xC6EF3720;
uint32_t i;

/* a key schedule constant */
uint32_t delta = 0x9e3779b9;

/* cache key */
uint32_t k0 = k[0];
uint32_t k1 = k[1];
uint32_t k2 = k[2];
uint32_t k3 = k[3];

/* basic cycle start */
for ( i = 0; i < 32; ++i )

v1 -= ( ( v0 << 4 ) + k2 ) ^ ( v0 + sum ) ^ ( ( v0 >> 5 ) + k3 );
v0 -= ( ( v1 << 4 ) + k0 ) ^ ( v1 + sum ) ^ ( ( v1 >> 5 ) + k1 );
sum -= delta;

/* end cycle */

v[0] = v0;
v[1] = v1;

Комментарии:

* v — исходный текст, состоящий из двух частей по 32 бита
* k — ключ, состоящий из четырёх 32-битных частей

Изменения по сравнению с оригинальным кодом:

* используется тип uint32_t вследствие того, что он всегда имеет размер 32 бита в отличие от long (присутствующий в оригинальном коде), который может содержать 64 бита (например в некоторых 64-битных системах)
* исходный код не использует тип const
* в исходном коде опущены избыточные скобки в выражениях для v0 и v1, в данной модификации они оставлены для большей наглядности

## Криптоанализ

[править | править код]

Предполагается, что данный алгоритм обеспечивает защищённость, сравнимую с алгоритмом шифрования IDEA, так как он использует ту же идею использования операций из ортогональных алгебраических групп.[1] Этот подход отлично защищает от методов линейного криптоанализа.

### Атаки на связанных ключах

[править | править код]

Алгоритм наиболее уязвим для «атак на связанных ключах» (англ. Related-key attack) из-за простого расписания ключей (в том числе отсутствия алгоритма расписания ключей как такового). Существуют как минимум три известные атаки данного типа, они были представлены в работе Джона Келси (John Kelsea), Брюса Шнайера (Bruce Schneier) и Дэвида Вагнера (David Wagner) в 1997 году[6]. Наиболее простые из них дают дифференциальную характеристику с вероятностью 2−32 после 32 циклов алгоритма, поэтому требуется не менее 234 выбранных открытых текстов для нахождения дифференциальной характеристики с вероятностью 1 и определения всех бит ключа. Более сложная в реализации атака, сочетающая в себе идеи «атаки на связанных ключах» Эли Бихама (Eli Biham)[7] и дифференциальной атаки, даёт дифференциальную характеристику с вероятностью 2−11, требует всего 223 выбранных открытых текстов и время порядка 232 времён шифрования (то есть требует количество битовых операций порядка 232).

### Дифференциальный криптоанализ

[править | править код]

Было обнаружено, что TEA довольно устойчив к дифференциальному криптоанализу. Атака на 10 раундов TEA требует 252,5 выбранных открытых текстов и имеет временную сложность 284[8]. Лучший результат — криптоанализ 17 раундов TEA[9]. Данная атака требует всего 1920 выбранных открытых текстов, однако имеет временную сложность 2123,37.

### Эквивалентные ключи

[править | править код]

Ещё одна проблема алгоритма TEA — наличие эквивалентных ключей. Было показано, что каждый ключ имеет три ему эквивалентных[4]. Это означает, что эффективная длина ключа имеет всего 126 бит вместо 128, задуманных разработчиками, поэтому TEA нежелательно использовать в качестве хеш-функции, что было отражено в книге Эндрю Хуанга (Andrew Huang) «Hacking the Xbox: an introduction to reverse engineering» («Взлом Xbox: введение в обратный инжиниринг») на примере взлома игровой приставки Microsoft Xbox.

Таблица эквивалентных ключей:

K[0]  | K[1]  | K[2]  | K[3]

|
|
|

K[0]  | K[1]  | K[2]  ⊕ {\displaystyle \oplus } 80000000h | K[3]  ⊕ {\displaystyle \oplus } 80000000h
K[0]  ⊕ {\displaystyle \oplus } 80000000h | K[1]  ⊕ {\displaystyle \oplus } 80000000h | K[2]  | K[3]
K[0]  ⊕ {\displaystyle \oplus } 80000000h | K[1]  ⊕ {\displaystyle \oplus } 80000000h | K[2]  ⊕ {\displaystyle \oplus } 80000000h | K[3]  ⊕ {\displaystyle \oplus } 80000000h

## Расширения алгоритма

[править | править код]

Выявление ряда серьёзных уязвимостей и слабых мест в исходном алгоритме TEA привело к скорому созданию его расширений. Основными отличиями всех этих алгоритмов являются усовершенствованное расписание ключей, динамическая зависимость ключа от текста, а также другой размер ключа, входного блока и/или количество раундов сети Фейстеля.

#### XTEA

[править | править код]

XTEA имеет размер блока, равный 64 битам, размер ключа — 128 битам, количество раундов сети Фейстеля равно 64. Алгоритм был разработан Дэвидом Уилером и Роджером Нидхэмом и опубликован в 1997 году. Главное отличие от исходного алгоритма TEA — наличие алгоритма расписания ключей, что позволило устранить критическую уязвимость для «атак на связанных ключах», но привело к ухудшению стойкости к дифференциальному криптоанализу[9]. Существуют три модификации этого алгоритма, разработанные Томом Дэнисом (Tom Denis)[10]: 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 бит. Практическая эффективность опубликованной анонимно дифференциальной атаки не доказана[11].

#### RTEA

[править | править код]

Существует также альтернативная модификация алгоритма TEA, получившая наименование RTEA, разработанная в 2007 году «Marcos el Ruptor». Размер блока — 64 бита; для 128-битного ключа число раундов сети Фейстеля равно 48, для 256-битного — 64. По заявлениям разработчиков, этот алгоритм производительнее и более устойчив к криптоанализу[12], чем XTEA, однако и на этот алгоритм уже существует «атака на связанных ключах»[13].

#### Raiden

[править | править код]

С использованием механизмов генетического программирования в 2006 году командой разработчиков во главе с Хулио Кастро (англ. Julio César Hernández Castro) был создан алгоритм Raiden, призванный устранить уязвимости шифра TEA. Он практически в точности повторяет структуру алгоритма TEA за исключением того, что у алгоритма Raiden есть расширенный алгоритм расписания ключей. Стандартное число раундов сети Фейстеля равно 32 (16 циклов). Raiden использует ключевое расписание, близкое к ГПСЧ, трансформирует ключ и генерирует подключи для каждого раунда. Шифр успешно проходит тесты Diehard, Sexton и ENT[14].

#### Сравние различных версий расширения алгоритма TEA

[править | править код]

Здесь приведена сравнительная таблица основных характеристик алгоритмов семейства TEA:

Название алгоритма | Стандартное количество раундов сети Фейстеля | Размер блока | Размер ключа

|
|
|

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 на своей официальной странице[1] обращают внимание на то, что в реальных условиях практического использования алгоритм TEA все ещё остается довольно надежным и все найденные уязвимости, как правило, не являются критичными, к примеру, при передаче данных в реальном времени.

## См. также

[править | править код]

* XTEA
* XXTEA
* RTEA
* Raiden
* Сеть Фейстеля

## Примечания

[править | править код]

1. ↑ 1 2 3 4 5 Страница шифра TEA (неопр.). Дата обращения: 25 февраля 2009. Архивировано из оригинала 12 июня 2017 года.
2. ↑ 1 2 3 Roger M. Needham and David J. Wheeler. TEA, a Tiny Encryption Algorithm Архивная копия от 13 октября 2017 на Wayback Machine
3. ↑ Kelsey, John; Schneier, Bruce; Wagner, David. Key-schedule cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES (англ.) // Lecture Notes in Computer Science : journal. — 1996. — Vol. 1109. — P. 237—251. — doi:10.1007/3-540-68697-5_19. Архивировано 8 февраля 2012 года.
4. ↑ 1 2 Andem, Vikram Reddy (2003).A cryptoanalisys of the tiny encryption algorithm Архивировано 20 апреля 2009 года.
5. ↑ Seokhie Hong, Deukjo Hong, Youngdai Ko, Donghoon Chang, Wonil Lee, Sangjin Lee, (2003). Differential Cryptanalysis of TEA and XTEA (недоступная ссылка)
6. ↑ Kelsey, John; Schneier, Bruce; Wagner, David. Related-key cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X NewDES, RC2, and TEA (англ.) // Lecture Notes in Computer Science : journal. — 1997. — Vol. 1334. — P. 233—246. — doi:10.1007/BFb0028479. Архивировано 3 декабря 2008 года.
7. ↑ Eli Biham, Computer Science Department, Technion — Israel Institute of Technology, Haifa 32000, Israel, (1992). «New Types of Cryptanalytic Attacks Using Related Keys» (недоступная ссылка)
8. ↑ Moon, Dukjae; Hwang, Kyungdeok; Lee, Wonil; Lee, Sangjin; Lim, Jongin. Impossible differential cryptanalysis of reduced round XTEA and TEA (англ.) // Lecture Notes in Computer Science : journal. — 2002. — Vol. 2365. — P. 49—60. — doi:10.1007/3-540-45661-9_4. Архивировано 23 января 2022 года.
9. ↑ 1 2 Hong, Seokhie; Hong, Deukjo; Ko, Youngdai; Chang, Donghoon; Lee, Wonil; Lee, Sangjin. Differential cryptanalysis of TEA and XTEA (недоступная ссылка — история) (неопр.) // In Proceedings of ICISC 2003. — 2003.
10. ↑ Tom St Denis. Extended TEA Algorithms Архивная копия от 27 августа 2018 на Wayback Machine
11. ↑ Исходная статья с реализацией атаки на XXTEA и примером кода (неопр.). Дата обращения: 6 ноября 2009. Архивировано из оригинала 23 сентября 2009 года.
12. ↑ Сравнительные результаты устойчивости симметричных криптоалгоритмов Архивировано 25 июля 2008 года. (англ.)
13. ↑ A related key attack for RTEA. (недоступная ссылка)
14. ↑ [Raiden: An alternative to TEA Block Cipher (англ.) (неопр.). Дата обращения: 6 ноября 2009. Архивировано 5 марта 2016 года. Raiden: An alternative to TEA Block Cipher (англ.)]

## Ссылки

[править | править код]

* Страница алгоритма шифрования TEA
* Roger M. Needham and David J. Wheeler. «TEA, a Tiny Encryption Algorithm»(PDF)
* Andew Hang. «Hacking the Xbox: an introduction to reverse engineering»[1] ISBN 978-1593270292
* Журнал «Хакер Онлайн», TEA: блочный шифр своими руками, (2004)[2]
* Paris Kitsos,Yan Zhang. «RFID Security: Techniques, Protocols and System-On-Chip Design»[3]
* David J. Wheeler and Roger M. Needham. «Correction to xtea.» Technical report, Computer Laboratory, University of Cambridge, October 1998 (PDF).
* Roger M. Needham and David J. Wheeler. «Tea extensions.» Technical report, Computer Laboratory, University of Cambridge, October 1997 (PDF).
* Test vectors for TEA
* JavaScript implementation of XXTEA with Base64
* PHP implementation of XTEA
* JavaScript implementation of TEA
* Ruby implementation of XXTEA with Base64
* LGPL Java/J2ME implementation of TEA
* Visual Basic.NET implementation of TEA

Симметричные криптосистемы

Потоковые шифры|

* A3
* A5
* A8
* Decim
* F-FCSR
* Grain
* HC-256
* KCipher-2
* MICKEY
* MUGI
* PIKE
* Phelix
* RC4
* Rabbit
* SEAL
* SNOW
* SOSEMANUK
* Salsa20
* STRUMOK
* Trivium
* VMPC

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

* ГОСТ 28147-89 (Магма)
* Blowfish
* Camellia
* CAST-128
* CAST-256
* CIPHERUNICORN-A
* CIPHERUNICORN-E
* CLEFIA
* Cobra
* DEAL
* DES
* DESX
* DFC
* E2
* EnRUPT
* FEAL
* HPC
* IDEA
* KASUMI
* Khafre
* Khufu
* LOKI97
* MacGuffin
* MARS
* MESH
* MISTY1
* NewDES
* NDS
* RC5
* RC6
* SEED
* Simon
* Sinople
* Skipjack
* SM4
* Speck
* TEA
* XTEA
* XXTEA
* Raiden
* RTEA
* Triple DES
* Twofish

SP-сеть|

* Кузнечик
* 3-WAY
* ABC
* ARIA
* AES (Rijndael)
* Akelarre
* Anubis
* BaseKing
* BassOmatic
* BelT
* CRYPTON
* Diamond2
* Grand Cru
* Hierocrypt-3
* Hierocrypt-L1
* KHAZAD
* Kalyna
* Lucifer
* Present
* Rainbow
* SAFER
* SHARK
* SQUARE
* Serpent
* Threefish

Другие|

* FROG
* NUSH
* REDOC
* SC2000
* SHACAL
* CS-Cipher