Содержание статьи
В прошлый раз ты познакомился с великими и ужасными отечественными шифрами. Это был очень непростой урок, ведь эти криптосистемы стоят на страже государственной тайны. Скажешь, куда уж замудреннее? А вот сюда, пожалуйста! На самом деле не стоит пугаться, в этот раз не будем так глубоко погружаться в математику и рассматривать режимы шифрования — их принципы ты уже усвоил (ну или не усвоил). Пройдемся по самым топовым зарубежным шифрам и посмотрим, как же их применяют на практике.
Roadmap
Это четвертый урок из цикла «Погружение в крипту». Все уроки цикла в хронологическом порядке:
- Урок 1. Исторические шифры. Основы и исторические шифраторы. Как работают (и анализируются) шифры сдвига, замены, Рихарда Зорге, шифр Вернама и шифровальные машины
- Урок 2. Распределение ключей. Что это такое, как выполняется распределение ключей и как выбрать криптостойкий ключ
- Урок 3. Современные отечественные шифры. Что такое сеть Фейстеля и какими бывают отечественные блочные шифры, используемые в современных протоколах, — ГОСТ 28147—89, «Кузнечик»
- Урок 4. Современные зарубежные шифры. В чем разница между 3DES, AES, Blowfish, IDEA, Threefish от Брюса Шнайера и как они работают (ты здесь)
- Урок 5. Электронная подпись. Виды электронных подписей, как они работают и как их использовать
- Урок 6. Квантовая криптография. Что это такое, где используется и как помогает в распределении секретных ключей, генерации случайных чисел и электронной подписи
Чтобы не сесть в лужу с терминами, рекомендую освежить в памяти понятия поточных и блочных шифров, а также симметричного и асимметричного шифрования, блоков замены и сети Фейстеля.
3DES
Итак, первым в ряду зарубежных шифров рассмотрим 3DES, а точнее его ближайшего родственника DES (Data Encryption Standard), который хоть уже и не используется как таковой, но является предком 3DES.
DES разработан командой математиков научной лаборатории IBM, в которую входил уже знакомый нам Фейстель. Первая версия шифра получила имя «Люцифер», но затем он был модифицирован и в результате принят как официальный алгоритм шифрования данных (DEA). На протяжении более двадцати лет он оставался мировым стандартом, прежде чем его сменил Triple DES.
Рассмотрим, как работает алгоритм шифрования DES. Для этого необходимо вспомнить работу сети Фейстеля. DES — это сеть Фейстеля из 16 раундов с симметричными ключами шифрования. Длина блока текста — 64 бита, длина раундового ключа — 48 бит. Итак, пройдем основные этапы шифрования DES, опуская суровую математическую сторону:
- Текст, как и при любом другом шифровании, разбивается на блоки по 64 бита.
- Из 56-битного ключа генерируется 16 48-битных раундовых ключиков.
- Каждый блок подвергается перестановке, то есть все биты входного блока перемешиваются согласно определенной таблице.
- Блок расщепляется на половинки и поступает в знакомую нам сеть Фейстеля, где прокручивается 16 раундов.
- Соединяем половинки.
- И еще одна перестановка.
Начальная и конечная перестановки не имеют никакого значения для криптографии в DES. Обе перестановки — без ключей, и таблицы для них заданы заранее. Причина, по которой они включены в DES, неясна, и проектировщики DES об этом ничего не сказали. Можно предположить, что алгоритм планировалось реализовать в аппаратных средствах (на чипах) и что эти две сложные перестановки должны были затруднить программное моделирование механизма шифрования.
Вот, собственно, все, что надо знать о работе алгоритма DES. Если углубляться в то, как работает функция, заданная в сети Фейстеля, то в ней все прекрасно. Она осуществляет и перестановку, и замену (S-боксы, как ты можешь помнить из предыдущей статьи), и сложение с раундовым ключом.
Но вернемся к тройному DES, или Triple DES. В нем возникла необходимость, так как 56-битный ключ DES был уязвим к брутфорсу и с ростом вычислительных мощностей эта проблема вставала все острее. Используя доступную сегодня технологию, можно проверить один миллион ключей в секунду. Это означает, что потребуется более чем две тысячи лет, чтобы перебором дешифровать DES, используя компьютер только с одним процессором.
Но если взять компьютер с одним миллионом процессорных ядер, которые будут параллельно обрабатывать ключи, мы сможем проверить все множество ключей приблизительно за 20 часов. Когда был введен DES, стоимость такого компьютера равнялась нескольким миллионам долларов, но она быстро снизилась. Специальный компьютер был создан в 1998 году — и нашел ключ за 112 часов.
Чтобы решить проблему быстрого поиска ключа, умные зарубежные криптографы предложили использовать два ключа и применять DES дважды. Однако двойной DES оказался уязвим к атаке «встреча посередине». Чтобы реализовать эту атаку, злоумышленнику необходимо иметь открытый и соответствующий ему зашифрованный текст. Злоумышленник шифрует открытый текст на всех возможных ключах, записывая результаты в таблицу 1. Затем расшифровывает зашифрованный текст со всеми возможными ключами и записывает результат в таблицу 2. Далее злоумышленник ищет в таблицах 1 и 2 совпадения.
Атака данного типа заключается в переборе ключей на стороне шифрованного и открытого текста и требует примерно в четыре раза больше вычислений, чем перебор обычного ключа DES, и довольно много памяти для хранения промежуточных результатов. Тем не менее на практике атака осуществима, что делает алгоритм Double DES непригодным.
Совсем иначе дела обстоят с Triple DES. Использование трех ключей и применение алгоритмов в указанной на схеме последовательности продлило DES жизнь еще на несколько лет.
Замечательный DES
Так что же в DES такого замечательного? Этот алгоритм шифрования был подвергнут тщательному анализу. DES обладал двумя очень важными качествами блочных шифров — лавинностью и полнотой. Настало время расширить свой криптографический словарик!
Лавинный эффект означает, что небольшие изменения в исходном тексте (или ключе) могут вызвать значительные изменения в зашифрованном тексте.
Было доказано, что DES имеет все признаки этого свойства.
Исходный текст | 0000000000000000 | 0000000000000001 |
---|---|---|
Ключ | 22234512987ABB23 | 22234512987ABB23 |
Зашифрованный текст | 4789FD476E82A5F1 | OA4ED5C15A63FEA3 |
Хотя два блока исходного текста не совпадают только самым правым битом, блоки зашифрованного текста отличаются на 29 бит. Это означает, что изменение приблизительно в 1,5% исходного текста вызывает изменение приблизительно 45% зашифрованного текста.
Эффект полноты заключается в том, что каждый бит зашифрованного текста должен зависеть от многих битов исходного текста. Как мы уже выяснили, в DES применяются и перестановки, и замены — все преобразования устанавливают зависимость каждого бита шифротекста от нескольких битов исходного текста.
Где же применяется DES? Да почти везде, его реализации присутствуют в большинстве программных библиотек. Однако кто знает, насколько использование DES безопасно в наше время? Хотя IBM утверждала, что работа алгоритма была результатом 17 человеко-лет интенсивного криптоанализа, некоторые люди опасались, не вставило ли NSA в алгоритм лазейку, которая позволяет агентству легко дешифровывать перехваченные сообщения. Комитет по разведке сената США тщательно изучал этот вопрос и, разумеется, ничего не обнаружил, обвинения с NSA были сняты, результаты исследования тем не менее засекречены. Одним словом, в Америке еще долго крутились слухи и домыслы насчет того, стоит доверять DES или нет. Но, как я считаю, здесь ситуация описывается поговоркой «Умный не скажет, дурак не поймет». В конце концов NSA признало, что не могло доверить IBM столь важную миссию и внесло несколько корректировок вроде задания S-боксов.
Все время существования DES он был мишенью для различных методов криптоанализа. Криптоаналитики не переставали мериться машинами для вскрытия DES — за какое время кто сможет дешифровать текст. В связи с этим появилось несчетное количество различных модификаций этого алгоритма, и 3DES далеко не самая изощренная из них.
AES
Победитель конкурса AES, объявленный в конце 1997 года, алгоритм Rijndael был разработан двумя бельгийскими криптографами — Йоаном Даменом (Joan Daemen) и Винсентом Рейменом (Vincent Rijmen).
Для обеспечения криптостойкости алгоритм Rijndael включает в себя повторяющиеся раунды, каждый из которых состоит из замен, перестановок и прибавления ключа. Однако, в отличие от DES, шифрование и расшифрование в этом алгоритме — процедуры разные.
AES оперирует 128-битными блоками данных и ключами по 128, 192 и 256 бит. Концептуально он отличается от DES, так как не базируется на сети Фейстеля, а представляет собой подстановочно-перестановочную сеть (SP-сеть), которую мы сейчас рассмотрим подробнее.
В AES байты открытого текста не делятся на две части, как в сети Фейстеля, а записываются в форму — матрицу (двумерный массив) байтов, расположенных таким образом:
0 | 4 | 8 | 12 | 16 |
1 | 5 | 9 | 13 | ... |
2 | 6 | 10 | 14 | |
3 | 7 | 11 | 15 |
AES действует следующими операциями:
- ExpandKey — вычисление раундовых ключей для всех раундов.
- SubBytes — замена битов по таблице замены (S-боксу).
- ShiftRows — циклический сдвиг строк в форме на различные величины.
- MixColumns — смешивание данных внутри каждого столбца формы.
- AddRoundKey — сложение ключа раунда с формой.
Сегодня AES является официальным стандартом правительства США для симметричного шифрования и применяется повсеместно. Фактически это один из самых универсальных зарубежных шифров на данный момент. Что касается безопасности AES, то и у него, как и большинства шифров, есть некоторые уязвимости, и криптоаналитики продолжают их искать. Однако, несмотря на это, AES живее всех живых.
IDEA
IDEA (International Data Encryption Algorithm) — алгоритм блочного симметричного шифрования, который был предложен на замену стандарта DES. Начальная версия алгоритма IDEA появилась в 1990 году. Алгоритм запатентован в США и в большинстве европейских стран. Владеет патентом Ascom Tech, но в некоммерческих целях алгоритм можно использовать бесплатно.
Размер блока в этом шифре — 64 бита, длина ключа — 128. Стоит сразу сказать, что алгоритм IDEA — самый молодой из перечисленных и его математика очень сложна. Минутка криптографического словарика.
Конфузия — шифрование должно зависеть от ключа сложным и запутанным способом.
Диффузия — каждый бит незашифрованного текста должен влиять на каждый бит зашифрованного текста. Распространение одного незашифрованного бита на большое количество зашифрованных битов скрывает статистическую структуру незашифрованного текста.
В IDEA эти свойства достигаются за счет применения независимых математических операций. В отличие от DES, главной операцией которого является XOR (сложение по модулю 2), IDEA предусматривает наличие:
- XOR;
- сложения по модулю 216;
- умножения по модулю (216 + 1).
Комбинирование этих трех операций обеспечивает комплексное преобразование входных данных, затрудняя криптоанализ IDEA по сравнению с DES.
В шифре IDEA выполняется восемь раундов, и в каждом раунде блок открытого текста подвергается преобразованию посредством математических операций. Любители «зреть в корень» могут позреть на схему одного раунда шифра IDEA, приведенную ниже. Блок текста, длиной 64 бита, делится на подблоки по 16 бит. Каждый такой полученный блочок поступает на вход раунда и подвергается сложному преобразованию.
Неповторимая IDEA
«Мне кажется, это самый лучший и надежный блочный алгоритм, опубликованный до настоящего времени», — говорит Брюс Шнайер об алгоритме IDEA.
Действительно, IDEA отличается высокой стойкостью благодаря своим многочисленным математическим операциям. Кроме того, к достоинствам данного алгоритма относится высокая скорость зашифрования — почти в два раза выше, чем у алгоритма DES (в зависимости от платформы, на которой выполняется шифрование). Однако скорость расшифровки снижается из-за тяжелых операций вычисления, обратных умножению по модулю (216 + 1).
Разумеется, и на этот сложный шифр мудрые криптографы пытались провести всевозможные атаки. Успеха достиг Пол Хокер, который реализовал атаку, предполагая, что криптоаналитик не имеет прямого доступа к искомому ключу (например, ключ прошит в каком-либо аппаратном шифраторе или смарт-карте), но может изменять определенным образом различные фрагменты ключа.
Алгоритм IDEA не стал международным стандартом шифрования, как того желали его авторы. Однако его можно считать одним из наиболее распространенных в мире алгоритмов шифрования. IDEA используется во множестве приложений, в том числе в широко известном и распространенном протоколе защиты данных PGP.
Рыбы Брюса Шнайера
Брюс Шнайер — видная фигура криптографии наших дней. Он объездил полмира с лекциями и семинарами, его книги настойчиво рекомендуют тем, кто стремится знать криптографию. И конечно же, такой известный человек не хотел бы слыть сапожником без сапог — он сам входит в группу крипторазработчиков.
Мы вкратце познакомимся с одними из самых известных его детищ — алгоритмами шифрования Blowfish, Twofish и Threefish.
Blowfish
Первым на свет появился Blowfish. Как говорит сам Шнайер, этот алгоритм был разработан для реализации на больших микропроцессорах. Поэтому он компактен (всего 5 Кбайт памяти) и прост (использует простые математические операции — сложение, XOR и выборку из таблицы). Также алгоритм позволяет настраивать длину ключа (до 448 бит).
На 32-битных процессорах Blowfish выполняет шифрование значительно быстрее, нежели DES, однако на интеллектуальных платах в силу своей упрощенности он не особо применим. В основе Blowfish сеть Фейстеля из 16 раундов, которую ты уже должен хорошо понимать.
Алгоритм реализован в некоторых программных продуктах (FolderBolt, Nautilus, PGPfone), однако сейчас он уже теряет свою актуальность.
Twofish
За первой рыбой появились еще две — новый алгоритм Twofish был разработан Шнайером и компанией для участия в конкурсе AES. Работа Шнайера вышла в пятерку финалистов, однако победителем так и не стала, хотя обладала для этого всеми возможными плюсами. Это:
- 128-битный блочный симметричный шифр;
- длина ключей 128, 192 и 256 бит;
- эффективная программная (в первую очередь на 32-битных процессорах) и аппаратная реализация;
- гибкость (возможность использования ключа большей длины, применимость для поточного шифрования, хеш-функций и так далее);
- простота алгоритма — его удобно анализировать.
Однако по сравнению с Rijndael, занявшим пьедестал AES, Twofish был более сложным для анализа и обладал более низкой скоростью шифрования. Разработан этот алгоритм на основе Blowfish с некоторыми дополнениями и также представляет собой сеть Фейстеля.
На конкурсе шифр подвергли различным типам криптоанализа. По сравнению с остальными финалистами конкурса AES он оказался самым стойким. Однако его необычное строение и относительная сложность породили некоторые сомнения в качестве этой прочности. На данный момент Twofish используется еще реже, чем его предшественник.
Threefish
«В третий раз закинул старик в море невод...» и десять лет спустя получился шифр Threefish. На этот раз Шнайер решил переплюнуть AES и учел все недостатки предыдущего опыта. Криптограф не стал брать за основу сеть Фейстеля, а реализовал шифр на основе подстановочно-перестановочной сети (SP-сети), как в AES. Такая сеть основана на комбинации операций исключающего ИЛИ, сложения и циклического сдвига. В упрощенном виде все это выглядит так:
За счет простых операций Threefish значительно опережает в скорости AES. Кроме того, по заявлениям авторов, алгоритм имеет более высокий уровень безопасности, чем AES. Существует атака на 25 из 72 раундов Threefish, в то время как для AES — на 6 из 10. Так что Шнайер добился-таки своей победы, хоть и с опозданием.
Шифр послужил основой для создания хеш-функции Skein, которая участвовала в конкурсе на должность SHA-3. Сам Threefish широко используется и реализован в библиотеках для многих языков программирования.
Выводы
В заключение стоит сказать, что все западные криптографы, конечно, молодцы, разработали вагон и маленькую тележку различных алгоритмов шифрования. Какой-то более стойкий, какой-то более быстрый. Но пока все будут сравнивать их с DES и AES, потому что это классика.
В следующей статье познакомимся с электронными подписями, очень классным и важным средством криптографии.