Анализ шифра TEA

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

Используемая теория
Пусть проводится n независимых испытаний с исходами 1,…,N и вероятностями исходов p_1,…,p_N, и в векторе (ν^n ) ⃗ = (ν_1^n,ν_2^n,…,ν_N^n) координата ν_k^n, k=1,…,N, равна числу появлений исхода k в n испытаниях. Распределение вектора (ν^n ) ⃗ называют полиноминальным распределением с параметрами n и p ⃗ = (p_1,…, p_N).
P{ν_1^n =〖 n〗_(1,…,) ν_N^n =〖 n〗_N} = {█(n!/(〖 n〗_1 !…〖 n〗_N !) p_1^n…,p_N^n ,если ∑_(j=1)^N▒〖 n〗_j = n @0 в остальных случаях)┤
Случайная величина x_n^2 = ∑_(j=1)^N▒〖(ν_j^n -np_j)〗^2/(np_j ) называется статистикой Пирсона.
Пусть ξ ⃗ = (ξ_1,…,ξ_N) случайный вектор со сферически симметричным N-мерным нормальным распределением с единичной матрицей ковариаций. Распределение квадрата длины такого вектора называется распределением хи-квадрат с N степенями свободы. Иными словами, распределение суммы = ξ_1^2+ξ_2^2+…+ξ_N^2, в которой слагаемые независимы и имеют стандартное нормальное распределение.
Теорема о предельном распределении статистики Пирсона
Пусть случайный вектор (ν^n ) ⃗ = (ν_1^n,ν_2^n,…,ν_N^n,)имеет полиноминальное распределение с параметрами n и p ⃗ = (p_1,…, p_N). Если вектор p ⃗ = (p_1,…, p_N) фиксирован, а n → ∞, то распределение статистики Пирсона x_n^2 сходится к распределению с (N-1) степенями свободы.
Экспериментальная часть
Поиск связи между входным блоком и выходом
Рассматривались параллельно две схемы. Обе представляли собой шифр TEA, с заданными на них одинаковыми ключами, выбранными случайным образом. На вход одной схемы подавался случайный блок, на вход другой – тот же блок с одним инвертированным, случайно выбранным битом. После каждой итерации, промежуточный шифр текст побитово складывался над GF(2), с промежуточным текстом из другой схемы. Если получался 0, то это служило сигналом того, что две схемы дали на какой-то итерации один и тот же результат.
Пусть x∈GF(2^64) – входной блок, T(x) – значение блока, после одного раунда, p - случайно выбранный бит, N - число итераций.

Описание алгоритма шифра 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.
Если 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.
...

Отличие шифр текста TEA от случайной последовательности
Данный анализ основывался на том, что любая случайная последовательность должна обладать SAC(Strict Avalanche Criterion – в переводе значит лавинный критерий) свойством, которое заключается в том, что изменение любого бита на входе вызывает “лавинное” изменение в среднем половины выходных битов.
Алгоритм теста:
Пока(кол-во тестов<)
{
генерация входа
генерация позиции в
инвернтированиего бита в , и запись полученного значения в
вычисление расстояния Хемминга между
увеличение на 1 значение в массиве находящееся на позиции
}
Далее подсчитываются статистики Пирсона, по которым уже дают ответ о наличии свойства SAC, и возможности различения шифр текста TEA от случайной последовательности.
...

Используемая теория
Пусть проводится n независимых испытаний с исходами 1,…,N и вероятностями исходов ,…,, и в векторе= () координата , k=1,…,N, равна числу появлений исхода k в n испытаниях. Распределение вектораназывают полиноминальным распределением с параметрами n и = (,…,).
P{ = =} =
Случайная величина =называется статистикой Пирсона.
Пусть = () случайный вектор со сферически симметричным N-мерным нормальным распределением с единичной матрицей ковариаций. Распределение квадрата длины такого вектора называется распределением хи-квадрат с N степенями свободы. Иными словами, распределение суммы = ++…+, в которой слагаемые независимы и имеют стандартное нормальное распределение.
Теорема о предельном распределении статистики Пирсона
Пусть случайный вектор= ()имеет полиноминальное распределение с параметрами n и = (,…,). Если вектор = (,…,) фиксирован, а n → , то распределение статистики Пирсонасходится к распределению с (N-1) степенями свободы.
...

Поиск связи между входным блоком и выходом
Рассматривались параллельно две схемы. Обе представляли собой шифр TEA, с заданными на них одинаковыми ключами, выбранными случайным образом. На вход одной схемы подавался случайный блок, на вход другой – тот же блок с одним инвертированным, случайно выбранным битом. После каждой итерации, промежуточный шифр текст побитово складывался над , с промежуточным текстом из другой схемы. Если получался 0, то это служило сигналом того, что две схемы дали на какой-то итерации один и тот же результат.
Пусть – входной блок, T(x) – значение блока, после одного раунда, - случайно выбранный бит, - число итераций.

Далее, полученные значения побитово складывались над , и брался вес полученного значения:

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

Построение линейного аналога
Шифр TEA устойчив к линейному анализу за счёт присутствия в нем операции сложения над . Эксперимент заключается в том, чтобы найти такие случаи, когда оригинальную схему шифра TEA, можно рассматривать как линейную схему. Для этого производились наблюдения за тремя схемами: оригинальной схемой, оригинальной схемой, в которой сложение с ключом заменено на побитовое сложение над , и схемой в которой все сложения над заменены побитовыми сложениями над .
...

Первый эксперимент
Сперва анализировалась первая и вторая схемы. Обе схемы одинаково настраивались случайно выбранными ключами и произвольными входными блоками:
K[0] = 52A310;
K[1] = 1DA256;
K[2] = 840E75;
K[3] = BBC1C;
Data[0] = 31E2A3;
Data[1] = 51DAC8;
Результаты каждой итерации обеих схем побитово складывались, и анализировалось распределение веса полученного значения. То есть выполнялось следующее:
пусть T(x) – значение блока после раунда первой схемы, (x) – значение блока после раунда второй схемы, - число итераций.

Подсчитывался вес значений и записывался в память. Далее анализировались наиболее интересные для нас случаи, когда значение веса – минимально (или максимально). В этих ситуациях две схемы являются максимально приближенными друг к другу.
Напомню, что в стойком шифре на выходе функций старших степеней, каждый бит имеет вероятность инвертирования равную 0.5. Такое же распределение будет у .
...

Второй эксперимент
Анализировались все три схемы. Ключи выбраны случайно, но до конца эксперимента не менялись:
K[0] = 52A310;
K[1] = 1DA256;
K[2] = 840E75;
K[3] = BBC1C;
Проводилось 1 000 000 000 экспериментов, в каждом из которых генерировались случайные входные блоки, подававшиеся на входы всех трёх схем. Выходы второй и третей схем, побитово складывались с выходом первой схемы. Далее анализировался вес полученного вектора. Если его значение было меньше некоторой ранее оговоренной планки, то я его записывал в память. Частичный результат этого эксперимента:
1цикл различаются в 3 битах с first mod. при входных блоках 2488F3CC 7201010C
1цикл различаются в 3 битах с first mod. при входных блоках 638D0F4C 40001008
1цикл различаются в 3 битах с first mod. при входных блоках 3634DBEC 41A210E
1цикл различаются в 3 битах с first mod. при входных блоках 4EE76B0E 2A019506
1цикл различаются в 3 битах с first mod. при входных блоках 6B140CC7 60004528
…
(first mod.
...

Третий эксперимент
Является продолжением второго – блоки входов при которых получались схожие шифр тексты у первой и второй схем, считывались из памяти и комбинировались в различном порядке. Результаты получились следующие:
1 цикл различаются в 0 битах с first mod. при входных блоках 22011102 38404528
1 цикл различаются в 0 битах с first mod. при входных блоках 4DED74A6 4802412C
1 цикл различаются в 0 битах с first mod. при входных блоках 450E6B96 6C425424
1 цикл различаются в 0 битах с first mod. при входных блоках 4CAA48F4 34085522
1 цикл различаются в 0 битах с first mod. при входных блоках 2AC85122 6C02140C
1 цикл различаются в 0 битах с first mod. при входных блоках 200D8FAD 2848040C
1 цикл различаются в 0 битах с first mod.
...

Четвертый эксперимент
Была предпринята попытка зрительно уловить связь между тремя схемами. Для этого схемы настраивались следующим образом:
K[0] = 52A310;
K[1] = 1DA256;
K[2] = 840E75;
K[3] = BBC1C;
на вход подавали случайные блоки открытого текста.
...

Эксперимент первый
Перебираются все значения входа для произвольного ключа, и строятся 32-мерные векторы такого вида функция шифрования за 32 раунда. Опыт направлен на то, чтобы подобрать некоторое подпространство , в котором будет лежать большинство векторов .
Мы осуществляли поиск подпространства следующим образом: после образования всех векторов вида собирались частоты появления 0 на каждом бите на выходе. В случае если будет отклонение в позиции от среднего значения 32 768, то создавая наше подпространство из единичных векторов, мы можем отбросить вектор с единицей на позиции.
...

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

Задача заключается в том, чтобы подобрать некоторый вектор , чтобы распределение случайной величины не было . Такой вектор найдется только в том случае, если между координатами существует связь. Начать нужно с того, чтобы обнаружить векторы которые отклоняются от значения 32 768 на более чем .
...

1. David J. Wheeler, Roger M. Needham TEA, a Tiny Encryption Algorithm. – Computer Laboratory Cambridge University England.
2. Roger M. Needham and David J. Wheeler Tea extensions. – Notes October 1996, Revised March 1997, Corrected October 1997.
3. Moon D., Hwang K., Lee W., Lee S., Lim J., Impossible Differential Cryptanalysis of Reduced Round XTEA and TEA – CIST, Korea University.
4. Vikram Reddy Andem A cryptanalysis of the tiny encryption algorithm – The University of Alabama, Tuscaloosa, Alabama, 2003.
5. Hernandez J.C.,Sierra J.M., Ribagorda A., Ramos B., Mex-Perera J.C., Distinguishing TEA from a Random Permutation: Reduced Round Versions of TEA Do Not HAVE the SAC or Do Not Generate Random Numbers – Madrid,Spain,2001.
6. Kelsey J., Schneier B., Wagner D., realted-Key Cryptanalysis of 3-WAY, Biham-DES,CAST, DES-X, NewDES, RC2, and TEA.
7. Сергей Панасенко Алгоритмы шифрования – Санкт – Петербург, “БХВ-Петербург”, 2009