МЕТОДЫ КРИПТОАНАЛИЗА СИММЕТРИЧНЫХ КРИПТОСИСТЕМ

Методы криптоанализа блочных шифров

Рассмотрим блочный шифр F: ℤ^m₂×ℤⁿ₂→ℤ^m₂, где ключ kϵℤⁿ₂, а блоки открытого и зашифрованного текста X_i,Y_iϵℤ^m₂.

Идея, лежащая в основе большинства итерационных блочных шифров, состоит в построении криптографически стойкой системы путем последовательного применения относительно простых криптографических преобразований. Принцип многоразового шифрования с помощью простых криптографических преобразований был впервые предложен Шенноном: он использовал преобразования перестановки и подстановки. Первое из этих преобразований переставляет отдельные символы преобразуемого информационного блока, а второе – заменяет каждый символ (или группу символов) из преобразуемого информационного блока другим символом из того же алфавита (соответственно группой символов того же размера и из того же алфавита). Узлы, реализующие эти преобразования, называются, соответственно, P-блоками (P-box, permutation box) и S-блоками (S-box, substitution box).

Наибольший прогресс в разработке методов раскрытия блочных шифров был достигнут в конце ХХ века и в основном связан с появлением в начале 90-х годов двух методов – метода разностного (дифференциального) криптоанализа и метода линейного криптоанализа.

Статистический метод

Задачей статистического метода криптоанализа (как и других методов) является разработка алгоритмов определения неизвестного ключа (или части ключа) kϵℤ₂ⁿ. Реализации статистического метода криптоанализа для ряда блочных шифров позволяют получать оценки эффективности алгоритмов определения секретного ключа лучше, чем оценки метода полного перебора ключей. Входом алгоритма является некоторое число пар (X_i, Y_i), i=1, ..., N, открытого и шифрованного текста, полученных в результате применения отображения F с ключом k . Такие пары будем называть (шифро)материалом и обозначим буквой М. Объем материала соответствует числу пар (X_i, Y_i): |М|=N. Предполагается, что открытые тексты X_i, i=1, ..., N,выбраны случайно, равновероятно и независимо из всего пространства Z^m₂.

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

Доступными случайными наблюдениями в нашем случае является материал М, а неизвестным параметром – часть ключа или некоторые линейные комбинации битов ключа. Обозначим множество, в котором принимает значения неизвестный параметр, через Г, |Г|=s≤2ⁿ.

Каждая ПСК определяет разбиение всего пространства наблюдений на T>1 непересекающихся областей: M=M₁UM₂U…UM_T; M_i∩M_j=ø при i≠j, i, jϵ{1, ..., T}. Области M_i, iϵ{1, ..., T}, называют областями принятия решений, причем для заданного наблюдения mϵM сложность алгоритма определения номера i(m), такого, что mϵM_i(m), считается малой. Для каждой области M_i ПСК также определяет упорядоченный список объема s' (1≤s'≤s) элементов множества Г: γ_i,1, γ_i,2, … , γ_i,s', при этом γ_i,j1≠ γ_i,j2 при j1≠j2.

Для определения неизвестного параметра из Г выполняются следующие действия. Сначала по полученному наблюдению mϵM нужно определить номер области принятия решений i(m). Затем последовательно перебирают параметры из Г: γ_i(m),1, γ_i(m),2, … , γ_i(m),s' и проверяют, является ли значение j-го параметра (j=1,…,s') искомым или нет. Алгоритм проверки включает два этапа:

1. доопределение оставшейся части ключа;

2. проверка, правильно ли определен весь ключ.

Первый шаг отсутствует, если в качестве неизвестного параметра выступает весь ключ. В этом случае Г=ℤⁿ₂. Как правило, для доопределения оставшейся части ключа используется полный перебор всех оставшихся неизвестными битов ключа. Если параметром является часть ключа или невырожденная линейная комбинация битов ключа и Г= ℤ^n*₂, 1≤n*≤n, потребуется перебрать 2^n-n* вариантов.

Проверка того, правильно ли доопределен весь ключ, осуществляется следующим образом: для пар (X_i, Y_i)ϵM, X_i, Y_iϵ ℤⁿ₂, iϵ{1,...,N}, открытого и шифрованного текста из доступного материала M проверяют, выполнены или нет равенства: F(X_i, k*)=Y_i, где k*ϵℤⁿ₂ – опробуемый вариант всего ключа. Ложный ключ, как правило, отсеивается уже на первых шагах проверки. На самом деле проверку достаточно осуществить для d первых пар открытого и зашифрованного текста, где число d таково, что для любого набора из d различных открытых текстов X_i, i=1,...,d, и для любых двух различных ключей k₁≠k₂ϵℤⁿ₂ найдется такой номер jϵ{1,..,d}, что F(X_j, k₁)≠F(X_j, k₂) (минимальное d₀, удовлетворяющее этому условию, называют расстоянием единственности шифра F).

Алгоритмы определения ключа сравнивают по трем параметрам: N – объем используемого материала, Q₀ – средняя трудоемкость работы алгоритма и π₀ – надежность алгоритма. Q₀ и π₀ зависят от того, какие открытые тексты были случайно выбраны, и от искомого ключа. Трудоемкость соответствует математическому ожиданию числа шагов алгоритма при случайном выборе открытых текстов и случайном, равновероятном и независимом от выбора открытых текстов выборе ключа. Надежность алгоритма равна математическому ожиданию вероятности того, что процедура выдаст правильный результат в предположении, что ключ выбран в пространстве n случайно, равновероятно и независимо от выбора открытых текстов. Между параметрами Q₀ и π₀ существует прямая зависимость: чем выше надежность, тем больше трудоемкость, и наоборот.

__________________________________________________

Математическое ожидание – среднее значение случайной величины (распределение вероятностей стационарной случайной величины) при стремлении количества выборок (испытаний) ее к бесконечности. Математическое ожидание – одно из основных понятий в теории вероятностей. В англоязычной литературе обозначается через E[X], в русскоязычной –M[X].

Если X – дискретная случайная величина, имеющая распределение P(X=x_i)=p_i, Σ_i=1,∞p_i=1, то M[X]=Σ_i=1,∞x_ip_i.

__________________________________________________

Метод разностного анализа

Метод разностного (дифференциального) анализа сочетает в себе обобщение идеи общей линейной структуры с применением вероятностно-статистических методов исследования. Этот метод относится к атакам по выбранному открытому тексту. Попытки применить разностный анализ к известному открытому тексту в большинстве случаев приводили к резкому увеличению требуемого материала. Метод был разработан в 1990 году израильскими математиками Э. Бихамом и А. Шамиром. Криптографы с помощью этого метода провели атаку на DES, которая оказалась эффективнее атаки «в лоб». Идея, близкая к методу дифференциального анализа, была опубликована до работы Э. Бихама и А. Шамира в 1990 году С. Мерфи.

Пусть некоторый блочный шифратор (блочный алгоритм) с длиной блока m задается отображением F: E×(K₁×…×K_r)→Y, где F=F_r°F_r-1°…°F₂°F₁. При этом k_iϵK_i получаются по некоторой схеме из общего ключа k или выбирается независимо и равновероятно для каждого цикла. Пространство открытых текстов E снабжено групповой операцией ⊗, и для каждого XϵE в E существует элемент X-1ϵE, обратный к X относительно операции ⊗. Выходной информационный блок (i-1)-го цикла является входным блоком i-го цикла, т.е. X(i)=Y(i-1), для i=2,…,r; открытый текст X=X(1), зашифрованный текст Y=Y(r).

Иными словами, пусть блочный алгоритм строится по схеме

где K=(K₁, K₂, …, K_r) получается по некоторой схеме из k, или независимо и равновероятно выбирается для каждого цикла.

Под слабым криптографическим преобразованием F: E×K→E мы будем понимать такое криптографическое преобразование F(X, k)=Y, для которого по известным величинам Y=F(X, k), Y*=F(X*, k) и ΔX=X⊗(X*)^-1 можно, не зная X и X*, определить множество K', |K'|<<|K|, такое, что kϵK' (уменьшить множество кандидатов ключей).

Пусть одноцикловое преобразование F_j – криптографически слабое. Сделанное предположение вполне допустимо (идея Шеннона о суперпозиции простых шифров для получения сложного шифра). Пусть X и X* – открытые тексты. Два открытых текста определяют последовательность разностей ΔX(0), ΔX(1),…, ΔX(r), где

ΔX(0)=ΔX=X⊗(X*)^-1; ΔX(i)=X(i+1)⊗(X*(i+1))^-1, i=1,…,R-1; ΔX(r)=Y⊗(Y*)^-1.

Тогда для любого 1≤i≤r и любой пары (α, β) можно определить вероятность P⁽ⁱ⁾_αβ=P(ΔX(i)=β | ΔX(0)=α) при условии, что вход X и все одноцикловые ключи k_i выбраны случайно, независимо и равновероятно. Пара (α, β) возможных значений вектора (ΔX(0), ΔX(i)) называется дифференциалом i -го цикла.

Выберем пару (α, β), для которой величина P^(R-1)_αβ принимает максимальное значение, и пару (X, X*), такую, что ΔX=α. Для одноциклового шифра F_r, полагая ΔX(r-1)=β и зная истинные значения Y=F(X, k) и Y*=F(X*, k), определим множество вероятных одноцикловых ключей K'. Если теперь эту процедуру провести для различных пар (X, X*), удовлетворяющих условию ΔX=α, то ключи, наиболее часто встречающиеся в множествах K', можно считать кандидатами в истинный ключ r-го цикла шифрования. Ключ всей системы находим с помощью перебора оставшихся неизвестными разрядов ключа системы или с использованием особенностей процедуры выработки цикловых ключей из ключа всей системы.

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

Гипотеза о статистической эквивалентности:

P^(r-1)_αβ=P(ΔX(r-1)=β | ΔX(0)=α)≈Prob(ΔX(r-1)=β | ΔX(0)=α, k₁=ω₁, k_R-1=ω_R-1)

для почти всех значений частей ключа, используемых в циклах шифрования (ω₁,…,ω_R-1), где Prob(θ) обозначает вероятность события θ.

Иными словами, идея дифференциального криптоанализа заключается в том, чтобы найти такие ΔХ(1), что при случайном равновероятном выборе Х(1), k₁, …, k_r с вероятностью более 1/(2^N) появится ΔX(r-1), где N – число открытых текстов. Дифференциальный криптоанализ описывается следующей моделью.

Пусть f определяет операции в D и f криптографически слаба. Тогда возможна следующая атака.

1. Выбираем дифференциал (r-1)-го цикла (α, β), для которого вероятность Р(ΔX(r-1)=β | ΔХ(1)=α) большая.

2. Случайно выбираем Х(1) и подбираем Х*(1), чтобы ΔХ(1)=α.

Пусть известны Y(r) и Y*(r).

3. Делаем предположение, что ΔX(r-1)=β и, зная Y(r) и Y*(r), находим кандидата k_r.

4. Повторяем 2 и 3 пока один (частичный) ключ не начнет появляться чаще других. Это и будет k_r.

5. Повторяем 1-4 до нахождения полного ключа.

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

Эффективность метода разностного анализа существенно зависит от выбора характеристики, с помощью которой он проводится. Свойства подстановки Р на разностный анализ систем типа DES не влияют. В то же время, даже изменение порядковой нумерации S-блоков (без изменения их строения) может сильно ослабить DES. При неудачном подборе этой нумерации DES-16 раскрывается за 2⁴⁶ опробований. Стойкость системы DES к методу разностного анализа может также уменьшаться при замене операции векторного сложения на другие арифметические операции, при замене S-блоков на случайно выбранные и даже при внесении минимальных изменений в один S- блок.

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

Метод разностного анализа развивался в следующих направлениях:

1. Вскоре после изобретения метода разностного анализа было предложено использовать разностные характеристики для случая, когда операцию покоординатного суммирования векторов из Z³²₂ (для DES-алгоритма) по модулю 2 заменяют на операцию суммирования этих векторов по модулю2³², рассматривая их как 2-адическую запись целых чисел.

______________________________________________

Целым p-адическим числом для заданного простого p называется бесконечная последовательность x={x₁, x₂, …} вычетов x_n по модулю pⁿ, удовлетворяющих условию:

x_n≡x_n+1 (mod pⁿ).

Сложение и умножение целых p-адических чисел определяется как почленное сложение и умножение таких последовательностей.

______________________________________________

2. В 1993 году израильские математики Бен-Аройа и Бихам предложили искать разностные характеристики, считая, что ключ принимает не все возможные значения, а лишь значения из некоторого подмножества. Этот метод получил название «метод условных дифференциалов».

3. В 1994 году датский математик Ларс Кнудсен предложил строить по аналогии с обычным разностным методом криптоанализа метод усеченных дифференциалов. Идея Кнудсена заключается в том, чтобы "следить" в разностной характеристике лишь за частью бит векторов, участвующих в соотношении.

4. В 1994 году швейцарский криптограф Лаи показал, что для построения метода криптографического анализа вместо пар можно использовать разностные характеристики высших порядков: ⊕aϵLF(x⊕a)=d, где L – пространство в Zⁿ₂, dim L≥2.

5. В 1998 году Бихам, Бирюков и Шамир заметили, что для построения метода криптографического анализа можно использовать дифференциалы, имеющие не повышенную вероятность появления, а пониженную, еще лучше – нулевую (невозможные дифференциалы). Именно этим методом была обнаружена слабость в криптографическом алгоритме Skipjack – первом алгоритме, авторство которого официально признано Агентством Национальной Безопасности США.

6. Для шифров итерационного типа редко удается построить разностную характеристику, имеющую гарантированно большую вероятность. В 1999 году Вагнер предложил использовать не пары, а четверки открытых текстов с заданным набором разностей. Для построения таких четверок Вагнер разработал специальный метод, названный «методом прямоугольника». Развитие этого метода получило название «метода бумеранга».

1. Б. Шнайер. Прикладная криптография.

2. О. А. Логачёв,А. А. Сальников, В. В. Ященко. Булевы функции в теории кодирования и криптологии – М.: МЦНМО, 2004.

3. Ch. Swenson. Modern cryptanalysis.

4. Бехроуз А. Фороузан. Криптография и безопасность сетей.

5. Бехроуз А. Фороузан. Математика криптографии и теория шифрования.

6. Закревский. Программирование вычислений в многомерном булевом пространстве

7. Ю. А. Зуев. По океану дискретной математики: От перечислительной комбинаторики до современной криптографии. Т. 1.

8. JI. K. Бабенко, Е. А. Ищукова, Е. А. Маро, И. Д. Сидоров, П. Л. Кравченко. Развитие криптографических методов и средств защиты информации

9. JI. K. Бабенко, Е. А. Ищукова. Анализ симметричных криптосистем

10. С. М. Авдошин, А. А. Савельева. Криптоанализ: современное состояние и перспективы развития

11. Воронин. Алгебрпический криптоанализ однораундового S-AES

12. Jie Cui1, Liusheng Huang, Hong Zhong, Chinchen Chang, Wei Yang. an improved AES S-box and its performance analysis.

13. Л. К. Бабенко, Е. А. Ищукова. Дифференциальный криптоанализ упрощенной функции хэширования SHA.

14. Л. К. Бабенко, Е. А. Ищукова, Д. М. Алексеев. Реализация поиска слайдовых пар для алгоритма шифрования Магма с использованием технологии MPI.

15. Л. К. Бабенко, Е. А. Ищукова. Финалисты конкурса SHA-3 и основные сведения об их анализе.

16. Л. К. Бабенко, Е. А. Ищукова. И. Д. Сидоров. Параллельные вычисления в криптоанализе.

17. Howard M. Heys. A tutorial on Linear and Differential Cryptanalysys.

18. D. Rudolf. Optimised Differential Cryptanalysis of the DES.

19. K. S. Ooi, B. Ch. Vito. Cryptanalysis of S-DES.