TEA
Войти  |  Регистрация
Авторизация
» » TEA

TEA



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

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

Свойства

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

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

Ln+1 = Rn.

Если n = 2 * i — 1 для 1 ≤ i ≤ 32 (нечётные раунды), то Rn+1 = Ln ⊞ {displaystyle oxplus } ({ [ Rn ≪ {displaystyle ll } 4 ] ⊞ {displaystyle oxplus } K[0] } ⊕ {displaystyle oplus } { Rn ⊞ {displaystyle oxplus } i * δ } ⊕ {displaystyle oplus } { [ Rn ≫ {displaystyle gg } 5 ] ⊞ {displaystyle oxplus } K[1] })

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

Где

  • X ⊞ {displaystyle oxplus } Y — операция сложения чисел X и Y по модулю 232.
  • X ⊕ {displaystyle oplus } Y — побитовое исключающее «ИЛИ» (XOR) чисел X и Y, которое в языке программирования Си обозначается как X ^ Y
  • X ≪ {displaystyle ll } Y и X ≫ {displaystyle gg } Y — операции побитового сдвига числа X на Y бит влево и вправо соответственно.
  • Константа δ была выведена из Золотого сечения δ = ( 5 {displaystyle {sqrt {5}}} — 1) * 231 = 2654435769 = 9E3779B9h. В каждом раунде константа умножается на номер цикла 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 после 32 циклов алгоритма, поэтому требуется не менее 234 выбранных открытых текстов для нахождения дифференциальной характеристики с вероятностью 1 и определения всех бит ключа. Более сложная в реализации атака, сочетающая в себе идеи «атаки на связанных ключах» Эли Бихама (Eli Biham) и дифференциальной атаки, даёт дифференциальную характеристику с вероятностью 2−11, требует всего 223 выбранных открытых текстов и время порядка 232 времён шифрования (то есть требует количество битовых операций порядка 232).

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

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

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

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

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

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

Выявление ряда серьёзных уязвимостей и слабых мест в исходном алгоритме 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 использует ключевое расписание, близкое к ГПСЧ, трансформирует ключ и генерирует подключи для каждого раунда. Шифр успешно проходит тесты Diehard, Sexton и ENT.

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

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

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


Добавлено Admin 2-01-2021, 10:00 Просмотров: 21
Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent