TEA

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.

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

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

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

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

Свойства

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

Достоинствами шифра являются его простота в реализации, небольшой размер кода и довольно высокая скорость выполнения, а также возможность оптимизации выполнения на стандартных 32-битных процессорах, так как в качестве основных операций используются операции исключающего «ИЛИ» (XOR), побитового сдвига и сложения по модулю 2³². Поскольку алгоритм не использует таблиц подстановки и раундовая функция довольно проста, алгоритму требуется не менее 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) поступают правая и левая часть (L_n, R_n), тогда на выходе n-го раунда будут левая и правая части (L_n+1, R_n+1), которые вычисляются по следующим правилам:

L_n+1 = R_n.

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

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

Где

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

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

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

Реализация

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

#include <stdint.h>
 
void encrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0, i;           /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i < 32; i++) {                       /* basic cycle start */
        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, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0xC6EF3720, i;       /* set up */
    uint32_t delta=0x9e3779b9;                          /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];        /* cache key */
    for (i=0; i<32; i++) {                              /* basic cycle start */
        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 Sсhneier) и Дэвида Вагнера (David Wagner) в 1997 году^[6]. Наиболее простые из них дают дифференциальную характеристику с вероятностью 2⁻³² после 32 циклов алгоритма, поэтому требуется не менее 2³⁴ выбранных открытых текстов для нахождения дифференциальной характеристики с вероятностью 1 и определения всех бит ключа. Более сложная в реализации атака, сочетающая в себе идеи «атаки на связанных ключах» Эли Бихама (Eli Biham)^[7] и дифференциальной атаки даёт дифференциальную характеристику с вероятностью 2⁻¹¹, требует всего 2²³ выбранных открытых текстов и время порядка 2³² времён шифрования (то есть требует количество битовых операций порядка 2³²).

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

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

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

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

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

K[0]	K[1]	K[2]	K[3]
K[0]	K[1]	K[2] $\oplus$ 80000000h	K[3] $\oplus$ 80000000h
K[0] $\oplus$ 80000000h	K[1] $\oplus$ 80000000h	K[2]	K[3]
K[0] $\oplus$ 80000000h	K[1] $\oplus$ 80000000h	K[2] $\oplus$ 80000000h	K[3] $\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
2. ↑ ^{1 2 3} Roger M. Needham and David J. Wheeler. TEA, a Tiny Encryption Algorithm
3. ↑ Kelsey, John; Schneier, Bruce; Wagner, David (1996). «Key-schedule cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES». Lecture Notes in Computer Science 1109: 237–251. DOI:10.1007/3-540-68697-5_19.
4. ↑ ^{1 2} Andem, Vikram Reddy (2003).A cryptoanalisys of the tiny encryption algorithm
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 (1997). «Related-key cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X NewDES, RC2, and TEA». Lecture Notes in Computer Science 1334: 233–246. DOI:10.1007/BFb0028479.
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 (2002). «Impossible differential cryptanalysis of reduced round XTEA and TEA». Lecture Notes in Computer Science 2365: 49–60. DOI:10.1007/3-540-45661-9_4.
9. ↑ ^{1 2} Hong, Seokhie; Hong, Deukjo; Ko, Youngdai; Chang, Donghoon; Lee, Wonil; Lee, Sangjin (2003). «Differential cryptanalysis of TEA and XTEA». In Proceedings of ICISC 2003.
10. ↑ Tom St Denis. Extended TEA Algorithms
11. ↑ Исходная статья с реализацией атаки на XXTEA и примером кода
12. ↑ Сравнительные результаты устойчивости симметричных криптоалгоритмовангл. 
13. ↑ A related key attack for RTEA.
14. ↑ 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]
• Журнал «Хакер Онлайн», 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