В 1998 году известный американский криптограф Брюс Шнайер написал:
Любой, начиная с самого бестолкового любителя и заканчивая лучшим криптографом, может создать алгоритм, который он сам не в состоянии взломать.
Переформулировка этой цитаты, предложенная журналистом Кори Доктороу в 2004 году, стала известна как Закон Шнайера:
Каждый человек может изобрести систему безопасности, которую он был бы не в силах взломать.
Очень хорошей иллюстрацией к закону Шнайера, на мой взгляд, являются попытки усилить алгоритм шифрования DES.
Двойное шифрование
DES был принят в качестве стандарта в 1977 году. Длина ключа нового стандарта составляла 56 бит, довольно большое число по тем временам. Однако закон Мура неумолим, и некоторые криптографы уже тогда начали бить тревогу.
Одними из первых, кто подверг критике длину ключа нового стандарта были небезызвестные отцы-основатели криптографии с открытым ключом: Уитфилд Диффи и Мартином Хеллманом. В одной из своих статей они утверждали, что 56-битный ключ слишком мал и оставляет возможность для атаки полного перебора.
В свете вышеуказанного замечания вполне логичным выглядят попытки увеличить стойкость алгоритма DES, используя технику многократного шифрования. Этот способ позволяет искусственно увеличить длину ключа, применяя несколько раз операцию шифрования с разными ключами.
На первый взгляд может показаться, что для решения проблемы DES достаточно увеличить длину ключа вдвое, т.е. использовать следующую схему в качестве шифрования и расшифровки:
C=EK2 (EK1 (P)),
P=DK1 (DK2 (С)),
где C — шифртекст; P — открытый текст; а EK (P) и DK (С) — процедуры шифрования и расшифровки соответственно.
Приведенная схема увеличивает пространство ключа до 2112 и делает атаку грубой силой бессмысленной затеей.
Казалось бы решение найдено. Но в этот самый момент настало время вспомнить о Законе Шнайера. Если вы создали схему шифрования и не можете найти в ней недостатки, это не означает что их нет.
В 1981 году Ральф Меркл и Мартин Хеллман подробно разбирают безопасность двойного шифрования и описывают способ, позволяющий восстановить ключ шифрования не за 2112 операций шифрования, а за относительно пустяковые 257.
Метод, предложенный Мерклем и Хеллманом относится к классу атак на основе открытых текстов, и применим в случае если злоумышленнику известна пара открытый-закрытый текст.
Суть атаки заключается в следующем. Атакующему известен открытый текст P и соответствующий ему шифртекст С=EK2 (EK1(P)).
Для вскрытия ключа, атакующий осуществляет перебор всех возможных 256 вариантов ключа K1 и записывает в таблицу T1 значения {EK1(P), K1}.
Затем используя значение С, атакующий перебирает 256 вариантов ключа K2 и записывает в таблицу T2 значения {DK2(С), K2}.
Отсортировав таблицы T1 и T2 атакующий в качестве вероятных ключей принимает такие K1 и K2, для которых EK1(P) = DK2(С).
Описанная атака называется «встреча по середине», т.к. с одной стороны выполняется шифрование, а с другой расшифровка. Получившиеся «в середине» результаты сравниваются.
Тройное шифрование
В 1978 году Вальтер Тачман предложил использовать тройное шифрование для увеличения стойкости алгоритма DES. В схеме Тачмана также используется два ключа K1 и K2, но процесс шифрования и расшифровки выглядит следующим образом:
C=EK1 (DK2 (EK1(P)))
P=DK1 (EK2 (DK1(С))).
Этот способ защищен против атаки «встреча по середине». Даже если атакующий сформирует таблицу {DK1(С), K1}, для проведения атаки ему необходимо будет получить все возможные значения {DK2((EK1(P)), K1||K2}, что составляет 2112 записей и разумеется не представляется реальным.
Но и метод Тачмана не долго считался надежным.
Меркл и Хеллман описали вариант атаки с выбранным открытым текстом на схему тройного шифрования.
В предложенной Меклем и Хеллманом атаке злоумышленнику доступен т.н. расшифровывающий оракул. Это означает, что злоумышленник может отправить на вход шифрующей функции любое сообщение и получить его зашифрованный аналог.
Атака Меркла-Хеллмана на тройное шифрование сводится к следующим действиям:
- атакующий осуществляет перебор всех возможных 256 вариантов ключа K2, производит расшифровку блока, состоящего из нулевых байт и записывает в таблицу T1 значения {DK2(0), K2}
- атакующий для каждого из 256 вариантов ключа K1, производит расшифровку блока, состоящего из нулевых байт: DK1(0). Значение DK1(0) атакующий отправляет на вход шифрующему оракулу и расшифровывает полученный от оракула ответ с помощью подбираемого ключа K1: DK1(Enc(DK1(0))). Получившееся значение и вариант ключа K1 {DK1(Enc(DK1(0))), K1} записывается в таблицу T2
- Отсортировав таблицы T1 и T2 атакующий в качестве вероятных ключей принимает такие K1 и K2, для которых
DK1(Enc(DK1(0))) = DK2(0).
Суть метода не совсем очевидна. Для разъяснений распишем что представляет собой функция Enc(). Это сжатая запись тройного шифрования, т.е. Enc(x) = EK1 (DK2 (EK1(x))).
В атаке Меркла-Хеллмана атакующий вычисляет DK1(Enc(DK1(0))). Таким образом если K1 угадан верно в результате получается выражение DK1(EK1 (DK2 (EK1(DK1(0))))) = DK2(0).
Если получившееся значение имеется в таблице T1, то ключи K1 и K2 выбираются в качестве вероятных кандидатов.
Для реализации атаки требуется 257 операций шифрования, что значительно отличается от ожидаемой стойкости тройного шифрования 2112.
Разумеется атаки описанные Мерклем и Хеллманом носят больше теоретический характер и их практическая реализация весьма маловероятно, но они очень хорошо показывают как легко можно допустить ошибку при проектировании криптосистем.
Закон Шнайера
Закон Шнайера предостерегает от использования непроверенных систем безопасности и в особенности систем, спроектированные самостоятельно. Оба приведенных выше варианта решения проблемы длины ключа DES были предложены профессиональными криптографами и тем не менее содержали очень серьезные недостатки, которые были упущены при проектировании. Наивно полагать, что любитель сможет создать стойкую систему.
Фил Циммерманн, создатель PGP, написал по этому поводу следующее:
Когда я учился в колледже в 70-х я придумал, как мне тогда казалось, идеальную схему шифрования. Простой генератор псевдослучайных чисел генерировал гамму, которая суммировалась с открытым текстом. Схема была стойкой против частотного анализа шифртекста и была совершенно не взламываема для спецслужб, обладающим огромными вычислительными мощностями.
Годы спустя я нашел похожую схему в некоторых учебниках по криптографии. Классно. Другие криптографы думают в похожем направлении. К сожалению, схема была описана в качестве простого домашнего задания: взломайте схему, используя базовые методы криптоанализа.
Если вы считаете, что создали идеально стойкую систему, не спешите использовать ее в своем проекте. Вспомните о законе Шнайера и лучше воспользуйтесь широко известным методом.
Ссылки
Комментарии Брюса Шнайера о его законе.
Merkle, Hellman — On the security of multiple encryption
Phil Zimmermann on PGP
Автор: NeverWalkAloner
