Другие возможные проблемы процедуры расширения ключа

 

Существуют и другие потенциальные уязвимости, вносимые в алгоритм шифрования неудачно спроектированной процедурой расширения ключа, в частности [5]:

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

2. Слабые ключи – ключи, зашифрование с использованием которых эквивалентно расшифрованию, или обладающие другими характеристиками, существенно упрощающими вскрытие.

3. Эквивалентные ключи – различные ключи, но дающие один и тот же результат зашифрования на некоем подмножестве открытых текстов.

4. Классы ключей – возникают, когда криптоаналитик может относительно легко определить подмножество ключевого множества, которому принадлежит искомый ключ, и, соответственно, уменьшить таким образом область полного перебора ключа.

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

 

 

1. Biham E. New Types of Cryptanalytic Attacks Using Related Keys (Revised version). // http://www.cs.technion.ac.il – Technion – Israel Institute of Technology, Haifa, Israel.

2. Brown L., Kwan M., Pieprzyk J., Seberry J. Improving Resistance to Differential Cryptanalysis and the Redesign of LOKI. // http://www.unsw.adfa.edu.au – Australian Defence Force Academy, Canberra, Australia.

3. Brown L., Pieprzyk J., Seberry J. LOKI – A Cryptographic Primitive for Authentication and Secrecy Applications. // http://www.unsw.adfa.edu.au – Australian Defence Force Academy, Canberra, Australia.

4. Ciet M., Piret G., Quisquater J.-J. Related-Key and Slide Attacks: Analysis, Connections, and Improvements (Extended Abstract). // http://citeseer.ist.psu.edu – 2002 – Universite catholique de Louvain, Louvain-la-Neuve, Belgium.

5. Kelsey J., Schneier B., Wagner D. Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES. // http://www.schneier.com – 1996.

6. Kelsey J., Schneier B., Wagner D. Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, and TEA. // http://www.schneier.com.

7. Knudsen L.R. A Key-schedule Weakness in SAFER K-64. // http://citeseer.ist.psu.edu – 1995 – Ecole Normale Superieure, Paris, France.

8. Knudsen L.R. Cryptanalysis of LOKI91. // http://citeseer.ist.psu.edu – Aarhus Universitet, Denmark.

9. Massey J.L. SAFER K-64: A Byte-oriented Block-ciphering Algorithm. // http://citeseer.ist.psu.edu – 1994 – Swiss Federal Institute of Technology, Zurich.

10. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. – М.: Госстандарт СССР, 1989.

11. Панасенко С. Алгоритм шифрования FROG. // Банки и технологии. – 2005 - № 4 – с. 82-85.

12. Панасенко С. Алгоритм шифрования HPC. // Банки и технологии. – 2005 - № 5 – с. 62-65.

13. Панасенко С. Алгоритм шифрования Lucifer. // Мир и безопасность. - 2006 - № 5 - с. 30-34.

14. Панасенко С. Назначение и структура алгоритмов шифрования. // iXBT. – http://www.ixbt.com/soft/alg-encryption.shtml - 2006.

 

 

Об авторе:

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

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

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

http://www.panasenko.ru

 

 

Алгоритм шифрования AES и его криптоанализ

Опубликовано 02 июня 2007 года

Алгоритм шифрования AES (Advanced Encryption Standard – улучшенный стандарт шифрования) в настоящее время является стандартом блочного симметричного шифрования США. Данная статья посвящена истории появления стандарта AES, описанию алгоритма шифрования, лежащего в его основе, а также различным криптоаналитическим исследованиям этого алгоритма.

Конкурс 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.

Операция RotWord побайтно вращает входное слово на 1 байт влево.

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

Авторы алгоритма в [3] пишут также, что не следует задавать напрямую расширенный ключ – программная или аппаратная реализация алгоритма должна именно получать исходный ключ шифрования K и выполнять процедуру расширения ключа. Здесь стоит снова вспомнить алгоритм DES – известно, что DES с независимо задаваемыми ключами раундов оказался слабее против некоторых атак, чем исходный алгоритм DES (см. [10]).

 

Расшифрование

 

Расшифрование выполняется применением обратных операций в обратной последовательности. Соответственно, перед первым раундом расшифрования выполняется операция AddRoundKey (которая является обратной самой себе), выполняющая наложение на шифртекст четырех последних слов расширенного ключа, т.е. W_4R…W_4R+3.

 

 

Рис. 7. Раунд расшифрования.

 

 

Затем выполняется R раундов расшифрования, каждый из которых выполняет следующие преобразования (см. рис. 7):

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

2. Операция InvSubBytes выполняет побайтно обратную табличную замену, которая определена следующей таблицей:

6A

D5

A5

BF

A3

9E

F3

D7

FB

7C

E3

9B

2F

FF

8E

C4

DE

E9

CB

7B

A6

C2

3D

EE

4C

0B

FA

C3

4E

2E

A1

D9

B2

5B

A2

6D

8B

D1

F8

F6

D4

A4

5C

CC

5D

B6

6C

FD

ED

B9

DA

5E

A7

8D

9D

D8

AB

8C

BC

D3

0A

F7

E4

B8

B3

D0

2C

1E

8F

CA

3F

0F

C1

AF

BD

8A

6B

3A

4F

DC

EA

F2

CF

CE

F0

B4

E6

AC

E7

AD

E2

F9

E8

1C

DF

6E

F1

1A

1D

C5

6F

B7

0E

AA

BE

1B

FC

3E

4B

C6

D2

9A

DB

C0

FE

CD

5A

F4

1F

DD

A8

C7

B1

EC

5F

7F

A9

B5

4A

0D

2D

E5

7A

9F

C9

9C

EF

A0

E0

3B

4D

AE

2A

F5

B0

C8

EB

BB

3C

2B

7E

BA

D6

E1

0C

7D

Данную табличную замену можно выполнить, применив к входному байту преобразование, обратное операции 1.2 (см. описание операции SubBytes), после чего вычислить мультипликативную обратную величину от результата предыдущей операции в конечном поле GF(2⁸).

3. Операция AddRoundKey, как и при зашифровании, выполняет наложение на обрабатываемые данные четырех слов расширенного ключа W_4r…W_4r+3. Однако, нумерация раундов r при расшифровании производится в обратную сторону – от R -1 до 0.

4. Операция InvMixColumns выполняет умножение каждого столбца массива данных аналогично прямой операции MixColumns, однако, умножение производится на полином a^-1(x), определенный следующим образом:

a^-1(x) = Bx³ + Dx² + 9x + E.

Аналогично зашифрованию, последний раунд расшифрования не содержит операцию InvMixColumns.