Усечённый дифференциальный криптоанализ

Усечённый дифференциальный криптоанализ — это метод криптоанализа, основанный на изучении не полных, а частичных (усечённых) разностей между парами открытых и шифрованных текстов. В отличие от классического дифференциального криптоанализа, который требует точного знания разностей на всех раундах шифрования, усечённый метод оперирует предсказаниями только о некоторых битах или группах битов разности, что позволяет снизить требования к объёму данных и вычислительным ресурсам. Метод был впервые предложен Ларсом Кнудсеном в 1994 году как обобщение дифференциального криптоанализа для анализа блочных шифров с нелинейными преобразованиями.

История

Усечённый дифференциальный криптоанализ возник как развитие классического дифференциального криптоанализа, разработанного Эли Бихамом и Ади Шамиром в конце 1980-х годов. В 1994 году Ларс Кнудсен на конференции Fast Software Encryption (FSE) представил концепцию усечённых дифференциалов, продемонстрировав их применение к шифру SAFER. Идея заключалась в том, что для многих шифров точное предсказание разностей на всех раундах избыточно: достаточно знать, что разность принадлежит некоторому множеству возможных значений, а не является конкретным числом. Это позволило атаковать шифры, устойчивые к классическому дифференциальному анализу, например, за счёт использования нелинейных S-блоков с низкой вероятностью точных дифференциалов.

В 1995 году Кнудсен и Вагнер применили усечённый метод к шифру DES, показав, что он может быть эффективнее полного перебора для некоторых ключей. В 2000-х годах метод был адаптирован для анализа современных шифров, таких как AES, Serpent и Twofish. В 2010-х годах появились варианты усечённого анализа, интегрированные с линейным криптоанализом и методами на основе невозможных дифференциалов.

Основные понятия

Дифференциал и разность

В дифференциальном криптоанализе рассматривается пара открытых текстов \(P\) и \(P'\) с разностью \(\Delta P = P \oplus P'\) (где \(\oplus\) — операция XOR). После шифрования получаются шифротексты \(C\) и \(C'\) с разностью \(\Delta C = C \oplus C'\). Дифференциалом называется пара \((\Delta P, \Delta C)\), а его вероятность — доля пар, для которых при случайном ключе выполняется данное соотношение.

Усечённый дифференциал

В отличие от классического подхода, усечённый дифференциал задаёт не точное значение разности, а её частичное описание. Например, для 128-битного блока усечённый дифференциал может указывать, что разность в первых 32 битах равна нулю, а остальные биты произвольны. Формально, усечённый дифференциал — это множество пар разностей, удовлетворяющих определённому шаблону (маске). Такой подход позволяет агрегировать множество возможных точных дифференциалов, увеличивая вероятность обнаружения статистической аномалии.

Характеристики

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

Методология

Построение усечённых характеристик

1. Выбор начальной разности: Определяется шаблон разности на входе, например, ненулевая разность только в одном байте.
2. Анализ S-блоков: Для каждого нелинейного преобразования (S-блока) вычисляются возможные выходные разности при заданном входном шаблоне. Если S-блок имеет низкую дифференциальную равномерность, то усечённая характеристика может иметь высокую вероятность.
3. Распространение через линейные слои: Линейные преобразования (например, перестановки, смешивание) распространяют усечённые разности, сохраняя или изменяя шаблон.
4. Оценка вероятности: Суммарная вероятность характеристики вычисляется как произведение вероятностей для каждого раунда, но часто используется приближённая оценка через среднее по всем возможным точным разностям.

Атака

1. Сбор данных: Злоумышленник получает множество пар открытых текстов с заданной начальной разностью и соответствующие шифротексты.
2. Фильтрация: Отбираются пары, у которых шифротексты удовлетворяют усечённому дифференциалу на последнем раунде (или на нескольких раундах).
3. Угадывание ключа: Для отфильтрованных пар перебираются возможные значения ключа последнего раунда (или части ключа), и проверяется, соответствует ли разность после дешифрования предсказанной характеристике. Ключ, дающий наибольшее совпадение, считается истинным.

Отличие от классического метода

• Точность: Классический метод требует точного совпадения разностей, усечённый — только частичного.
• Объём данных: Усечённый метод часто требует меньше пар текстов, так как вероятность усечённого дифференциала выше.
• Сложность: Вычислительная сложность может быть выше из-за необходимости перебора большего числа кандидатов на ключ.

Применение

Шифр DES

Усечённый дифференциальный криптоанализ был применён к DES для сокращения числа раундов, необходимых для атаки. Для 16-раундового DES классический дифференциальный анализ требует \(2^{47}\) пар, а усечённый — около \(2^{40}\) пар при определённых условиях. Однако полная атака на 16-раундовый DES с помощью усечённого метода не была реализована на практике из-за высокой сложности, но метод показал принципиальную возможность атаки на редуцированные версии.

Шифр AES

Для AES (Rijndael) усечённый анализ применялся к версиям с уменьшенным числом раундов (например, 4–6 раундов). В 2000 году Кнудсен и Вагнер показали, что для 4-раундового AES усечённая атака требует около \(2^{20}\) пар, что значительно меньше, чем \(2^{128}\) для полного перебора. Для 6-раундового AES сложность возрастает до \(2^{50}\) пар, что всё ещё ниже экспоненциальной оценки для полного шифра. Полный 10-раундовый AES-128 устойчив к усечённому анализу, так как вероятность усечённых характеристик становится пренебрежимо малой.

Другие шифры

• Serpent: Усечённый анализ показал уязвимость редуцированных версий (до 8–10 раундов из 32), но полный шифр считается стойким.
• Twofish: Атаки на 6–8 раундов из 16 были успешными, но потребовали \(2^{60}\) пар.
• SAFER: Для SAFER K-64 усечённый метод позволил взломать 6 раундов из 8.

Преимущества и ограничения

Преимущества

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

Ограничения

• Сложность оценки: Вероятность усечённых характеристик трудно вычислить точно, часто используются приближения.
• Зависимость от структуры: Метод эффективен только для шифров с определённой структурой (например, с байт-ориентированными S-блоками).
• Вычислительная нагрузка: Перебор кандидатов на ключ может быть значительным, особенно при большом числе усечённых битов.

Критика и развитие

Усечённый дифференциальный криптоанализ критикуется за то, что его практическая применимость ограничена редуцированными версиями шифров. Для современных стандартов, таких как AES-256 или ГОСТ 28147-89, полные версии остаются устойчивыми. Однако метод стимулировал развитие других подходов, включая невозможный дифференциальный криптоанализ и интегральный криптоанализ. В 2000-х годах были предложены гибридные методы, объединяющие усечённые дифференциалы с линейными аппроксимациями, что позволило атаковать шифры с большим числом раундов.

Интересные факты

• Усечённые дифференциалы сыграли ключевую роль в анализе шифра SAFER, который изначально считался устойчивым к классическому дифференциальному анализу.
• В 1998 году Кнудсен использовал усечённый метод для демонстрации атаки на 6-раундовый DES на персональном компьютере за несколько часов.
• Идея усечённых разностей была позже адаптирована для анализа хеш-функций, таких как SHA-1 и SHA-2.

Источники

• Knudsen, L. R. (1994). "Truncated and Higher Order Differentials". Fast Software Encryption (FSE).
• Biham, E., & Shamir, A. (1991). "Differential Cryptanalysis of DES-like Cryptosystems". Journal of Cryptology.
• Daemen, J., & Rijmen, V. (2002). "The Design of Rijndael: AES — The Advanced Encryption Standard". Springer.
• Вагнер, Д., & Кнудсен, Л. (1995). "Truncated Differentials and DES". Proceedings of CRYPTO.