Криптоанализ шифра TEA. Исследование статистических связей в шифраторе TEA.

Работа посвящена исследованию статистических связей в шифре TEA. Проведено исследование взаимосвязей результатов работы двух экземпляров шифратора TEA, на которых используются ключи, различающиеся в малом числе бит (не превышающем 3). Обнаружены совокупности близких ключей, при которых зависимости между промежуточными гаммами наблюдаются даже после довольно большого числа раундов (вплоть до 18).
Защита проходила в 2015 году мех-мат МГУ. Оценка 5. ...

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ


Статистики
Пусть v ⃗=(γ0, γ1,…, γn-1) вектор пространства V _n.
Статистика веса
Статистика веса на векторе v ⃗ пространства V _n равна весу v ⃗(числу ненулевых координат).
Отметим, что в случае когда координаты γ0, γ1,…, γn-1, вектора v ⃗ являются случайными равновероятными, статистика веса имеет биномиальное распределение с параметрами (n,0.5).
Статистика количества серий
Определим понятие количества серий на векторе v ⃗ пространства V _n. Количеством серий в векторе v ⃗ пространства V _n называется число сплошных серий, образованных ненулевыми элементами γ0, γ1,…, γn в векторе v ⃗.
Статистика количества серий на векторе v ⃗ пространства V _n равна числу сплошных серий из ненулевых координат вектора v ⃗, для каждого значения веса вектора.(то есть при каждом из значений веса вектора v ⃗).
Пусть σ = γ0+γ1+…+γn-1, а при условии, что σ = s, число ρ серий из единиц (равное числу начал серий из единиц) ρ = γ0 + (1 – γ0) γ1 + (1 – γ1) γ2 +…+ (1 – γn-2) γn-1
Предложение 1
Пусть значения элементов γ0, γ1,…, γn-1, вектора v ⃗ случайны, независимы и равновероятны. Тогда условная вероятность появления i серий при условии, что вес вектора v ⃗ равен m, имеет вид P{ρ=i┤|σ=m}=(C_(n-m+1)^i C_(m-1)^(m-i))/(C_n^m ),i=1,…,m.
Доказательство:
Значение веса вектораv ⃗=( γ0, γ1,…, γn-1) равно m
...

TEA – простой алгоритм, несложно реализующийся на любом языке программирования, и быстро переводящийся в машинный код, за счет использования, в основном, битовых операций при шифровании. По мнению авторов, алгоритм TEA является “лучшим компромиссом между стойкостью, простотой реализации и производительностью”. Также заметим, что отсутствие табличных подстановок и оптимизация под 32-разрядную архитектуру процессоров позволяет реализовать его на языке ASSEMBLER в предельно малом объеме кода
Благодаря своим особенностям, алгоритм TEA вызывал достаточно большой интерес у криптологического сообщества, и до сих пор, периодически, появляются работы, посвященные его криптоанализу. Анализом TEA занимались такие известные криптографы как Джон Келси, Брюс Шнайер, Дэвид Вагнер, Фаузан Мирза, Роджер Фл еминг. Выводы исследователей, на настоящий момент, таковы, что за исключением атак на связанных ключах, TEA не имеет серьезных проблем с криптостойкостью. Благодаря этому и простоте реализации, TEA получил большое распространение в ряде криптографических приложений и широком спектре аппаратного обеспечения. Алгоритм имеет как программную реализацию на разных языках программирования, так и аппаратную реализацию на интегральных схемах типа FPGA.
Настоящая работа посвящена исследованию статистических связей в шифре TEA. Основной целью работы является обнаружение некоторых статистических особенностей, позволяющих снизить стойкость данного алгоритма

0789355(P=0)4588(P=0)2509(P=0)1221(P=0)632(P=0)287(P=0)140(P=0)77(P=0)39(P=0)1.06183403(P=0)18631(P=0)9807(P=0)5044(P=0)2471(P=0)1296(P=0)602(P=0)307(P=0)151(P=0)1.0464817(P=1.82077e-014)1412(P=0)919(P=0)499(P=0)232(P=0)119(P=0)57(P=0)27(P=0)11(P=9.00342e-008)1.05658197(P=0)11909(P=0)6335(P=0)3274(P=0)1627(P=0)849(P=0)439(P=0)218(P=0)93(P=0)1.007422(P=0.502951)200(P=0)210(P=0)126(P=0)54(P=0)43(P=0)17(P=1.02141e-014)7(P=0.000361863)4(P=0.0547239)1.069870(P=1)59(P=0)84(P=0)51(P=0)25(P=0)11(P=1.10463e-007)3(P=0.211461)2(P=0.527229)4(P=0.0636062)1.03328121(P=0)11092(P=0)6272(P=0)3086(P=0)1522(P=0)786(P=0)363(P=0)186(P=0)90(P=0)1.14562154(P=0)10469(P=0)5626(P=0)2836(P=0)1390(P=0)701(P=0)333(P=0)176(P=0)91(P=0)1.033930(P=1)0(P=1)0(P=1)1(P=0.644394)0(P=1)0(P=1)3(P=0.200224)1(P=0.644394)2(P=0.513384)1.2952795(P=0)9269(P=0)5028(P=0)2568(P=0)1208(P=0)629(P=0)328(P=0)168(P=0)85(P=0)1.09897115(P=0)9830(P=0)5390(P=0)2695(P=0)1326(P=0)690(P=0)316(P=0)171(P=0)106(P=0)1.241620(P=1)0(P=1)1(P=0.711084)2(P=0.588821)2(P=0.588821)1(P=0.711084)0(P=1)0(P=1)4(P=0.0912951)1.4130998(P=0)11931(P=0)6833(P=0)3451(P=0)1732(P=0)812(P=0)401(P=0)183(P=0)106(P=0)Продолжение таблицы для 10-20 раундов:номерРаунда::10111213141516171819201.031051592(P=0)771(P=0)380(P=0)192(P=0)89(P=0)50(P=0)25(P=0)18(P=8.88178e-016)7(P=0.000409809)6(P=0.00254006)3(P=0.199329)1.05519109(P=0)71(P=0)36(P=0)17(P=2.05391e-014)11(P=9.72163e-008)1(P=0.651875)3(P=0.206861)1(P=0.651875)3(P=0.206861)0(P=1)6(P=0.00281115)1.0789316(P=4.34319e-013)8(P=7.64134e-005)5(P=0.0156133)5(P=0.0156133)3(P=0.214308)1(P=0.660041)0(P=1)0(P=1)0(P=1)2(P=0.530666)1(P=0.660041)1.0618380(P=0)24(P=0)19(P=0)5(P=0.0147852)7(P=0.00047955)5(P=0.0147852)2(P=0.52416)2(P=0.52416)2(P=0.52416)0(P=1)0(P=1)1.046488(P=6.30345e-005)3(P=0.204138)3(P=0.204138)1(P=0.648829)1(P=0.648829)1(P=0.648829)1(P=0.648829)1(P=0.648829)0(P=1)1(P=0.648829)1(P=0.648829)1.0565852(P=0)29(P=0)5(P=0.014537)9(P=8.47882e-006)7(P=0.000467045)2(P=0.522148)4(P=0.061661)1(P=0.652357)2(P=0.522148)0(P=1)1(P=0.652357)1.007424(P=0.0547239)2(P=0.502951)0(P=1)1(P=0.634839)3(P=0.191998)0(P=1)0(P=1)1(P=0.634839)1(P=0.634839)2(P=0.502951)1(P=0.634839)1.069870(P=1)2(P=0.527229)1(P=0.656947)2(P=0.527229)0(P=1)2(P=0.527229)0(P=1)0(P=1)3(P=0.211461)0(P=1)0(P=1)1.0332851(P=0)28(P=0)14(P=4.79259e-011)9(P=7.20556e-006)1(P=0.644161)1(P=0.644161)2(P=0.513128)0(P=1)0(P=1)0(P=1)2(P=0.513128)1.1456242(P=0)27(P=0)13(P=1.95657e-009)7(P=0.000717195)2(P=0.555312)3(P=0.23541)1(P=0.681973)1(P=0.681973)1(P=0.681973)1(P=0.681973)2(P=0.555312)1.033930(P=1)1(P=0.644394)0(P=1)0(P=1)2(P=0.513384)0(P=1)0(P=1)0(P=1)0(P=1)1(P=0.644394)1(P=0.644394)1.2952734(P=0)20(P=2.22045e-016)12(P=7.25938e-008)6(P=0.00676782)6(P=0.00676782)3(P=0.283346)3(P=0.283346)1(P=0.726177)0(P=1)1(P=0.726177)3(P=0.283346)1.0989734(P=0)15(P=7.83262e-012)9(P=1.12855e-005)5(P=0.0166208)1(P=0.666787)3(P=0.220625)0(P=1)1(P=0.666787)2(P=0.538194)0(P=1)2(P=0.538194)1.241621(P=0.711084)1(P=0.711084)3(P=0.266107)2(P=0.588821)3(P=0.266107)1(P=0.711084)0(P=1)1(P=0.711084)3(P=0.266107)3(P=0.266107)0(P=1)1.4130952(P=0)33(P=0)11(P=1.39021e-006)11(P=1.39021e-006)3(P=0.321185)3(P=0.321185)3(P=0.321185)0(P=1)3(P=0.321185)2(P=0.643156)2(P=0.643156)Зависимость просматривается на протяжении 19 раундов.Близкие ключи, отличающиеся в1,33 битахПроводилось 1000000 экспериментов, в каждом из которых случайным образом генерировался входной блок и ключевой блок. Близкий ключ, подающийся на вторую схему, отличен в 1 и 33 битах. Результаты приведены в виде фрагмента таблицы типа 2(для 1-9 раундов):номерРаунда::1234567891.03105496355(P=0)357054(P=0)179622(P=0)88600(P=0)44170(P=0)22469(P=0)11281(P=0)5643(P=0)2808(P=0)1.055191196(P=0)27193(P=0)14239(P=0)7020(P=0)3438(P=0)1814(P=0)888(P=0)489(P=0)229(P=0)1.0789394(P=0)4448(P=0)2351(P=0)1199(P=0)611(P=0)295(P=0)161(P=0)77(P=0)40(P=0)1.06183566(P=0)16949(P=0)8760(P=0)4441(P=0)2159(P=0)1098(P=0)584(P=0)276(P=0)143(P=0)1.0464819(P=0)1588(P=0)912(P=0)468(P=0)237(P=0)113(P=0)63(P=0)32(P=0)16(P=2.81553e-013)1.05658307(P=0)11100(P=0)5967(P=0)2868(P=0)1453(P=0)712(P=0)342(P=0)159(P=0)92(P=0)1.007421(P=0.634839)236(P=0)179(P=0)117(P=0)59(P=0)31(P=0)19(P=0)6(P=0.00229367)1(P=0.634839)1.069871(P=0.656947)77(P=0)65(P=0)38(P=0)18(P=1.55431e-015)8(P=7.24634e-005)7(P=0.000499226)4(P=0.0636062)3(P=0.211461)1.03328181(P=0)10758(P=0)5815(P=0)2896(P=0)1461(P=0)731(P=0)327(P=0)191(P=0)93(P=0)1.14562212(P=0)10086(P=0)5235(P=0)2671(P=0)1297(P=0)615(P=0)323(P=0)143(P=0)81(P=0)1.033930(P=1)0(P=1)0(P=1)0(P=1)0(P=1)0(P=1)0(P=1)3(P=0.200224)1(P=0.644394)Продолжение таблицы для 10-18 раундов:номерРаунда::1011121314151617181.031051408(P=0)679(P=0)336(P=0)176(P=0)96(P=0)37(P=0)27(P=0)6(P=0.00254006)2(P=0.512261)1.05519110(P=0)58(P=0)26(P=0)14(P=6.19531e-011)9(P=8.3981e-006)3(P=0.206861)4(P=0.0614598)2(P=0.521616)0(P=1)1.0789322(P=0)11(P=1.19413e-007)2(P=0.530666)4(P=0.0649493)1(P=0.660041)6(P=0.00309773)1(P=0.660041)4(P=0.0649493)3(P=0.214308)1.0618365(P=0)34(P=0)9(P=8.79034e-006)8(P=6.90986e-005)3(P=0.208938)3(P=0.208938)1(P=0.654177)2(P=0.52416)1(P=0.654177)1.0464810(P=8.87095e-007)2(P=0.518258)1(P=0.648829)4(P=0.0602028)2(P=0.518258)1(P=0.648829)2(P=0.518258)0(P=1)2(P=0.518258)1.0565847(P=0)15(P=4.66138e-012)8(P=6.69734e-005)7(P=0.000467045)4(P=0.061661)2(P=0.522148)1(P=0.652357)0(P=1)0(P=1)1.007423(P=0.191998)2(P=0.502951)0(P=1)1(P=0.634839)2(P=0.502951)0(P=1)0(P=1)0(P=1)3(P=0.191998)1.069873(P=0.211461)2(P=0.527229)1(P=0.656947)1(P=0.656947)2(P=0.527229)2(P=0.527229)1(P=0.656947)0(P=1)0(P=1)1.0332845(P=0)21(P=0)13(P=6.15758e-010)6(P=0.00256418)5(P=0.0134669)1(P=0.644161)1(P=0.644161)3(P=0.20002)2(P=0.513128)1.1456250(P=0)28(P=0)12(P=2.10061e-008)5(P=0.019123)6(P=0.0040163)3(P=0.23541)1(P=0.681973)1(P=0.681973)0(P=1)1.033932(P=0.513384)0(P=1)1(P=0.644394)0(P=1)0(P=1)2(P=0.513384)1(P=0.644394)1(P=0.644394)2(P=0.513384)Зависимость просматривается на протяжении 17 раундов.Близкие ключи, отличающиеся в i,32+i битах , где i=0,30 и i=64,94В итоге, практически были получены следующие результаты при исследовании близких ключей, различающихся в битах с номерами (i,32+i), где i=0,30 и i=64,94 :Инвертируемые битыРезультатИнвертируемые битыРезультат0,32Зависимость просматривается на протяжении 18 раундов64,96Зависимость просматривается на протяжении 18 раундов1,33Зависимость просматривается на протяжении 17 раундов65,97Зависимость просматривается на протяжении 17 раундов2,34Зависимость просматривается на протяжении 17 раундов66,98Зависимость просматривается на протяжении 17 раундов3,35Зависимость просматривается на протяжении 17 раундов67,99Зависимость просматривается на протяжении 17 раундов4,36Зависимость просматривается на протяжении 11 раундов68,100Зависимость просматривается на протяжении 11 раундов5,37Зависимость просматривается на протяжении 11 раундов69,101Зависимость просматривается на протяжении 11 раундов6,38Зависимость просматривается на протяжении 11 раундов70,102Зависимость просматривается на протяжении 11 раундов7,39Зависимость просматривается на протяжении 11 раундов71,103Зависимость просматривается на протяжении 11 раундов8,40Зависимость просматривается на протяжении 11 раундов72,104Зависимость просматривается на протяжении 11 раундов9,41Зависимость просматривается на протяжении 11 раундов73,105Зависимость просматривается на протяжении 11 раундов10,42Зависимость просматривается на протяжении 11 раундов74,106Зависимость просматривается на протяжении 11 раундов11,43Зависимость просматривается на протяжении 11 раундов75,107Зависимость просматривается на протяжении 11 раундов12,44Зависимость просматривается на протяжении 11 раундов76,108Зависимость просматривается на протяжении 11 раундов13,45Зависимость просматривается на протяжении 11 раундов77,109Зависимость просматривается на протяжении 11 раундов14,46Зависимость просматривается на протяжении 11 раундов78,110Зависимость просматривается на протяжении 11 раундов15,47Зависимость просматривается на протяжении 11 раундов79,111Зависимость просматривается на протяжении 11 раундов16,48Зависимость просматривается на протяжении 11 раундов80,112Зависимость просматривается на протяжении 11 раундов17,49Зависимость просматривается на протяжении 11 раундов81,113Зависимость просматривается на протяжении 11 раундов18,50Зависимость просматривается на протяжении 11 раундов82,114Зависимость просматривается на протяжении 11 раундов19,51Зависимость просматривается на протяжении 11 раундов83,115Зависимость просматривается на протяжении 11 раундов20,52Зависимость просматривается на протяжении 11 раундов84,116Зависимость просматривается на протяжении 11 раундов21,53Зависимость просматривается на протяжении 11 раундов85,117Зависимость просматривается на протяжении 11 раундов22,54Зависимость просматривается на протяжении 11 раундов86,118Зависимость просматривается на протяжении 11 раундов23,55Зависимость просматривается на протяжении 11 раундов87,119Зависимость просматривается на протяжении 11 раундов24,56Зависимость просматривается на протяжении 11 раундов88,120Зависимость просматривается на протяжении 11 раундов25,57Зависимость просматривается на протяжении 11 раундов89,121Зависимость просматривается на протяжении 11 раундов26,58Зависимость просматривается на протяжении 13 раундов90,122Зависимость просматривается на протяжении 13 раундов27,59Зависимость просматривается на протяжении 16 раундов91,123Зависимость просматривается на протяжении 16 раундов28,60Зависимость просматривается на протяжении 17 раундов92,124Зависимость просматривается на протяжении 17 раундов29,61Зависимость просматривается на протяжении 17 раундов93,125Зависимость просматривается на протяжении 17 раундов30,62Зависимость просматривается на протяжении 18 раундов94,126Зависимость просматривается на протяжении 18 раундовВыводБыло найдено 62 варианта искажений 2 битов, при использовании которых наблюдается наличие зависимости в заполнениях регистров до 11 раунда (включительно). Это означает, что для поиска истинного ключа, в 11 раундовом шифраторе TEA, достаточно будет обнаружить один из 63 ключей (62 близких, либо 1 истинный), путем обнаружения неравновероятности распределения вектора различий d0d1, например с помощью статистики количества серий и веса, далее, если был обнаружен близкий ключ, перебрать все возможные варианты близких ключей к найденному, отличающихся в (i,32+i) битах, где i=0,30 и i=64,94. Заметим, что вероятность того, что случайно выбранный ключ из ключевого множества для опробования, окажется либо истинным, либо близким ключом к истинному, равна 632126 (вместо 2128 мы пишем 2126 за счет наличия эквивалентных ключей см.[4]). Таким образом, для поиска истинного ключа, достаточно будет перебрать 212663≈2120.5 вариантов ключей.Аналогичным образом, для 13 раундового шифратора TEA, для поиска истинного ключа достаточно будет перебрать 212619≈2122 вариантов ключей.Для 16 раундового шифратора TEA, для поиска истинного ключа достаточно будет перебрать 212617≈2122 вариантов ключей.Для 17 раундового шифратора TEA, для поиска истинного ключа достаточно будет перебрать 212615≈2122.5 вариантов ключей.Для 18 раундового шифратора TEA, для поиска истинного ключа достаточно будет перебрать 21265≈2124 вариантов ключей.Однако данный результат не представляет интереса для практики, в силу большой трудоёмкости задачи проверки ключа на близость.Уменьшенная выборкаДля упрощения задачи проверки ключа на близость, была проведена серия экспериментов по исследованию взаимосвязи между схемами с близкими ключами отличными i,32+i битах , где i=0,30 и i=64,94, в условиях малой выборки.Близкие ключи, отличающиеся в 0 и 32 битахПроводилось 1000 экспериментов, в каждом из которых случайным образом генерировался входной блок и ключевой блок. Близкий ключ, подающийся на вторую схему, отличен в 0 и 32 битах. Данные будут выведены в виде фрагмента таблицы типа 2(для 1-10 раундов):номерРаунда::123456789101.02148507(P=0)669(P=0)367(P=0)187(P=0)84(P=0)47(P=0)18(P=6.66134e-016)13(P=5.08585e-010)8(P=5.30768e-005)3(P=0.1962)1.019070(P=1)12(P=6.03301e-009)24(P=0)5(P=0.0127748)10(P=6.88683e-007)2(P=0.507565)5(P=0.0127748)2(P=0.507565)0(P=1)1(P=0.639259)1.033390(P=1)20(P=0)23(P=0)14(P=4.45872e-011)5(P=0.0134034)2(P=0.513178)5(P=0.0134034)3(P=0.199899)0(P=1)1(P=0.64439)1.077690(P=1)8(P=7.44575e-005)12(P=1.07065e-008)10(P=1.09442e-006)5(P=0.0154748)2(P=0.530211)3(P=0.21376)1(P=0.659815)6(P=0.00305594)2(P=0.530211)1.072350(P=1)0(P=1)4(P=0.0638193)4(P=0.0638193)0(P=1)3(P=0.212083)0(P=1)1(P=0.657992)2(P=0.528185)1(P=0.657992)1.000590(P=1)8(P=4.6549e-005)10(P=5.91452e-007)12(P=4.99727e-009)5(P=0.0119917)4(P=0.0536577)2(P=0.500236)0(P=1)2(P=0.500236)1(P=0.632522)1.036210(P=1)0(P=1)15(P=3.30624e-012)0(P=1)2(P=0.514279)0(P=1)4(P=0.0585927)0(P=1)1(P=0.645393)1(P=0.645393)1.094230(P=1)4(P=0.0670899)13(P=1.10197e-009)6(P=0.00326551)2(P=0.536441)1(P=0.665403)1(P=0.665403)1(P=0.665403)4(P=0.0670899)0(P=1)1.206990(P=1)0(P=1)4(P=0.0851616)3(P=0.254851)2(P=0.577041)0(P=1)1(P=0.701122)3(P=0.254851)1(P=0.701122)1(P=0.701122)Зависимость просматривается на протяжении 9 раундов.Несмотря на то, что эксперимент проводился в условиях малой выборки, зависимость продолжала наблюдаться на большом числе раундов, поэтому имеет смысл провести подобный эксперимент для остальных близких ключей вида i,32+i битах , где i=0,30 и i=64,94.Близкие ключи, отличающиеся в i,32+i битах , где i=0,30 и i=64,94 в условиях малой выборкиВ итоге, практически были получены следующие результаты при исследовании близких ключей, различающихся в битах с номерами (i,32+i), где i=0,30 и i=64,94 :Инвертируемые битыРезультатИнвертируемые битыРезультат0,32Зависимость просматривается на протяжении 9 раундов64,96Зависимость просматривается на протяжении 9 раундов1,33Зависимость просматривается на протяжении 8 раундов65,97Зависимость просматривается на протяжении 8 раундов2,34Зависимость просматривается на протяжении 8 раундов66,98Зависимость просматривается на протяжении 8 раундов3,35Зависимость просматривается на протяжении 8 раундов67,99Зависимость просматривается на протяжении 8 раундов4,36Зависимость просматривается на протяжении 6 раундов68,100Зависимость просматривается на протяжении 6 раундов5,37Зависимость просматривается на протяжении 6 раундов69,101Зависимость просматривается на протяжении 6 раундов6,38Зависимость просматривается на протяжении 6 раундов70,102Зависимость просматривается на протяжении 6 раундов7,39Зависимость просматривается на протяжении 6 раундов71,103Зависимость просматривается на протяжении 6 раундов8,40Зависимость просматривается на протяжении 6 раундов72,104Зависимость просматривается на протяжении 6 раундов9,41Зависимость просматривается на протяжении 6 раундов73,105Зависимость просматривается на протяжении 6 раундов10,42Зависимость просматривается на протяжении 6 раундов74,106Зависимость просматривается на протяжении 6 раундов11,43Зависимость просматривается на протяжении 6 раундов75,107Зависимость просматривается на протяжении 6 раундов12,44Зависимость просматривается на протяжении 6 раундов76,108Зависимость просматривается на протяжении 6 раундов13,45Зависимость просматривается на протяжении 6 раундов77,109Зависимость просматривается на протяжении 6 раундов14,46Зависимость просматривается на протяжении 6 раундов78,110Зависимость просматривается на протяжении 6 раундов15,47Зависимость просматривается на протяжении 6 раундов79,111Зависимость просматривается на протяжении 6 раундов16,48Зависимость просматривается на протяжении 6 раундов80,112Зависимость просматривается на протяжении 6 раундов17,49Зависимость просматривается на протяжении 6 раундов81,113Зависимость просматривается на протяжении 6 раундов18,50Зависимость просматривается на протяжении 6 раундов82,114Зависимость просматривается на протяжении 6 раундов19,51Зависимость просматривается на протяжении 6 раундов83,115Зависимость просматривается на протяжении 6 раундов20,52Зависимость просматривается на протяжении 6 раундов84,116Зависимость просматривается на протяжении 6 раундов21,53Зависимость просматривается на протяжении 6 раундов85,117Зависимость просматривается на протяжении 6 раундов22,54Зависимость просматривается на протяжении 6 раундов86,118Зависимость просматривается на протяжении 6 раундов23,55Зависимость просматривается на протяжении 6 раундов87,119Зависимость просматривается на протяжении 6 раундов24,56Зависимость просматривается на протяжении 6 раундов88,120Зависимость просматривается на протяжении 6 раундов25,57Зависимость просматривается на протяжении 6 раундов89,121Зависимость просматривается на протяжении 6 раундов26,58Зависимость просматривается на протяжении 6 раундов90,122Зависимость просматривается на протяжении 6 раундов27,59Зависимость просматривается на протяжении 6 раундов91,123Зависимость просматривается на протяжении 6 раундов28,60Зависимость просматривается на протяжении 7 раундов92,124Зависимость просматривается на протяжении 7 раундов29,61Зависимость просматривается на протяжении 8 раундов93,125Зависимость просматривается на протяжении 8 раундов30,62Зависимость просматривается на протяжении 8 раундов94,126Зависимость просматривается на протяжении 8 раундовВыводБыло найдено 62 варианта искажений 2 битов, при использовании которых наблюдается наличие зависимости в заполнениях регистров до 6 раунда (включительно). Это означает, что для поиска истинного ключа, в 6 раундовом шифраторе TEA, достаточно будет обнаружить один из 63 ключей (62 близких, либо 1 истинный), путем обнаружения неравновероятности распределения вектора различий d0d1, например с помощью статистики количества серий и веса, далее, если был обнаружен близкий ключ, перебрать все возможные варианты близких ключей к найденному, отличающихся в (i,32+i) битах, где i=0,30 и i=64,94. Заметим, что вероятность того, что случайно выбранный ключ из ключевого множества для опробования, окажется либо истинным, либо близким ключом к истинному, равна 632126 (вместо 2128 мы пишем 2126 за счет наличия эквивалентных ключей см.[4]). Таким образом, для поиска истинного ключа, достаточно будет перебрать 212663≈2120.5 вариантов ключей.Аналогичным образом, для 7 раундового шифратора TEA, для поиска истинного ключа достаточно будет перебрать 212615≈2123,5 вариантов ключей.Для 8 раундового шифратора TEA, для поиска истинного ключа достаточно будет перебрать 212613≈2123,5 вариантов ключей.Для 9 раундового шифратора TEA, для поиска истинного ключа достаточно будет перебрать 21263≈2124.5 вариантов ключей.В данном случае, задача проверки ключа на близость не является сложной, однако описанный выше способ перебора не может быть применён на практике, поскольку его трудоемкость больше трудоёмкости тотального перебора ключей.Слабые ключиВ данной серии экспериментов было проведено исследование взаимосвязи схем, использующих близкие ключи, отличные в двух битах вида i,32+i, где i=0,30 и i=64,94., при условии, что ключи являются слабыми (распределение битов ключа не является случайным равновероятным).В данном разделе будут приведены результаты экспериментов только для близких ключей, отличающихся в 0 и 32 битах, но их можно обобщить до результатов исследования близких ключей, отличающихся в i,32+i битах, где i=0,30 и i=64,94, так как для любых близких ключей данного множества, результат эксперимента, приведённого ниже, выражает одну и ту же мысль.Близкие ключи, отличающиеся в 0, 32 битах(эксперимент 1)Проводилось 1000000 экспериментов, в каждом из которых случайным образом генерировался входной блок и первых 32 бита ключевого блока (иными словами случайным образом генерировался ключ key[0]), остальные биты ключа равнялись 0 (key1=0,key2=0,key3=0). Близкий ключ, подающийся на вторую схему, отличен в 0 и 32 битах. Результаты приведены в виде фрагмента таблицы типа 2(для 1-9 раундов):номерРаунда::1234567891.03105496154(P=0)394815(P=0)199763(P=0)99985(P=0)50623(P=0)25042(P=0)12610(P=0)6271(P=0)3167(P=0)1.055191376(P=0)29991(P=0)15789(P=0)7825(P=0)3927(P=0)1954(P=0)999(P=0)515(P=0)242(P=0)1.07893228(P=0)4113(P=0)2395(P=0)1240(P=0)569(P=0)299(P=0)149(P=0)77(P=0)47(P=0)1.