Криптографическая стойкость

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

Типы криптостойких систем шифрования

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

Абсолютно стойкие системы

Основная статья: Абсолютно стойкий шифр

Aбсолютно стойкие (или теоретической стойкости) - если криптосистема не может быть раскрыта ни теоретически, ни практически даже при наличии у атакующего бесконечно больших вычислительных ресурсов.

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

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

Шенноном было доказано, что примером абсолютно стойкого алгоритма является шифр Вернама (одноразовый блокнот). Иными словами, корректное использование шифра Вернама не даёт злоумышленнику никакой информации об открытом тексте (любой бит сообщения он может лишь угадать с вероятностью $1/2$).

Достаточно стойкие системы

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

Стойкость таких систем базируется на теории сложности и оценивается в расчёте на определённый момент времени и последовательно c двух позиций:

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

В каждом конкретном случае могут существовать дополнительные критерии оценки стойкости.

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

Оценка криптостойкости систем шифрования

Начальная оценка

Поскольку атака методом грубой силы (полным перебором всех ключей) возможна для всех типов криптографических алгоритмов, кроме абсолютно стойких «по Шеннону», для вновь созданного алгоритма она может являться единственной существующей. Способы её оценки основываются на вычислительной сложности, которая затем может быть выражена во времени, деньгах, и требуемой производительности вычислительных ресурсов, например, в MIPS. Эта оценка пока является максимальной и минимальной одновременно.

Текущая оценка

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

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

Также важным способом проверки стойкости являются атаки на реализацию, выполняемые для конкретного программно-аппаратно-человеческого комплекса.

Важность длительной проверки и открытого обсуждения

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

Недостаточная проверка (по мнению многих криптографов — искусственное ослабление) алгоритма потокового шифрования А5/1 привела к успешной атаке.

См. также

• Криптодоказующие программы
• Полный перебор
• Уровень криптостойкости

Литература

• Мао В. Современная криптография: Теория и практика / пер. Д. А. Клюшина — М.: Вильямс, 2005. — 768 с. — ISBN 978-5-8459-0847-6
• Нильс Фергюсон, Брюс Шнайер. Практическая криптография = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М. : Диалектика, 2004. — 432 с. — 3000 экз. — ISBN 5-8459-0733-0, ISBN 0-4712-2357-3.
• Клод Шеннон. Теория связи в секретных системах / пер. с англ. В. Ф. Писаренко // Работы по теории информации и кибернетике / Под редакцией Р. Л. Добрушина и О. Б. Лупанова. — М. : Издательство иностранной литературы, 1963. — 829 с.
• Гатченко Н.А., Исаев А.С., Яковлев А.Д. Криптографическая защита информации. — СПб : НИУ ИТМО, 2012. — 142 с.
• Н. Смарт. Криптография = Cryptography: An Introduction / пер. с англ. С.А. Кулешова под ред.С.К. Ландо. — М. : Техносфера, 2005. — 528 с. — ISBN 5-94836-043-1. — ISBN 0077099877.

Ссылки

• Перевод статьи Брюса Шнайера, посвящённой атакам на различные блочные шифры;
• Подробно о A5/1, Киви Берд