Компьютерные сети. 6-е изд.

8.5. Алгоритмы с симметричным ключом

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

Первый класс алгоритмов шифрования, который мы изучим, — алгоритмы с симметричным ключом (symmetric-key algorithms). Их название говорит о том, что для шифрования и дешифрования сообщений применяется один и тот же ключ. На илл. 8.9 показан пример использования алгоритма с симметричным ключом. В частности, мы подробно рассмотрим блочные шифры (block ciphers), которые принимают на входе n-битные блоки открытого текста и преобразуют их с использованием ключа в n-битный шифр.

Криптографические алгоритмы можно реализовать как аппаратно (что повышает скорость их работы), так и программно (для повышения гибкости). Несмотря на то что в основном мы рассматриваем алгоритмы и протоколы вне зависимости от конкретной реализации, в данном случае интересно обсудить шифровальное оборудование. Подстановки и перестановки могут осуществляться при помощи простых электрических цепей. На илл. 8.13 (а) показан P-блок (P означает «permutation» — «перестановка»). Это устройство используется для перестановки восьми входных разрядов. Если пронумеровать входные биты сверху вниз (01234567), выход данного P-блока будет выглядеть как 36071245. При определенной распайке проводов P-блок может выполнить любую операцию перестановки практически со скоростью света, так как никакие вычисления в нем не производятся, он лишь обеспечивает распространение сигнала.

Илл. 8.13. Базовые элементы продукционных шифров: (а) P-блок; (б) S-блок; (в) продукционный шифр

Это соответствует принципу Керкгоффса: взломщик знает, что используется метод перестановки битов, но он не знает, в каком порядке эти биты располагаются.

Подстановки выполняются S-блоками (S означает «substitution» — «подстановка, замена»), как показано на илл. 8.13 (б). В данном примере на вход подается 3-битный открытый текст, а на выходе появляется 3-битный зашифрованный текст. Для каждого входного сигнала выбирается одна из восьми выходных линий декодера путем установки ее в 1. Все остальные линии устанавливаются в 0. Затем эти восемь линий проходят через P-блок, представляющий собой вторую ступень S-блока. Третья ступень производит обратное кодирование одной из восьми линий в 3-битное двоичное число. При таком устройстве проводки восьмеричные числа 01234567 заменяются на 24506713 соответственно. То есть 0 заменяется числом 2, 1 — числом 4 и т.д. Опять же, при соответствующей распайке проводов P-блока внутри S-блока можно реализовать любой вариант подстановки. Помимо этого, P-блок может быть встроен в оборудование и работать на огромных скоростях, поскольку шифраторы и дешифраторы вносят лишь одну или две вентильные задержки (менее 1 нс), а время распространения сигнала внутри P-блока вполне может быть менее 1 пс.

Эффективность этих базовых элементов становится очевидной, если расположить каскадом целый ряд блоков (илл. 8.13 (в)), создав продукционный шифр (product cipher). В нашем примере на первом этапе (P1) 12 входных линий меняются местами. На второй ступени вход разбивается на четыре группы из 3 бит, с каждой из которых операция замены выполняется независимо (S1–S4). Такое расположение позволяет составить большой S-блок из множества мелких. Это хороший способ, так как небольшие S-блоки удобны при аппаратной реализации (к примеру, восьмиразрядный S-блок можно представить в виде 256-разрядной таблицы перекодировки), однако большие S-блоки довольно трудно построить (например, 12-разрядный S-блок потребует минимум 212 = 4096 перекрещенных проводов в средней стадии). Хотя этот метод является лишь частным случаем, он достаточно эффективный. Выход продукционного шифра можно сделать сложной функцией входа, используя достаточно большое количество дополнительных ступеней.

Продукционные шифры, работающие с k-битными входами и производящие k-битные последовательности, широко распространены. В частности, часто применяются шифры с k, равным 256. Аппаратная реализация обычно имеет не семь, как на илл. 8.13 (в), а по крайней мере 20 физических этапов. Программная реализация совершает минимум восемь циклических итераций, каждая из которых производит S-блочные подстановки в подблоках блока данных длиной от 64 до 256 бит, после чего производится перестановка, которая перемешивает результаты S-блоков. Часто также производятся две дополнительные перестановки в начале и в конце. В литературе эти итерации называются раундами.

8.5.1. Стандарт шифрования данных DES

В январе 1977 года правительство США приняло продукционный шифр, разработанный IBM, в качестве официального стандарта для незасекреченной информации. Этот шифр, получивший название DES (Data Encryption Standard — стандарт шифрования данных), широко применялся в промышленности для защиты информации. Хотя в своем исходном виде он уже небезопасен, его модифицированная версия по-прежнему изредка используется. Эффективность исходной версии сомнительна: изначально длина ключа равнялась 128 бит, но после консультаций с АНБ компания IBM «добровольно» уменьшила ее до 56 бит, что, по мнению криптографов, было слишком мало даже для того времени. Алгоритм DES действует практически так же, как показано на илл. 8.13 (в), но использует блоки большего размера. Открытый текст (в двоичном виде) разбивается на 64-битные блоки, каждый из которых шифруется по отдельности путем выполнения перестановок и подстановок, параметризованных 56-битным ключом в каждом из 16 последовательных раундов. По сути, это очень большой моноалфавитный подстановочный шифр на базе алфавита с 64-битными символами (о которых мы поговорим чуть позже).

Уже в 1979 году стало ясно, что 56-битный ключ слишком короткий, и IBM разработала обратно совместимую схему увеличения длины ключа за счет одновременного использования двух 56-битных ключей, что в совокупности давало 112-битный ключ (Такман; Tuchman, 1979). Эта новая схема, названная тройным DES (Triple DES), используется до сих пор (илл. 8.14).

Илл. 8.14. (а) Тройное шифрование с помощью DES. (б) Дешифрование

Возникает два резонных вопроса. Первый: почему здесь используется два, а не три ключа? Второй: для чего выполняется шифрование, дешифрование и затем снова шифрование? Ответ следующий. В случае, когда компьютеру, использующему тройной DES, необходимо связаться с компьютером, на котором реализован одинарный DES, он может применить тройной DES, взяв в качестве обоих ключей одно и то же значение. Это даст тот же результат, что и применение одинарного DES. Такой подход упростил поэтапное внедрение тройного DES. Сегодня этот алгоритм можно считать устаревшим, но он по-прежнему используется в некоторых областях применения, которые трудно поддаются изменениям.

8.5.2. Улучшенный стандарт шифрования AES

Когда стало понятно, что DES (даже с тройным шифрованием) устаревает, Национальный институт стандартов и технологий (National Institute of Standards and Technology, NIST) — агентство Министерства торговли, занимающееся разработкой стандартов для Федерального правительства США, — решил создать новый криптографический стандарт для несекретных данных. Специалисты NIST ясно осознавали противоречия, связанные с DES. Они прекрасно понимали, что, услышав о новом стандарте, все, кто хоть что-то смыслит в криптографии, решат, что и здесь есть лазейка, с помощью которой АНБ получит доступ к данным. Вряд ли в таких условиях люди согласятся применять новую технологию, и она, скорее всего, канет в Лету.

Исходя из этого, NIST выбрал неожиданное для правительственной бюрократии решение и организовал криптографический конкурс. В январе 1997 года ученые со всего мира были приглашены для представления своих разработок нового стандарта, который назвали AES (Advanced Encryption Standard — продвинутый стандарт шифрования). Ниже перечислены требования к разработкам конкурсантов:

1. Алгоритм использует симметричный блочный шифр.

2. Все детали разработки общедоступны.

3. Поддерживаются длины ключей 128, 192 и 256 бит.

4. Возможна как программная, так и аппаратная реализация.

5. Алгоритм общедоступен или лицензирован на недискриминационных условиях.

Было рассмотрено 15 серьезных предложений. На открытых конференциях разработчики представляли свои проекты, а оппоненты должны были приложить максимум усилий, чтобы найти в них недостатки. В августе 1998 года NIST выбрал пять финалистов, руководствуясь критериями безопасности, эффективности, простоты, гибкости, а также требований к памяти (это важно для встроенных систем). Затем были проведены конференции, на которых высказывались дополнительные критические замечания.

В октябре 2000 года NIST объявил победителей конкурса — Йоана Дамена (Joan Daemen) и Винсента Рэймена (Vincent Rijmen), предложивших метод Rijndael. Название Rijndael (произносится примерно как «Райн-дол») представляет собой сокращение фамилий авторов разработки. В ноябре 2001 года Rijndael был объявлен стандартом правительства США и опубликован как FIPS 19742. Благодаря абсолютной открытости конкурса, техническим возможностям метода и тому факту, что победившая команда состояла из двух молодых бельгийских криптографов (которые вряд ли стали бы сотрудничать с NSA, предоставляя какие-то лазейки), Rijndael стал главным мировым криптографическим стандартом. AES в настоящее время является частью набора инструкций для некоторых процессоров.

Rhindael поддерживает длины ключей и размеры блоков от 128 до 256 бит с шагом в 32 бита. Длины ключей и блоков могут выбираться независимо друг от друга. При этом AES задает размер блока в 128 бит, а длину ключа — в 128, 192 или 256 бит. Вряд ли кто-то будет использовать 192-битные ключи, поэтому фактически есть два варианта AES: 128-битный блок с 128-битным ключом и 128-битный блок с 256-битным ключом.

Ниже мы рассмотрим только один вариант алгоритма — 128/128, поскольку это стандарт для коммерческих приложений. При использовании 128-битного ключа размер ключевого пространства составляет 2128 ≈ 3 × 1038 ключей. Даже если АНБ удастся собрать компьютер с миллионом параллельных процессоров, каждый из которых способен вычислять один ключ в пикосекунду, на перебор всех значений потребуется около 1010 лет. К тому времени Солнце уже давно потухнет, и нашим потомкам придется читать распечатку ключа при свечах.

Rijndael

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

Как и в DES, в Rijndael применяются подстановки и перестановки. И там и там используется несколько итераций, число которых зависит от размера ключа и блока и равно 10 для 128-разрядного ключа и 128-битных блоков (при максимальном размере ключа и блоков число итераций равно 14). Однако, в отличие от DES, все операции выполняются над целым количеством байтов, что позволяет создавать эффективные реализации как в аппаратном, так и в программном исполнении. Из-за того что DES ориентирован на использование битов, его программные реализации работают медленно.

Алгоритм Rijndael обеспечивает не только высокую степень безопасности, но и отличную скорость. Хорошая программная реализация на компьютере с частотой 2 ГГц может шифровать данные со скоростью 700 Мбит/с. Этого достаточно для шифрования более десяти видеофайлов в формате 4K в режиме реального времени. Аппаратные реализации работают еще быстрее.

8.5.3. Режимы шифрования

Несмотря на всю эту сложность, по сути, AES (а также DES и любой другой блочный код) является моноалфавитным подстановочным шифром с большими длинами символов (128-битные символы в AES, 64-битные — в DES). Для любого отрывка открытого текста шифр при прогоне через один и тот же шифрующий блок будет всегда одинаковым. Скажем, если вы 100 раз зашифруете открытый текст abcdefgh, используя алгоритмы DES или AES с одним и тем же ключом, то вы 100 раз получите на выходе одинаковый зашифрованный текст. Взломщик может попытаться использовать это свойство при попытке расшифровки текста.

Режим электронной кодовой книги

Чтобы понять, как использовать это свойство моноалфавитного подстановочного шифра для частичного взлома шифра, мы рассмотрим кодирование (тройное) по стандарту DES (поскольку изображать 64-разрядные блоки проще, чем 128-разрядные). Имейте в виду, что AES сталкивается с такими же проблемами. Самый очевидный способ кодирования длинного сообщения заключается в разбиении его на отдельные блоки по 8 байт (64 бита) и кодировании этих блоков одним и тем же ключом по очереди. Последний блок при необходимости можно дополнить до 64 бит. Этот метод назван режимом ECB (Electronic Code Book mode — режим электронной кодовой книги) по аналогии с традиционными кодовыми книгами, в которых содержались слова и соответствующие им шифры (обычно пятизначные десятичные числа).

На илл. 8.15 показано начало компьютерного файла; это список годовых премий сотрудников компании. Файл состоит из последовательных 32-разрядных записей (по одной на сотрудника) следующего формата: 16 байт на имя, 8 байт на должность и 8 байт на премию. Каждый из шестнадцати 8-байтных блоков (пронумерованных от 0 до 15) кодируется шифром DES.

Илл. 8.15. Открытый текст файла, зашифрованного в виде 16 DES-блоков

Лесли только что поругалась с начальством и не рассчитывает на большую премию. Ким, напротив, — любимица босса, и все это знают. Лесли может получить доступ к файлу после его зашифровки, но до его отправки в банк. Может ли Лесли исправить ситуацию, имея доступ только к зашифрованному файлу?

Это не проблема. Все, что нужно сделать, — это скопировать зашифрованный блок 12 (с премией Ким) и заменить им блок 4 (с премией Лесли). Даже не зная содержимого блока 12, Лесли может рассчитывать на гораздо более веселое Рождество. (Можно скопировать и зашифрованный блок 8, но скорее всего это обнаружат; да и Лесли, в общем-то, не жадная.)

Режим сцепления блоков шифра

Чтобы противостоять подобным атакам, все блочные шифры можно модернизировать так, чтобы замена одного блока вызывала повреждение других блоков открытого текста после их расшифровки, превращая их (начиная с модифицированного места) в мусор. Один из таких методов — сцепление блоков шифра (cipher block chaining) (илл. 8.16). Перед зашифровкой каждый блок открытого текста складывается по модулю 2 с предыдущим уже зашифрованным блоком. Следовательно, блокам открытого текста не соответствуют одни и те же блоки зашифрованного текста, и этот метод не является большим моноалфавитным подстановочным шифром. Первый блок складывается по модулю 2 со случайно выбранным вектором инициализации (Initialization Vector, IV), который передается в виде открытого текста вместе с зашифрованными блоками.

Илл. 8.16. Сцепление блоков шифра. (а) Шифрование. (б) Дешифрование

Рассмотрим сцепление блоков шифра на примере, представленном на илл. 8.16. Сначала мы вычисляем C0 = E(P0 XOR IV), затем C1 = E(P1 XOR C0) и т.д. При дешифровании мы также используем операцию XOR, чтобы обратить этот процесс: P0 = IV XOR D(C0) и т.д. Следует заметить, что блок i является функцией всех блоков открытого текста с 0 по i – 1, поэтому один и тот же исходный блок текста преобразуется в разные зашифрованные блоки в зависимости от их расположения. При таком способе шифрования преобразование, произведенное Лесли, приведет к появлению двух блоков бессмысленного содержания, начиная с поля премии Лесли. Для сообразительного сотрудника службы безопасности эта странность может послужить подсказкой в последующем расследовании.

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

Режим шифрованной обратной связи

Однако у метода сцепления блоков шифра есть один недостаток: прежде чем начнется дешифрование, должен появиться целый 64-битный блок данных. Для побайтового шифрования может применяться режим шифрованной обратной связи (cipher feedback mode) с использованием DES (тройного), как показано на илл. 8.17. Для AES принцип тот же, только применяется 128-разрядный сдвиговый регистр. На рисунке мы видим состояние шифровальной машины после того, как байты с 0-го по 9-й уже зашифрованы и отправлены. Когда приходит 10-й байт открытого текста (илл. 8.17 (а)), алгоритм DES обрабатывает 64-разрядный сдвиговый регистр, чтобы произвести 64-разрядный зашифрованный блок. Самый левый байт этого зашифрованного текста извлекается, складывается по модулю 2 с P10 и передается по линии. Затем сдвиговый регистр смещается влево на 8 разрядов. При этом байт C2 извлекается с левого конца регистра, а байт C10 вставляется на освободившееся место справа от C9.

Илл. 8.17. Режим шифрованной обратной связи. (а) Шифрование. (б) Дешифрование

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

При использовании этого метода дешифрование аналогично шифрованию. В частности, содержимое сдвигового регистра шифруется, а не дешифруется, поэтому байт, который складывается по модулю 2 с C10 для получения P10, равен тому байту, который складывается по модулю 2 с P10 для получения C10. Пока содержимое двух сдвиговых регистров идентично, дешифрование выполняется корректно (илл. 8.17 (б)).

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

Режим группового шифра

Однако встречаются сценарии применения, в которых один испорченный при передаче бит приводит к порче 64 бит открытого текста, а это слишком много. Для таких случаев существует четвертый вариант, называемый режимом группового (потокового) шифра (stream cipher mode). Его суть заключается в том, что выходной блок получают путем шифрования вектора инициализации с использованием ключа. Затем этот выходной блок снова шифруется с помощью ключа, чтобы вычислить второй выходной блок, который, в свою очередь, шифруется для получения третьего, и т.д. Последовательность выходных блоков, называемая ключевым потоком (keystream), может иметь произвольную длину. Она расценивается как одноразовый блокнот и складывается по модулю 2 с открытым текстом. В результате получается зашифрованный текст (илл. 8.18 (а)). Обратите внимание: вектор инициализации используется только на первом шаге. После этого шифруются выходные блоки. Кроме того, ключевой поток не зависит от данных, поэтому в случае необходимости он может быть вычислен заранее и совершенно нечувствителен к ошибкам передачи. Процесс дешифрования показан на илл. 8.18 (б).

Илл. 8.18. Групповой шифр. (а) Шифрование. (б) Дешифрование

Дешифрование происходит путем создания точно такого же ключевого потока на принимающей стороне. Поскольку он зависит только от вектора инициализации и ключа, ошибки передачи зашифрованного текста на него не влияют. Таким образом, ошибка в одном бите передаваемого шифра приводит к ошибке лишь в одном бите расшифрованного текста.

Важно никогда не использовать одну и ту же пару (ключ, вектор инициализации) в одном и том же групповом шифре, иначе каждый раз будет получаться одинаковый ключевой поток. Повторное использование ключевого потока может привести к взлому шифра при помощи многократного использования ключевого потока (keystream reuse attack). Допустим, блок открытого текста P0 шифруется с помощью ключевого потока, в результате вычисляется P0 XOR K0. Затем берется второй блок открытого текста Q0 и шифруется тем же ключевым потоком (получаем Q0 XOR K0). Криптоаналитик, перехвативший оба блока зашифрованного текста, может просто сложить их вместе по модулю 2 и получить P0 XOR Q0, тем самым убирая ключ. Теперь у него есть XOR двух блоков открытого текста. Если один из них известен (или его можно угадать), найти второй не проблема. В любом случае взломать XOR двух блоков открытого текста можно, используя статистические свойства сообщения.

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

42 Federal Information Processing Standard — Федеральный стандарт обработки информации.