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

Первые открытые упоминания в литературе с 1990 года в работах Мерфи, Бихема и Шамира. Методика анализа строится индивидуально для каждого алгоритма и основана на знании пар сообщений m и m’ для которых известны соответствующие шифртексты E_k(m) и E_k(m’) и XOR-разности между ними с рассмотрением разности между промежуточными частями блоков сообщений.

Для двухветвевой сети Файстеля Δm_i = m_i  m’_i. При этом для каждого раунда в отдельности справедливо следующее:

Δm_i+1 = m_i+1  m’_i+1 = Δm_i-1  [f(m_i,K_i)  f(m’_i,K_i)]

Предполагается, что для многих пар входных данных функции f, имеющих одну и ту же XOR-разность, при использовании одного и того же подключа одинаковой оказывается и XOR-разность для соответствующих выходных пар. Формально говорят, что X влечет Y с вероятностью р, если для относительной доли р входных пар с XOR-разностью Х для соответствующих выходных пар XOR-разность оказывается равной Y. Предположим теперь, что имеется ряд значений X, которые с высокой вероятностью влекут определенные разности выходных значений. Тогда если нам с большой вероятностью известны значения Δm_i-1 и Δm_i то мы с большой вероятностью можем определить и Δm_i-₁. А если удастся найти достаточно много таких значений разности, становится возможным определить подключ, используемый функцией f.

Общая стратегия дифференциального криптоанализа основывается на представленной выше методике для каждого раунда шифрования в отдельности. Процедура начинается с рассмотрения двух сообщений открытого текста m и m' с заданной разностью и имеет своей целью получение вероятностных оценок разностей промежуточных результатов последовательно раунд за раундом с тем, чтобы определить вероятностную оценку для разности соответствующих шифрованных текстов. На самом деле получаются вероятностные оценки для двух 32-битовых половинок сообщения (m₁₇ || m₁₆). После этого выполняется шифрование m и m’, чтобы определить реальные разности при неизвестном ключе, а затем , сравнить результат с вычисленными вероятностными оценками. Если результаты совпадают, т.е.

Е_к(m)  Е_к(m’) = (Δm₁₇||m₁₆),

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

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

Более новым направлением в криптоанализе является линейный криптоанализ. Метод линейного криптоанализа заключается в построении линейной аппроксимации преобразования, выполняемого в ходе шифрования DES. Данный метод позволяет найти ключ DES при наличии 2⁴⁷ известных фрагментов открытого текста, тогда как для дифференциального криптоанализа требуется 2⁴⁷ фрагментов избранного открытого текста.

Пусть для шифра с n-битовыми блоками открытого и шифрованного текста и m-битовым ключом блок открытого текста будет обозначен Р[1],...,Р[n], блок шифрованного текста - С[1],..., С[n], а ключ - К[1],..., K[n]. Тогда определим

A[i,j,…,k] = A[i]  A[j] ...A[k].

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

Р[α₁, α₂„..., α_a]  С[β₁, β₂,..., β_b] = К[γ₁, γ₂,..., γ_c],

выполняющегося с вероятностью р  0,5 (где х = 0 или 1, 1 ≤ а, b ≤ n, 1 ≤ с ≤ т, а α, β и γ представляют фиксированные битовые позиции в блоках). Чем больше значение р отклоняется от 0,5, тем более подходящим считается уравнение. После этого вычисляются значения левой части данного уравнения для большого числа пар соответствующих фрагментов открытого и шифрованного текста. Если результат оказывается равным 0 более чем в половине случаев, полагают, что K[γ₁, γ₂,..., γ_c] = 0. Если же в большинстве случаев получается 1, полагают, что K[γ₁, γ₂,..., γ_c] = 1. Достаточное количество полученных таким образом равенств образуют систему, решением которой определяется ключ. Ввиду линейности получаемых уравнений, проблему можно решать для каждого раунда шифрования в отдельности, а полученные результаты затем объединить.

Атаки на симметричные криптоалгоритмы

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

1. Атака с использованием только шифрованного текста (ciphertext-only attack). Самая сложная атака, при которой злоумышленник обладает минимальным объемом информации. Цель атаки – нахождение ключа и/или открытого текста.

2. Атака с известным открытым текстом (known plaintext attack). Злоумышленник знает один или произвольное количество открытых текстов и соответствующих им шифртекстов. Цель атаки – нахождение ключа и/или открытых текстов, зашифрованных на том же ключе.

3. Атаки с избранным открытым текстом (chosen plaintext attack): автономная (offline) и оперативная (online). Злоумышленник имеет возможность сам выбирать один или произвольное количество открытых текстов и вычислять соответствующий ему шифртекст. Набор открытых текстов подготавливается заранее (автономно) или генерируется в процессе атаки (оперативно). Цель атаки – нахождение ключа.

4. Атака с избранным шифрованным текстом (chosen ciphertext attack). Злоумышленник имеет возможность выбирать как открытый текст (получая соответствующий ему шифрованный текст), так и шифрованный текст (с получением соответствующего ему открытого текста). Цель атаки – нахождение ключа.

5. Различающие атаки (distinguishing attack). Любые нетривиальные методы, позволяющие обнаружить различие между идеальным и реальным шифром. Цель атаки – дискредитация криптосистемы.

6. Атаки на основе коллизий: Атака на основе парадокса задачи о днях рождения (birthday attack) на хэш-функции. Двусторонняя атака или «встреча посередине» (meet-in-the-middle attack) на код аутентификации. Цель – подмена-имитация сообщений.

Отдельно различают атаки с использованием активного аппаратного воздействия на криптосистему при помощи различных излучений, вызывающих помехи и ошибки. Данные атаки возникли в связи с массовым использованием интеллектуальных электронных карточек (smart cards).

Вопрос №17. Состав методов и моделей оценки эффективности КСЗИ