TEA

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

В криптографии,Tiny Encryption Algorithm (TEA)^[1] — блочный алгоритм шифрования типа «Сеть Фейстеля». Алгоритм был разработан на факультете компьютерных наук Кембриджского университета Дэвидом Уилером^[en] (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 $\text{[math]}$ $\text{[math]}$ $\boxplus$ ({ [ R_n $\text{[math]}$ $\text{[math]}$ $\ll$ 4 ] $\text{[math]}$ $\text{[math]}$ $\boxplus$ K[0] } $\text{[math]}$ $\text{[math]}$ $\oplus$ { R_n $\text{[math]}$ $\text{[math]}$ $\boxplus$ i * δ } $\text{[math]}$ $\text{[math]}$ $\oplus$ { [ R_n $\text{[math]}$ $\text{[math]}$ $\gg$ 5 ] $\text{[math]}$ $\text{[math]}$ $\boxplus$ K[1] })

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

Где

X $\text{[math]}$ $\text{[math]}$ $\boxplus$ Y — операция сложения чисел X и Y по модулю 2³².
X $\text{[math]}$ $\text{[math]}$ $\oplus$ Y — побитовое исключающее «ИЛИ» (XOR) чисел X и Y, которое в языке программирования Си обозначается как X ^ Y
X $\text{[math]}$ $\text{[math]}$ $\ll$ Y и X $\text{[math]}$ $\text{[math]}$ $\gg$ Y — операции побитового сдвига числа X на Y бит влево и вправо соответственно.
Константа δ была выведена из Золотого сечения δ = ( $\text{[math]}$ $\text{[math]}$ ${\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, 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 циклов алгоритма, поэтому требуется не менее 2³⁴ выбранных открытых текстов для нахождения дифференциальной характеристики с вероятностью 1 и определения всех бит ключа. Более сложная в реализации атака, сочетающая в себе идеи «атаки на связанных ключах» Эли Бихама (Eli Biham)^[7] и дифференциальной атаки, даёт дифференциальную характеристику с вероятностью 2⁻¹¹, требует всего 2²³ выбранных открытых текстов и время порядка 2³² времён шифрования (то есть требует количество битовых операций порядка 2³²).

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

Было обнаружено, что TEA довольно устойчив к дифференциальному криптоанализу. Атака на 10 раундов TEA требует 2^52,5 выбранных открытых текстов и имеет временную сложность 2⁸⁴^[8]. Лучший результат — криптоанализ 17 раундов TEA^[9]. Данная атака требует всего 1920 выбранных открытых текстов, однако имеет временную сложность 2^123,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] $\text{[math]}$ $\text{[math]}$ $\oplus$ 80000000_h	K[3] $\text{[math]}$ $\text{[math]}$ $\oplus$ 80000000_h
K[0] $\text{[math]}$ $\text{[math]}$ $\oplus$ 80000000_h	K[1] $\text{[math]}$ $\text{[math]}$ $\oplus$ 80000000_h	K[2]	K[3]
K[0] $\text{[math]}$ $\text{[math]}$ $\oplus$ 80000000_h	K[1] $\text{[math]}$ $\text{[math]}$ $\oplus$ 80000000_h	K[2] $\text{[math]}$ $\text{[math]}$ $\oplus$ 80000000_h	K[3] $\text{[math]}$ $\text{[math]}$ $\oplus$ 80000000_h

Расширения алгоритмаПравить

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

См. такжеПравить

ПримечанияПравить

↑ ¹ ² ³ ⁴ ⁵ Страница шифра TEA (неопр.). Дата обращения: 25 февраля 2009. Архивировано из оригинала 12 июня 2017 года.
↑ ¹ ² ³ Roger M. Needham and David J. Wheeler. TEA, a Tiny Encryption Algorithm Архивная копия от 13 октября 2017 на Wayback Machine
↑ 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.
↑ ¹ ² Andem, Vikram Reddy (2003).A cryptoanalisys of the tiny encryption algorithm Архивировано 20 апреля 2009 года.
↑ Seokhie Hong, Deukjo Hong, Youngdai Ko, Donghoon Chang, Wonil Lee, Sangjin Lee, (2003). Differential Cryptanalysis of TEA and XTEA (недоступная ссылка)
↑ 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.
↑ Eli Biham, Computer Science Department, Technion — Israel Institute of Technology, Haifa 32000, Israel, (1992). «New Types of Cryptanalytic Attacks Using Related Keys» (недоступная ссылка)
↑ 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.
↑ ¹ ² Hong, Seokhie; Hong, Deukjo; Ko, Youngdai; Chang, Donghoon; Lee, Wonil; Lee, Sangjin. Differential cryptanalysis of TEA and XTEA (неопр.) // In Proceedings of ICISC 2003. — 2003. (недоступная ссылка)
↑ Tom St Denis. Extended TEA Algorithms Архивная копия от 27 августа 2018 на Wayback Machine
↑ Исходная статья с реализацией атаки на XXTEA и примером кода (неопр.). Дата обращения: 6 ноября 2009. Архивировано из оригинала 23 сентября 2009 года.
↑ Сравнительные результаты устойчивости симметричных криптоалгоритмов Архивировано 25 июля 2008 года. (англ.)
↑ A related key attack for RTEA. (недоступная ссылка)
↑ [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

[teasite-1] ¹ ² ³ ⁴ ⁵ Страница шифра TEA (неопр.). Дата обращения: 25 февраля 2009. Архивировано из оригинала 12 июня 2017 года.

[tea-2] ¹ ² ³ Roger M. Needham and David J. Wheeler. TEA, a Tiny Encryption Algorithm Архивная копия от 13 октября 2017 на Wayback Machine

[kelsey1996-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.

[cryptoanalisys-4] ¹ ² Andem, Vikram Reddy (2003).A cryptoanalisys of the tiny encryption algorithm Архивировано 20 апреля 2009 года.

[differential-5] Seokhie Hong, Deukjo Hong, Youngdai Ko, Donghoon Chang, Wonil Lee, Sangjin Lee, (2003). Differential Cryptanalysis of TEA and XTEA (недоступная ссылка)

[kelsey1997-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.

[relatedkey-7] Eli Biham, Computer Science Department, Technion — Israel Institute of Technology, Haifa 32000, Israel, (1992). «New Types of Cryptanalytic Attacks Using Related Keys» (недоступная ссылка)

[impossible-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.

[autogenerated1-9] ¹ ² Hong, Seokhie; Hong, Deukjo; Ko, Youngdai; Chang, Donghoon; Lee, Wonil; Lee, Sangjin. Differential cryptanalysis of TEA and XTEA (неопр.) // In Proceedings of ICISC 2003. — 2003. (недоступная ссылка)

[extended-10] Tom St Denis. Extended TEA Algorithms Архивная копия от 27 августа 2018 на Wayback Machine

[11] Исходная статья с реализацией атаки на XXTEA и примером кода (неопр.). Дата обращения: 6 ноября 2009. Архивировано из оригинала 23 сентября 2009 года.

[rteatests-12] Сравнительные результаты устойчивости симметричных криптоалгоритмов Архивировано 25 июля 2008 года. (англ.)

[rka-13] A related key attack for RTEA. (недоступная ссылка)

[raidenhome-14] [Raiden: An alternative to TEA Block Cipher (англ.) (неопр.). Дата обращения: 6 ноября 2009. Архивировано 5 марта 2016 года. Raiden: An alternative to TEA Block Cipher (англ.)]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]