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

Вторая часть статьи посвящена криптоанализу алгоритма AES.

Первичная оценка криптостойкости

Первичная оценка криптостойкости алгоритма Rijndael была приведена авторами алгоритма в его спецификации [13], представленной на конкурс AES. Согласно оценкам авторов, Rijndael не подвержен следующим видам криптоаналитических атак:
1. У алгоритма отсутствуют слабые ключи, а также возможности его вскрытия с помощью атак на связанных ключах (описание криптоаналитических атак, упомянутых в данной статье, можно найти в статьях «Современные методы вскрытия алгоритмов шифрования», «Атаки на шифраторы с использованием утечек данных по побочным каналам» и «Криптоаналитические атаки на связанных ключах»).
2. К алгоритму не применим дифференциальный криптоанализ.
3. Алгоритм не атакуем с помощью линейного криптоанализа и усеченных дифференциалов.
4. Square-атака (специфичная атака на алгоритмы со структурой «квадрат», к которым относится и AES, подробно описана в [11]) также не применима к алгоритму Rijndael.
5. Алгоритм не вскрывается методом интерполяции.

Исследования в рамках конкурса AES

Сначала рассмотрим те результаты криптоанализа, которые были учтены экспертами при выборе алгоритма-победителя конкурса AES. Прежде всего, было найдено несколько атак на усеченные (с уменьшенным количеством раундов) версии алгоритма Rijndael [24]:

· В упомянутой выше первичной оценке криптостойкости были приведены некоторые атаки на усеченные версии Rijndael [13], из которых стоит отметить Square-атаку на 6-раундовую версию алгоритма, для которой необходимо 2³² выбранных открытых текстов и 2⁷² операций шифрования.

· Square-атака на 6-раундовую версию Rijndael была незначительно усилена Эли Бихамом (Eli Biham) и Натаном Келлером (Nathan Keller) [4], которые также предложили атаку методом невозможных дифференциалов на 5-раундовую версию алгоритма; для нее требуется 2^29,5 выбранных открытых текстов и 2³¹ операций. Атака с помощью невозможных дифференциалов рядом корейских специалистов была распространена на 6-раундовую версию Rijndael [8]: для данной атаки требуется 2^91,5 выбранных открытых текстов и 2¹²² операций шифрования.

· Впоследствии Square-атака была расширена на 7 раундов алгоритма Rijndael. Однако, данная атака весьма непрактична: для ее реализации требуется 2³² выбранных открытых текстов и от 2¹⁸⁴ до 2²⁰⁸ операций шифрования [19].

· Авторы алгоритма Twofish (финалиста конкурса AES) с участием ряда других специалистов продолжили усиление Square-атаки против алгоритма Rijndael: новая Square-атака позволяла вскрыть 6-раундовый Rindael выполнением 2⁴⁴ операций, а 7-раундовый – от 2¹⁵⁵ до 2¹⁷² операций шифрования при том же требуемом количестве выбранных открытых текстов [14]. Кроме того, новая атака позволяет вскрыть 7- и 8-раундовые (последнюю – только при использовании 256-битного ключа) версии Rijndael при наличии от 2¹¹⁹ до 2¹²⁸ выбранных открытых текстов выполнением, соответственно, 2¹²⁰ или 2²⁰⁴ операций.

· Та же команда криптологов предложила атаку на связанных ключах на 9-раундовую версию Rijndael с 256-ключом, которой необходимо 2⁷⁷ выбранных открытых текстов, зашифрованных на 256 связанных ключах, и 2²²⁴ операций шифрования.

С учетом того, что в алгоритме Rijndael выполняется, как минимум, 10 раундов, запас криптостойкости алгоритма экспертами был признан адекватным [24]. С этим, однако, согласны далеко не все специалисты. В частности, в материалах [2, 18, 27, 29] достаточным запасом криптостойкости считается двукратное увеличение количества раундов алгоритма по сравнению с максимально атакуемым (однако, стоит отметить, что далеко не все атаки на Rijndael с уменьшенным количеством раундов являются осуществимыми на практике [31]). В [2] достаточно убедительно утверждается, что алгоритм, выбранный в качестве стандарта AES, должен оставаться криптографически стойким до 2100 года. Ясно, что за почти сто лет будет сделано огромное количество попыток вскрытия AES («AES будет наиболее привлекательной мишенью для лучших криптоаналитиков мира» [29]), некоторые из которых приведут к увеличению количества вскрываемых раундов. Судя по последнему десятилетию, появятся и принципиально новые виды криптоаналитических атак. Поэтому, считая формально, согласно [2] и [27], Rijndael должен выполнять, как минимум, 18 раундов.

Авторы [27] утверждают, что в алгоритме Rijndael сделан чрезмерный акцент на быстродействие в ущерб криптостойкости, и рекомендуют даже 24 раунда, а не 18. Ясно, что в этом случае Rijndael по быстродействию будет заметно проигрывать другим алгоритмам-финалистам конкурса AES. Они же считают, что успешные атаки на алгоритм Rijndael происходят именно благодаря его чересчур простой структуре. Стоит сказать, что документ [27] написан авторами «конкурирующего» с Rijndael алгоритма Twofish; в нем настолько убедительно доказывается преимущество Twofish над остальными финалистами конкурса (аналогичные доказательства приведены и в работе [29]), что после его прочтения выбор Rijndael (а не Twofish) в качестве стандарта AES начинает удивлять.

В рамках исследований в течение первого раунда конкурса AES было также отмечено [25], что Rijndael имеет ряд потенциальных уязвимостей при реализации данного алгоритма в смарт-картах:

· Rijndael может быть подвержен атаке по потребляемой мощности, нацеленной на его процедуру расширения ключа [5], что, однако, не доказано авторами [5] Эли Бихамом и Эди Шамиром (Adi Shamir).

· Весьма интересное исследование [7] на данную тему было проведено специалистами исследовательского центра компании IBM. Они выполнили реализацию алгоритма Twofish для типичной смарт-карты с CMOS-архитектурой и проанализировали возможность атаки на данный алгоритм с помощью дифференциального анализа потребляемой мощности (DPA – Differential Power Analysis). Оказалось, что атаке подвержена процедура входного отбеливания алгоритма Twofish, в результате чего можно вычислить ключ шифрования данного алгоритма. Атака была (теоретически) распространена на остальные алгоритмы-участники конкурса AES. Аналогично алгоритму Twofish, с помощью DPA атакуется предварительное наложение материала ключа, выполняемое в алгоритме Rijndael, после чего вычисляется ключ шифрования целиком. Авторы [7] утверждают, что среди алгоритмов-финалистов конкурса AES несколько менее данной атаке подвержены MARS и RC6 по сравнению с Twofish, Rijndael и Serpent.

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

Среди других исследований можно отметить работу [23], в которой утверждается, что алгоритм Rijndael не обеспечивает достаточное рассеивание (распространение влияния одного бита открытого текста на несколько бит шифртекста) данных (это указано и в [29], где предложены конкретные меры усиления алгоритма), однако, конкретных атак в [23] предложено не было. Дискуссия между авторами [23] и авторами Rijndael продолжилась [12, 22], однако, данная потенциальная проблема также не повлияла на выбор алгоритма-победителя.

Исследования после конкурса AES

Как и предполагали эксперты, после принятия алгоритма Rijndael в качестве стандарта AES попытки вскрытия данного алгоритма существенно усилились.

Можно сказать, что криптоанализ алгоритма AES стал развиваться, в основном, в следующих четырех направлениях:

Во-первых, попытки усиления «классических» атак или применения других известных атак к данному алгоритму. Например, работа [6] описывает атаку методом бумеранга на 6-раундовую версию алгоритма со 128-битным ключом, для выполнения которой требуется 2³⁹ выбранных открытых текстов, 2⁷¹ шифртекстов с адаптивным выбором и 2⁷¹ операций шифрования.

Во-вторых, применение различных методов криптоанализа на связанных ключах, в частности:

· В работе [33] предложено несколько вариантов атак на связанных ключах на 7- и 8-раундовый AES-192 с использованием невозможных дифференциалов.

· Комбинация метода бумеранга и связанных ключей предложена в работе [3]: 9-раундовый AES-192 атакуется при наличии 2⁷⁹ выбранных открытых текстов, каждый из которых шифруется на 256 связанных ключах, выполнением 2¹²⁵ операций шифрования; для атаки на 10-раундовый AES-256 требуется 2^114,9 выбранных открытых текстов (включая зашифрование на 256 связанных ключах) и 2^171,8 операций. Данная атака использует слабость процедуры расширения ключа, состоящую в ее недостаточной нелинейности.

· Эта атака была усилена в работе [17], в которой, в частности, предлагается атака на 10-раундовый алгоритм AES-192, для которой требуется 2¹²⁵ выбранных открытых текстов (на 256 связанных ключах) и 2^146,7 операций.

Несмотря на то, что предложенные атаки на связанных ключах являются весьма непрактичными, настораживает тот факт, что атаке подвержены уже 10 из 12 раундов алгоритма AES-192 (и это после всего 5 лет после принятия стандарта AES!) – возникает опасение, что эксперты (указывающие на недостаточность раундов в алгоритме Rijndael) были правы и полнораундовый алгоритм AES будет вскрыт существенно раньше, чем предполагали эксперты института NIST.

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

· В работе [16] найдены линейные соотношения в таблице замен Rijndael (т.е. в единственном нелинейном элементе алгоритма). Однако, как и в других аналогичных работах, каких-либо практических возможностей использования данного свойства не предложено.

· Как показано в работе [15], зашифрование с помощью Rijndael можно выразить относительно (особенно по сравнению с другими «серьезными» алгоритмами шифрования) простой формулой. Авторы не нашли практического применения данной формулы, но предположили, что она будет использована в реальных атаках в течение ближайших примерно 20 лет.

· В работе [21] показано, что вскрытие алгоритма AES эквивалентно решению системы квадратичных уравнений в конечном поле GF(2⁸).

Попытки использования алгебраических свойств алгоритма для его вскрытия были названы «алгебраическими атаками» [9]. Стоит отметить, что были и работы с попытками доказательства того факта, что простая структура алгоритма AES не ухудшает его криптостойкости, например, [30].

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

· Много работ содержат примеры успешного вскрытия различных реализаций полнораундового алгоритма AES с помощью атак по времени исполнения (например, [1]), потребляемой мощности (например, [20]) и атак на основе сбоев (например, [26]). Автор [1] (данная работа описывает успешное вскрытие сервера OpenSLL, использующего для шифрования алгоритм AES), в частности, считает, что эксперты NIST при выборе Rijndael в качестве AES допустили весьма серьезную ошибку, посчитав, что время выбора значения из таблицы замен является константной величиной в конкретной реализации; вывод автора таков: выбор Rijndael, скорее всего, был ошибочным.

· Не меньше исследований (например, [10, 28]) посвящено безопасным (т.е. защищенным от утечек данных по побочным каналам) программным или аппаратным реализациям AES.

Весьма большой список работ, посвященных side-channel-атакам на AES и методам защиты от них, можно найти, например, на ресурсе [32], посвященном криптоанализу AES.

Заключение

Итак, на май 2007 г., по прошествии всего 6 лет после принятия алгоритма Rijndael в качестве стандарта AES, криптоаналитики весьма серьезно продвинулись во вскрытии данного алгоритма:

· Предложена теоретическая атака уже на 10 раундов (из 12) алгоритма AES-192.

· Существует множество примеров вскрытия реализаций алгоритма AES с помощью side-channel-атак.

Не правда ли, все это производит впечатление, что эксперты NIST могли ошибиться в выборе алгоритма-победителя конкурса AES?

1. Bernstein D.J. Cache-timing attacks on AES. // http://cr.yp.to – 2005.04.14 – The University of Illinois at Chicago.

2. Biham E. Comment on Selecting the Cipher for the AES Second Round. // http://csrc.nist.gov – Technion – Israel Institute of Technology, Haifa, Israel.

3. Biham E., Dunkelman O., Keller N. Related-Key Boomerang and Rectangle Attacks. // http://vipe.technion.ac.il – 2005.

4. Biham E., Keller N. Cryptanalysis of Reduced Variants of Rijndael. // http://csrc.nist.gov – Technion – Israel Institute of Technology, Haifa, Israel.

5. Biham E., Shamir A. Power Analysis of the Key Scheduling of the AES Candidates. // http://csrc.nist.gov.

6. Biryukov A., The Boomerang Attack on 5 and 6-round Reduced AES. // http://www.cosic.esat.kuleuven.be – 2004 – Katholieke Universiteit Leuven, Heverlee, Belgium.

7. Chari S., Jutla C., Rao J.R., Rohatgi P. A Cautionary Note Regarding Evaluation of AES Candidates on Smart-Cards. // http://csrc.nist.gov – I.B.M. J.T.Watson Research Center, Yorktown Heights, USA.

8. Cheon J.H., Kim M., Kim K., Lee J.-Y., Kang S. Improved Impossible Differential Cryptanalysis of Rijndael and Crypton. // http://citeseer.ist.psu.edu – 2001.

9. Courtois N.T. Is AES a Secure Cipher. // http://www.cryptosystem.net.

10. Courtois N.T., Goubin L. An Algebraic Masking Method to Protect AES Against Power Attacks. // http://eprint.iacr.org.

11. Daemen J., Knudsen L., Rijmen V. The Block Cipher Square. // http://www.esat.kuleuven.ac.be.

12. Daemen J., Rijmen V. Answer to “new observations on Rijndael”. // http://www.esat.kuleuven.ac.be – August 11, 2000.

13. Daemen J., Rijmen V. AES Proposal: Rijndael. // http://csrc.nist.gov – Document version 2 – 03/09/99.

14. Ferguson N., Kelsey J., Lucks S., Schneier B., Stay M., Wagner D., Whiting D. Improved Cryptanalysis of Rijndael. // http://www.schneier.com.

15. Ferguson N., Schroeppel R., Whiting D. A simple algebraic representation of Rijndael. // http://citeseer.ist.psu.edu – Draft 2001/05/16.

16. Fuller J., Millan W. On Linear Redundancy in the AES S-box. // http://eprint.iacr.org – 2002 – Queensland University of Technology, Brisbane, Australia.

17. Kim J. Combined Differential, Linear and Related-Key Attacks on Block Ciphers and MAC Algorithms. // http://www.cosic.esat.kuleuven.be – November 2006 – Katholieke Universiteit Leuven.

18. Knudsen L.R. Some thoughts on the AES process. // http://csrc.nist.gov – April 15, 1999.

19. Lucks S. Attacking Seven Rounds of Rijndael under 192-bit and 256-bit Keys. // http://citeseer.ist.psu.edu – University of Mannheim, Germany.

20. Mangard S., Pramstaller N., Oswald E. Successfully Attacking Masked AES Hardware Implementations. // http://www.iaik.tu-graz.ac.at – 2005 – Graz University of Technology, Austria.

21. Murphy S., Robshaw M.J.B. Essential Algebraic Structure Within the AES. // http://citeseer.ist.psu.edu – University of London, Egham, U.K.

22. Murphy S., Robshaw M. Further Comments on the Structure of Rijndael. // http://www.isg.rhul.ac.uk – University of London, Egham, U.K. – 17 August, 2000.

23. Murphy S., Robshaw M. New Observations on Rijndael. Preliminary Draft. // http://www.isg.rhul.ac.uk – University of London, Egham, U.K. – 7 August, 2000.

24. 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.

25. Nechvatal J., Barker E., Dodson D., Dworkin M., Foti J., Roback E. Status report on the first round of the development of the advanced encryption standard. // http://csrc.nist.gov – National Institute of Standards and Technology.

26. Peacham D., Thomas B. A DFA attack against the AES key schedule. // http://www.siventure.com – 26 October 2006 – SiVenture.

27. Schneier B., Kelsey J., Whiting D., Wagner D., Hall C., Ferguson N., Kohno T., Stay M. The Twofish Team’s Final Comments on AES Selection. // http://csrc.nist.gov – May 15, 2000.

28. Schramm K., Paar C. Higher Order Masking of the AES. // http://www.crypto.ruhr-uni-bochum.de – 2006 – Ruhr University Bochum, Germany.

29. Schroeppel R. AES Comments. // Public Comments Regarding The Advanced Encryption Standard (AES) Development Effort. Round 2 Comments – http://csrc.nist.gov – University of Arizona – May 15, 2000.

30. Song B., Seberry J. Further Observations on the Structure of the AES Algorithm. // http://citeseer.ist.psu.edu – University of Wollongong, Australia.

31. Tang J. A Survey of Cryptanalysis of Rijndael. // http://www.cs.auckland.ac.nz – The University of Auckland.

32. The AES Lounge. // http://iaik.tu-graz.ac.at.

33. Wentao Z., Wenling W., Lei Z., Dengguo F. Improved Related-Key Impossible Differential Attacks on Reduced-Round AES-192. // http://www.lois.cn – 2006 – Chinese Academy of Science, Beijing, China.

Об авторе:

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

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

или по E-mail develop@ancud.ru

http://www.panasenko.ru