Способы криптоанализа симметричных шифров

Пусть некоторый блочный шифратор с  длиной блока m задается  отображением F:Ξ×(K₁×…K₂)→Y, где F=F_R*F_R-1*…*F₂*F₁. При этом k_i∈K_i получаются по некоторой схеме из общего ключа k или выбирается независимо и равновероятно для каждого цикла. Пространство открытых текстов Ξ снабжено групповой операцией , и для каждого X∈Ξ в Ξ существует элемент X⁻¹∈Ξ, обратный к X относительно операции . Выходной информационный блок (i −1)-го цикла является входным блоком i-го цикла, т.е. X (i) = Y(i −1), для 2≤i≤R; открытый текст X=X(1),

зашифрованный текст Y = Y(R).

Пусть одноцикловое преобразование F_j -криптографически слабое. Сделанное предположение вполне допустимо (идея Шеннона о суперпозиции простых шифров для получения сложного шифра). Под слабым криптографическим преобразованием F: Ξ×K →Y будем понимать такое криптографическое преобразование F(X,k)=Y, для которого по известным величинам Y=F(X,k), Y* = F(X*,k) и ΔX = X ⊗ (X*)⁻¹ можно, не зная X и X*, определить множество K′, |K′| << |K|, такое, что k∈K′.

Пусть X и X* - открытые тексты. Два открытых текста определяют последовательность разностей ΔX(0), ΔX(1),…,ΔX(R), где ΔX(0)=ΔX=X⊗(X*)^-1; ΔX(i) = X(i+1)⊗(X*(i+1))^-1, 1≤i≤R-1; ΔX(R)=Y⊗(Y*)^-1. Тогда для любого 1≤i≤R и любой пары (α,β) можно определить вероятность при условии, что вход X и все одноцикловые ключи k_i выбраны случайно, независимо и равновероятно. Пара (α,β) возможных значений вектора (ΔX (0), ΔX (i)) называется дифференциалом i-го цикла.

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

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

       (2)

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

(ω₁,…,ω_R-1), где Pr{θ} обозначает вероятность события θ.

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

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

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

3. Метод линейного анализа

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

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

Пусть имеется блочный шифр , отображающий при фиксированном ключе k∈ вектор открытого текста p∈ в вектор шифротекста c∈. Предполагается, что открытый текст выбирается случайно и равновероятно, а подключи в каждом раунде независимы друг от друга. Сложность атаки связана с количеством необходимых известных открытых текстов, т.к. для любой пары (открытый текст, шифротекст) требуется небольшое количество вычислений для реализации алгоритма.

Эта атака может быть проведена, если имеется только шифротекст. Мацуи были получены следующие результаты:

• если известно, что открытый текст на английском языке, представленный в ASCII кодах, то при 8-раундовый DES вскрывается при 229 известных шифртекстах;
• если открытый текст является случайным ASCII кодом, то 8-раундовый DES вскрывается при 237 известных шифротекстах.

Метод линейного криптоанализа является частным случаем общего статистического метода и основан на использовании выражений вида (формула 3):

(Y(t₁), a) ⊕ (Y(t₂), b) = (k, c),                (3)

где a,b∈, c∈, 0≤t₁<t₂≤R (при этом пару векторов (a,b) называют линейной характеристикой), - скалярное произведение векторов g и h одинаковой размерности. В методе линейного криптоанализа используют только те выражения типа (3), которые выполняются с вероятностью, отличной от 0.5.

Вероятность, с которой выполняется равенство (3), удобно записывать в виде (формула 4):

,               (4)

где -0.5≤ε≤0.5. Число ε называют преобладанием (deviation, bias).

Рассмотрим  простейший (но не самый эффективный) вариант метода линейного криптоанализа - алгоритм определения одного бита ключа, называемый также «алгоритм 1 Мацуи». Этот алгоритм использует выражение типа (3) при t₁ = 0 и t₂ = R, т.е. подставляются непосредственно открытый и зашифрованный тексты (формула 5):

       (5)

где 1≤i≤N, (X_i,Y_i) - пары открытого и зашифрованного текста, известные криптоаналитику. Метод линейного криптоанализа в данном варианте определяет линейную комбинацию (K, c) битов ключа. Подсчитывается мощность множества:

Процедура статистической классификации разбивает  все пространство наблюдений M на две области M₀ и M₁ (M = M₀∪M₁): к области M₀ относят все те наблюдения, для которых N₀ ≥ , а к области M₁ - те наблюдения, для которых N₀< .

Алгоритм  использует принцип максимума правдоподобия: если N₀ ≥   и в равенстве (4) ε > 0 или N₀ < и в равенстве (4) ε < 0, то алгоритм выдает значение (k, c) = 0 , в противном случае (k, c) = 1. Остальные биты ключа определяют методом перебора.

Улучшенный  «алгоритм 2 Мацуи» представляет собой естественное обобщение алгоритма 1 и заключается в использовании выражений вида (3) при t₂ > R и/или t₁ > 0.

Таким образом, метод линейного криптоанализа сводится к построению таких векторов a,b∈, c∈ чтобы модуль ε в выражении (4) был как можно больше. При этом надежность и трудоемкость метода определяются этой величиной |ε|, т.е. для построенных векторов a,b∈, c∈ надо уметь оценивать |ε| в выражении (4).

Эту задачу метод линейного криптоанализа решает, используя итерационную структуру блоковых шифров. Первым шагом при этом является анализ в каждом раунде алгоритма шифрования нелинейных элементов. Для каждого нелинейного элемента вычисляют для всех a’∈, b’∈ вероятности при случайном равновероятном выборе X’ из . Для получения оценки на преобладание для всего алгоритма рассматривают последовательности «согласованных» линейных соотношений для соседних раундов (т.е. соотношения, когда выходная линейная комбинация предыдущего раунда совпадает с входной линейной комбинацией последующего раунда).

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

Поточные  шифры преобразуют открытый текст  в шифртекст шифрованный побитово. Простейшая реализация поточного шифра представлена на рисунке 1. Генератор гаммы выдает поток битов: k₁, k₂,…, k_i, называемый ключевым потоком, или бегущим ключом, или гаммой. Гамма шифра и поток битов открытого текста p₁, p₂,…, p_i подвергаются операции XOR , в результате чего создается поток битов шифротекста c₁, c₂,…,c_i, где c_j = p_j⊕k_j (этот режим шифрования называется гаммированием).  При расшифровании для восстановления битов открытого текста над битами шифртекста и той же самой гаммой тоже выполняется операция XOR: p_j = c_j⊕k_j.

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

Рисунок 1.

Значительная  часть предлагаемых поточных схем состоит  из унифицированных узлов и блоков, напоминая тем самым выставку поделок из детского конструктора. Основными деталями этого «криптографического конструктора» являются:

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

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

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

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

Поточные  шифры почти всегда работают быстрее  и обычно обладают меньшей конструктивной сложностью, чем блочные шифры. Наиболее известный поточный шифр был разработан Р. Ривестом; это шифр RC4, который характеризуется переменным размером ключа и байт-ориентированными операциями. На один байт требуется от 8 до 16 действий, программная реализация шифра выполняется очень быстро. Независимые аналитики исследовали шифр, и он считается защищенным. RC4 используется для шифрования файлов в таких изделиях, как RSA SecurPC. Он также применяется для защиты коммуникаций, например, для шифрования потока данных в Интернет-соединениях, использующих протокол SSL.

Хотя  подавляющее большинство существующих шифров с секретным ключом с определенностью могут быть отнесены или к поточным, или к блочным шифрам, теоретически граница между этими классами остается довольно размытой. Так, например, допускается использование алгоритмов блочного шифрования в режиме поточного шифрования (например, режимы CBF и OFB для алгоритма DES или режим гаммирования для алгоритма ГОСТ 28147-89).

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

Другая  опасность состоит в том, что  одна или несколько внутренних выходных последовательностей – часто выходы отдельных регистры сдвига с линейной обратной связью – могут иметь корреляцию с объединенной гаммой и атакованы при помощи линейной алгебры. Такие атаки называют «корреляционными атаками», или атаками «разделяй и властвуй». Основная идея состоит в выявлении определенной корреляции между выходом генератора и одной из его составных частей. Используя эту информацию, можно собирать данные о других промежуточных выходах до тех пор, пока генератор не будет взломан. К поточным шифрам также применим линейный и дифференциальный криптоанализ.