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 раундов). Сеть Фейстеля несимметрична из-за использования в качестве операции наложения сложения по модулю 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 \boxplus ({ [ Rn \ll 4 ] \boxplus K[0] } \oplus { Rn \boxplus i * δ } \oplus { [ Rn \gg 5 ] \boxplus K[1] })

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

Где

  • X \boxplus Y — операция сложения чисел X и Y по модулю 232.
  • X \oplus Y — побитовое исключающее «ИЛИ» (XOR) чисел X и Y, которое в языке программирования Си обозначается как X ^ Y
  • X \ll Y и X \gg Y — операции побитового сдвига числа X на Y бит влево и вправо соответственно.
  • Константа δ была выведена из Золотого сечения δ = (\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, 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 после 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» на примере взлома игровой приставки 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 все еще остается довольно надежным и все найденные уязвимости, как правило, не являются критичными, к примеру, при передаче данных в реальном времени.

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

  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  (англ.)

Ссылки[править | править исходный текст]