2.3.2. Алгоритмы блочного симметричного шифрования . Алгоритм TEA (Tiny Encryption Algorithm)

Привет, Вы узнаете о том , что такое алгоритмы блочного симметричного шифрования, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое алгоритмы блочного симметричного шифрования, tea, tiny encryption algorithm , настоятельно рекомендую прочитать все из категории Криптография и криптоанализ, Стеганография и Стегоанализ.

Специфика информационных потоков, циркулирующих в современных ИТ-системах, часто требует обеспечения конфиденциальности передаваемых данных, что, проще всего, достигается путем применения средств криптографической защиты информации (КЗИ). Неотъемлемым элементом подсистемы КЗИ в компьютерных системах стали блочные симметричные шифры (БСШ). Последнее десятилетие ознаменовалось эволюционной сменой стандартов в области алгоритмов КЗИ, которая не обошла и БСШ.

Так, новый международный стандарт БСШ FIPS-197 [1] (победитель проекта AES [1] – алгоритм Rijndael), сегодня фактически вытеснил, широко распространенный еще 10 лет назад, стандарт блочного шифрования DES и его 3-х каскадную версию – Triple-DES [2].

В настоящее время в некторых странах отсутствует национальный стандарт БСШ, и временно разрешен к применению стандарт бывшего СССР – ГОСТ 28147-89 , принятый в 1989 году. Однако, учитывая значительный прогресс в сфере методов и средств криптоанализа, на протяжении последних 10 – 20 лет, этот алгоритм уже переходит в класс “морально устаревших”. Косвенным подтверждением этого факта стали результаты проведенных в США и Европе конкурсов (проекты AES [4] и NESSIE [5] соответственно), которые были направлены на выбор новых криптопримитивов, удовлетворяющих возросшим требованиям безопасности. Так, в соответствии с требованиями проекта NESSIE, алгоритм ГОСТ 28147-89 [3] относиться только к третьему (наименьшему) классу стойкости.

Схема Фейштеля используется в криптоалгоритмах DES, ГОСТ 28147-89, FEAL, Blowfish, LOKI, CAST и др.

Рассмотрим практическую реализацию блочного шифра, построенного по принципу сети Фейштеля, на примере алгоритма TEA (Tiny Encryption Algorithm) .

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

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

Свойства алгоритма TEA

Алгоритм шифрования 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], поэтому данный алгоритм не следует использовать в качестве хеш-функции.

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

Исходный текст разбивается на блоки по 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.

Где

• X Y — операция сложения чисел X и Y по модулю 232.
• X Y — побитовое исключающее «ИЛИ» (XOR) чисел X и Y, которое в языке программирования Си обозначается как X ^ Y
• X Y и X Y — операции побитового сдвига числа X на Y бит влево и вправо соответственно.
• Константа δ была выведена из Золотого сечения δ = ( — 1) * 231 = 2654435769 = 9E3779B9h. В каждом раунде константа умножается на номер цикла i. Это было сделано для предотвращения простых атак, основанных на симметрии раундов.

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

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

Алгоритм TEA (рис.2.6) разработан в Кембриджском университете, представляет собой схему сети Фештеля на 64 раунда, размер шифруемого блока 64 бита, размер ключа шифрования 128 бит.

Рис.2.6. Схема работы алгоритма TEA

Алгоритмы шифрования, получившие большее признание среди криптографов, используют в функциях преобразования нелинейные операции. Так, например, алгоритм шифрования DES (Data Encryption Standard), который до недавнего времени являлся мировым стандартом шифрования, использует в своей образующей функции операции табличной подстановки, которые существенно усложняют процедуру линейного криптоанализа этого шифра. Схема раунда алгоритма DES представлена на рис. 2.7.
Достоинством алгоритма TEA является простота реализации, однако, отсутствие в образующей функции нелинейных операций приходится компенсировать большим количеством раундов. КEY0, КEY1, КEY2, КEY3 на рис.2.6 – это ключи раунда, которые получаются простым делением ключа шифрования на 4 части. Необходимо также отметить, что TEA является несимметричным алгоритмом, поскольку ветви смешиваются обычным арифметическим сложением, поэтому операция дешифрации требует незначительных изменений.

Каждый раунд преобразования включает перестановку правой части блока, причем на вход модуля расширения подается 32-разрядное число, а снимается с него 48-разрядное (некоторые биты входного числа копируются на выход дважды). Об этом говорит сайт https://intellect.icu . После сложения с материалом ключа осуществляется табличная подстановка, в результате которой по 8 таблицам подстановки происходит замена 48-битного входа на 32-битный выход (каждая S-таблица подстановки заменяет 6-битный вход на 4-битный выход). Выход S-блока поступает на блок перестановки, где биты переставляются по законам, определяемым специальной P-таблицей. Заканчивается раунд традиционным для сетей Фейштеля смешиванием ветвей между собой. За счет использования нелинейных операций преобразований удалось уменьшить количество раундов до 16 при размере ключа 56 бит.

С момента опубликования алгоритма DES в 1977 году он подвергся серьезному криптоанализу. Так, в частности, были обнаружены 4 слабых ключа DES, которые половину из возможных 264 входных блоков кодируют самих в себя. Был предложен также ряд специфических атак на DES, которые еще в 80-е годы позволяли с использованием компьютеров специализированной архитектуры или распределенных вычислений провести успешную атаку на алгоритм в течение нескольких часов. Для современного технологического уровня время взлома шифра DES составляет несколько десятков минут. В связи с этим, для обеспечения более высокого криптостойкости рекомендуется применять тройное DES-шифрование на трех или двух различных ключах. Такие схемы называются EDE (encrypt-decrypt-encrypt) шифрованием. При двух ключах шифрования блок открытого текста сначала шифруется на ключе K1, затем дешифруется на ключе K2, а затем вновь шифруется на ключе K1. Размер ключевого пространства (общее количество возможных ключей шифрования) в этом случае возрастает до 2112 (у обычного DES – 256). При использовании трех ключей шифрования блок открытого текста сначала шифруется на ключе K1, затем дешифруется на ключе K2, а затем шифруется на ключе K3, что обеспечивает размер ключевого пространства 2168.

Из-за недостаточной длины ключа шифрования, а также ориентированности шифра DES на аппаратную реализацию (в связи с большим количеством используемых перестановок бит), американским национальным институтом стандартов в 1997 был объявлен конкурс на криптостандарт блочного шифрования AES (Advanced Encryption Standard). В 2000 году победителем конкурса был объявлен алгоритм Rijndael, разработанный бельгийскими криптографами. Его отличительной особенностью является то, что он построен не по принципу сети Фейштеля, а использует нетрадиционную структуру KALST- сети.

Алгоритм Rijndael представляет блок данных в виде двухмерного байтового массива размером 4х4, 4х6 или 4х8 (допускается использование нескольких фиксированных размеров шифруемого блока информации). Все операции выполняются с отдельными байтами массива, а также с независимыми столбцами и строками.

Алгоритм Rijndael выполняет четыре преобразования: BS (ByteSub) - табличная замена каждого байта массива, SR (ShiftRow) - сдвиг строк массива. При этой операции первая строка остается без изменений, а остальные циклически побайтно сдвигаются влево на фиксированное число байт, зависящее от размера массива. Например, для массива размером 4X4 строки 2, 3 и 4 сдвигаются соответственно на 1, 2 и 3 байта. Далее выполняется MC (MixColumn) - операция над независимыми столбцами массива , когда каждый столбец по определенному правилу умножается на фиксированную матрицу. И, наконец,AK (AddRoundKey) - добавление ключа. Каждый бит массива складывается по модулю 2 с соответствующим битом ключа раунда, который, в свою очередь, определенным образом вычисляется из ключа шифрования. Количество раундов шифрования в алгоритме Rijndael переменное (10, 12 или 14 раундов) и зависит от размеров блока и ключа шифрования (для ключа также предусмотрено несколько фиксированных размеров).

Достоинствами шифра Rijndael является то, что он обеспечивает высокую скорость шифрования на всех платформах: как при программной, так и при аппаратной реализации. Его отличают несравнимо лучшие возможности распараллеливания вычислений по сравнению с другими алгоритмами, представленными на конкурс AES. Кроме того, требования к ресурсам для его работы минимальны, что важно при его использовании в устройствах, обладающих ограниченными вычислительными возможностями.

Российским стандартом блочного шифрования является алгоритм ГОСТ 28147-89, построенный по структуре сети Фейштеля. Его особенностью следует признать большой размер ключа (256 бит), непубликуемые таблицы подстановки, большое количество раундов (32 раунда).

Реализация Tiny Encryption Algorithm

Реализация на языке программирования Си (адаптированный вариант кода, представленного в статье Дэвида Уилера и Роджера Нидхэма[2]) функций шифрования и расшифрования с использованием алгоритма TEA:

#include <stdint.h>

void encrypt (uint32_t* v, 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, 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» на примере взлома игровой приставки Microsoft Xbox.

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

K[0]	K[1]	K[2]	K[3]
K[0]	K[1]	K[2] {\displaystyle \oplus } 80000000h	K[3] {\displaystyle \oplus } 80000000h
K[0] {\displaystyle \oplus } 80000000h	K[1] {\displaystyle \oplus } 80000000h	K[2]	K[3]
K[0] {\displaystyle \oplus } 80000000h	K[1] {\displaystyle \oplus } 80000000h	K[2] {\displaystyle \oplus } 80000000h	K[3] {\displaystyle \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. Federal Information Processing Standards Publication 197 (FIPS PUB 197). Specification for the Advanced Encryption Standard (AES). // Department of Commerce, National Institute of Standards and Technology, Information Technology Laboratory. November 26, 2001.
2. Federal Information Processing Standards Publication 46-3 (FIPS PUB 46-3). Specification for the Data Encryption Standard (DES). // U.S. Department of Commerce / National Institute of Standards and Technology. October 25, 1999.
3. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. – М.: Госстандарт СССР.
4. AES discussion forum [Электрон. ресурс]. – Режим доступа: http://aes.nist.gov.
5. NESSIE Call for Cryptographic Primitives, Version 2.2, 8th March 2000 [Электрон. ресурс]. – Режим доступа: http://cryptonessie.org/.
6. Головашич С.А. Методы построения высокостойких блочных симметричных шифров и схем их применения. // Дисс. канд. техн. наук. – Х.: Харьковский национальный университет радиоэлектроники, 2001. – 180 с.
7. Горбенко И.Д., Головашич С.А. Алгоритм блочного симметричного шифрования «Торнадо». Спецификация преобразования // Радиотехника: Всеукр. межвед. научн.-техн. сб. – Х.: ХНУРЭ, 2003. – Вып. 134. – С. 62-80.
8. Долгов В.И., Головашич С.А., Руженцев В.И. Криптостойкость шифра «Торнадо». // Радиотехника: Всеукр. межвед. научн.-техн. сб. – Х.: ХНУРЭ, 2003. – Вып. 134. – С. 81-88.
9. Головашич С.А., Лепеха А.И. Статистический анализ БСШ «Торнадо» // Радиотехника: Всеукр. межвед. научн.-техн. сб. – Х.: ХНУРЭ, 2003. – Вып. 134. – С. 89-96.
10. Головашич С.А. Принцип построения инволютивных шифров // Проблемы бионики. – 2001. – Вып. 54. – С. 118-125.
11. Головашич С.А. Метод конструирования цикловых функций БСШ // Автоматизированные системы управления и приборы автоматики: Всеукр. межвед. научн.-техн. сб. – Х.: ХНУРЭ, 2001. – Вып. 117. – С. 155-161.
12. Головашич С.А. Метод построения управляемых S-блоков с предельными показателями нелинейности // Радиотехника: Всеукр. межвед. научн.-техн. сб. – Х.: ХНУРЭ, 2001. – Вып. 123. – С. 215-221.

13. NIST Special Publication 800-38A 2001 Edition – Recommendation for Block Cipher Modes of Operation. Methods and Techniques // Computer Security Division Information Technology Laboratory National Institute of Standards and Technology, Gaithersburg, MD 20899-8930. December 2001.

14. «Supporting Document on E2», Nippon Telegraph and Telephone Corporation, June 14, 1998.
15. Головашич С.А. Безопасность режимов блочного шифрования // Радиотехника: Всеукр. межвед. научн.- техн. сб. – Х.: ХНУРЭ, 2001. – Вып. 119. – С. 135-145.

В заключение, эта статья об алгоритмы блочного симметричного шифрования подчеркивает важность того что вы тут, расширяете ваше сознание, знания, навыки и умения. Надеюсь, что теперь ты понял что такое алгоритмы блочного симметричного шифрования, tea, tiny encryption algorithm и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Криптография и криптоанализ, Стеганография и Стегоанализ