Глава 8

Современные методы анализа симметричных

криптографических шифров

8.1. Цели и содержание криптографического анализа

Под криптографическим анализом понимается всестороннее исследование криптосистемы, в ходе которого оцени-

ваются ее криптографические характеристики.

Цель при разработке – определение возможности и условий применения криптосистемы для защиты информации;

Цель при атаке – определение возможности и условий вскрытия криптосистемы.

Основное содержание криптографического анализа:

1. Исследование свойств криптографических функций системы;

2. Разработка и моделирование методов вскрытия криптосистемы при различных исходных данных, оценка ресур-

сов, необходимых для реализации разработанных методов;

3. Разработка обоснованных рекомендаций по применению криптосистемы или по реализации дешифрования.

8.2. Условия криптографического анализа

Криптоаналитику известны:

· вся выходная информация криптосистемы, например, известны шифрованные сообщения и соответствующие им

открытые сообщения, длины сообщений и их число полагается максимальными при ограничениях, определяе-

мыми конкретными условиями;

· математическая модель семейства криптографических функций {fk } криптосистемы, т. е. может моделировать

для любого открытого сообщения x вычисление значений криптографической функции fk (x) при любом ключе

k;

· криптограммы y1, . . . , yt так и соответствующие им открытые сообщения x1, . . . , xt, при этом не известен ключ

k.

8.3. Практические условия проведения криптоанализа

· Криптоанализ на основе только известных криптограмм;

· Криптоанализ на основе известного открытого сообщения;

· Криптоанализ на основе выбранного открытого сообщения;

· Криптоанализ на основе выбранной криптограммы

8.4. Классификация методов криптографического анализа

По используемым математическим методам:

· Методы апробирования или алгоритмические методы (полный перебор, перебор с учетом эквива-

лентности, использование каталогов, метод Хеллмана и др.);

· Алгебраические или аналитические методы (каталог функций, линейный криптоанализ и др.);

· Статистические методы (частотный анализ, дифференциальный криптоанализ);

По области применения:

· Универсальные метод криптоанализа;

· Специальные методы криптоанализа.

8.5. Метод полного перебора (МПП)

МПП состоит в последовательном переборе всех элементов ключевого множества криптосистемы с целью проверки

ключей на истинность.

Вычислительная сложность (трудоемкость) выполнения МПП используется как эталон для сравнения с другими

методами.

Формальное описание МПП:

8.6. Характеристики МПП

Ek (a1, . . . , at) = (b1, . . . , bt)

(8.1)

Где a1, ldots, at – открытое сообщение в алфавите A;

b1, ldots, bt – криптограмма в алфавите B; Ek - преобразование на ключе k из K; t - lkb.

Условия перебора:

· Известны открытое сообщение (a1, . . . , at) и соответствующая ему криптограмма (b1, . . . , bt);

· Известна криптограмма (b1, . . . , bt) и статистика (например, статистические оценки вероятностей знаков) откры-

того сообщения.

В условии 1 ключ k называется истинным если он удовлетворяет равенству (8.1).

8.6. Характеристики МПП

Оценка сверху трудоемкости МПП:

T ≤ C(t) · |K|,

T - трудоемкость МПП; C(t) – трудоемкость проверки ключа на истинность; |K|- мощность множества ключей.

Надежность метода МПП равна 1.

Оценка средней трудоемкости МПП:

T = C(t) · µ,

– математическое ожидание; µ - число опробываемых ключей до первого успеха;

M C(t) =

1 − pt

q

1

, p = , q = 1 − p, m −

m

(8.2)

1 ≤ M C(t) ≤ 2M µ =

n

i=1

i

n

=

n +1

2

≈

n

2

(8.3)

MT ≈

1 − p n

·

q 2

(8.4)

n

2

≤ MT ≤ n

(8.5)

8.7. Атаки на основе парадокса дней рождений

Полагая равномерным распределение дней рождений (случайно выбранных людей) по дням в году, определить,

сколько человек в среднем достаточно собрать вместе, чтобы хотя бы у двоих был общий день рождения?

· Средняя численность группы людей, среди которой найдется человек, родившийся в заданный день, равна 365.

· Искомая группа из n людей должна содержать 365 различных пар.

· Из Cn ≥ 365 находим n = 28.

Парадокс дней рождений используется для оценки трудоемкости поиска коллизий.

8.8. Применение парадокса дней рождений и хеш-функции

Хеш-функции

Хеш функцией назовем отображение H : M → h следующего вида:

1. M >> h

2. длина h фиксирована

3. M1 = M2 ⇒ P {h1 = h2} > P , где P - наперед заданная вероятность

4. Нахождение M1 = M2 таких что h1 = h2 по времени ограничено снизу наперед заданной константой T0

Применение парадокса дней рождений

Имеется хеш-функция f (x), принимающая значения во множестве Xm, где X – конечное множество;

1. Для заданного y из Xm определить такое сообщение , при котором f (x) = y;

2. Определить коллизию, т. е. сообщение такие x и x , при которых x = x и f (x) = f (x ).

Трудоемкость поиска коллизий

33

t

2

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

T

2

≥ |X|m

Если значение хеш-функции m-разрядные двоичные числа, то для поиска коллизий достаточно перебрать 2(m+1)/2

сообщений. Если требуется возникновение коллизий у случайной пары с вероятностью не больше 2−50, то достаточно

100 разрядной хеш-функции.

8.9. Метод перебора ключей с учетом эквивалентности

Усовершенствование МПП для криптосистем имеющих эквивалентные ключи. Т.е. атака в частности на алгоритм

ключевого расписания.

Ключи k и q из ключевого множества K эквивалентны если Ek (a1, . . . , at) = Eq (a1, . . . , at), для любого натурального

t и любого сообщения a1, . . . , at.

В этом случае множество K можно разбить на не пересекающиеся классы эквивалентности в смысле преобразова-

ния Ek

K = K (1) . . . K (S)

и провести МПП по представителям из классов эквивалентности.

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

8.10. Метод Разделяй и побеждай

Метод предполагает представление ключей k из K в виде вектора k = (k1, k2, . . . kn), k1 из K1, k2 из K2, . . . kn из

Kn) и наличия критерия (или критериев) h позволяющего при известном открытом сообщении и соответствующей

ему криптограмме проверять правильность подлкючей независимо друг от друга.

Если 1, 2, . . . n – трудоемкости апробирования подключей k1, k2, . . . kn то общая трудоемкость является их суммой.

В случае невозможности независимого апробирования общая трудоемкость является произведением (или близко к

нему).

8.11. Линейный криптоанализ

Линейный криптоанализ основан на возможности замены нелинейной функции ее линейным аналогом.

E – функция шифрования, X(i) – блок открытого текста на i−ом цикле, Y(i) – блок шифротекста, K(i) – исполь-

зуемый подключ, X(i), Y(i) – вектора размерности n, K(i) – вектор размерности m.

Введем обозначения (X, a) – скалярное произведение векторов. S – {0,1}, случайная величина для которой P {S =

1} = p, P (S = 0) = 1 − p, ∆(S) = |1 − 2p|

Линейным статистическим аналогом нелинейной функции Y(i) = E(X(i), K(i)) называется случайная величина:

S(i) = (Y(i), α(i)) ⊗ (X(i), β(i)) ⊗ (K, χ(i))

1

Если вероятность P (S(i) = 1) = p = 2 для случайно выбранного открытого текста X(i).

Отклонение ∆(S) = |1 − 2p| определяет эффективность линейного статистического аналога.

Для применения линейного криптоанализа необходимо решить следующие задачи:

1. Нахождение эффективного статистического линейного аналога и вычисление его вероятности;

2. Определение ключа (или несколько битов ключа) с использованием линейного статистического аналога.

8.12. Дифференциальный криптоанализ

Метод основан на выборе открытых текстов. Анализ заключается в изучении процесса изменения несходства для

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

ния с одним и тем же ключом.

Ограничений на выбор открытых текстов не накладывается. Исходя из различий в получившихся шифротекстах,

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

Представим шифр в виде

34

8.12. Дифференциальный криптоанализ

Где K = (K(1), K(2), . . . , K(r)) получается по некоторой схеме из исходного ключа или независимо выбирается для

каждого раунда.

Пусть X(1) и X (1) – пара открытых текстов. Рассмотрим разности

∆X(1) = X(1) − X (1);

∆Y (i) = Y (i) − Y (i).

(8.6)

(8.7)

Задача дифференциального криптоанализа заключается в том, что бы найти такие DeltaX(1), что при случайном

равновероятном выборе X(1), K(1), K(2), . . . , K(r − 1) с вероятностью более 1/(2n) появится ∆Y (r − 1).

Пара (α, β) возможных значений вектора (∆X(i), ∆Y (i)) называется дифференциалом i-го цикла

Рис. 11. Модель дифференциального криптоанализа

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

алгоритму:

1. Выбираем дифференциал (r − 1)-го раунда (α, β), для которого вероятность P (∆X(1)) = α, ∆Y (r − 1) = β)

большая;

2. Случайно выбираем X(1) и подбираем X (1) так, чтобы ∆X(1) = α. Пусть известны Y (r) и Y (r);

3. Делаем предположение, что ∆Y (r − 1) = β, и зная Y (r) и Y (r) находим K(r); Повторяем пп. 2 и 3, пока один

подключ не начнет появляться чаще других

35

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

x

36