TEA

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

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

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

Свойства

Алгоритм шифрования 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 ({ [ Rn 4 ] K[0] } { Rn i * δ } { [ Rn 5 ] K[1] })

Если n = 2 * i для 1 ≤ i ≤ 32 (чётные раунды), то Rn+1 = Ln ({ [ Rn 4 ] K[2] } { Rn i * δ } { [ Rn 5 ] K[3] })

Где

  • X Y — операция сложения чисел X и Y по модулю 232.
  • X Y — побитовое исключающее «ИЛИ» (XOR) чисел X и Y, которое в языке программирования Си обозначается как X ^ Y
  • X Y и X Y — операции побитового сдвига числа X на Y бит влево и вправо соответственно.
  • Константа δ была выведена из Золотого сечения δ = ( — 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] 80000000h K[3] 80000000h
K[0] 80000000h K[1] 80000000h K[2] K[3]
K[0] 80000000h K[1] 80000000h K[2] 80000000h K[3] 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:

Название алгоритмаСтандартное количество раундов сети ФейстеляРазмер блокаРазмер ключа
TEA6464 бита128 бит
XTEA6464 бита128 бит
XTEA-13264 бита128 бит
XTEA-264128 бит128 бит
XTEA-364128 бит256 бит
XXTEA52 + 12 * M64 * M бит128 бит
RTEA48 или 6464 бита128 или 256 бит
Raiden3264 бита128 бит

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

См. также

Примечания

  1. Страница шифра TEA (недоступная ссылка). Дата обращения: 25 февраля 2009. Архивировано 12 июня 2017 года.
  2. Roger M. Needham and David J. Wheeler. TEA, a Tiny Encryption Algorithm
  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.
  4. 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.
  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.
  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. (недоступная ссылка)
  10. Tom St Denis. Extended TEA Algorithms
  11. Исходная статья с реализацией атаки на XXTEA и примером кода (недоступная ссылка). Дата обращения: 6 ноября 2009. Архивировано 23 сентября 2009 года.
  12. Сравнительные результаты устойчивости симметричных криптоалгоритмов Архивировано 25 июля 2008 года. (англ.)
  13. A related key attack for RTEA. (недоступная ссылка)
  14. Raiden: An alternative to TEA Block Cipher (англ.)

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.