Криптоанализ ГОСТ 28147-89
Криптоалгоритм ГОСТ 28147-89 был разработан на начальном этапе развития блочного шифрования спецслужбами СССР. Алгоритм не был запатентован, поэтому может быть бесплатно использован в коммерческих приложенияхJ. Kelsey, B. Schneier, D. Wagner Key Schedule Cryptanalysis of IDEA,G-DES, GOST, SAFER, and Triple-DES. — Advances in Cryptology — CRYPTO’96, volume 1109 of Lecture Notes of Computer Science, Springer-Verlag. — 1996. — pp. 237—251. 300, 303
Чтобы передать данные, их разбивают на блоки. Каждый состоит из 64 бит. Чтобы их зашифровать, необходимо использовать ключ большего размера. Используется ключ размером 256 бит. Для шифрования реализуется классическая сеть Фейстеля, состоящая из 32 раундов с двумя ветвями.
Раунды получаются из разбиения 256 бит ключа на 8 групп по 32 бита. Части ключа применяются в прямом порядке 4 раза. Для дешифрования используется тот же код, но в обратном порядке. Данный процесс называется схемой развертывания ключа.
Чтобы зашифровать текст, необходимо разбить его на левую и правую половину. На -м этапе используется часть ключа:
Функция состоит в следующем : и складываются по модулю Результат делится на 8 частей по 4 бита каждый. Затем каждая часть поступает в свой -блок (перестановка чисел от 0 до 15). Выходная последовательность объединяется в 32-битное слово и сдвигается на 11 битов влево. Результат с помощью XOR объединяется с левой половиной, получается новая правая половина. Так повторяется 32 раза. В этом заключается криптоалгоритм ГОСТ 28147-89.
Краткий обзор криптоатак
Название работыКоличество раундов ГОСТКоличество текста (ОТ — открытого, СПТ — специально подобранного)Вычислительная сложностьАтака скольжения на модифицированный ГОСТAlex Biryukov and David Wagner Advanced Slide Attacks. — Applied Mathematics Department Technion — Israel Institute of Technology Haifa. — 2000 20()(ОТ) Метод рационального продолженияРостовцев А. Г., Маховенко Е. Б., Филиппов А.С, Чечулин А.А О стойкости ГОСТ 28147-89. — СПбГПУ. — 2001 32 несколько десятков(СПТ) 1R атака на связанных ключахKo Y., Hong S., Lee W., Lee S., Kang J S Related Key Differential Attacks on 27 Rounds of XTEA and Full-Round GOST. — Springer, Heidelberg. — 2004. — pp. 299—316 32 (СПТ) Улучшенная атака скольженияBiham E., Dunkelman O., Keller N. Improved slide attacks. — FSE-2007, Lect. Notes Comput. Sci. — 2007. — 153—166 24 (ОТ) Атаки О. КараKara O. Reflection cryptanalysis of some ciphers. — INDOCRYPT-2008, Lect. Notes Comput. Sci., 5365. — 2008. — 294—307 30 (СПТ) Атака методом бумерангаRudskoy V. On zero rractical significance of key recovery attack on full GOST block cipher with zero time and memory. — 2010 32 пар открытого/зашифрованного текста Атаки ИсобеIsobe T. A single-key attack on the full GOST block cipher. — FSE-2011, Lect. Notes Comput. Sci., 6733, 2011. — 290—305 32 (ОТ) Атаки Динура-Данкельмана-ШамираDinur I., O. Dunkelman, A. Shamir Improved Attacks on Full GOST. — FSE 2012, LNCS 7549. — pp. 9-28 32 (ОТ) Атаки Динура-Данкельмана-Шамира 8 (ОТ) Атака на шифросистему с 12 связанными ключамPudovkina M., Khoruzhenko G. Related-key attacks on the full GOST block cipher with two or four related keys. — BulCrypt-2012, Sofia. — 2012 . — 107—127 8 от до (СПТ) Алгебраический анализBabenko L.K., Maro E.A. Algebraic Cryptanalysis of GOST Encryption Algorithm. — SECTION IV. METHODS AND MEANS OF CRYPTOGRAPHY AND STEGANOGRAPHY. — 2014 32 (ОТ)
Атаки на схему развертывания ключа
4R атака на 24-раундовый ГОСТ
В работе применяется атака на связанных ключах. Атакующий использует парадокс дней рождений, чтобы найти пары для скольжения такие, что . Шифротексты также сохранят зависимость: . Такая атака может быть проведена только при условии, что могут быть взломаны с помощью двух известных пар текста, что случается не всегда.
Используется тройка однораундовых характеристик , не длиннее 4 бит, где каждая характеристика проходит через один активный блок. В входной отличительный признак находится в старших битах. В в младших битах выходной отличительный признак отсутствует, получено с помощью функции сети Фейстеля из . Далее выходной отличительный признак сдвигается раундовой функцией на 11 бит. Три ненулевых бита из попадают на вход активного -блока второго раунда, получаем . Теперь входной отличительный признак отсутствует в трех старших битах, и мы можем получить из . То есть за счет сдвига отличительные признаки остались на тех же местах, что и были в первом раунде.
Авторы атаки подсчитали вероятность нахождения таких зависимостей для 12-раундов стандартного набора -блоков. Она равна , что недостаточно для взлома криптосистемы. В случае вероятностной генерации блоков, вероятность появления таких зависимостей варьировалась от до .
Атака скольжения на модифицированный ГОСТ
В работе была произведена атака скольжения, не зависящая от числа раундов, на модифицированный ГОСТ 28147-89. Вместо сложения с ключом использовалась операция исключающего или. С помощью предложенной атаки можно вскрыть только алгоритмы, раунды которых обладают существенным сходством. Имея две пары текстов, связанные между собой лишь одним раундом шифрования, криптоаналитик способен получить значение ключа для любого раунда.
Авторы доказали необходимость введения с 24 раунда обратного хода ключа для ГОСТ 28147-89, чтобы криптоалгоритм противостоял атакам скольжения. В случае, если вместо сложения с ключом используется операция исключающего или будет найдено порядка слабых ключей.
Для 20-раундового ГОСТ 28147-89() используется следующий ключ K4 K5 K6 K7 K0 K1 K2 K3 K4 K5 K6 K7 K7 K6 K5 K4 K3 K2 K1 K0 K0 K1 K2 K3 K4 K5 K6 K7 K7 K6 K5 K4 K3 K2 K1 K0 K7 K6 K5 K4. Пусть провели 4 раунда ГОСТ 28147-89, тогда используя открытых текстов, авторы ожидали найти две пары для скольжения . Свойство пары: . Каждая пара дала бы две входные/выходные пары для поиска . Как только найдена пара, шифр взломан из-за уязвимости для атаки с известным открытым текстом. Взлом по двум текстам сравним с временем выполнения 4 раундов ГОСТ 28147-89 раза. После нахождения K4 K5 K6 K7 ищутся оставшиеся подключи с помощью поиска фиксированных точек. Предложенная атака, потребовавшая открытых текстов, времени и памяти, работает для любых -блоков, но затраты памяти делают её не реализуемой.
1R атака на связанных ключах Специалисты из Кореи предложили атаку с помощью которой, используя дифференциальный криптоанализ на связанных ключах, можно получить с вероятностью 91,7 % 12 бит секретного ключа. Для атаки требуется выбранных открытых текстов и операций шифрования.
Возможность нахождения дифференциальных характеристик зависит не только от входных-выходных зависимостей, но и от подключей. Чтобы уменьшить данный эффект были выбраны специфические дифференциальные характеристики.
Предлагается атака распознавания ГОСТ 28147-89 от случайной последовательности (вероятность успеха ). Пусть дан открытый текст и ключ и открытый текст и ключ . Сам ключ не известен, но известно соотношение . Для ГОСТ 28147-89 сохранится зависимость и в шифротексте для любого раунда. Для произвольной же последовательности после каждого раунда мы не сможем предсказать зависимости. Так можно отличать ГОСТ 28147-89 от произвольного алгоритма с вероятностью .
Для атаки на 31-раундовый ГОСТ 28147-89 были использованы следующие зависимости у ключей : , шифротексты и . Данная зависимость сохранялась 24 раунда. Для следующих 6 раундов используются вероятностные зависимости между отличительными признаками. С вероятностью можно будет атаковать криптосистему, зная зависимость между двумя ключами. Создатели статьи смогли восстановить 32 бита ключа с 97,9 % успеха.
Был предложен алгоритм атаки на полный ГОСТ 28147-89 с успешным открытием 12 бит ключа. Пусть и с ключами и . Тогда после каждого раунда зависимость исчезнет с вероятностью . Вероятность создания 30 раундовой дифференциальной характеристики равна . Вероятность успешности такой атаки 0,917.
Улучшенная атака скольжения
Были опробованы улучшенные атаки скольжения на 24 раунда ГОСТ 28147-89, основанные на слабостях алгоритма развертывания ключа и раундовой функции. Они существенно уменьшают время, необходимое на атаку. Однако так атаковать можно только 24-раундовый ГОСТ 28147-89 со слабыми ключами и неизвестными -блоками, либо 30-раундовый ГОСТ 28147-89 с известными -блоками.
Авторы вместо поиска пар для скольжения с помощью парадокса дней рождения используют циклическую структуру функции продолжения ключа и круговых функций. Найденные пары могут быть использованы в атаке с известным открытым текстом или, если достаточно пар найдено, — в атаке с избранным открытым текстом. Атака на выполняется только один раз, вне зависимости от свойств .
Атака начинается с открытого текста . Шифрование повторяется пока не будет снова получен . Когда это произошло — мы нашли цикл, кроме того, он не зависит ни от , ни от его длины. Найденные пары для скольжения — это и , где — процедура расширения ключа. Для случайной величины матожидание длины цикла , поэтому авторы и находили пар для скольжения. Учитывая независимость длины циклов друг от друга, после атак вероятность успеха была равна , где — функция Эйлера, : .
Атаки на алгоритм шифрования
Метод рационального продолжения
Ростовцев предложил следующий метод. В основе лежит продолжение кольца (многочленов Жегалкина)на упорядоченное множество рациональных чисел с евклидовым нормированием и на множество целых 2-адических чисел с 2-адическим неевклидовым нормированием. Это позволяет задать метрику для подсчета расстояния между тестируемым ключом и истинным. Криптоанализ построен на поиске локального максимума продолженной целевой функции в предположении, что истинное значение ключа дает увеличение продолженной целевой функции.
Метод состоит из нескольких этапов. На первом этапе для каждого бита ключа составляется статистический «нулевой и единичный портреты шифра» при некоторых приближениях. На втором этапе для неизвестного ключа составляется аналогичный «портрет». Далее решается задача определения, на какой (нулевой или единичный) «портрет» он больше похож. Данный метод позволяет строить статистику на основе нескольких открытых текстов.
В основе лежит предположение: вероятность правильного вскрытия бита ключа превышает 0,5 и не зависит от вида разреженных открытых текстов. В этом случае сложность криптоанализа определяется первыми двумя этапами и практически не превышает . Тогда ключ ГОСТ 28147-89 может быть вскрыт с малой сложностью на основе нескольких десятков подобранных открытых текстов.
Атаки О. Кара
Были изданы две работы O. Кара об атаке на ГОСТ 28147-89, обладающей особыми свойствами ключей, и на 30-раундовый ГОСТ 28147-89. Используется предположение биективности -блоков, зависимости между шифрованием и расшифрованием данных.
Запишем алгоритм ГОСТ 28147-89 в следующем виде: , где — инвертированная , — операция замены. Пусть существует фиксированная точка такая, что и . Таких ключей штук. Тогда — фиксированная точка и для функции . Атака будет следующая: зашифруем текста, чьи левые и правые части одинаковые. Соберем все фиксированные точки в массив . Если массив пуст, то атаку провести нельзя. Иначе решим выражение для всех из для . Таких решений найдется штук. Для каждого предполагаем и затем определяем и из системы, учитывающей биективность и . Ищем обратные функции от и , определяем входные данные, а затем и и .
Вторая предложенная атака — это атака с открытым ключом на 30-раундовый ГОСТ 28147-89. Функция шифрования выглядит следующим образом . У имеется фиксированных точек, тогда по доказанной О. Кара лемме у тоже . Пусть — одна из фиксированных точек, — соответствующий открытый текст. Имеем . Предположив значения , мы получим двух раундовую сеть Фейстеля с ключами и входной/выходной парой . Тогда восстановим и путём обращения круговой функции. Искомый ключ будет одним из вариантов.
Атака методом бумеранга