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

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

Свойства

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

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

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

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

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

Предположим, что на вход 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 ${\displaystyle \boxplus }$ ({ [ R _n ${\displaystyle \ll }$ 4 ] ${\displaystyle \boxplus }$ K[0] } ${\displaystyle \oplus }$ { R _n ${\displaystyle \boxplus }$ i * δ } ${\displaystyle \oplus }$ { [ R _n ${\displaystyle \gg }$ 5 ] ${\displaystyle \boxplus }$ K[1] })

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

Где

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

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

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

Реализация

Реализация на языке программирования Си (адаптированный вариант кода, представленного в статье Дэвида Уилера и Роджера Нидхэма ) функций шифрования и расшифрования с использованием алгоритма 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 , так как он использует ту же идею использования операций из ортогональных алгебраических групп . Этот подход отлично защищает от методов линейного криптоанализа .

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

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

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

Было обнаружено, что TEA довольно устойчив к дифференциальному криптоанализу . Атака на 10 раундов TEA требует 2 ^52,5 выбранных открытых текстов и имеет временную сложность 2 ⁸⁴ . Лучший результат — криптоанализ 17 раундов TEA . Данная атака требует всего 1920 выбранных открытых текстов, однако имеет временную сложность 2 ^123,37 .

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

Ещё одна проблема алгоритма TEA — наличие эквивалентных ключей. Было показано, что каждый ключ имеет три ему эквивалентных . Это означает, что эффективная длина ключа имеет всего 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 }$ 80000000 h	K[3] ${\displaystyle \oplus }$ 80000000 h
K[0] ${\displaystyle \oplus }$ 80000000 h	K[1] ${\displaystyle \oplus }$ 80000000 h	K[2]	K[3]
K[0] ${\displaystyle \oplus }$ 80000000 h	K[1] ${\displaystyle \oplus }$ 80000000 h	K[2] ${\displaystyle \oplus }$ 80000000 h	K[3] ${\displaystyle \oplus }$ 80000000 h

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

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

XTEA

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

RTEA

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

Raiden

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

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

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

В то же время авторы алгоритма TEA на своей официальной странице обращают внимание на то, что в реальных условиях практического использования алгоритм TEA все ещё остается довольно надежным и все найденные уязвимости, как правило, не являются критичными, к примеру, при передаче данных в реальном времени.

См. также

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

Примечания

Ссылки

• Roger M. Needham and David J. Wheeler. «TEA, a Tiny Encryption Algorithm»
• Andew Hang. «Hacking the Xbox: an introduction to reverse engineering» ISBN 978-1593270292
• Журнал «Хакер Онлайн», TEA: блочный шифр своими руками, (2004)
• Paris Kitsos,Yan Zhang. « RFID Security: Techniques, Protocols and System-On-Chip Design»
• David J. Wheeler and Roger M. Needham. «Correction to xtea.» Technical report, Computer Laboratory, University of Cambridge, October 1998 .
• Roger M. Needham and David J. Wheeler. «Tea extensions.» Technical report, Computer Laboratory, University of Cambridge, October 1997 .