Олег Бойцев - Защити свой компьютер на 100% от вирусов и хакеров

В марте 1999 года прошла вторая конференция AES, а в августе 1999 года были объявлены пять финалистов, среди которых оказались: MARS, RC6, Rijndael, Serpent и Twofish. Все они были разработаны авторитетными криптографами, имеющими мировое признание. На 3-й конференции AES в апреле 2000 года все авторы представили свои алгоритмы.

В Нью-Йорке 13 и 14 апреля 2000 года, незадолго до завершения второго этапа, прошла третья конференция AES. Двухдневная конференция была разделена на восемь сессий по четыре в день. На сессиях первого дня обсуждались вопросы, связанные с программируемыми матрицами (FGPA), проводилась оценка реализации алгоритмов на различных платформах, в том числе PA-RISC, IA-64, Alpha, высокоуровневых смарт-картах и сигнальных процессорах, сравнивалась производительность претендентов на стандарт, анализировалось количество раундов в алгоритмах-кандидатах. На второй день был проанализирован Rijndael с сокращенным количеством раундов и показана его слабость в этом случае, обсуждался вопрос об интегрировании в окончательный стандарт всех пяти алгоритмов-претендентов, еще раз тестировались все алгоритмы. В конце второго дня была проведена презентация, на которой претенденты рассказывали о своих алгоритмах, их достоинствах и недостатках. О Rijndael как о лидере рассказал Винсент Риджмен (Vincent Rijmen), заявивший о надежности защиты, высокой общей производительности и простоте архитектуры своего кандидата.

2 октября 2000 года было объявлено, что победителем конкурса стал алгоритм Rijndael, и началась процедура стандартизации. 28 февраля 2001 года был опубликован проект, а 26 ноября 2001 года AES был принят как FIPS 197.

Строго говоря, AES и Rijndael не одно и то же, так как Rijndael поддерживает широкий диапазон длин ключей и блоков.

Особо следует подчеркнуть тот факт, что алгоритм Rijndael не похож на большинство известных алгоритмов симметричного шифрования, в основе которых лежит сеть Фейштеля. Напомним нашим читателям, что особенность сети Фейштеля состоит в том, что входное значение разбивается на два и более субблоков, часть из которых в каждом раунде обрабатывается по определенному закону, после чего накладывается на необрабатываемые субблоки.

В отличие от ГОСТ 28147, который будет рассмотрен ниже, алгоритм Rijndael представляет блок данных в виде двухмерного байтового массива размером 4 х 4, 4 х 6 или 4 х 8 (допускается использование нескольких фиксированных размеров шифруемого блока информации). Все операции выполняются с отдельными байтами массива, а также с независимыми столбцами и строками.

Алгоритм Rijndael предусматривает выполнение четырех последовательных преобразований.

1. BS (ByteSub) – табличная замена каждого байта массива (рис. 2.2).

Рис. 2.2. Табличная замена каждого байта массива

2. SR (ShiftRow) – сдвиг строк массива. При этой операции первая строка остается без изменений, а остальные циклически побайтно сдвигаются влево на фиксированное количество байт, зависящее от размера массива. Например, для массива размером 4 х 4 строки 2, 3 и 4 сдвигаются на 1, 2 и 3 байта соответственно (рис. 2.3).

3. Следующим идет MC (MixColumn) – операция над независимыми столбцами массива, когда каждый столбец по определенному правилу умножается на фиксированную матрицу C(X) (рис. 2.4).

4. Заключительный этап – AK (AddRoundKey) – добавление ключа. Каждый бит массива складывается по модулю 2 с соответствующим битом ключа раунда, который, в свою очередь, определенным образом вычисляется из ключа шифрования (рис. 2.5).

Рис. 2.3. Сдвиг строк массива

Рис. 2.4. Операция MixColumn

Рис. 2.5. Операция добавления ключа

Вышеперечисленные преобразования шифруемых данных поочередно выполняются в каждом раунде (рис. 2.6).

Рис. 2.6. Последовательность раундов Rijndael

В алгоритме Rijndael количество раундов шифрования ® переменное (10, 12 или 14 раундов) и зависит от размеров блока и ключа шифрования (для ключа также предусмотрено несколько фиксированных размеров).

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

При всех преимуществах и оригинальности алгоритма AES можно было бы считать абсолютом надежности и стойкости, но, как оно всегда и бывает, совершенных продуктов нет.

26 мая 2006 года на конференции Quo Vadis IV Николя Тадеуш Куртуа (польский криптограф, проживающий во Франции) представил практическое доказательство существования алгебраических атак, оптимизированных против шифра AES-Rijndael. За полтора часа на своем ноутбуке он осуществил демо-взлом всего лишь по нескольким шифртекстам близкого аналога Rijndael. Хотя это был только модельный шифр, он являлся таким же стойким, в него не было добавлено существенных слабостей, он имел такие же хорошие диффузионные характеристики и устойчивость ко всем известным до этого видам криптоанализа. Единственным отличием были лишь измененные в рамках модели алгебраических атак параметры S-блоков и уменьшенное для наглядности количество раундов. Однако этого было достаточно, чтобы убедить скептиков в реальности алгебраических атак и несовершенстве даже такого, казалось бы, совершенного метода шифрования.

ГОСТ 28147. Следующим алгоритмом симметричного шифрования, который мы рассмотрим, станет ГОСТ 28147-89. Это советский и российский стандарт симметричного шифрования, введенный 1 июля 1990 года. Стандарт обязателен для организаций, предприятий и учреждений, применяющих криптографическую защиту данных, хранимых и передаваемых в сетях ЭВМ, в отдельных вычислительных комплексах или ЭВМ.

Алгоритм был разработан в бывшем Главном Управлении КГБ СССР или в одном из секретных НИИ в его системе. Первоначально имел гриф (ОВ или СС – точно неизвестно), затем гриф последовательно снижался и к моменту официального проведения алгоритма через Госстандарт СССР в 1989 году был снят. Алгоритм остался ДСП (как известно, ДСП не считается грифом). В 1989 году стал официальным стандартом СССР, а позже, после распада СССР, федеральным стандартом Российской Федерации.

С момента опубликования ГОСТа на нем стоял ограничительный гриф "Для служебного пользования", и формально шифр был объявлен "полностью открытым" только в мае 1994 года. По известным причинам, история создания шифра и критерии его проектирования до сих пор неизвестны.

ГОСТ 28147-89 представляет собой блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Основа алгоритма – уже известная нам сеть Фейштеля. Основным режимом шифрования по ГОСТ 28147-89 является режим простой замены (определены также более сложные режимы гаммирования и гаммирования с обратной связью). Рассмотрим механизм работы алгоритма подробнее.

При работе ГОСТ 28147-89 информация шифруется блоками по 64 бита (такие алгоритмы называются блочными), которые затем разбиваются на два субблока по 32 бита (N1 и N2). После завершения обработки субблока N1 его значение складывается со значением субблока N2 (сложение выполняется по модулю 2, то есть применяется логическая операция XOR – исключающее ИЛИ), а затем субблоки меняются местами. Данное преобразование выполняется определенное количество раз (раундов): 16 или 32 в зависимости от режима работы алгоритма. В каждом раунде выполняются две операции (рис. 2.7).

Рис. 2.7. Преобразование выполняется определенное количество раз

Первая операция подразумевает наложение ключа. Содержимое субблока N1 складывается по модулю 2 с 32-битной частью ключа Kx. Полный ключ шифрования представляется в виде конкатенации 32-битных подключей: K0, K1, K2, K3, K4, K5, K6, K7. В процессе шифрования используется один из этих подключей, в зависимости от номера раунда и режима работы алгоритма.

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

Алгоритм, определяемый ГОСТ 28147-89, может работать в четырех режимах:

♦ простой замены;

♦ гаммирования;

♦ гаммирования с обратной связью;

♦ генерации имитоприставок.

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

В режиме простой замены для зашифровки каждого 64-битного блока информации выполняются 32 описанных выше раунда. Каждый из блоков шифруется независимо от другого, то есть результат шифрования каждого блока зависит только от его содержимого (соответствующего блока исходного текста). При наличии нескольких одинаковых блоков исходного (открытого) текста соответствующие им блоки шифртекста тоже будут одинаковы, что дает дополнительную полезную информацию для пытающегося вскрыть шифр криптоаналитика. Поэтому данный режим применяется в основном для шифрования самих ключей шифрования (очень часто реализуются многоключевые схемы, в которых по ряду соображений ключи шифруются друг на друге). Для шифрования собственно информации предназначены два других режима работы: гаммирования и гаммирования с обратной связью.