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

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

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

· Square-атака на 6-раундовую версию Rijndael была незначительно усилена Эли Бихамом (EliBiham) и Натаном Келлером (NathanKeller) [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] Эли Бихамом и Эди Шамиром (AdiShamir).

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

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

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