Шифрование. Часть 2
AES
Напомню нашим читателям, что в предыдущей части статьи мы начали рассматривать алгоритмы симметричного шифрования (см. КГ № 24). Одним из первых стандартов, который мы рассмотрели, был DES. Вскоре после его выхода обнаружилась очевидная слабость алгоритма: необходимость в принятии нового стандарта была более чем очевидна – небольшая длина ключа DES (56 бит) позволяла применить метод грубой силы против этого алгоритма. Кроме того, архитектура DES была ориентирована на аппаратную реализацию, и программная реализация алгоритма на платформах с ограниченными ресурсами не давала достаточного быстродействия. Модификация TDES обладала достаточной длиной ключа, но при этом была еще медленнее. TDES не просуществовал столь долго, чтобы можно было говорить о том, что алгоритм стоек и надёжен. Ему на смену, как это и следовало ожидать, пришёл более стойкий и надёжный алгоритм – AES, который, между прочим, был выбран в результате конкурса и принят в качестве американского стандарта шифрования правительством США. Немного о самом конкурсе.
2 января 1997 года NIST (Национальный Институт Стандартов и Технологий) объявляет о намерении найти замену DES, являвшегося американским стандартом с 1977 года. NIST принял достаточное количество предложений от заинтересованных сторон о том, каким образом следует выбирать алгоритм. Активный отклик со стороны открытого криптографического сообщества привел к объявлению конкурса 12 сентября 1997г. Алгоритм могла предложить практически любая организация или группа исследователей. Минимальные требования к новому стандарту были следующими:
. это должен быть блочный шифр;
. длина блока – равная 128 битам;
. ключи длиной 128, 192 и 256 бит;
. использовать операции, легко реализуемые как аппаратно (в микрочипах), так и программно (на персональных компьютерах и серверах); . ориентироваться на 32-разрядные процессоры;
. не усложнять без необходимости структуру шифра для того, чтобы все заинтересованные стороны были в состоянии самостоятельно провести независимый криптоанализ алгоритма и убедиться, что в нём не заложено каких-либо недокументированных возможностей.
Кроме всего вышеперечисленного, алгоритм, который претендует на то, чтобы стать стандартом, должен распространяться по всему миру без платы за пользование патентом.
20 августа 1998 года на 1-ой конференции AES был объявлен список из 15 кандидатов: CAST-256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER+, Serpent и Twofish. Понятное дело, что в последующих обсуждениях эти алгоритмы подвергались самому тщательному анализу, причем исследовались не только криптографические свойства, такие как стойкость к известным атакам и отсутствие слабых ключей, но и практические аспекты реализации. Так, особое внимание при выборе алгоритма было направлено на оптимизацию скорости выполнения кода на различных архитектурах (от ПК до смарт-карт и аппаратных реализаций), возможность оптимизации размера кода, возможность распараллеливания. В марте 1999 года прошла 2-ая конференция AES, а в августе 1999 года были объявлены 5 финалистов, среди которых оказались: MARS, RC6, Rijndael, Serpent, and Twofish. Все эти алгоритмы были разработаны авторитетными криптографами, имеющими мировое признание. На 3-ей конференции AES в апреле 2000 года все авторы представили свои алгоритмы.
В Нью-Йорке 13 и 14 апреля 2000 года, незадолго до завершения второго этапа, прошла третья конференция AES. Двухдневная конференция была разделена на восемь сессий, по четыре в день. На сессиях первого дня обсуждались вопросы, связанные с программируемыми матрицами (FGPA), проводилась оценка реализации алгоритмов на различных платформах, в том числе PA-RISC, IA-64, Alpha, высокоуровневых смарт-картах и сигнальных процессорах, сравнивалась производительность претендентов на стандарт, анализировалось число раундов в алгоритмах-кандидатах. На второй день был проанализирован Rijndael с сокращённым числом раундов и показана его слабость в этом случае, обсуждался вопрос об интегрировании в окончательный стандарт всех пяти алгоритмов-претендентов, ещё раз тестировались все алгоритмы. В конце второго дня была проведена презентация, на которой претенденты рассказывали о своих алгоритмах, их достоинствах и недостатках. О Rijndael как о лидере рассказал Винсент Риджмен, заявивший о надёжности защиты, высокой общей производительности и простоте архитектуры своего кандидата.
2 октября 2000 года было объявлено, что победителем конкурса стал алгоритм Rijndael, и началась процедура стандартизации. 28 февраля 2001 года был опубликован проект, а 26 ноября 2001 года AES был принят как FIPS 197.
Строго говоря, AES не одно и тоже, что и Rijndael, т.к. Rijndael поддерживает широкий диапазон длин ключей и блоков.
Особо следует подчеркнуть тот факт, что алгоритм Rijndael не похож на большинство известных алгоритмов симметричного шифрования, в основе которых стоит "сеть Фейштеля". Напомню нашим читателям, что особенность "сети Фейштеля" состоит в том, что входное значение разбивается на два и более субблоков, часть из которых в каждом раунде обрабатывается по определенному закону, после чего накладывается на необрабатываемые субблоки (схему сети см. в первой части статьи).
В отличие от ГОСТ 28147, который будет рассмотрен ниже, алгоритм Rijndael представляет блок данных в виде двухмерного байтового массива размером 4X4, 4X6 или 4X8 (допускается использование нескольких фиксированных размеров шифруемого блока информации). Все операции выполняются с отдельными байтами массива, а также с независимыми столбцами и строками.
Алгоритм Rijndael предусматривает выполнение четырёх последовательных преобразований:
. BS (ByteSub) – табличная замена каждого байта массива (рис. 1).
. SR (ShiftRow) – сдвиг строк массива (рис. 2). При этой операции первая строка остается без изменений, а остальные циклически побайтно сдвигаются влево на фиксированное число байт, зависящее от размера массива. Например, для массива размером 4X4 строки 2, 3 и 4 сдвигаются соответственно на 1, 2 и 3 байта.
. После этого идёт MC (MixColumn) – операция над независимыми столбцами массива (рис. 3), когда каждый столбец по определенному правилу умножается на фиксированную матрицу c(x).
. Заключительный этап – AK (AddRoundKey) – добавление ключа. Каждый бит массива складывается по модулю 2 с соответствующим битом ключа раунда, который, в свою очередь, определенным образом вычисляется из ключа шифрования:
Вышеперечисленные преобразования над шифруемыми данными поочередно выполняются в каждом раунде (рис. 5).
Рис.5 Последовательность раундов Rijndael.
Исключения касаются лишь первого и последнего раундов: перед первым раундом дополнительно выполняется операция AK, а в последнем раунде отсутствует MC. В результате последовательность операций при зашифровке выглядит так:
AK, {BS, SR, MC, AK} (повторяется R-1 раз), BS, SR, AK.
В алгоритме Rijndael количество раундов шифрования (R) переменное (10, 12 или 14 раундов) и зависит от размеров блока и ключа шифрования (для ключа также предусмотрено несколько фиксированных размеров).
Почему же Rijndael стал новым стандартом шифрования, опередившим другие алгоритмы? Прежде всего, он обеспечивает высокую скорость шифрования, причём на всех платформах: как при программной, так и при аппаратной реализации. Алгоритм отличается удачным механизмом распараллеливания вычислений по сравнению с другими алгоритмами, представленными на конкурс. Кроме того, требования к ресурсам для его работы минимальны, что важно при его использовании в устройствах, обладающих ограниченными вычислительными возможностями.
Взлом AES возможен?!..
При всех преимуществах и оригинальности алгоритма AES можно было бы считать абсолютом надёжности и стойкости, но… как оно всегда и бывает, совершенных продуктов нет…
26 мая 2006 года (незадолго до EUROCRYPT 2006) на конференции Quo Vadis IV Николя Тадеуш Куртуа (польский криптограф, живущий во Франции) представит практическое доказательство существования алгебраических атак, оптимизированных против шифра AES-RIJNDAEL. За полтора часа на своём ноутбуке он осуществит демовзлом всего лишь по нескольким шифртекстам близкого аналога RIJNDAEL. Хотя это будет модельный шифр, он будет таким же стойким, в нём не будет добавлено существенных слабостей, он будет иметь такие же хорошие диффузионные характеристики и устойчивость ко всем известным до этого видам криптоанализа. Единственным отличием будут изменённые в рамках модели алгебраических атак параметры S-блоков и уменьшенное для наглядности число раундов. Однако этого достаточно, чтобы убедить скептиков в реальности алгебраических атак…
ГОСТ 28147
Следующим алгоритмом симметричного шифрования, который мы рассмотрим, станет ГОСТ 28147-89. ГОСТ 28147-89 – советский и российский стандарт симметричного шифрования, введённый 1-го июля 1990 года. Стандарт обязателен для организаций, предприятий и учреждений, применяющих криптографическую защиту данных, хранимых и передаваемых в сетях ЭВМ, в отдельных вычислительных комплексах или в ЭВМ.
Алгоритм был разработан в бывшем 8-м Главном Управлении КГБ СССР или в одном из секретных НИИ в его системе. Первоначально имел гриф (ОВ или СС - точно не известно), затем гриф последовательно снижался и к моменту официального проведения алгоритма через Госстандарт СССР в 1989 году был снят, алгоритм остался ДСП (как известно, ДСП не считается грифом). В 1989 году стал официальным стандартом СССР, а позже, после распада СССР, федеральным стандартом Российской Федерации.
С момента опубликования ГОСТа на нём стоял ограничительный гриф "Для служебного пользования", и формально шифр был объявлен "полностью открытым" только в мае 1994 года. По известным причинам история создания шифра и критерии его проектирования до сих пор неизвестны. ГОСТ 28147-89 представляет собой блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Основа алгоритма уже нам известная Сеть Фейштеля. Основным режимом шифрования по ГОСТ 28147-89 является режим простой замены (определены также более сложные режимы гаммирования и гаммирования с обратной связью). Рассмотрим механизм работы алгоритма подробней.
При Работе ГОСТ 28147-89 информация шифруется блоками по 64 бит (такие алгоритмы называются блочными), которые затем разбиваются на два субблока по 32 бит (N1 и N2). Субблок N1 обрабатывается таким образом, после чего его значение складывается со значением субблока N2 (сложение выполняется по модулю 2, т. е. применяется логическая операция XOR - "исключающее или"), а затем субблоки меняются местами. Данное преобразование выполняется определенное число раз ("раундов"): 16 или 32 в зависимости от режима работы алгоритма. В каждом раунде выполняются две операции:
Первая операция подразумевает наложение ключа. Содержимое субблока N1 складывается по модулю 2[32] с 32-битной частью ключа Kx. Полный ключ шифрования представляется в виде конкатенации 32-битных подключей: K0, K1, K2, K3, K4, K5, K6, K7. В процессе шифрования используется один из этих подключей - в зависимости от номера раунда и режима работы алгоритма.
Вторая операция осуществляет табличную замену. После наложения ключа субблок N1 разбивается на 8 частей по 4 бит, значение каждой из которых заменяется в соответствии с таблицей замены для данной части субблока. Затем выполняется побитовый циклический сдвиг субблока влево на 11 бит.
Алгоритм, определяемый ГОСТ 28147-89 может работать в четырёх режимах работы:
. простой замены;
. гаммирования;
. гаммирования с обратной связью;
. и генерации имитоприставок.
В них (генерации имитоприставок) используется одно и то же описанное выше шифрующее преобразование, но, поскольку назначение режимов различно, осуществляется это преобразование в каждом из них по-разному.
В режиме простой замены для зашифровки каждого 64-битного блока информации выполняются 32 описанных выше раунда. При этом 32-битные подключи используются в следующей последовательности:
K0, K1, K2, K3, K4, K5, K6, K7, K0, K1 и т. д. - в раундах с 1-го по 24-й;
K7, K6, K5, K4, K3, K2, K1, K0 - в раундах с 25-го по 32-й.
Расшифровка в данном режиме проводится точно так же, но с несколько другой последовательностью применения подключей:
K0, K1, K2, K3, K4, K5, K6, K7 - в раундах с 1-го по 8-й;
K7, K6, K5, K4, K3, K2, K1, K0, K7, K6 и т. д. - в раундах с 9-го по 32-й.
Каждый из блоков шифруются независимо друг от друга, т. е. результат шифрования каждого блока зависит только от его содержимого (соответствующего блока исходного текста). При наличии нескольких одинаковых блоков исходного (открытого) текста соответствующие им блоки шифртекста тоже будут одинаковы, что дает дополнительную полезную информацию для пытающегося вскрыть шифр криптоаналитика. Поэтому данный режим применяется в основном для шифрования самих ключей шифрования (очень часто реализуются многоключевые схемы, в которых по ряду соображений ключи шифруются друг на друге). Для шифрования собственно информации предназначены два других режима работы - гаммирования и гаммирования с обратной связью.
В режиме гаммирования каждый блок открытого текста побитно складывается по модулю 2 с блоком гаммы шифра размером 64 бит. Гамма шифра - это специальная последовательность, которая получается в результате определенных операций с регистрами N1 и N2 (см. рис. 6).
1. В регистры N1 и N2 записывается их начальное заполнение - 64-бит величина, называемая синхропосылкой.
2. Выполняется зашифровка содержимого регистров N1 и N2 (в данном случае - синхропосылки) в режиме простой замены.
3. Содержимое регистра N1 складывается по модулю (232 - 1) с константой C1 = 224 + 216 + 28 + 24, а результат сложения записывается в регистр N1.
4. Содержимое регистра N2 складывается по модулю 232 с константой C2 = 224 + 216 + 28 + 1, а результат сложения записывается в регистр N2.
5. Содержимое регистров N1 и N2 подается на выход в качестве 64-битного блока гаммы шифра (в данном случае N1 и N2 образуют первый блок гаммы).
Если необходим следующий блок гаммы (т. е. необходимо продолжить зашифровку или расшифровку), выполняется возврат к операции 2.
Для расшифровки гамма вырабатывается аналогичным образом, а затем к битам зашифрованного текста и гаммы снова применяется операция XOR. Поскольку эта операция обратима, в случае правильно выработанной гаммы получается исходный текст (таблица).
Таблица 1. Зашифровка и расшифровка в режиме гаммирования
Для выработки нужной для расшифровки гаммы шифра у пользователя, расшифровывающего криптограмму, должен быть тот же ключ и то же значение синхропосылки, которые применялись при зашифровки информации. В противном случае получить исходный текст из зашифрованного не удастся. В большинстве реализаций алгоритма ГОСТ 28147-89 синхропосылка не секретна, однако есть системы, где синхропосылка – такой же секретный элемент, как и ключ шифрования. Для таких систем эффективная длина ключа алгоритма (256 бит) увеличивается еще на 64 бита секретной синхропосылки, которую также можно рассматривать как ключевой элемент.
В режиме гаммирования с обратной связью для заполнения регистров N1 и N2, начиная со 2-го блока, используется не предыдущий блок гаммы, а результат зашифровки предыдущего блока открытого текста (рис. 2). Первый же блок в данном режиме генерируется полностью аналогично предыдущему. Рассматривая режим генерации имитоприставок, следует определить понятие предмета генерации. Имитоприставка – это криптографическая контрольная сумма, вычисляемая с использованием ключа шифрования и предназначенная для проверки целостности сообщений. При генерации имитоприставки выполняются следующие операции: первый 64-битный блок массива информации, для которого вычисляется имитоприставка, записывается в регистры N1 и N2 и зашифровывается в сокращенном режиме простой замены (выполняются первые 16 раундов из 32). Полученный результат суммируется по модулю 2 со следующим блоком информации с сохранением результата в N1 и N2.
Цикл повторяется до последнего блока информации. Получившееся в результате этих преобразований 64-битное содержимое регистров N1 и N2 или его часть и называется имитоприставкой. Размер имитоприставки выбирается, исходя из требуемой достоверности сообщений: при длине имитоприставки r бит вероятность, что изменение сообщения останется незамеченным, равна 2-r.Чаще всего используется 32-битная имитоприставка, т. е. половина содержимого регистров. Этого достаточно, поскольку, как любая контрольная сумма, имитоприставка предназначена прежде всего для защиты от случайных искажений информации. Для защиты же от преднамеренной модификации данных применяются другие криптографические методы - в первую очередь электронная цифровая подпись.
При обмене информацией имитоприставка служит своего рода дополнительным средством контроля. Она вычисляется для открытого текста при зашифровке какой-либо информации и посылается вместе с шифртекстом. После расшифровки вычисляется новое значение имитоприставки, которое сравнивается с присланной. Если значения не совпадают - значит, шифртекст был искажен при передаче или при расшифровке использовались неверные ключи. Особенно полезна имитоприставка для проверки правильности расшифровки ключевой информации при использовании многоключевых схем. Алгоритм ГОСТ 28147-89 считается достаточно сильным алгоритмом – в настоящее время для его раскрытия не существует более эффективных методов, чем упомянутый выше brute force. Высокая стойкость алгоритма достигается в первую очередь за счет большой длины ключа, равной 256 бит. К тому же, при использовании секретной синхропосылки эффективная длина ключа увеличивается до 320 бит, а засекречивание таблицы замен прибавляет дополнительные биты. Кроме того, криптостойкость ГОСТ 28147-89 уже при 32 раундах можно считать более чем достаточной, и это при том, что полный эффект рассеивания входных данных достигается уже после 8 раундов.
На сегодняшний день, алгоритм ГОСТ 28147-89 полностью удовлетворяет всем требованиям криптографии и обладает теми же достоинствами, что и другие алгоритмы, но лишен их недостатков. К очевидным достоинством нашего алгоритма можно отнести:
. эффективность реализации и соответственно высокое быстродействие на современных компьютерах;
. бесперспективность силовой атаки (XSL-атаки в учёт не берутся, т.к. их эффективность на данный момент полностью не доказана).
Однако же, как оно всегда и бывает, алгоритм не лишён недостатков:
. Тривиально доказывается, что у ГОСТа существуют "слабые" ключи и S-блоки, но в стандарте не описываются критерии выбора и отсева "слабых". Также стандарт не специфицирует алгоритм генерации S-блоков (таблицы замен). С одной стороны, это может являться дополнительной секретной информацией (помимо ключа), а с другой – поднимает ряд проблем: нельзя определить криптостойкость алгоритма, не зная заранее таблицы замен; реализации алгоритма от различных производителей могут использовать разные таблицы замен и могут быть несовместимы между собой.
Продолжение следует
Олег Бойцев, security-expert boytsev_om@mail.ru
Напомню нашим читателям, что в предыдущей части статьи мы начали рассматривать алгоритмы симметричного шифрования (см. КГ № 24). Одним из первых стандартов, который мы рассмотрели, был DES. Вскоре после его выхода обнаружилась очевидная слабость алгоритма: необходимость в принятии нового стандарта была более чем очевидна – небольшая длина ключа DES (56 бит) позволяла применить метод грубой силы против этого алгоритма. Кроме того, архитектура DES была ориентирована на аппаратную реализацию, и программная реализация алгоритма на платформах с ограниченными ресурсами не давала достаточного быстродействия. Модификация TDES обладала достаточной длиной ключа, но при этом была еще медленнее. TDES не просуществовал столь долго, чтобы можно было говорить о том, что алгоритм стоек и надёжен. Ему на смену, как это и следовало ожидать, пришёл более стойкий и надёжный алгоритм – AES, который, между прочим, был выбран в результате конкурса и принят в качестве американского стандарта шифрования правительством США. Немного о самом конкурсе.
2 января 1997 года NIST (Национальный Институт Стандартов и Технологий) объявляет о намерении найти замену DES, являвшегося американским стандартом с 1977 года. NIST принял достаточное количество предложений от заинтересованных сторон о том, каким образом следует выбирать алгоритм. Активный отклик со стороны открытого криптографического сообщества привел к объявлению конкурса 12 сентября 1997г. Алгоритм могла предложить практически любая организация или группа исследователей. Минимальные требования к новому стандарту были следующими:
. это должен быть блочный шифр;
. длина блока – равная 128 битам;
. ключи длиной 128, 192 и 256 бит;
. использовать операции, легко реализуемые как аппаратно (в микрочипах), так и программно (на персональных компьютерах и серверах); . ориентироваться на 32-разрядные процессоры;
. не усложнять без необходимости структуру шифра для того, чтобы все заинтересованные стороны были в состоянии самостоятельно провести независимый криптоанализ алгоритма и убедиться, что в нём не заложено каких-либо недокументированных возможностей.
Кроме всего вышеперечисленного, алгоритм, который претендует на то, чтобы стать стандартом, должен распространяться по всему миру без платы за пользование патентом.
20 августа 1998 года на 1-ой конференции AES был объявлен список из 15 кандидатов: CAST-256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER+, Serpent и Twofish. Понятное дело, что в последующих обсуждениях эти алгоритмы подвергались самому тщательному анализу, причем исследовались не только криптографические свойства, такие как стойкость к известным атакам и отсутствие слабых ключей, но и практические аспекты реализации. Так, особое внимание при выборе алгоритма было направлено на оптимизацию скорости выполнения кода на различных архитектурах (от ПК до смарт-карт и аппаратных реализаций), возможность оптимизации размера кода, возможность распараллеливания. В марте 1999 года прошла 2-ая конференция AES, а в августе 1999 года были объявлены 5 финалистов, среди которых оказались: MARS, RC6, Rijndael, Serpent, and Twofish. Все эти алгоритмы были разработаны авторитетными криптографами, имеющими мировое признание. На 3-ей конференции AES в апреле 2000 года все авторы представили свои алгоритмы.
В Нью-Йорке 13 и 14 апреля 2000 года, незадолго до завершения второго этапа, прошла третья конференция AES. Двухдневная конференция была разделена на восемь сессий, по четыре в день. На сессиях первого дня обсуждались вопросы, связанные с программируемыми матрицами (FGPA), проводилась оценка реализации алгоритмов на различных платформах, в том числе PA-RISC, IA-64, Alpha, высокоуровневых смарт-картах и сигнальных процессорах, сравнивалась производительность претендентов на стандарт, анализировалось число раундов в алгоритмах-кандидатах. На второй день был проанализирован Rijndael с сокращённым числом раундов и показана его слабость в этом случае, обсуждался вопрос об интегрировании в окончательный стандарт всех пяти алгоритмов-претендентов, ещё раз тестировались все алгоритмы. В конце второго дня была проведена презентация, на которой претенденты рассказывали о своих алгоритмах, их достоинствах и недостатках. О Rijndael как о лидере рассказал Винсент Риджмен, заявивший о надёжности защиты, высокой общей производительности и простоте архитектуры своего кандидата.
2 октября 2000 года было объявлено, что победителем конкурса стал алгоритм Rijndael, и началась процедура стандартизации. 28 февраля 2001 года был опубликован проект, а 26 ноября 2001 года AES был принят как FIPS 197.
Строго говоря, AES не одно и тоже, что и Rijndael, т.к. Rijndael поддерживает широкий диапазон длин ключей и блоков.
Особо следует подчеркнуть тот факт, что алгоритм Rijndael не похож на большинство известных алгоритмов симметричного шифрования, в основе которых стоит "сеть Фейштеля". Напомню нашим читателям, что особенность "сети Фейштеля" состоит в том, что входное значение разбивается на два и более субблоков, часть из которых в каждом раунде обрабатывается по определенному закону, после чего накладывается на необрабатываемые субблоки (схему сети см. в первой части статьи).
В отличие от ГОСТ 28147, который будет рассмотрен ниже, алгоритм Rijndael представляет блок данных в виде двухмерного байтового массива размером 4X4, 4X6 или 4X8 (допускается использование нескольких фиксированных размеров шифруемого блока информации). Все операции выполняются с отдельными байтами массива, а также с независимыми столбцами и строками.
. BS (ByteSub) – табличная замена каждого байта массива (рис. 1).
Вышеперечисленные преобразования над шифруемыми данными поочередно выполняются в каждом раунде (рис. 5).
Рис.5 Последовательность раундов Rijndael.
Исключения касаются лишь первого и последнего раундов: перед первым раундом дополнительно выполняется операция AK, а в последнем раунде отсутствует MC. В результате последовательность операций при зашифровке выглядит так:
AK, {BS, SR, MC, AK} (повторяется R-1 раз), BS, SR, AK.
В алгоритме Rijndael количество раундов шифрования (R) переменное (10, 12 или 14 раундов) и зависит от размеров блока и ключа шифрования (для ключа также предусмотрено несколько фиксированных размеров).
Почему же Rijndael стал новым стандартом шифрования, опередившим другие алгоритмы? Прежде всего, он обеспечивает высокую скорость шифрования, причём на всех платформах: как при программной, так и при аппаратной реализации. Алгоритм отличается удачным механизмом распараллеливания вычислений по сравнению с другими алгоритмами, представленными на конкурс. Кроме того, требования к ресурсам для его работы минимальны, что важно при его использовании в устройствах, обладающих ограниченными вычислительными возможностями.
Взлом AES возможен?!..
При всех преимуществах и оригинальности алгоритма AES можно было бы считать абсолютом надёжности и стойкости, но… как оно всегда и бывает, совершенных продуктов нет…
26 мая 2006 года (незадолго до EUROCRYPT 2006) на конференции Quo Vadis IV Николя Тадеуш Куртуа (польский криптограф, живущий во Франции) представит практическое доказательство существования алгебраических атак, оптимизированных против шифра AES-RIJNDAEL. За полтора часа на своём ноутбуке он осуществит демовзлом всего лишь по нескольким шифртекстам близкого аналога RIJNDAEL. Хотя это будет модельный шифр, он будет таким же стойким, в нём не будет добавлено существенных слабостей, он будет иметь такие же хорошие диффузионные характеристики и устойчивость ко всем известным до этого видам криптоанализа. Единственным отличием будут изменённые в рамках модели алгебраических атак параметры S-блоков и уменьшенное для наглядности число раундов. Однако этого достаточно, чтобы убедить скептиков в реальности алгебраических атак…
ГОСТ 28147
Следующим алгоритмом симметричного шифрования, который мы рассмотрим, станет ГОСТ 28147-89. ГОСТ 28147-89 – советский и российский стандарт симметричного шифрования, введённый 1-го июля 1990 года. Стандарт обязателен для организаций, предприятий и учреждений, применяющих криптографическую защиту данных, хранимых и передаваемых в сетях ЭВМ, в отдельных вычислительных комплексах или в ЭВМ.
Алгоритм был разработан в бывшем 8-м Главном Управлении КГБ СССР или в одном из секретных НИИ в его системе. Первоначально имел гриф (ОВ или СС - точно не известно), затем гриф последовательно снижался и к моменту официального проведения алгоритма через Госстандарт СССР в 1989 году был снят, алгоритм остался ДСП (как известно, ДСП не считается грифом). В 1989 году стал официальным стандартом СССР, а позже, после распада СССР, федеральным стандартом Российской Федерации.
С момента опубликования ГОСТа на нём стоял ограничительный гриф "Для служебного пользования", и формально шифр был объявлен "полностью открытым" только в мае 1994 года. По известным причинам история создания шифра и критерии его проектирования до сих пор неизвестны. ГОСТ 28147-89 представляет собой блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Основа алгоритма уже нам известная Сеть Фейштеля. Основным режимом шифрования по ГОСТ 28147-89 является режим простой замены (определены также более сложные режимы гаммирования и гаммирования с обратной связью). Рассмотрим механизм работы алгоритма подробней.
При Работе ГОСТ 28147-89 информация шифруется блоками по 64 бит (такие алгоритмы называются блочными), которые затем разбиваются на два субблока по 32 бит (N1 и N2). Субблок N1 обрабатывается таким образом, после чего его значение складывается со значением субблока N2 (сложение выполняется по модулю 2, т. е. применяется логическая операция XOR - "исключающее или"), а затем субблоки меняются местами. Данное преобразование выполняется определенное число раз ("раундов"): 16 или 32 в зависимости от режима работы алгоритма. В каждом раунде выполняются две операции:
Первая операция подразумевает наложение ключа. Содержимое субблока N1 складывается по модулю 2[32] с 32-битной частью ключа Kx. Полный ключ шифрования представляется в виде конкатенации 32-битных подключей: K0, K1, K2, K3, K4, K5, K6, K7. В процессе шифрования используется один из этих подключей - в зависимости от номера раунда и режима работы алгоритма.
Вторая операция осуществляет табличную замену. После наложения ключа субблок N1 разбивается на 8 частей по 4 бит, значение каждой из которых заменяется в соответствии с таблицей замены для данной части субблока. Затем выполняется побитовый циклический сдвиг субблока влево на 11 бит.
Алгоритм, определяемый ГОСТ 28147-89 может работать в четырёх режимах работы:
. простой замены;
. гаммирования;
. гаммирования с обратной связью;
. и генерации имитоприставок.
В них (генерации имитоприставок) используется одно и то же описанное выше шифрующее преобразование, но, поскольку назначение режимов различно, осуществляется это преобразование в каждом из них по-разному.
В режиме простой замены для зашифровки каждого 64-битного блока информации выполняются 32 описанных выше раунда. При этом 32-битные подключи используются в следующей последовательности:
K0, K1, K2, K3, K4, K5, K6, K7, K0, K1 и т. д. - в раундах с 1-го по 24-й;
K7, K6, K5, K4, K3, K2, K1, K0 - в раундах с 25-го по 32-й.
Расшифровка в данном режиме проводится точно так же, но с несколько другой последовательностью применения подключей:
K0, K1, K2, K3, K4, K5, K6, K7 - в раундах с 1-го по 8-й;
K7, K6, K5, K4, K3, K2, K1, K0, K7, K6 и т. д. - в раундах с 9-го по 32-й.
Каждый из блоков шифруются независимо друг от друга, т. е. результат шифрования каждого блока зависит только от его содержимого (соответствующего блока исходного текста). При наличии нескольких одинаковых блоков исходного (открытого) текста соответствующие им блоки шифртекста тоже будут одинаковы, что дает дополнительную полезную информацию для пытающегося вскрыть шифр криптоаналитика. Поэтому данный режим применяется в основном для шифрования самих ключей шифрования (очень часто реализуются многоключевые схемы, в которых по ряду соображений ключи шифруются друг на друге). Для шифрования собственно информации предназначены два других режима работы - гаммирования и гаммирования с обратной связью.
1. В регистры N1 и N2 записывается их начальное заполнение - 64-бит величина, называемая синхропосылкой.
2. Выполняется зашифровка содержимого регистров N1 и N2 (в данном случае - синхропосылки) в режиме простой замены.
3. Содержимое регистра N1 складывается по модулю (232 - 1) с константой C1 = 224 + 216 + 28 + 24, а результат сложения записывается в регистр N1.
4. Содержимое регистра N2 складывается по модулю 232 с константой C2 = 224 + 216 + 28 + 1, а результат сложения записывается в регистр N2.
5. Содержимое регистров N1 и N2 подается на выход в качестве 64-битного блока гаммы шифра (в данном случае N1 и N2 образуют первый блок гаммы).
Если необходим следующий блок гаммы (т. е. необходимо продолжить зашифровку или расшифровку), выполняется возврат к операции 2.
Для расшифровки гамма вырабатывается аналогичным образом, а затем к битам зашифрованного текста и гаммы снова применяется операция XOR. Поскольку эта операция обратима, в случае правильно выработанной гаммы получается исходный текст (таблица).
Таблица 1. Зашифровка и расшифровка в режиме гаммирования
| Операция | Результат | |
| Исходный текст | 100100 | |
| Гамма | XOR | 111000 |
| Шифртекст | = | 011100 |
| Гамма | XOR | 111000 |
| Исходный текст | = | 100100 |
Для выработки нужной для расшифровки гаммы шифра у пользователя, расшифровывающего криптограмму, должен быть тот же ключ и то же значение синхропосылки, которые применялись при зашифровки информации. В противном случае получить исходный текст из зашифрованного не удастся. В большинстве реализаций алгоритма ГОСТ 28147-89 синхропосылка не секретна, однако есть системы, где синхропосылка – такой же секретный элемент, как и ключ шифрования. Для таких систем эффективная длина ключа алгоритма (256 бит) увеличивается еще на 64 бита секретной синхропосылки, которую также можно рассматривать как ключевой элемент.
В режиме гаммирования с обратной связью для заполнения регистров N1 и N2, начиная со 2-го блока, используется не предыдущий блок гаммы, а результат зашифровки предыдущего блока открытого текста (рис. 2). Первый же блок в данном режиме генерируется полностью аналогично предыдущему. Рассматривая режим генерации имитоприставок, следует определить понятие предмета генерации. Имитоприставка – это криптографическая контрольная сумма, вычисляемая с использованием ключа шифрования и предназначенная для проверки целостности сообщений. При генерации имитоприставки выполняются следующие операции: первый 64-битный блок массива информации, для которого вычисляется имитоприставка, записывается в регистры N1 и N2 и зашифровывается в сокращенном режиме простой замены (выполняются первые 16 раундов из 32). Полученный результат суммируется по модулю 2 со следующим блоком информации с сохранением результата в N1 и N2.
Цикл повторяется до последнего блока информации. Получившееся в результате этих преобразований 64-битное содержимое регистров N1 и N2 или его часть и называется имитоприставкой. Размер имитоприставки выбирается, исходя из требуемой достоверности сообщений: при длине имитоприставки r бит вероятность, что изменение сообщения останется незамеченным, равна 2-r.Чаще всего используется 32-битная имитоприставка, т. е. половина содержимого регистров. Этого достаточно, поскольку, как любая контрольная сумма, имитоприставка предназначена прежде всего для защиты от случайных искажений информации. Для защиты же от преднамеренной модификации данных применяются другие криптографические методы - в первую очередь электронная цифровая подпись.
При обмене информацией имитоприставка служит своего рода дополнительным средством контроля. Она вычисляется для открытого текста при зашифровке какой-либо информации и посылается вместе с шифртекстом. После расшифровки вычисляется новое значение имитоприставки, которое сравнивается с присланной. Если значения не совпадают - значит, шифртекст был искажен при передаче или при расшифровке использовались неверные ключи. Особенно полезна имитоприставка для проверки правильности расшифровки ключевой информации при использовании многоключевых схем. Алгоритм ГОСТ 28147-89 считается достаточно сильным алгоритмом – в настоящее время для его раскрытия не существует более эффективных методов, чем упомянутый выше brute force. Высокая стойкость алгоритма достигается в первую очередь за счет большой длины ключа, равной 256 бит. К тому же, при использовании секретной синхропосылки эффективная длина ключа увеличивается до 320 бит, а засекречивание таблицы замен прибавляет дополнительные биты. Кроме того, криптостойкость ГОСТ 28147-89 уже при 32 раундах можно считать более чем достаточной, и это при том, что полный эффект рассеивания входных данных достигается уже после 8 раундов.
На сегодняшний день, алгоритм ГОСТ 28147-89 полностью удовлетворяет всем требованиям криптографии и обладает теми же достоинствами, что и другие алгоритмы, но лишен их недостатков. К очевидным достоинством нашего алгоритма можно отнести:
. эффективность реализации и соответственно высокое быстродействие на современных компьютерах;
. бесперспективность силовой атаки (XSL-атаки в учёт не берутся, т.к. их эффективность на данный момент полностью не доказана).
Однако же, как оно всегда и бывает, алгоритм не лишён недостатков:
. Тривиально доказывается, что у ГОСТа существуют "слабые" ключи и S-блоки, но в стандарте не описываются критерии выбора и отсева "слабых". Также стандарт не специфицирует алгоритм генерации S-блоков (таблицы замен). С одной стороны, это может являться дополнительной секретной информацией (помимо ключа), а с другой – поднимает ряд проблем: нельзя определить криптостойкость алгоритма, не зная заранее таблицы замен; реализации алгоритма от различных производителей могут использовать разные таблицы замен и могут быть несовместимы между собой.
Продолжение следует
Олег Бойцев, security-expert boytsev_om@mail.ru
Компьютерная газета. Статья была опубликована в номере 25 за 2007 год в рубрике безопасность
