Вычислительная стойкость криптоалгоритмов

Вычислительная стойкость является количественной характеристикой алгоритмов шифрования и определяется объемом ресурсов, необходимым для вскрытия конкретного алгоритма шифрования при определенных условиях (в том числе и определенным криптоаналитическим методом). Под ресурсами в данном случае понимаются:

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

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

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

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

На практике криптографический алгоритм считается стойким, если:

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

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

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

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

Одним из наиболее ярких примеров анализа алгоритмов с модифицированной структурой является вскрытие алгоритма Skipjack-3XOR (модификации алгоритма шифрования Skipjack, в которой удалены три конкретных операции XOR из 320 подобных). Атака на такой ослабленный алгоритм может быть произведена при наличии всего 2⁹ выбранных открытых текстов и знании соответствующих им шифротекстов выполнением всего около миллиона (10⁶) тестовых операций шифрования^[1]. Этот факт вызывал неоднократные (хотя так и не доказанные) предположения о низком запасе криптостойкости алгоритма Skipjack.

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

• [1] Панасенко С. П. Алгоритмы шифрования: специальный справочник.