Закон Шнайера

    image

    В 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
    Share post

    Comments 12

      0
      В нормальных системах должны быть механизмы смены ключа после некоторого количества операций шифрования. А тут есть возможность послать 2^54 запросов оракулу, это уже ставит под большое сомнение стойкость всей системы.
        +2
        Да, конечно это выглядит весьма нереалистично, однако лучше лишний раз перестраховаться и в случае крайней нужды использовать схему с тремя ключами.
          +2
          Может быть уже просто пора перестать пользоваться различными вариациями DES? Разве есть принципиальная необходимость пользоваться им, когда есть, например, AES?
            0
            И в очередной раз вынужден с вами согласиться:)
            Разумеется, AES выглядит куда более предпочтительным решением. Но ситуации бывают всякие и поэтому я и написал в своем комментарии: «в случае крайней нужды».
        +3
        3des до сих пор валидный сьют, даже в TLS 1.2. Впрочем, как и RC4. C другой стороны, даже использование серьезных либ вроде openSSL не защищает от всяких хартблидов и прочей нечисти, сводящей крипту на нет. А что выбрать — черный ящик, потенциально взламываемый школьником, или общеизвестное решение (тоже, потенциально взламываемое школьником) вопрос больше философский.
          +2
          Да не, я все-таки считаю что стойкость любого черного ящика из той же плоскости что и неуловимость ковбоя Джо. Если это кому-нибудь действительно станет нужно, то проприетарное решение имеет больше шансов оказаться уязвимым, по той простой причине, что не было должным образом исследовано. При этом, учитывая закрытость решения, факт взлома может оставаться в секрете достаточно длительное время и это может привести к большому ущербу.
          +24
          Министерство обороны предупреждает:
          Пользуйтесь только лицензированными алгоритмами шифрования. Только они сохранят ваши данные в тайне.
            +1
            Ага, поддержи отечественного производителя.
            +12
            В эпичных фразах о криптографии и безопасности Брюс Шнайер преуспел не меньше чем в криптографии
              0
              Кстати, кто-нибудь может подкинуть ссылку на то, как взломать шифр на суммировании с ГПСЧ?
              А то у меня идей нет, кроме полного перебора всех известных гспч-алгоритмов и последующего подбора начального состояния.
                0
                Криптоанализ обычно подразумевает, что сам алгоритм известен, неизвестен только ключ, а у вас тут security thru obscurity.
                  +2
                  Я уже както кратко писал о возможных атаках на Вихрь Мерсенна и регистр с линейной обратной связью тут.
                  Использование каскадов РСЛОС, как например в сетях GSM, тоже весьма небезопасное решение.
                  RC4 тоже имеет свои недостатки, позволяющие при наличие большого объема известных пар открытый-закрытый текстов восстановить секретную информацию, скажем куки.
                  Механизмы атаки зависят от используемого ГПСЧ, но в общем случае почти всегда сводятся к атаке с известным открытым текстом или используют неправильную реализацию(к примеру, шифрование одним и тем же ключевым потоком двух и более сообщений).

                Only users with full accounts can post comments. Log in, please.