Атаки на алгоритмы шифрования

Атаки на алгоритмы шифрования

Опубликовано 26 февраля 2007 года

В вышедшем недавно на нашем сайте цикле статей «Современные методы вскрытия алгоритмов шифрования» были описаны различные виды криптоаналитических атак на алгоритмы симметричного блочного шифрования. Все описанные атаки объединяло одно – они использовали некоторые уязвимости структуры атакуемого алгоритма. Т.е. данные атаки, фактически, рассматривали алгоритм шифрования только с теоретической точки зрения – как некое математическое преобразование, с помощью которого из открытого текста получается шифртекст.

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

Все атаки, использующие утечки данных по побочным каналам (side-channelattacks) можно разделить на две категории [7]:

1. Пассивные (passive) атаки, в процессе реализации которых криптоаналитик лишь пассивно «прослушивает» шифратор с целью получения необходимой информации для ее последующего анализа.

 

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

 

В этой части статьи рассмотрим подробно пассивные атаки.

 

Атака по времени выполнения

 

Начало подобным атакам положили работы Пола Кохера (PaulKocher), прежде всего, статья [3], в которой была представлена атака по времени выполнения (timingattack). Данная атака использует тот факт, что на некоторых аппаратных платформах определенные операции могут выполняться за различное число тактов процессора. Результат – различное время выполнения операций. Соответственно, криптоаналитик может путем высокоточных замеров времени выполнения шифратором определенных операций может сделать какие-либо предположения о значении определенных фрагментов секретного ключа.

 

В отчете [6] приведена следующая классификация используемых в криптоалгоритмах операций по степени их подверженности атакам по времени выполнения:

 

1. Не подвержены атакам по времени выполнения (т.е. выполняются за одинаковое число тактов на всех платформах) операции табличной замены, сдвига и вращения на фиксированное число бит, а также логические операции.

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

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

Одним из наиболее показательных алгоритмов, против которых может быть проведена атака по времени выполнения, является алгоритм RC5 (его подробное описание на русском языке можно найти в [11]).

Рассмотрим раунд данного алгоритма (см. рис. 1).

 

 

Рис. 1 Раунд алгоритма RC5.

 

Как видно, в раунде RC5 присутствуют операции вращения на переменное число бит, что приводит к появлению неких, зависящих от обрабатываемых данных и значения секретного ключа, временн ы х характеристик. Это делает атаку на RC5 теоретически возможной. Среди других алгоритмов, подверженных данной атаке, Кохер в [3] упоминает такие известные алгоритмы, как IDEA [5], Blowfish [8] и DES (см. часть 3 статьи «Современные методы вскрытия алгоритмов шифрования»).

 

В качестве «противоядия» к атакам по времени выполнения Кохер предлагает следующее [3]:

 

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

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

 

Другие пассивные атаки

 

В 2000 г. была предложена атака, использующая высокоточные измерения электромагнитного излучения шифратора, возникающего в процессе шифрования (см., например, [2]). Аналогично SPA и DPA, рассматриваются два варианта такой атаки: SEMA (simpleelectromagneticanalysis) и DEMA (differentialelectromagneticanalysis). Авторы статьи [2] в качестве атакуемых устройств избрали криптографические смарт-карты, реализующие алгоритмы DES, RSA и COMP128. Во всех трех случаях атака методом DEMA позволила вычислить значения ключей шифрования.

 

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

 

Практически реализуемая атака, основанная на сообщениях об ошибках (errormessageleakage), была предложена известным криптологом Сержем Воденэ (SergeVaudenay) в [9].

 

Успех описанных атак зависит от множества различных факторов, в частности:

 

· содержит ли атакуемый алгоритм операции, критичные с точки зрения утечек информации по побочным каналам;

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

 

Наиболее часто атакуемыми оказываются криптографические смарт-карты, т.е. достаточно низкоскоростные шифраторы, работающие в условиях ограниченных ресурсов. В данном случае для проведения атаки нет необходимости в столь высокоточных замерах, какие были бы необходимы, например, для атаки на программный шифратор, работающий на современном персональном компьютере. Помимо упомянутой статьи [2], весьма показательной в данном случае является работа [1], посвященная атаке по времени выполнения на смарт-карту CASCADE.

 

Информация, полученная с помощью атак с использованием утечек данных по побочным каналам, может использоваться криптоаналитиком в контексте других атак, например, для сужения области возможных значений ключа шифрования. Однако, как показано в [2], возможен и идеальный для криптоаналитика вариант: полное раскрытие алгоритма (т.е. вычисление ключа шифрования) только за счет пассивнойside-channel-атаки.

 

 

1. Dhem J.-F., Koeune F., Leroux P.-A., Mestre P., Quisquater J.-J., Willems J.-L. A practical implementation of the timing attack. // http://citeseer.ist.psu.edu – June 15, 1998 – Universite catholique de Louvain, Louvain-la-Neuve, Belgium.

2. Gandolfi K., Mourtel C., Olivier F. Electromagnetic Analysis: Concrete Results. // http://citeseer.ist.psu.edu – 2001 – Gemplus Card International, France.

3. Kocher P.C. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. // http://citeseer.ist.psu.edu - Cryptography Research, Inc., San Francisco, USA.

4. Kocher P., Jaffe J., Jun B. Differential Power Analysis. // http://citeseer.ist.psu.edu – 1999 – Cryptography Research, Inc., San Francisco, CA, USA.

5. Lai X., Massey J. A Proposal for a New Block Encryption Standard. // http://bybin.narod.ru - 1990.

6. Nechvatal J., Barker E., Bassham L., Burr W., Dworkin M., Foti J., Roback E. Report on the Development of the Advanced Encryption Standard (AES). // http://csrc.nist.gov – National Institute of Standards and Technology.

7. Preneel B., Biryukov A., Oswald E., Van Rompay B., Granboulan L., Dottax E., Murphy S., Dent A., White J., Dichtl M., Pyka S., Schafheutle M., Serf P., Biham E., Barkan E., Dunkelman O., Quisquater J.-J., Ciet M., Sica F., Knudsen L., Parker M., Raddum H. Public Report D20: NESSIE security report. // http://www.cosic.esat.kuleuven.be. – February 19, 2003 – Version 2.0.

8. Schneier B. The Blowfish encryption algorithm. // http://www.schneier.com.

9. Vaudenay S. Security Flaws Induced by CBC Padding Applications to SSL, IPSEC, WTLS… // http://lasecwww.epfl.ch – Swiss Federal Institute of Technology.

10. Панасенко С. Алгоритм шифрования DES и его варианты. // Connect! Мир связи. – 2006 - №№ 3, 4, 5, 7.

11. Панасенко С. Интересные алгоритмы шифрования, часть 2. // BYTE/Россия. – 2006 - № 5 – с. 74-79.

 

 

Об авторе:

Панасенко Сергей Петрович, нач. отдела разработки программного обеспечения фирмы АНКАД, кандидат технических наук.

С автором можно связаться: по телефонам (495)532-1313, (495)531-0000

или по E-mail [email protected]

http://www.panasenko.ru

 

 

Расширение ключа

Для начала стоит сказать о том, что весьма редко встречаются алгоритмы шифрования, которые используют ключ шифрования (или его фрагменты) в «чистом» виде (таким алгоритмом является, например, отечественный стандарт шифрования ГОСТ 28147-89 [10]). Подавляющее большинство алгоритмов шифрования выполняет существенную модификацию исходного ключа шифрования для его последующего использования в процессе преобразований. Такая модификация называется расширением ключа (keyextension, keyschedule); существуют примеры алгоритмов, в которых процедура расширения ключа является исключительно сложной по сравнению с собственно шифрованием, среди них стоит упомянуть алгоритмы HPC и FROG (см. описание в [12] и [11]). Название процедуры проистекает из того факта, что исходный ключ шифрования обычно имеет размер существенно меньший совокупности подключей, используемых в раундах алгоритма, т.е. расширенного ключа.

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

 

Рис. 1 Назначение процедуры расширения ключа.

 

К процедуре расширения ключа предъявляется немало требований, целью которых является повышение криптостойкости и других характеристик алгоритма, например:

· Весьма желательно, чтобы процедура расширения ключа могла вычислять ключи «на лету» (on-the-fly), т.е. параллельно с шифрующими преобразованиями: это позволит как распараллеливать вычисления в многопроцессорных системах, так и не тратить память для хранения всего расширенного ключа при шифровании в условиях ограниченных ресурсов.

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

· Степень подверженности алгоритма атакам на связанных ключах также весьма зависит от процедуры расширения ключа.

 

«Классическая» атака на связанных ключах

 

«Классическая» атака на связанных ключах, предложенная Эли Бихамом (EliBiham) в работе [1], во многом похожа на сдвиговую атаку, описанную в 5-й части статьи «Современные методы вскрытия алгоритмов шифрования». Основное различие состоит в том, что сдвиговая атака использует два открытых текста P и P’, связанных между собой следующим соотношением:

P’ = F(P, k₁),

где F() – функция раунда, а k₁ – подключ 1-го раунда, тогда как атака на связанных ключах использует весьма похожее соотношение между ключами.

Итак, предположим, что искомый ключ шифрования K в результате его обработки процедурой расширения ключа Ex(K) дает следующую последовательность подключей:

Ex(K) = {k₁, k₂, …, k_r-1, k_r},

где r – количество раундов алгоритма шифрования.

Предположим также, что есть некий ключ K’, расширение которого дает следующую последовательность:

Ex(K’) = {k₂, k₃, …, k_r, k₁},

т.е. последовательность подключей, формируемая на основе ключа K’, циклически сдвинута относительна последовательности искомого ключа K на 1 раунд (см. рис. 2).

 

 

 

Рис. 2 Подключи в «классической» атаке на связанных ключах

 

Суть атаки состоит в следующем [1, 4]:

1. Снова предположим, что криптоаналитику известно 2 ^{n /2} пар (P, C) открытых текстов и соответствующих им шифртекстов (зашифрованных на искомом ключе K), где n – размер блока шифруемых данных в битах.

2. Кроме того, криптоаналитику известно столько же (2 ^{n /2}) пар текстов (P’, C’), полученных уже с использованием ключа K’, связанного с K приведенным выше соотношением.

3. Для каждого соотношения текстов (P, C) и (P’, C’) криптоаналитик решает систему уравнений:

F(P, k*) = P’,

F(C, k*) = C’.

Криптоаналитик не может знать заранее, какой из 2 ^{n /2} текстов P’ соответствует конкретному тексту P. Однако, вероятность того, что два случайных текста будут соответствовать требуемому соотношению, равна 2^{- n}; соответственно, согласно парадоксу дней рождения (см. часть 5 статьи «Современные методы вскрытия алгоритмов шифрования»), требуемая пара (P, P’) должна быть найдена в среднем после анализа не более, чем 2 ^{n /2 + 1} текстов.

Весьма вероятно, что некий ключ k*, удовлетворяющий приведенным выше уравнениям, и есть искомый подключ k₁. В зависимости от процедуры расширения ключа знание k₁ может дать криптоаналитику достаточно много информации о искомом ключе K. Например, расширение ключа алгоритма LOKI89 [3] построено таким образом, что k₁ представляет собой просто левую 32-битную половину ключа K, т.е. после вычисления k₁ для нахождения K достаточно хотя бы перебора всего 2³² вариантов.

Необходимое условие для проведения данной атаки состоит в том, что функция раунда F() атакуемого алгоритма должна быть достаточно слабой для вычисления k*, что, однако, можно сказать применительно к большинству современных алгоритмов шифрования.

В зависимости от структуры самого алгоритма шифрования, трудоемкость атаки может быть существенно меньше описанного выше общего случая. В частности, для алгоритмов, основанных на сбалансированной сети Фейстеля (см., например, [14]), раунд алгоритма модифицирует данные, например, следующим образом:

{L_i+1, R_i+1} = {R_i, L_iÅF(R_i)},

где L и R – соответственно, левая и правая половины обрабатываемого блока данных, а i – номер раунда. Ясно, что в этом случае поиск требуемых пар (P, P’) существенно упрощается [4].

Описанная выше атака на связанных ключах не выглядит практичной. Легко согласиться с тем, что она требует слишком большого количества предположений. Данная атака достаточно долго считалась достаточно мощной, но сугубо теоретической. Однако, сейчас многие эксперты считают, что атаки на связанных ключах могут иметь практическое применение. В работе [5] отмечается, что основное условие для атаки выглядит достаточно странно: криптоаналитик может писать ключ (т.е. модифицировать искомый неизвестный ключ требуемым образом), но не может его читать. Тем не менее, некоторые реализации криптоалгоритмов или сетевых протоколов (например, протоколов аутентификации или обмена ключами) могут быть атакованы с использованием связанных ключей. В любом случае, в работе [5] категорически рекомендуется принимать в расчет криптоанализ на связанных ключах при разработке алгоритмов шифрования и их реализации. Там же приведен пример реализации протокола защищенного обмена ключами, вскрываемого с использованием связанных ключей при условии, что лежащий в основе данного протокола алгоритм шифрования подвержен атакам на связанных ключах. И там же отмечается, что атаки на связанных ключах могут быть весьма опасны и в случае использования алгоритмов симметричного шифрования для построения функций хэширования (криптографического контрольного суммирования данных).

 

Атакуемые алгоритмы

 

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

Рис. 3 Процедура расширения ключа алгоритма LOKI89.

 

Чрезмерная простота процедуры расширения ключа делает алгоритм подверженным описанной выше атаке на основе связанных ключей [1]:

· Для успешной атаки на основе выбранных открытых текстов (см. часть 1 статьи «Современные методы вскрытия алгоритмов шифрования») требуется всего 2¹⁷ тестовых операций шифрования.

· В случае использования известных открытых текстов сложность атаки возрастает до порядка 2³² операций.

В следующей версии алгоритма LOKI – LOKI91 [2] – процедура расширения ключа была несколько модифицирована, однако, алгоритм остался подверженным «классической» атаке на связанных ключах: для ее осуществления требуется 2³² (выбранные открытые тексты) или 2⁴⁸ (известные открытые тексты) операций [1]. Еще одна атака, использующая слабость процедуры расширения ключа алгоритма LOKI91, была предложена Ларсом Кнудсеном (LarsKnudsen) в работе [8]

Согласно [1], данной атакой вскрывается также один из вариантов алгоритма Lucifer (подробное описание всех вариантов алгоритма Lucifer можно найти в [13]); для его вскрытия на основе выбранных открытых текстов требуется около 2³² операций.

Другой вариант атаки на связанных ключах описан в [7]. Атака использует весьма интересную особенность алгоритма шифрования SAFERK-64 [9]: для почти каждого ключа K существует ключ K’ (отличающийся от K значением одного байта), такой, что для достаточно большого множества открытых текстов (до 2²⁸ из возможных 2⁶⁴) после 6 раундов шифрования (SAFERK-64 выполняет 6 раундов и финальное преобразование данных) результаты шифрования каждого из текстов на ключах K и K’ абсолютно эквивалентны. Финальное преобразование делает результаты шифрования различными, но только в одном байте шифртекста. Данная особенность позволяет вычислить 8 бит 64-битного ключа шифрования алгоритма SAFERK-64 на основе от 2⁴⁴ до 2⁴⁷ выбранных открытых текстов.

 

Конкурс AES

В отличие от многих других криптографических стандартов (например, предыдущего стандарта шифрования США DES [4] или отечественного стандарта ГОСТ 28147-89 [9]), AES не был разработан «в недрах спецслужб», а выбран на открытом конкурсе из относительно большого числа алгоритмов-претендентов.
До принятия в качестве стандарта алгоритма AES в данном качестве использовался алгоритм DES (Data Encryption Standard – стандарт шифрования данных). Несмотря на множество найденных криптоаналитических методов, применимых к DES (подробно о алгоритме DES и его криптоанализе см. [10]), фактически, не было обнаружено каких-либо серьезных уязвимостей в данном алгоритме, за исключением одного, но весьма принципиального недостатка: весьма короткого ключа, реальный размер которого составляет всего 56 бит. Насколько это мало, можно судить из следующей весьма распространенной оценки: для полного перебора ключей DES достаточно примерно 20 часов работы миллиона процессоров, каждый из которых перебирает миллион ключей DES в секунду [8]. Ясно, что такой стойкости против вскрытия алгоритма методом «грубой силы» (см. часть 2 статьи «Современные методы вскрытия алгоритмов шифрования») категорически недостаточно. Тем не менее, DES оставался стандартом шифрования до начала XXI века.

В 1997 году Институт Стандартов и Технологий США (NIST – NationalInstituteofStandardsandTechnology) объявил о проведении конкурса по замене стандарта DES. На конкурс могли быть присланы алгоритмы шифрования, разработанные как организациями, так и частными лицами в любой стране. Алгоритм-победитель этого конкурса должен был стать новым стандартом блочного симметричного шифрования США.

Для участия в конкурсе (которому было присвоено название AES) алгоритм шифрования должен был соответствовать всего двум обязательным требованиям [2]:

· 128-битный размер блока шифруемых данных,

· не менее трех поддерживаемых алгоритмом размеров ключей шифрования: 128, 192 и 256 бит.

Кроме того, NIST в [2] предъявил большое число требований, носивших рекомендательный характер. Именно по соответствию этим требованиям, фактически, и был выбран алгоритм-победитель конкурса. Рекомендации NIST были таковы:

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

2. Структура алгоритма должна быть ясной, простой и обоснованной. Прежде всего, такая структура облегчила бы анализ алгоритма в рамках конкурса. Кроме того, ясность и простота структуры давала бы некоторую гарантию отсутствия в алгоритме специально внедренных авторами «закладок», т.е. некоторых недокументированных особенностей алгоритма, которые могли бы быть использованы авторами для его вскрытия.

3. Должны отсутствовать слабые и эквивалентные ключи (т.е. ключи, являющиеся различными, но приводящие к одному и тому же результату шифрования).

4. Скорость шифрования данных должна быть высокой на всех потенциальных аппаратных платформах – от 8-битных до 64-битных.

5. Структура алгоритма должна позволять распараллеливание операций в многопроцессорных системах и аппаратных реализациях.

6. Алгоритм должен предъявлять минимальные требования к оперативной и энергонезависимой памяти.

7. Не должно быть ограничений для использования алгоритма; в частности, алгоритм не должен ограничивать свое использование в различных стандартных режимах работы (см. [5]), в качестве основы для построения хэш-функций, генераторов псевдослучайных последовательностей и т.д.

В конкурсе AES приняли участие 15 алгоритмов шифрования [1, 7]:

Алгоритм	Автор	Достоинства и недостатки алгоритма
CAST-256	Entrust Technologies, Inc.	В алгоритме не обнаружено уязвимостей. Однако, скорость шифрования у данного алгоритма невысока; кроме того, у него высокие требования к оперативной и энергонезависимой памяти.
Crypton	Future Systems, Inc.	Алгоритм без явных недостатков. Однако,Crypton уступает по всем характеристикам похожему на него алгоритму Rijndael. Эксперты конкурса сочли, что в финале конкурса Crypton однозначно проиграет Rijndael, поэтому не выбрали его во второй раунд конкурса.
DEAL	Richard Outerbridge, Lars Knudsen	Множество недостатков: наличие подмножеств слабых ключей (см. статью «Криптоаналитические атаки на связанных ключах»), подверженность дифференциальному криптоанализу (см. часть 3 статьи «Современные методы вскрытия алгоритмов шифрования»), отсутствие усиления при использовании 192-битных ключей по сравнению с 128-битными.
DFC	CNRS – Centre National pour la Recherche Scientifique – Ecole Normale Superieure	Достоинство алгоритма: очень высокая скорость шифрования на 64-битных платформах. При этом алгоритм весьма медленно шифрует на остальных платформах, а также имеет классы слабых ключей.
E2	NTT – Nippon Telegraph and Telephone Corporation	Аналогично алгоритму CAST-256, в E2 не найдено уязвимостей, но требования к энергонезависимой памяти слишком высоки.
FROG	TecApro Internacional S.A.	Алгоритм с наиболее оригинальной структурой и с наибольшим количеством недостатков: наличие уязвимостей, низкая скорость шифрования и высокие требования к ресурсам.
HPC	Richard Schroeppel	Аналогично алгоритму DFC, HPC очень быстро шифрует на 64-битных платформах, но весьма медленно на остальных. Кроме того, сложная и медленная процедура расширения ключа ограничивает возможные применения алгоритма, а наиболее сложная из всех представленных на конкурс алгоритмов структура раунда усложняет анализ алгоритма и делает недоказуемым отсутствие закладок.
LOKI97	Lawrie Brown, Josef Pieprzyk, Jennifer Seberry	Низкая скорость шифрования, высокие требования к ресурсам, наличие уязвимостей.
Magenta	Deutsche Telekom AG	Алгоритм подвержен атакам методами линейного (см. часть 4 статьи «Современные методы вскрытия алгоритмов шифрования») и дифференциального криптоанализа; медленная скорость шифрования.
MARS	IBM	У алгоритма отсутствуют серьезные недостатки, за исключением низкой скорости шифрования на ряде платформ, не имеющих аппаратной поддержки требуемых операций и некоторых других незначительных недостатков. Алгоритм был незначительно модифицирован в течение первого раунда; измененный вариант вышел в финал конкурса.
RC6	RSA Laboratories	RC6 имеет весьма похожие на MARS проблемы с реализацией на некоторых платформах. Эксперты посчитали это незначительным недостатком – алгоритм вышел в финал конкурса.
Rijndael	Joan Daemen, Vincent Rijmen	Каких-либо недостатков у алгоритма не обнаружено; алгоритм вышел в финал конкурса.
SAFER+	Cylink Corporation	Алгоритм подвержен ряду атак и имеет низкую скорость выполнения.
Serpent	Ross Anderson, Eli Biham, Lars Knudsen	Выявлены некоторые незначительные недостатки, алгоритм вышел в финал конкурса.
Twofish	Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson	Из недостатков эксперты отметили сложность алгоритма, затрудняющую его анализ. Алгоритм вышел в финал конкурса.

Как видно из данной таблицы, список участников конкурса оказался весьма разнообразен, среди них можно отметить:

· всемирно известных криптологов, например, «звездный» коллектив авторов алгоритма Twofish;

· организации, давно работающие в данной области и обладающие как богатым опытом разработки криптоалгоритмов, так и сильнейшими специалистами в данной области, например, американская фирма RSA – автор алгоритма RC6;

· всемирно известные корпорации, обладающие большим научным потенциалом, например японский телекоммуникационный гигант NTT с алгоритмом E2;

· образовательные учреждения, известные своими достижениями в области криптографии, например EcoleNormaleSuperieure (Париж, Франция) с алгоритмом DFC;

· и наоборот, организации, весьма малоизвестные до проведения конкурса AES, например, фирма Tecnologia Apropriada (автор алгоритма FROG) из латиноамериканского государства Коста-Рика.

Анализ алгоритмов-претендентов проводился как специалистами института NIST, так и различными независимыми экспертами – на конкурс было прислано множество материалов, посвященных участвовавшим в конкурсе алгоритмам; все эти материалы можно найти на сайте института NISThttp://csrc.nist.gov. По результатам анализа, как видно из приведенной выше таблицы, во второй раунд конкурса вышли следующие 5 алгоритмов:MARS, RC6, Rijndael, Serpent и Twofish.

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

Подробное описание алгоритмов MARS, RC6, Serpent и Twofish можно найти в статье [11]. Здесь же подробно рассмотрим алгоритм шифрования Rijndael, которому (как победителю конкурса) было присвоено название AES.

 

Структура алгоритма

 

Алгоритм AES представляет блок данных в виде двумерного байтового массива размером 4 X 4. Все операции производятся над отдельными байтами массива, а также над независимыми столбцами и строками.

 

 

 

Рис.1. Раунд алгоритма.

 

В каждом раунде алгоритма выполняются следующие преобразования (см. рис. 1) [3, 6]:

1. Операция SubBytes, представляющая собой табличную замену каждого байта массива данных согласно следующей таблице (см. рис. 2):

7C

7B

F2

6B

6F

C5

2B

FE

D7

AB

CA

C9

7D

FA

F0

AD

D4

A2

AF

9C

A4

C0

B7

FD

3F

F7

CC

A5

E5

F1

D8

C7

C3

9A

E2

EB

B2

2C

1A

1B

6E

5A

A0

3B

D6

B3

E3

2F

D1

ED

FC

B1

5B

6A

CB

BE

4A

4C

CF

D0

EF

AA

FB

4D

F9

7F

3C

9F

A8

A3

8F

9D

F5

BC

B6

DA

FF

F3

D2

CD

0C

EC

5F

D7

C4

A7

7E

3D

5D

4F

DC

2A

EE

B8

DE

5E

0B

DB

E0

3A

0A

5C

C2

D3

AC

E4

E7

C8

6D

8D

D5

4E

A9

6C

F4

EA

7A

AE

BA

2E

1C

A6

B4

C6

E8

DD

1F

4B

BD

8B

8A

3E

B5

F6

0E

B9

C1

1D

9E

E1

F8

D9

8E

9B

1E

E9

CE

DF

8C

A1

0D

BF

E6

2D

0F

B0

BB

Таблица меняет входное значение 0 на 63 (шестнадцатеричное значение), 1 – на 7C, 2 – на 77 и т.д.

 

 

Рис. 2. Операция SubBytes.

 

Вместо данной табличной замены можно выполнить эквивалентную ей комбинацию двух операций:

1.1. Вычисление мультипликативной обратной величины от входного значения в конечном поле GF(2⁸); обратной величиной от 0 является 0.

1.2. Выходное значение b вычисляется следующим образом:

b_i = a_iÅa_{i + 4 mod 8}Åa_{i+5 mod 8}Åa_{i+6 mod 8}Åa_{i+7 mod 8}Åc_i,

где n_i обозначает i -й бит величины n,

a – результат предыдущей операции,

c – шестнадцатеричная константа 63.

2. Операция ShiftRows, которая выполняет циклический сдвиг влево всех строк массива данных, за исключением нулевой (см. рис. 3). Сдвиг i -й строки массива (для i = 1, 2, 3) производится на i байт.

3. Операция MixColumns. Выполняет умножение каждого столбца массива данных (см. рис. 4), который рассматривается как полином в конечном поле GF(2⁸), на фиксированный полином a(x):

a(x) = 3x³ + x² + x + 2.

Умножение выполняется по модулю x⁴ + 1.

4. Операция AddRoundKey выполняет наложение на массив данных материала ключа. А именно, на i -й столбец массива данных (i = 0…3) побитовой логической операцией «исключающее или» (XOR) накладывается определенное слово расширенного ключа W_4r+i, где r – номер текущего раунда алгоритма, начиная с 1 (процедура расширения ключа будет описана ниже). Операция AddRoundKey представлена на рис. 5.

Количество раундов алгоритма R зависит от размера ключа следующим образом:

Размер ключа, бит	R

Перед первым раундом алгоритма выполняется предварительное наложение материала ключа с помощью операции AddRoundKey, которая выполняет наложение на открытый текст первых четырех слов расширенного ключа W₀…W₃.

Последний же раунд отличается от предыдущих тем, что в нем не выполняется операция MixColumns.

 

 

Рис. 3. Операция ShiftRows.

 

 

 

Рис. 4. Операция MixColumns.

 

 

 

Рис. 5. Операция AddRoundKey.

 

Расширение ключа

 

AES использует ключи шифрования трех фиксированных размеров: 128, 192, и 256 бит. В зависимости от размера ключа, конкретный вариант алгоритма AES может обозначаться как AES-128, AES-192 и AES-256 соответственно [6].

Задача процедуры расширения ключа состоит в формировании нужного количество слов расширенного ключа для их использования в операции AddRoundKey. Как было сказано выше, под «словом» здесь понимается 4-байтный фрагмент расширенного ключа, один из которых используется в первичном наложении материала ключа и по одному – в каждом раунде алгоритма. Таким образом, в процессе расширения ключа формируется 4*(R +1) слов.

Расширение ключа выполняется в два этапа, на первом из которых производится инициализация слов расширенного ключа (обозначаемых как W_i): первые Nk (Nk – размер исходного ключа шифрования K в словах, т.е. 4, 6 или 8) слов W_i (т.е. i = 0… Nk-1) формируются их последовательным заполнением байтами ключа (см. рис. 6).

 

 

 

Рис. 6. Инициализация первых слов расширенного ключа.

 

Последующие слова W_i формируются следующей последовательностью операций для каждого i = Nk …4*(R +1)-1:

Шаг 1. Инициализируется временная переменная T:

T = W_i-1.

Шаг 2. Данная переменная модифицируется следующим образом:

a. если i кратно Nk, то:

T = SubWord(RotWord(T)) Å RC_ëi/Nkû;

операции SubWord, RotWord будут описаны ниже, а константы RC_n представляют собой слова, в которых все байты, кроме первого являются нулевыми, а первый байт имеет значение 2 ^{n -1} mod 256;

b. если Nk = 8 и (i mod Nk) = 4, то:

T = SubWord(T);

c. в остальных случаях модификация переменной T не выполняется.

Шаг 3. Формируется i -е слово расширенного ключа:

W_i = W_i-Nk Å T.

Операция SubWord выполняет над каждым байтом входного значения табличную замену, которая была описана выше – см. операцию SubBytes.

Операци<