Криптоанализ модифицированных алгоритмов

Существует немало алгоритмов шифрования, которые являются криптографически стойкими. В известной работе понятие стойкого (strong) алгоритма определено так:
алгоритм является криптографически стойким, если не существует каких-либо методов его вскрытия, кроме метода «грубой силы» (brute force), который будет рассмотрен далее;
кроме того, размер ключа алгоритма является достаточно большим для того, чтобы использование метода «грубой силы» стало невозможным при текущем уровне развития вычислительной техники.

Однако, например, бывает необходимо сравнить между собой два или более криптографически стойких алгоритма шифрования (как, например, на открытом конкурсе по выбору AES, нового стандарта шифрования США. В этом случае используют другую характеристику (скорее качественную, чем количественную) — запас криптостойкости (security margin).

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

Другой вариант определения запаса криптостойкости — анализ модификаций исследуемого алгоритма с незначительными изменениями структуры раунда. Один из наиболее ярких примеров — вскрытие алгоритма Skipjack-3XOR при наличии всего 29 выбранных открытых текстов и соответствующих им шифртекстов выполнением всего около миллиона тестовых операций шифрования. По современным меркам, благодаря данной атаке Skipjack-3XOR можно считать весьма слабым алгоритмом, а ведь он отличается от известного и достаточно распространенного алгоритма шифрования.

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

Алгоритмы шифрования