Algebraic cryptanalysis of one-round S-AES.pdf Advanced Encryption Standard (AES) - симметричный алгоритм блочного шифро-вания, принятый в США в качестве стандарта шифрования. AES проектировался какалгоритм, который может эффективно противостоять различным методам крипто-анализа. Но в 2002 г. Николя Куртуа и Йозеф Пипджик высказали предположение овозможности алгебраической атаки на шифры с подобной AES структурой [1]. Алгеб-раическая атака нацелена на анализ уязвимости в математических частях алгоритмаи использование его внутренних алгебраических структур. Однако об эффективноститакой атаки мало что известно.В работе исследуется применимость алгебраической атаки к упрощенному вариан-ту S-AES, разработанному в [2]. Длина шифруемого блока и ключа равна 16 битам.Число раундов шифрования равно двум. Для анализа используются соотношения, по-добные тем, которые получены в [1] для AES. Точнее, для S-блоков шифра выполненоVx = 0 1 = x * y,Vx x = y * x2,z = Ay ф b,где x, z - входной и выходной векторы S-блока длины 4; y - обратный вектор к xв поле GF(24) с порождающим многочленом А4 + А + 1; A - некоторая фиксированнаяматрица и b - фиксированный вектор. С помощью данных уравнений строится систе-ма относительно битов открытого текста p, шифртекста c и ключа шифрования k,полностью описывающая процесс шифрования однораундового S-AES:15 15 15 15 15 15Е aijmPiCj ф Е cj ф ai j m k i k j ф Е Am,pi ф Е Atmki ф 7то - °i,j=0 i,j=0 i,j=0 i,j=0 i=0 i=0где m = 0,... , 31; о ^ в г т , Ym G {0,1} определяются только структурой шифра и независят от выбранных значений p, c, k.По сравнению с ранее предложенными в [1, 3, 4] атаками, наш подход отличаетсяиспользованием двух различных пар открытых текстов/шифртекстов (p,c) и (p',c/)при одном и том же ключе k, что позволяет получить систему из небольшого числауравнений, а именно15 15 15 15Е 0 Pi)(Cj 0 cj ) 0 Е 0 pi )kj 0 E « j m ^ 0 cj ) 0 E Am (Pi 0 pi) = 0, (1)ij=0 i,j=0 i,j=0 i=0m = 0,... , 31, которая является линейной относительно неизвестных битов ключа.Система содержит 32 уравнения с 16 неизвестными.Будем говорить, что вектор длины 16 обладает дефектом, если при разбиении егона четыре подвектора длины 4 хотя бы один из них является нулевым.Теорема 1. Пусть ключ k случаен и фиксирован. Тогда верны предложения:(i) При случайном равновероятном выборе открытых текстов p, p/ система урав-нений (1) непротиворечива с вероятностью 0,6074.(ii) При фиксированном p/, таком, что p/ 0 k не имеет дефекта, и случайном равно-вероятном выборе открытого текста p система уравнений (1) непротиворечивас вероятностью 0,7725.Однако непротиворечивость системы еще не означает существования единственно-го решения. Использование столь небольшого количества уравнений позволяет в кон-кретных случаях проанализировать фактическую эффективность алгебраической ата-ки. Например, для ключа k = 1010111111001000 и p/ = 0110010101010101 найдено44 747 (68,28%) открытых текстов p, таких, что система (1) имеет единственное реше-ние - ключ k.Ранее анализ упрощенного варианта AES проводился в [3, 4]. В [3] для анализаслегка измененного S-AES используются соотношение (15) и соотношения, получен-ные с помощью таблицы истинности S-блоков. В общей сложности один раунд шиф-ра описывается системой из 150 уравнений с 24 переменными. После преобразованиясистемы к линейному виду она содержит 3600 уравнений с 2324 неизвестными. Дляпроанализированной в [3] пары открытого текста и шифртекста алгоритм выдаёт вкачестве решения 4 ключа, любой из которых является подходящим для данной пары.В [4] проведён анализ шифра, аналогичного S-AES, с S-блоками по 3 бита. Ана-лиз заключается в переборе всех 4194 304 возможных квадратичных уравнений от-носительно переменных S-блока, выборе тех из них, которые выполняются при всехзначениях входных битов S-блока и битов выхода. Найдена система из 16 383 линей-но зависимых уравнений. Из неё выбрана некоторая более удобная для анализа под-система. После преобразования подсистемы к линейному виду получена система из392 уравнений с 164 неизвестными. В [4] приводится её решение.Система относительно двухраундового S-AES содержит 96 квадратичных уравне-ний с 32 неизвестными. Использование двух различных пар открытых текстов/шифр-текстов сокращает количество мономов с 232 до 160, что позволяет более эффективноприменять методы, разработанные для подобных систем.

Скачать электронную версию публикации