Закон Шнайера
В 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 encryptionPhil Zimmermann on PGP
