Криптоанализ ГОСТ 28147-89

Криптоанализ ГОСТ 28147-89

Криптоалгоритм ГОСТ 28147-89 был разработан на начальном этапе развития блочного шифрования спецслужбами СССР. Алгоритм не был запатентован, поэтому может быть бесплатно использован в коммерческих приложениях

Чтобы передать данные, их разбивают на блоки. Каждый состоит из 64 бит. Чтобы их зашифровать, необходимо использовать ключ большего размера. Используется ключ размером 256 бит. Для шифрования реализуется классическая сеть Фейстеля, состоящая из 32 раундов с двумя ветвями.

Раунды получаются из разбиения 256 бит ключа на 8 групп ${K}_{i}$ по 32 бита. Части ключа применяются в прямом порядке 4 раза. Для дешифрования используется тот же код, но в обратном порядке. Данный процесс называется схемой развертывания ключа.

Чтобы зашифровать текст, необходимо разбить его на левую $L$ и правую $R$ половину. На $i$-м этапе используется ${K}_{i}$ часть ключа:

${L}_{i}={R}_{i-1}$

${R}_{i}={L}_{i-1}\oplus f(R_{i-1},K_{i})$

Функция $f$ состоит в следующем : $R_{i-1}$ и $K_{i}$ складываются по модулю $2^{32}.$ Результат делится на 8 частей по 4 бита каждый. Затем каждая часть поступает в свой $S$-блок (перестановка чисел от 0 до 15). Выходная последовательность объединяется в 32-битное слово и сдвигается на 11 битов влево. Результат с помощью XOR объединяется с левой половиной, получается новая правая половина. Так повторяется 32 раза. В этом заключается криптоалгоритм ГОСТ 28147-89.

Краткий обзор криптоатак

Название работы	Количество раундов ГОСТ	Количество текста (ОТ — открытого, СПТ — специально подобранного)	Вычислительная сложность
Атака скольжения на модифицированный ГОСТ	20($\oplus$)	$2^{33}$(ОТ)	$2^{70}$
Метод рационального продолжения	32	несколько десятков(СПТ)	$10^{10}$
1R атака на связанных ключах	32	$2^{35}$(СПТ)	$2^{36}$
Улучшенная атака скольжения	24	$2^{64}$(ОТ)	$2^{63}$
Атаки О. Кара	30	$2^{32}$(СПТ)	$2^{224}$
Атака методом бумеранга	32	$2^{10}$ пар открытого/зашифрованного текста	$2^{26}$
Атаки Исобе	32	$2^{32}$(ОТ)	$2^{224}$
Атаки Динура-Данкельмана-Шамира	32	$2^{64}$(ОТ)	$2^{192}$
Атаки Динура-Данкельмана-Шамира	8	$2^{32}$(ОТ)	$2^{224}$
Атака на шифросистему с 12 связанными ключам	8	от $2^{50}$ до $2^{106}$(СПТ)	$2^{60}$
Алгебраический анализ	32	$2^{38}$(ОТ)	$2^{32}$

Атаки на схему развертывания ключа

4R атака на 24-раундовый ГОСТ

В работе применяется атака на связанных ключах. Атакующий использует парадокс дней рождений, чтобы найти пары для скольжения $(P_{1},P_{2})$ такие, что $P_{2}=f_{k}(P_{1})$. Шифротексты $(C_{1},C_{2})$ также сохранят зависимость: $C_{2}=f_{k}(C_{1})$. Такая атака может быть проведена только при условии, что $f_{k}$ могут быть взломаны с помощью двух известных пар текста, что случается не всегда.

Используется тройка однораундовых характеристик $A\rightarrow B\rightarrow C\rightarrow A$, не длиннее 4 бит, где каждая характеристика проходит через один активный $S$ блок. В $A$ входной отличительный признак находится в старших битах. В $B$ в младших битах выходной отличительный признак отсутствует, $B$ получено с помощью функции сети Фейстеля из $A$. Далее выходной отличительный признак сдвигается раундовой функцией на 11 бит. Три ненулевых бита из $B$ попадают на вход активного $S$-блока второго раунда, получаем $C$. Теперь входной отличительный признак отсутствует в трех старших битах, и мы можем получить из $C$ $A$. То есть за счет сдвига отличительные признаки остались на тех же местах, что и были в первом раунде.

Авторы атаки подсчитали вероятность нахождения таких зависимостей для 12-раундов стандартного набора $S$-блоков. Она равна $2^{-68}$, что недостаточно для взлома криптосистемы. В случае вероятностной генерации блоков, вероятность появления таких зависимостей варьировалась от $2^{-43}$ до $2^{-80}$.

Атака скольжения на модифицированный ГОСТ

В работе была произведена атака скольжения, не зависящая от числа раундов, на модифицированный ГОСТ 28147-89. Вместо сложения с ключом использовалась операция исключающего или. С помощью предложенной атаки можно вскрыть только алгоритмы, раунды которых обладают существенным сходством. Имея две пары текстов, связанные между собой лишь одним раундом шифрования, криптоаналитик способен получить значение ключа для любого раунда.

Авторы доказали необходимость введения с 24 раунда обратного хода ключа для ГОСТ 28147-89, чтобы криптоалгоритм противостоял атакам скольжения. В случае, если вместо сложения с ключом используется операция исключающего или будет найдено порядка $2^{128}$ слабых ключей.

Для 20-раундового ГОСТ 28147-89($\oplus$) используется следующий ключ 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, тогда используя $2^{33}$ открытых текстов, авторы ожидали найти две пары для скольжения $(P',C')$. Свойство пары: $P'=f(P),C'=f(C)$. Каждая пара дала бы две входные/выходные пары для поиска $f$. Как только найдена пара, шифр взломан из-за уязвимости для атаки с известным открытым текстом. Взлом $f$ по двум текстам сравним с временем выполнения 4 раундов ГОСТ 28147-89 $2^{9}$ раза. После нахождения K4 K5 K6 K7 ищутся оставшиеся подключи с помощью поиска фиксированных точек. Предложенная атака, потребовавшая $2^{33}$ открытых текстов, $2^{70}$ времени и $2^{65}$ памяти, работает для любых $S$-блоков, но затраты памяти делают её не реализуемой.

1R атака на связанных ключах

Специалисты из Кореи предложили атаку с помощью которой, используя дифференциальный криптоанализ на связанных ключах, можно получить с вероятностью 91,7 % 12 бит секретного ключа. Для атаки требуется $2^{35}$ выбранных открытых текстов и $2^{36}$ операций шифрования.

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

Предлагается атака распознавания ГОСТ 28147-89 от случайной последовательности (вероятность успеха $1-2^{-64}$). Пусть дан открытый текст $P$ и ключ $K=(K1...K8)$ и открытый текст $P'$ и ключ $K'=(K1\oplus e32...K8\oplus e32)$. Сам ключ не известен, но известно соотношение $K'\oplus K=(e,...,e)$. Для ГОСТ 28147-89 сохранится зависимость и в шифротексте $C\oplus C'=(e,...,e)$ для любого раунда. Для произвольной же последовательности после каждого раунда мы не сможем предсказать зависимости. Так можно отличать ГОСТ 28147-89 от произвольного алгоритма с вероятностью $1-2^{-64}$.

Для атаки на 31-раундовый ГОСТ 28147-89 были использованы следующие зависимости у ключей : $K=(K1...K8),K'=(K1\oplus e...K7\oplus e32,K8)$, шифротексты $P=(Pl,Pr)$ и $P'=(Pl,Pr\oplus e32)$. Данная зависимость сохранялась 24 раунда. Для следующих 6 раундов используются вероятностные зависимости между отличительными признаками. С вероятностью $2^{-23,33}$ можно будет атаковать криптосистему, зная зависимость между двумя ключами. Создатели статьи смогли восстановить 32 бита ключа с 97,9 % успеха.

Был предложен алгоритм атаки на полный ГОСТ 28147-89 с успешным открытием 12 бит ключа. Пусть $P=(Pl,Pr)$ и $P'=(Pl\oplus e32,Pr\oplus e32)$ с ключами $K=(K1,...,K8)$ и $K'=(K1\oplus e32,K2\oplus e32,...,K8\oplus e32)$. Тогда после каждого раунда зависимость исчезнет с вероятностью $2^{-1}$. Вероятность создания 30 раундовой дифференциальной характеристики равна $2^{-30}$. Вероятность успешности такой атаки 0,917.

Улучшенная атака скольжения

Были опробованы улучшенные атаки скольжения на 24 раунда ГОСТ 28147-89, основанные на слабостях алгоритма развертывания ключа и раундовой функции. Они существенно уменьшают время, необходимое на атаку. Однако так атаковать можно только 24-раундовый ГОСТ 28147-89 со слабыми ключами и неизвестными $S$-блоками, либо 30-раундовый ГОСТ 28147-89 с известными $S$-блоками.

Авторы вместо поиска пар для скольжения с помощью парадокса дней рождения используют циклическую структуру функции продолжения ключа и круговых функций. Найденные пары могут быть использованы в атаке с известным открытым текстом или, если достаточно пар найдено, — в атаке с избранным открытым текстом. Атака на $f_{k}$ выполняется только один раз, вне зависимости от свойств $f_{k}$.

Атака начинается с открытого текста $P$. Шифрование повторяется пока не будет снова получен $P$. Когда это произошло — мы нашли цикл, кроме того, он не зависит ни от $f_{k}$, ни от его длины. Найденные пары для скольжения — это $(P,E_{k}^{d}(P))$ и $(E_{k}^{t}(P),E_{k}^{d+t}(P))$, где $E_{k}$ — процедура расширения ключа. Для случайной величины $x$ матожидание длины цикла $E[CycleLength(x)]=2^{n-1}$, поэтому авторы и находили $2^{n-1}$ пар для скольжения. Учитывая независимость длины циклов друг от друга, после $t$ атак вероятность успеха была равна $1-{(1-\phi (l)/l)}^{t}$, где $\phi (l)$ — функция Эйлера, $l$ : $E_{k}=f_{k}^{l}$.

Атаки на алгоритм шифрования

Метод рационального продолжения

Ростовцев предложил следующий метод. В основе лежит продолжение кольца $G_{n}$(многочленов Жегалкина)на упорядоченное множество $Q$ рациональных чисел с евклидовым нормированием и на множество $Z_{2}$ целых 2-адических чисел с 2-адическим неевклидовым нормированием. Это позволяет задать метрику для подсчета расстояния между тестируемым ключом и истинным. Криптоанализ построен на поиске локального максимума продолженной целевой функции в предположении, что истинное значение ключа дает увеличение продолженной целевой функции.

Метод состоит из нескольких этапов. На первом этапе для каждого бита ключа составляется статистический «нулевой и единичный портреты шифра» при некоторых приближениях. На втором этапе для неизвестного ключа составляется аналогичный «портрет». Далее решается задача определения, на какой (нулевой или единичный) «портрет» он больше похож. Данный метод позволяет строить статистику на основе нескольких открытых текстов.

В основе лежит предположение: вероятность правильного вскрытия бита ключа превышает 0,5 и не зависит от вида разреженных открытых текстов. В этом случае сложность криптоанализа определяется первыми двумя этапами и практически не превышает $10^{10}$. Тогда ключ ГОСТ 28147-89 может быть вскрыт с малой сложностью на основе нескольких десятков подобранных открытых текстов.

Атаки О. Кара

Были изданы две работы O. Кара об атаке на ГОСТ 28147-89, обладающей особыми свойствами ключей, и на 30-раундовый ГОСТ 28147-89. Используется предположение биективности $S$-блоков, зависимости между шифрованием и расшифрованием данных.

Запишем алгоритм ГОСТ 28147-89 в следующем виде: $E_{k}=f_{k}[8,1]\circ S\circ f_{k}^{3}[1,8]$, где $f_{k}[8,1]$ — инвертированная $f_{k}[1,8]$, $S$ — операция замены. Пусть существует фиксированная точка $x$ такая, что $S(x)=x$ и $f_{k}[1,8](x)=x$. Таких ключей $2^{224}$ штук. Тогда $x$ — фиксированная точка и для функции $E_{k}$. Атака будет следующая: зашифруем $2^{32}$ текста, чьи левые и правые части одинаковые. Соберем все фиксированные точки в массив $U$. Если массив пуст, то атаку провести нельзя. Иначе решим выражение для всех $x$ из $U$ $f_{k}[1,8](x)=x$ для $K$. Таких решений найдется $2^{192}$ штук. Для каждого предполагаем $k0,k1,...,k5$ и затем определяем $k6$ и $k7$ из системы, учитывающей биективность $f_{k6}$ и $f_{k7}$. Ищем обратные функции от $f_{k6}$ и $f_{k7}$, определяем входные данные, а затем и $k6$ и $k7$.

Вторая предложенная атака — это атака с открытым ключом на 30-раундовый ГОСТ 28147-89. Функция шифрования выглядит следующим образом $E_{k}^{(30)}(x)=f_{k}[8,1]\circ S\circ f_{k}^{2}[1,8]\circ f_{k}[3,8](x)$. У $S$ имеется $2^{32}$ фиксированных точек, тогда по доказанной О. Кара лемме у $f_{k}[8,1]\circ S\circ f_{k}^{2}[1,8]$ тоже $2^{32}$. Пусть $y$ — одна из фиксированных точек, $x$ — соответствующий открытый текст. Имеем $E_{k}^{(30)}(x)=y=f_{k}[1,8]\circ f_{k}[3,8](x)$. Предположив значения $k2,k3,...,k7$, мы получим двух раундовую сеть Фейстеля с ключами $k0,\ k1$ и входной/выходной парой $(f_{k}[3,8](x),f_{k}[8,3](y))$. Тогда восстановим $k0$ и $k1$ путём обращения круговой функции. Искомый ключ будет одним из $2^{192}$ вариантов.

Атака методом бумеранга

В работе приведена атака на алгоритм блочного шифрования ГОСТ 28147-89 на основе метода бумеранга со связанными ключами, которая содержит ряд ошибок и на самом деле не работает. Однако основная идея работы позволяет подправить атаку и, внеся дополнительные модификации, получить работающий алгоритм.

В работе проведен разбор, показано, что предложенная атака не быстрее полного перебора. Так же Рудской предлагает новую атаку. Для нахождения всего ключа шифрования при использовании $S$-блоков требуется 18 связанных ключей и проводится $2^{26}$ зашифрований. Однако есть ряд случаев, к которым эти результаты неприменимы. Если подстановка s8 обладает линейным транслятором, то невозможно различить истинные биты ключа от ложных с помощью представленного в работе различителя. Также данный различитель не позволяет найти раундовые ключи 25- и 26-го раундов. Тем самым определяются только 192 бита ключа шифрования. Для этого требуется 14 связанных ключей.

Атака методом бумеранга состоит из двух шагов — различительного и восстановительного. В процессе различительного шага атакующий ищет правильные пары открытого текста, чтобы разница между ними была $E0$ и $E1$(4 текста). Далее делается попытка, используя известные соотношения между входными и выходными различиями найденных пар, восстановить некоторые ключевые биты. Для атаки предположим, что атакующий может шифровать и расшифровывать любой нужный ему текст с помощью ключа, чью разницу с другим известным ему ключом он может установить. ГОСТ 28147-89 представляется в виде $E=E0\circ E1$, где $E0$ представляет первые 24 раунда, $E1$ — оставшиеся. Известны следующие зависимости между ключами : $\alpha \rightarrow \beta =(0,e31)\rightarrow (0,e31)$ для $E0$ и $\gamma \rightarrow \delta =(0,0)\rightarrow (e7,0)$ для $E1$. Используя дифференциальные характеристики, восстанавливаются все биты ключа.

Атаки Исобе и Динура-Данкельмана-Шамира

Общая идея атак Исобе и Динура-Данкельмана-Шамира заключается в построении для зависящего от ключа узкого множества открытых текстов эквивалентного на этом множестве преобразования, имеющего более простую, чем само шифрующее преобразование, структуру. При попадании открытого текста в это множество результат полного 32-раундового преобразования ГОСТ 28147-89 совпадает с результатом 16-раундового, что и эксплуатируется автором атаки. Для всякого открытого текста из этого множества преобразование ГОСТ 28147-89 работает в точности так же, как последние его 8 раундов, что и упрощает анализ.

Трудоемкость атаки Исобе составляет $2^{224}$ операций зашифрования, атаки Динура-Данкельмана-Шамира — $2^{192}$. Для метода Исобе требуется $2^{32}$ пар открытых и шифрованных текстов, а для метода ДДШ — $2^{64}$. Обработка таких объемов материала без смены ключа априорно неприемлема для любого блочного шифра с длиной блока 64.

Атаки Куртуа

Куртуа использует несколько модифицированный вариант дифференциального метода. В работе приводятся дифференциальные характеристики для малого числа раундов. Однако такая атака оказывается не лучше полного перебора.

Атака на шифросистему с 12 связанными ключами

Пудовкина М.А. совместно с Г. И. Хоруженко провели атаку на шифросистему с 12 связанными ключами. Она основана на комбинации методов бумеранга и связанных ключей и для произвольного $S$-блока позволяет найти все 256 бит ключа шифрования. В ряде случаев ключ шифрования может быть найден на ЭВМ за приемлемое время. Число связанных ключей зависит от (вероятностных) свойств $S$-блока. Недостатком атаки является её применимость только к некоторому множеству $S$-блоков.

Далее была проведена модификация атаки, позволяющая восстановить весь ключ шифрования с 12 связанными ключами для произвольного $S$-блока. При наличии линейного транслятора для его нахождения используется модификация различителя. Для восстановления раундовых ключей 25- и 26-го раундов применяется разностная характеристика. Предложенный способ нахождения ключа шифрования состоит из двух этапов. На первом этапе методом бумеранга со связанными ключами определяются множества кандидатов в раундовые ключи 32- и 31-го раундов, используя четверку связанных ключей. На втором этапе находятся множества кандидатов в раундовые ключи 30, 29, …, 25-го раундов разностным методом со связанными ключами. Каждый из этапов предполагает наличие двух модификаций в зависимости от свойств подстановки $s_{8}$(подключ).

Алгебраический анализ

В 2014 году вышла в свет работа, Бабенко Л. К. и Маро Е. А. провели алгебраический анализ ГОСТ 28147-89, получили системы уравнений для различных размеров таблиц нелинейных преобразований замены упрощенного алгоритма шифрования ГОСТ 28147-89, решили одну из систем методом XSL. Был проведен анализ полученных нелинейных систем и выполнена оценка трудоемкости метода XSL алгебраического криптоанализа для восьми блоков замены. Для алгоритма ГОСТ 28147-89 вычисление блоков замены потребовало выполнения не более $2^{32}$ операций зашифрования для однозначного определения $S$ блоков.

Поскольку сложность анализа во многом зависит от числа анализируемых раундов, то используется метод сокращения числа раундов. Если на входе 25 раунда левая и правая части входного значения будут равны, то в последних восьми раундах будет выполнено расшифрование предыдущих восьми раундов. Таким образом, атака с выбранным открытым текстом методом дифференциального или алгебраического анализа будет выполняться всего над 16 раундами вместо 32. Авторами работы предлагается алгоритм поиска таких текстов. Среди $2^{38}$ открытых текстов были найдены 69 текстов, удовлетворяющих условиям поиска.

Литература

• Панасенко Сергей Петрович. 3.1. Алгоритм ГОСТ 28147-89 § Криптойкость алгоритма // Алгоритмы шифрования. Специальный справочник. — БХВ-Петербург, 2009. — С. 79-82. — 564 с. — ISBN 9785977503198.

Ссылки

• Е. К. Алексеев, С. В. Смышляев. ГОСТ 28147-89: «Не спеши его хоронить». Часть 1. Стойкость алгоритма  (неопр.). Блог компании КриптоПро (27 августа 2013). Дата обращения: 22 мая 2015.