). Одновременно с этим в российских СМИ и блогах российских пользователей растет число заметок о данном алгоритме: как освещающих различной степени достоверности результаты атак на российский стандарт, так и содержащих мнения о его эксплуатационных характеристиках. У авторов (а, следовательно, и читателей) данных заметок зачастую складывается впечатление, что отечественный алгоритм шифрования является морально устаревшим, медленным и обладающим уязвимостями, делающими его подверженным атакам в существенной мере больше, чем зарубежные алгоритмы шифрования с аналогичной длиной ключа. Данной серией заметок мы хотели бы в доступной форме рассказать о настоящем положении дел с российским стандартом. В первой части будут освещены все известные международной криптографической общественности атаки на ГОСТ 28147-89, текущие оценки его стойкости. В будущих публикациях мы также подробно рассмотрим свойства стандарта с точки зрения возможности построения эффективных реализаций.
Николя Куртуа - «великий и ужасный»
Начнем с рассказа о деятельности Николя Куртуа, который является автором целого цикла работ, посвященных российскому стандарту блокового шифрования ().
В октябре 2010 года был начат процесс рассмотрения вопроса о включении алгоритма ГОСТ 28147-89 в международный стандарт ISO/IEC 18033-3. Уже в мае 2011 года на электронном архиве ePrint появилась статья известного криптографа Николя Куртуа , отмеченного весьма неоднозначным отношением к нему мирового криптографического сообщества. Публикации Куртуа представляют собой печальный пример манипулирования понятиями, которое не открывает никаких новых свойств рассматриваемого объекта, но с претензией на сенсацию провоцирует распространение в некомпетентной среде ошибочных мнений о его действительных свойствах.
Алгебраический метод
Рассуждения Куртуа строятся вокруг двух классов методов криптоанализа: алгебраических методов и дифференциальных. Рассмотрим первый класс методов.
Упрощенно метод алгебраического криптоанализа можно описать как составление и решение большой системы уравнений, каждое из решений которой соответствует цели криптоаналитика (например, если система составляется по одной паре открытого и шифрованного текстов, то все решения этой системы соответствуют ключам, при которых данный открытый текст преобразуется в данный шифрованный). То есть, в случае задачи криптоанализа блокового шифра, суть алгебраического метода криптоанализа состоит в том, что ключ находится в результате решения системы полиномиальных уравнений. Основная сложность состоит в том, чтобы с учетом особенностей конкретного шифра суметь составить как можно более простую систему, чтобы процесс ее решения занял как можно меньше времени. Здесь ключевую роль играют особенности каждого конкретного анализируемого шифра.
Алгебраический метод, эксплуатируемый Куртуа, коротко можно описать так. На первом этапе используются такие свойства ГОСТ 28147-89, как существование неподвижной точки для части шифрующего преобразования, а также так называемой точки отражения (reflection point). Благодаря этим свойствам из достаточно большого количества пар открытых-шифрованных текстов выбирается несколько пар, которые позволяют рассматривать преобразования не на 32, а лишь на 8 раундах. Второй этап состоит в том, что по полученным на первом этапе результатам 8-ми раундовых преобразований строится система нелинейных уравнений, неизвестными в которой являются биты ключа. Далее эта система решается (это звучит просто, но в действительности является самой трудоемкой частью метода, т.к. система состоит из нелинейных уравнений).
Как уже отмечалось выше, нигде в работе нет детального описания и анализа трудоемкости второго и главного этапа определения ключа. Именно трудоемкость второго этапа определяет трудоемкость всего метода в целом. Вместо этого автор приводит пресловутые «факты», на основе которых делает оценки трудоемкости. Утверждается, что эти «факты» основаны на результатах экспериментов. Анализ «фактов» из работы Куртуа в целом приведен в работе отечественных авторов. Авторами этой работы отмечается, что многие из представленных без каких-либо доказательств «фактов» Куртуа при экспериментальной проверке оказались ложными. Авторы статьи пошли дальше и за Куртуа провели анализ трудоемкости второго этапа с помощью хорошо обоснованных алгоритмов и оценок. Получившиеся в результате оценки трудоемкости показывают полную неприменимость представленной атаки. Помимо отечественных авторов, большие проблемы, которые возникают у Куртуа с оценками и обоснованием своих методов, отмечались также, например, в работе .
Дифференциальный метод
Рассмотрим второй метод Куртуа, который основан на дифференциальном криптоанализе.
Общий метод дифференциального криптоанализа базируется на эксплуатации свойств используемых в криптографических примитивах нелинейных отображений, связанных с влиянием значения ключа на зависимости между разностями пар входных и пар выходных значений данных отображений. Опишем основную идею дифференциального метода криптографического анализа блокового шифра. Обычно блоковые шифры преобразуют входные данные поэтапно с помощью некоторого количества так называемых раундовых преобразований, причем каждое раундовое преобразование использует не весь ключ, а лишь некоторую его часть. Рассмотрим немного «усеченный» шифр, который отличается от исходного тем, что в нем нет последнего раунда. Предположим, что удалось установить, что в результате зашифрования с помощью такого «усеченного» шифра двух открытых текстов, отличающихся в некоторых фиксированных позициях, с большой вероятностью получаются шифртексты, которые также отличаются в некоторых фиксированных позициях. Это свойство показывает, что «усеченный» шифр с большой вероятностью оставляет зависимость между некоторыми открытыми текстами и результатами их зашифрования. Чтобы с помощью этого явного недостатка восстановить часть ключа, необходимо иметь возможность зашифровать заранее выбранные открытые тексты на том ключе, который мы хотим восстановить (так называемая «атака с выбранным открытым текстом»). В начале процедуры «вскрытия ключа» случайно генерируется некоторое количество пар открытых текстов, отличающихся в тех самых фиксированных позициях. Все тексты зашифровываются с помощью «полного» шифра. Полученные пары шифртекстов используются для восстановления тех битов ключа, которые используются в последнем раундовом преобразовании, следующим образом. С помощью некоторого выбранного наугад значения искомых битов ключа ко всем шифртекстам применяется преобразование, обратное последнему раундовому преобразованию. По сути, если мы угадали искомое значение битов ключа, мы получим результат работы «усеченного» шифра, а если не угадали - мы фактически «еще больше зашифруем данные», что только уменьшит замеченную выше зависимость между блоками (отличие в некоторых фиксированных позициях). Другими словами, если среди результатов такой «дообработки» шифртекстов нашлось достаточно много пар, отличающихся в известных нам фиксированных позициях, то это означает, что мы угадали искомые биты ключа. В противном случае таких пар найдется существенно меньше. Поскольку в каждом раунде используется только часть ключа, искомых битов (то есть битов ключа, используемых в последнем раунде) не так много, как битов в полном ключе и их можно просто перебрать, повторяя указанные выше действия. В таком случае мы обязательно когда-нибудь наткнемся на правильное значение.
Из приведенного выше описания следует, что самое важное в дифференциальном методе анализа - это номера тех самых позиций в открытых текстах и шифртекстах, отличия в которых играют ключевую роль при восстановлении битов ключа. Принципиальное наличие этих позиций, как и набор их номеров, напрямую зависит от свойств тех нелинейных преобразований, которые используются в любом блоковом шифре (обычно вся «нелинейность» сосредоточена в так называемых S-блоках или узлах замены).
Куртуа использует несколько модифицированный вариант дифференциального метода. Сразу же отметим, что свой анализ Куртуа проводит для S-блоков, отличных от действующих и от предложенных в ISO. В работе приводятся дифференциальные характеристики (те самые номера, в которых должны отличаться блоки) для малого числа раундов. Обоснование продления характеристик на большее число раундов, как водится, основано на «фактах». Куртуа высказывает, опять же, ничем, кроме его авторитета, не подкрепленное предположение, что изменение S-блоков не повлияет на стойкость ГОСТ 28147-89 против его атаки (при этом по непонятным причинам S-блоки из 1-го рабочего проекта дополнения к стандарту ISO/IEC 18033-3 не рассматривались). Анализ, проведенный авторами статьи , показывает, что даже если принять на веру необоснованные «факты» Куртуа и провести анализ ГОСТ 28147-89 с другими S-блоками, то атака опять же оказывается не лучше полного перебора.
Детальный анализ работ Куртуа с подробным обоснованием беспочвенности всех утверждений о снижении стойкости российского стандарта был проведен в работах [ , ].
При этом абсолютное отсутствие аккуратности выкладок признает даже сам Куртуа! Следующий слайд взят из презентации Куртуа на секции коротких объявлений FSE 2012.
Необходимо отметить, что работы Куртуа неоднократно критиковались также и зарубежными исследователями. Например, его работы по построению атак на алгоритм блокового шифрования AES с помощью XSL-метода содержали те же принципиальные недоработки, что и работы по анализу российского стандарта: большинство оценок трудоемкости появляется в тексте совершенно безосновательно и бездоказательно - подробную критику можно найти, например, в работе . Кроме того, сам Куртуа признает повсеместные отказы в публикации его работ на крупных криптографических конференциях и в признанных рецензируемых журналах, оставлявшие ему зачастую лишь возможность выступить на секции коротких объявлений. Об этом, например, можно прочитать в разделе 3 работы . Вот некоторые цитаты, приводимые самим Куртуа и относящиеся к его работам:
- «I think that the audiences of Asiacrypt will not feel it is interesting». Рецензент Asiacrypt 2011.
- «… there is a big, big, big problem: this attack, which is the main contribution of the paper has already been published at FSE’11 (it was even the best paper), …». Рецензент Crypto 2011.
Таким образом, профессиональная часть международной криптографической общественности относится к качеству работ Куртуа с не меньшим сомнением, чем, скажем, к не подтвержденным никакими последовательными выкладками заявлениям некоторых российских специалистов об их умении взламывать AES за 2 100 или к очередным "доказательствам" на две страницы гипотезы о неравенстве сложностных классов P и NP.
Атаки Исобе и Динура-Данкельмана-Шамира
Общая идея атак Исобе () и Динура-Данкельмана-Шамира (далее: атака ДДШ) () заключается в построении для определенного (зависящего от ключа) узкого множества открытых текстов эквивалентного на этом множестве преобразования, имеющего более простую, чем само шифрующее преобразование, структуру. В случае метода Исобе это множество таких 64-битных блоков x, что F 8 -1 (Swap(F 8 (z))) = z, где z = F 16 (x), через F 8 (x) и F 16 (x) обозначены первые 8 и первые 16 раундов шифрования ГОСТ 28147-89 соответственно, через Swap - операция обмена местами половинок 64-байтового слова. При попадании открытого текста в это множество результат полного 32-раундового преобразования ГОСТ 28147-89 совпадает с результатом 16-раундового, что и эксплуатируется автором атаки. В случае метода ДДШ это множество таких x, что F 8 (x) = x (неподвижная точка преобразования F 8). Для всякого открытого текста из этого множества преобразование ГОСТ 28147-89 работает в точности так же, как последние его 8 раундов, что и упрощает анализ.
Трудоемкость атаки Исобе составляет 2 224 операций зашифрования, атаки ДДШ - 2 192 . Однако все вопросы о том, следует ли, что атаки Исобе и ДДШ вносят новые ограничения на условия применения нашего алгоритма, снимает оценка требований к объему материала, необходимого для проведения каждой из атак: для метода Исобе требуется 2 32 пар открытых и шифрованных текстов, а для метода ДДШ - 2 64 . Обработка таких объемов материала без смены ключа априорно неприемлема для любого блокового шифра с длиной блока 64: на материале объемом 2 32 , с учетом задачи о днях рождения (см., например, ), близка к 1/2 вероятность появления повторяющихся блоков, что предоставит нарушителю возможность делать по шифрованным текстам некоторые заключения об открытых текстах без определения ключа. Наличие же 2 64 пар открытых и шифрованных текстов, полученных на одном ключе, фактически позволяет противнику осуществлять операции зашифрования и расшифрования вообще без знания этого ключа. Это обусловлено чисто комбинаторным свойством: противник в этом случае обладает всей таблицей шифрующего преобразования. Такая ситуация абсолютно недопустима ни при каких разумных эксплуатационных требованиях. Например, в КриптоПро CSP присутствует техническое ограничение на объём шифруемого (без преобразования ключа) материала в 4 Мб (см. ). Таким образом, строгий запрет на использование ключа на материале такого объема присущ всякому блоковому шифру с длиной блока 64 бита, а следовательно, атаки Исобе и ДДШ никоим образом не сужают область использования алгоритма ГОСТ 28147-89 при сохранении максимально возможной стойкости 2 256 .
Безусловно, нельзя не отметить, что исследователями (Исобе и Динуром-Данкельманом-Шамиром) было показано, что некоторые свойства алгоритма ГОСТ 28147-89 позволяют находить пути анализа, не учтенные создателями алгоритма. Простой вид ключевого расписания, существенно упрощающий задачу построения эффективных реализаций, также позволяет для некоторых редких случаев ключей и открытых текстов строить более простые описания преобразований, производимых алгоритмом.
В работе продемонстрировано, что данное негативное свойство алгоритма может быть легко устранено с полным сохранением эксплуатационных характеристик, однако оно, к сожалению, является неотъемлемой частью алгоритма в повсеместно используемом его виде.
Отметим, что определенные небрежности в оценках средней трудоемкости присутствуют и в работе Динура, Данкельмана и Шамира. Так, при построении атаки не уделяется должного внимания следующему моменту: для существенной доли ключей множество открытых текстов x, таких, что F 8 (x) = x, является пустым: неподвижных точек у 8 раундов преобразования может просто не быть. Существование неподвижных точек зависит также и от выбора узлов замены. Таким образом, атака является применимой только при определенных узлах замены и ключах.
Стоит упомянуть также еще об одной работе с атакой на ГОСТ 28147-89. В феврале 2012 года на электронном архиве ePrint международной криптографической ассоциации появилась обновленная версия статьи (от ноября 2011 года), которая содержала новую атаку на ГОСТ 28147-89. Характеристики представленной атаки таковы: объем материала - 2 32 (как у Исобе), а трудоемкость - 2 192 (как у ДДШ). Таким образом, эта атака улучшала рекордную по времени атаку ДДШ по объему материала с 2 64 до 2 32 . Отметим отдельно, что авторы честно привели все выкладки с обоснованием трудоемкости и объема материала. Через 9 месяцев в приведенных выкладках была найдена принципиальная ошибка, и с ноября 2012 года обновленная версия статьи в электронном архиве уже не содержит каких-либо результатов касательно отечественного алгоритма.
Атаки в предположении, что нарушитель знает «кое-что» о ключах
Заметим напоследок, что в литературе также имеется некоторое количество работ (см., например, и ), посвященных атакам на ГОСТ 28147-89 в так называемой модели со связанными ключами. Данная модель в своей основе содержит предположение о возможности нарушителя получать доступ для анализа не просто к парам открытых и шифрованных с помощью искомого ключа текстов, но также к парам открытых и шифрованных текстов, полученных с помощью (также неизвестных) ключей, отличающихся от искомого известным регулярным образом (например, в фиксированных битовых позициях). В данной модели действительно удается получить интересные результаты о ГОСТ 28147-89, однако в этой модели не менее сильные результаты удается получать и о, например, получившем наиболее широкое распространение в современных сетях общего пользования стандарте AES (см, например, ). Заметим, что условия для проведения такого рода атак возникают при использовании шифра в некотором протоколе. Нельзя не отметить, что результаты такого рода, хоть и представляют несомненный академический интерес с точки зрения изучения свойств криптографических преобразований, но фактически не относятся к практике. Например, все сертифицированные ФСБ России средства криптографической защиты информации выполняют строжайшие требования по схемам выработки ключей шифрования (см., например, ). Как указано в результатах проведенного в анализа, при наличии 18 связанных ключей и 2 10 пар блоков открытого и шифрованного текста трудоемкость полного вскрытия закрытого ключа, при вероятности успеха 1-10 -4 , действительно составляет 2 26 . Однако при соблюдении упомянутых выше требований по выработке ключевого материала вероятность обнаружения таких ключей равна 2 -4352 , то есть в 2 4096 раз меньше, чем если просто попытаться угадать секретный ключ с первой попытки.
К работам, относящимся к модели со связанными ключами, относится также и работа , наделавшая в 2010 году много шума в российских электронных изданиях, не страдающих от привычки внимательно проверять материал в процессе гонки за сенсациями. Результаты, представленные в ней, не были подкреплены каким-либо сколь-нибудь строгим обоснованием, зато содержали громкие заявления о возможности взламывать государственный стандарт Российской Федерации на слабеньком ноутбуке за считанные секунды - в общем, статья была написана в лучших традициях Николя Куртуа. Но, несмотря на совершенно очевидную мало-мальски знакомому с основными принципами научности публикаций читателю безосновательность статьи, именно для успокоения российской общественности после работы Рудским был написан подробный и обстоятельный текст , содержащий всесторонний анализ данной недостатьи. В статье с говорящим названием "О нулевой практической значимости работы «Key recovery attack on full GOST block cipher with zero time and memory»" приводится обоснование того, что средняя трудоемкость приведенного в метода не меньше, чем трудоемкость полного перебора.
Сухой остаток: какова стойкость на практике?
В заключение приведем таблицу, содержащую данные обо всех известных международному криптографическому сообществу результатах строго описанных и обоснованных атак на ГОСТ 28147-89. Отметим, что сложность приводится в операциях зашифрования алгоритма ГОСТ 28147-89, а память и материал указаны в блоках алгоритма (64 бита = 8 байт).
| Атака | Трудоемкость | Память | Требуемый материал |
| Исобе | 2 224 | 2 64 | 2 32 |
| Динур-Данкельман-Шамир, FP, 2DMitM | 2 192 | 2 36 | 2 64 |
| Динур-Данкельман-Шамир, FP, low-memory | 2 204 | 2 19 | 2 64 |
| 2 224 | 2 36 | 2 32 | |
| Динур-Данкельман-Шамир, Reflection, 2DMitM | 2 236 | 2 19 | 2 32 |
| Полный перебор | 2 256 | 1 | 4 |
| Количество наносекунд с возникновения Вселенной | 2 89 |
Несмотря на достаточно масштабный цикл исследований в области стойкости алгоритма ГОСТ 28147-89, на данный момент не известно ни одной атаки, условия для осуществления которой являлись бы достижимыми при сопутствующих длине блока в 64 бита эксплуатационных требованиях. Вытекающие из параметров шифра (битовая длина ключа, битовая длина блока) ограничения на объем материала, который может быть обработан на одном ключе, существенно строже минимального объема, который необходим для осуществления любой из известных на данный момент атак. Следовательно, при выполнении существующих эксплуатационных требований ни один из предложенных к настоящему моменту методов криптоанализа ГОСТ 28147-89 не позволяет определять ключ с трудоемкостью меньшей полного перебора.
Этот алгоритм является обязательным для применения в качестве алгоритма шифрования в государственных организациях РФ и ряде коммерческих .
Описание алгоритма
Схема алгоритма показана на рис. 3.1 . Как видно, схема этого алгоритма достаточно проста, что однозначно упрощает его программную или аппаратную реализацию.
Алгоритм ГОСТ 28147-89 шифрует информацию блоками по 64 бита, которые разбиваются на два субблока по 32 бита (N1 и N2). Субблок N1 определенным образом обрабатывается, после чего его значение складывается
со значением субблока N2 (сложение выполняется по модулю 2), затем субблоки меняются местами. Такое преобразование выполняется определенное количество раундов: 16 или 32 в зависимости от режима работы алгоритма (описаны далее). В каждом раунде выполняются следующие операции:
1. Наложение ключа. Содержимое субблока /VI складывается по модулю 2 32 с частью ключа Кх.
Ключ шифрования алгоритма ГОСТ 28147-89 имеет размерность 256 битов, а Кх— это его 32-битная часть, т. е. 256-битный ключ шифрования представляется в виде конкатенации 32-битных подключей (рис. 3.2):
Щ ATI, АГ2, Ю, АГ4, К5, Кб, К7.
В процессе шифрования используется один из этих подключей — в зависимости от номера раунда и режима работы алгоритма.
Рис. 3.1. Схема алгоритма ГОСТ 28147-
Рис. 3.2. Ключ шифрования алгоритма ГОСТ 28147-89
2. Табличная замена. После наложения ключа субблок /VI разбивается на 8 частей по 4 бита, значение каждой из которых по отдельности заменяется в соответствии с таблицей замены для данной части субблока. Табличные замены (Substitution box, S-box) часто используются в современных алгоритмах шифрования, поэтому стоит рассмотреть их подробнее.
Табличная замена используется таким образом: на вход подается блок данных определенной размерности (в этом случае — 4-битный), числовое представление которого определяет номер выходного значения. Например, имеем S-box следующего вида:
4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.
Пусть на вход пришел 4-битный блок «0100», т. е. значение 4. Согласно таблице, выходное значение будет равно 15, т.е. «1111» (0 заменяется на 4, 1 — на 11, значение 2 не изменяется и т. д.).
Как видно, схема алгоритма весьма проста, что означает, что наибольшая нагрузка по шифрованию данных ложится на таблицы замен. К сожалению, алгоритм обладает тем свойством, что существуют «слабые» таблицы замен, при использовании которых алгоритм может быть раскрыт криптоаналитическими методами. К числу слабых относится, например, таблица, в которой выход равен входу :
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
3. Побитовый циклический сдвиг влево на 11 битов.
Режимы работы алгоритма
Алгоритм ГОСТ 28147-89 имеет 4 режима работы:
□ режим простой замены;
□ режим гаммирования;
П режим гаммирования с обратной связью;
□ режим выработки имитоприставок.
Эти режимы несколько отличаются от общепринятых (описанных в разд. 1.4), поэтому стоит рассмотреть их подробнее.
Данные режимы имеют различное назначение, но используют одно и то же описанное выше шифрующее преобразование.
Режим простой замены
В режиме простой замены для зашифровывания каждого 64-битного блока информации просто выполняются 32 описанных выше раунда. 32-битные подключи используются в следующей последовательности:
□ КО, Kl, К2, КЗ, К4, К5, Кб, АГ7, КО, ATI и т. д. — в раундах с 1-го по 24-й;
□ К1, Кб, К5, К4, КЗ, К2, К\, КО —в раундах с 25-го по 32-й.
Расшифровывание в режиме простой замены производится совершенно так же, но с несколько другой последовательностью применения подключей:
□ КО, К\, К2, КЗ, К4, К5, Кб, КП — в раундах с 1-го по 8-й;
□ КП, Кб, К5, К4, КЗ, К2, К\, КО, К1, Кб и т. д. — в раундах с 9-го по 32-й.
Аналогично стандартному режиму ЕСВ, по причине раздельного шифрования блоков режим простой замены категорически не рекомендуется использовать для шифрования собственно данных; он должен использоваться только для шифрования других ключей шифрования в многоключевых схемах.
Режим гаммирования
В режиме гаммирования (рис. 3.3) каждый блок открытого текста побитно складывается по модулю 2 с блоком гаммы шифра размером 64 бита. Гамма шифра — это специальная последовательность, которая вырабатывается с помощью описанных выше преобразований следующим образом:
1. В регистры N1 и N2 записывается их начальное заполнение— 64-битная величина, называемая «синхропосылкой» (синхропосылка, практически, является аналогом вектора инициализации в режимах СВС, CFB и OFB).
2. Выполняется зашифровывание содержимого регистров /VI и N2 (в данном случае — синхропосылки) в режиме простой замены.
3. Содержимое N1 складывается по модулю (2 32 – 1) с константой CI = 2 24 + 2 16 + 2 8 + 4 , результат сложения записывается в регистр /VI.
4. Содержимое N2 складывается по модулю 2 с константой С2 = 2 24 + 2 16 + 2 8 +1, результат сложения записывается в регистр N2.
5. Содержимое регистров /VI и N2 подается на выход в качестве 64-битного блока гаммы шифра (т. е. в данном случае /VI и N2 образуют первый блок гаммы).
6. Если необходим следующий блок гаммы (т. е. необходимо продолжить зашифровывание или расшифровывание), выполняется возврат к шагу 2.
Для расшифровывания аналогичным образом выполняется выработка гаммы, затем снова применяется операция XOR к битам зашифрованного текста и гаммы.
Для выработки той же самой гаммы шифра у пользователя, расшифровывающего криптограмму, должен быть тот же самый ключ и то же значение синхропосылки, которые применялись при зашифровывании информации. В противном случае получить исходный текст из зашифрованного не удастся.
В большинстве реализаций алгоритма ГОСТ 28147-89 синхропосылка не является секретным элементом, однако синхропосылка может быть так же секретна, как и ключ шифрования. В этом случае можно считать, что эффективная длина ключа алгоритма (256 битов) увеличивается еще на 64 бита синхропосылки, которую можно рассматривать как дополнительный ключевой элемент.
Режим гаммирования с обратной связью
В режиме гаммирования с обратной связью в качестве заполнения регистров /VI и Л/2, начиная со 2-го блока, используется не предыдущий блок гаммы, а результат зашифровывания предыдущего блока открытого текста (рис. 3.4). Первый же блок в данном режиме генерируется полностью аналогично предыдущему.
Рис. 3.4. Выработка гаммы шифра в режиме гаммирования с обратной связью
Режим выработки имитоприставки
Имитоприставка — это криптографическая контрольная сумма, вычисляемая с использованием ключа шифрования и предназначенная для проверки целостности сообщений. Для ее вычисления существует специальный режим алгоритма ГОСТ 28147-89.
Генерация имитоприставки выполняется следующим образом:
1. Первый 64-битный блок информации, для которой вычисляется имитоприставка, записывается в регистры N1 и N2 и зашифровывается в сокращенном режиме простой замены, в котором выполняются первые 16 раундов из 32.
2. Полученный результат суммируется по модулю 2 со следующим блоком информации с сохранением результата в N1 и N2.
3. М и N2 снова зашифровываются в сокращенном режиме простой замены и т. д. до последнего блока информации.
Имитоприставкой считается 64-битное результирующее содержимое регистров N1 и N2 или его часть. Чаще всего используется 32-битная имитоприставка, т. е. половина содержимого регистров. Этого достаточно, поскольку, как и любая контрольная сумма, имитоприставка предназначена, прежде всего, для защиты от случайных искажений информации. Для защиты же от преднамеренной модификации данных применяются другие криптографические методы — в первую очередь электронная цифровая подпись {см. разд. 1.1).
Имитоприставка используется следующим образом:
1. При зашифровывании какой-либо информации вычисляется имитоприставка открытого текста и посылается вместе с шифртекстом.
2. После расшифровывания имитоприставка снова вычисляется и сравнивается с присланной.
3. Если вычисленная и присланная имитоприставки не совпадают— шифр-текст был искажен при передаче или использовались неверные ключи при расшифровывании.
Имитоприставка особенно полезна для проверки правильности расшифровывания ключевой информации при использовании многоключевых схем.
Имитоприставка— это некоторый аналог кода аутентификации сообщений MAC, вычисляемого в режиме СВС; отличие состоит в том, что при вычислении имитоприставки не используется синхропосылка, тогда как при вычислении MAC используется вектор инициализации.
Криптостойкость алгоритма
В 1994 г. описание алгоритма ГОСТ 28147-89 было переведено на английский язык и опубликовано ; именно после этого стали появляться результаты его анализа, выполненного зарубежными специалистами; однако в течение значительного времени не было найдено каких-либо атак, приближающихся к практически осуществимым .
□ большой длины ключа — 256 битов; вместе с секретной синхропосылкой эффективная длина ключа увеличивается до 320 битов;
□ 32 раундов преобразований; уже после 8 раундов достигается полный эффект рассеивания входных данных: изменение одного бита блока открытого текста повлияет на все биты блока шифртекста, и наоборот, т. е. существует многократный запас стойкости.
Рассмотрим результаты криптоанализа алгоритма ГОСТ 28147-89.
Анализ таблиц замен
Поскольку таблицы замен в стандарте не приведены, в ряде работ (например, в ) высказывается предположение, что «компетентная организация» может выдать как «хорошие», так и «плохие» таблицы замен. Однако в известнейший эксперт Брюс Шнайер называет такие предположения «слухами». Ясно, что криптостойкость алгоритма во многом зависит от свойств используемых таблиц замен, соответственно, существуют слабые таблицы замен (пример см. выше), применение которых может упростить вскрытие алгоритма. Тем не менее, возможность использования различных таблиц замен кажется весьма достойной идеей, в пользу которой можно привести два следующих факта из истории стандарта шифрования DES (подробности см. в разд. 3.15):
□ атаки с помощью как линейного, так и дифференциального криптоанализа алгоритма DES используют конкретные особенности таблиц замен; при использовании других таблиц криптоанализ придется начинать сначала;
□ были предприняты попытки усилить DES против линейного и дифференциального криптоанализа путем использования более стойких таблиц замен; такие таблицы, действительно более стойкие, были предложены, например, в алгоритме s 5 DES ; но, увы, заменить DES на s 5 DES было невозможно, поскольку таблицы замен жестко определены в стандарте , соответственно, реализации алгоритма наверняка не поддерживают возможность смены таблиц на другие.
В ряде работ (например, , и ) ошибочно делается вывод о том, что секретные таблицы замен алгоритма ГОСТ 28147-89 могут являться частью ключа и увеличивать его эффективную длину (что несущественно, поскольку алгоритм обладает весьма большим 256-битным ключом). Однако в работе доказано, что секретные таблицы замен могут быть вычислены с помощью следующей атаки, которая может быть применена практически:
1. Устанавливается нулевой ключ и выполняется поиск «нулевого вектора», т. е. значения z = /(0), где /() — функция раунда алгоритма. Этот этап занимает порядка 2 операций шифрования.
2. С помощью нулевого вектора вычисляются значения таблиц замен, что занимает не более 2 11 операций.
Модификации алгоритма и их анализ
В работе проведен криптоанализ модификаций алгоритма ГОСТ 28147-89:
□ алгоритма GOST-H, в котором, относительно оригинального алгоритма, изменен порядок использования подключей, а именно в раундах с 25-го по 32-й подключи используются в прямом порядке, т. е. точно так же, как и в предыдущих раундах алгоритма;
□ 20-раундового алгоритма GOST®, в раунде которого для наложения ключа используется операция XOR вместо сложения по модулю 2 32 .
По результатам анализа сделан вывод о том, что GOST-H и GOST© слабее исходного алгоритма ГОСТ 28147-89, поскольку оба имеют классы слабых ключей. Стоит отметить, что в части криптоанализа GOST© работа слово в слово повторяет раздел, посвященный криптоанализу алгоритма ГОСТ 28147-89, вышедшей в 2000 г. известной работы (без каких-либо ссылок на оригинал). Это ставит под сомнение профессионализм авторов работы и остальные ее результаты.
Весьма интересная модификация алгоритма предложена в работе : таблицы S\…Ss обязательно должны быть различными; в каждом раунде алгоритма должна выполняться их перестановка по определенному закону. Данная перестановка может быть зависимой от ключа шифрования, а может быть и секретной (т. е. являться частью ключа шифрования большего размера по сравнению с исходным 256-битным ключом). Оба этих варианта, по мнению их авторов, существенно усиливают стойкость алгоритма против линейного и дифференциального криптоанализа.
И еще одна модификация, связанная с таблицами замен, приведена в работе , в которой анализируется один из возможных методов вычисления таблиц замен на основе ключа шифрования. Авторы работы сделали вывод, что подобная зависимость ослабляет алгоритм, поскольку приводит к наличию слабых ключей и к некоторым потенциальным уязвимостям алгоритма.
Анализ полнораундового алгоритма
Существуют атаки и на полнораундовый ГОСТ 28147-89 без каких-либо модификаций. Одна из первых открытых работ, в которых был проведен анализ алгоритма,— широко известная работа — посвящена атакам, использующим слабости процедуры расширения ключа ряда известных алгоритмов шифрования. В частности, полнораундовый алгоритм ГОСТ 28147-89 может быть вскрыт с помощью дифференциального криптоанализа на связанных ключах, но только в случае использования слабых таблиц замен. 24-раундовый вариант алгоритма (в котором отсутствуют первые 8 раундов) вскрывается аналогичным образом при любых таблицах замен, однако сильные таблицы замен (например, приведенная в ) делают такую атаку абсолютно непрактичной.
Отечественные ученые А. Г. Ростовцев и Е. Б. Маховенко в 2001 г. в работе предложили принципиально новый метод криптоанализа (по мнению авторов, существенно более эффективный, чем линейный и дифференциальный криптоанализ ) путем формирования целевой функции от известного открытого текста, соответствующего ему шифртекста и искомого значения ключа и нахождения ее экстремума, соответствующего истинному значению ключа. Они же нашли большой класс слабых ключей алгоритма ГОСТ 28147-89, которые позволяют вскрыть алгоритм с помощью всего 4-х выбранных открытых текстов и соответствующих им шифртекстов с достаточно низкой сложностью. Криптоанализ алгоритма продолжен в работе .
В 2004 г. группа специалистов из Кореи предложила атаку, с помощью которой, используя дифференциальный криптоанализ на связанных ключах, можно получить с вероятностью 91,7 % 12 битов секретного ключа . Для атаки требуется 2 35 выбранных открытых текстов и 2 36 операций шифрования. Как видно, данная атака, практически, бесполезна для реального вскрытия алгоритма.
«Пока ты жив, не умирай, на этот мир взгляни.
У многих здесь душа мертва – они мертвы внутри.
Но ходят и смеются, не зная, что их нет,
Не торопи свой смертный час» – она сказала мне.
Ария, «Там высоко»
- Введение
- Предварительные сведения о блочных шифрах
2.1
Сети Файстеля.
2.2
Блочный шифр ГОСТ 28147-89
- Теоретический минимум
3.1
Ключевая информация
3.2
Основной шаг криптопреобразования
3.3 Базовые циклы: “ 32-З ” , “ 32-Р ” .
- Практика
4.1
Реализация основного шага криптопреобразования
4.2
Увеличение быстродействия алгоритма
5.
6.
Список использованной литературы
7.
Благодарности.
Введение.
Данный документ является моей попыткой описать метод простой замены алгоритма шифрования ГОСТ 28147-89 наиболее простым, но, тем не менее, технически-грамотным языком. О том, насколько получилось ли это у меня, читатель скажет свое мнение, после того как прочтет первые шесть пунктов.
Для того, что бы мой труд дал больше пользы рекомендую вооружиться трудами авторов указанных в списке используемой литературы. Рекомендуется также калькулятор, чтобы в нем были функция по расчету операции XOR , т.к. прочтение статьи предполагает, что читающий вознамерился изучить данный алгоритм шифрования. Хотя в качестве справочного пособия она тоже подойдет, но я писал эту статью именно, как обучающую.
Предварительные сведения о блочных шифрах.
Прежде чем мы начнем рассматривать алгоритм, нам необходимо ознакомиться с историей создания такого рода шифров. Алгоритм относится к разряду блочных шифров, в архитектуре которых информация разбивается на конечное количество блоков, конечный естественно может быть не полным. Процесс шифрования происходит именно над полными блоками, которые и образуют шифрограмму. Конечный блок, если он неполный дополняется чем либо (о нюансах по его дополнению я скажу ниже) и шифруется так же как и полные блоки. Под шифрограммой я понимаю – результат действия функции шифрования над некоторым количеством данных, которые пользователь подал для шифрования. Другими словами шифрограмма – это конечный результат шифрования.
История развития блочных шифров ассоциируется с началом 70х годов, когда компания IBM осознав необходимость защиты информации при передаче данных по каналам связи ЭВМ, приступила к выполнению собственной программы научных исследований, посвященных защите информации в электронных сетях, в том числе и криптографии.
Группу исследователей – разработчиков фирмы IBM, приступившей к исследованию систем шифрования с симметричной схемой использования ключей, возглавил доктор Хорст Файстель .
2.1 Сети Файстеля
Предложенная Файстелем архитектура нового метода шифрования в классической литературе получила название «Архитектура Файстеля», но на данный момент в русской и зарубежной литературе используется более устоявшийся термин – «сеть Файстеля» или Feistel`s NetWork. В последствии по данной архитектуре был построен шифр «Люцифер» — который позднее был опубликован и вызвал новую волну интереса к криптографии в целом.
Идея архитектуры «сети Файстеля» заключается в следующем: входной поток информации разбивается на блоки размером в n битов, где n четное число. Каждый блок делится на две части – L и R, далее эти части подаются в итеративный блочный шифр, в котором результат j-го этапа определяется результатом предыдущего этапа j-1! Сказанное можно проиллюстрировать на примере:
Рис. 1
Где, функция А – это основное действие блочного шифра. Может быть простым действием, таким как операция XOR, а может иметь более сложный вид быть последовательностью ряда простых действий – сложение по модулю, сдвиг влево, замена элементов и т.д., в совокупности эти простые действия образуют так называемый – основной шаг криптопреобразования.
Следует заметить, что ключевыми элементами работы функции является подача элементов ключей и операция XOR и от того насколько хорошо продуманы работа этих операций, говорит о криптостойкости шифра в целом.
Для того чтобы идея сетей Файстеля была окончательна ясна, рассмотрим простейший случай изображенный на рис. 1 , где в функции А – выступит операции “mod 2” (“xor”), но это простейший случай, в более серьезной ситуации, например сокрытие информации государственной важности функция А может быть более сложной (сколько я видел функция А действительно бывает очень сложной):
Исходные данные:
L = 1110b, R = 0101, K = 1111b
Получить шифрограмму
- (R + K) mod 2 4 = Smod, Smod = 0100b
- (Smod + L) mod 2 = Sxor, Sxor = 1010b
- L = R, R = Sxor
L = 0101b, R = 1010b
Поясним наши действия:
- Эта операция сложение по mod 2 4 . На практике такая операция сводится к простому сложению, где мы должны сложить два числа и проигнорировать перенос в 5й разряд. Так как, если проставить над разрядами двоичного представления числа проставить показатели степени, над пятым разрядом как раз будет показатель четыре, взглянем на рисунок ниже, где изображены действия нашей операции:
Рис. 2
Здесь я стрелкой указал на показатели степени, как видно, результат должен был получиться 10100, но так как при операции mod 2 4 игнорируется перенос, мы получаем 0100.
- Эта операция в литературе называется mod 2, на языке ассемблера реализуется командой XOR . Но ее более правильное название mod 2 1 . Без этой уникальной операции вряд ли можно построить быстрый, легко реализуемый алгоритм шифрования и при этом, чтобы он был еще довольно криптостойким. Уникальность этой операции заключается в том, что она сама себе обратная! К примеру, если число А поXORить с числом Б, в результате получим В, в дальнейшем достаточно переXORить числа Б и В между собой, чтобы получить прежнее значение А!
В этой операции мы получили 1010 имея числа 1110 и 0100, чтобы получить обратно 1110, достаточно переXORрить между собой числа 0100 и 1010! Более подробно об этой операции можно почитать в статье, которая вложена на сайте www.wasm.ru , «Элементарное руководство по CRC_алгоритмам обнаружения ошибок » автор, которой Ross N. Williams . В этом труде есть пункт — «5. Двоичная арифметика без учета переносов ». Вот именно в этой статье и описана операция xor! Я восклицаю потому что в этой статье эта операция так расписана, что читатель не просто понимает как работает эта операция, он даже начинает ее видеть, слышать и чувствовать!
- Это действие необходимо, чтобы при расшифровывании из шифрограммы можно было получить исходные значения.
2.2 Блочный шифр ГОСТ 28147-89
Алгоритм шифрования ГОСТ 28147 – 89 относится к разряду блочных шифров работающих по архитектуре сбалансированных сетей Файстеля, где две части выбранного блока информации имеют равный размер. Алгоритм был разработан в недрах восьмого отдела КГБ преобразованного ныне в ФАПСИ и был закреплен, как стандарт шифрования Российской Федерации еще в 1989 году при СССР.
Для работы данного метода алгоритма необходимо разбить информацию на блоки размером в 64 бита. Сгенерировать или ввести в систему шифрования, следующую ключевую информацию: ключ и таблицу замен. К выбору ключа и таблицы замен при шифровании следует отнестись очень серьезно, т.к. именно это фундамент безопасности вашей информации. О том, какие требования налагаются на ключ, и таблицу замен смотри пункт «Требования к ключевой информации».
При рассмотрении метода мы не будем заострять на этом внимания, т.к. эта статья, как я уже говорил выше, написана с целью, научить читающего, шифровать данные по методу простой замены данного алгоритма шифрования, но мы обязательно коснемся этого вопроса в конце статьи.
Теоретический минимум.
3.1 Ключевая информация
Как я уже говорил выше, в шифровании данных активное участие принимают:
3.1.1. Ключ – это последовательность восьми элементов размером в 32 бита каждый. Далее будем обозначать символом К, а элементы из которых он состоит – k1,k2,k3,k4,k5,k6,k7,k8.
3.1.2 Таблица замен – матрица из восьми строк и шестнадцати столбцов, в дальнейшем – Hij. Каждый элемент на пересечении строки i и столбца j занимает 4 бита.
Основным действием в процессе шифрования является – основной шаг криптопреобразования. Это ничто иное, как действие по шифрованию данных по определенному алгоритму, только название разработчики ввели уж больно громоздкое:).
Прежде чем начать шифровать, блок разбивают на две части L и R, по 32 бита каждая. Выбирают элемент ключа и только потом подают эти две части блока, элемент ключа таблицу замен в функцию основного шага, результат основного шага это одна итерация базового цикла, о котором речь пойдет в следующем пункте. Основной шаг состоит из следующих действий:
- Сложение часть блока R суммируется с элементом ключа K по mod 2 32 . О подобной операции я описал выше, здесь тоже самое только показатель степени не «4», а «32» — результат этой операции в дальнейшем буду обозначать Smod.
- Полученный ранее результат Smod делим на четырех битные элементы s7,s6,s5,s4,s3,s2,s1,s0 и подаем в функцию замены. Замена происходит следующим образом: выбирается элемент Smod — s i , с начала начинаем с младшего элемента, и заменяем значением из таблицы замен по i — той строке и столбцу, на который указывает значение элемента s i . Переходим к s i +1 элементу и поступаем аналогичным образом и продолжаем так, пока не заменим значение последнего элемента Smod – результат этой операции будем обозначать как, Ssimple.
- В этой операции значение Ssimple сдвигаем циклически влево на 11 бит и получаем Srol.
- Выбираем вторую часть блока L и складываем по mod 2 с Srol, в итоге имеем Sxor.
- На этой стадии часть блока L становится равным значению части R, а часть R в свою очередь инициализируется результатом Sxor и на этом функция основного шага завершена!
3.3 Базовые циклы: “32-З”, “32-Р”.
Для того чтобы зашифровать информацию надо разбить ее на блоки размером в 64 бита, естественно последний блок может быть меньше 64 битов. Этот факт является ахиллесовой пятой данного метода «простая замена». Так как его дополнение до 64 бит является очень важной задачей по увеличению криптостойкости шифрограммы и к этому чувствительному месту, если оно присутствует в массиве информации, а его может и не быть (к примеру, файл размером в 512 байт!), следует отнестись с большой ответственностью!
После того как вы разбили информацию на блоки, следует разбить ключ на элементы:
K = k1,k2,k3,k4,k5,k6,k7,k8
Само шифрование заключается в использовании, так называемых – базовых циклов. Которые в свою очередь включают в себя n – ое количество основных шагов криптопреобразования.
Базовые циклы имеют, как бы это сказать, маркировку: n – m. Где n – количество основных шагов криптопреобразования в базовом цикле, а m – это «тип» базового цикла, т.е. о чем идет речь, о «З» ашифровывании или «Р» асшифровывании данных.
Базовый цикл шифрования 32–З состоит из 32-х основных шагов криптопреобразования. В функцию реализующую действия шага подают блок N и элемент ключа К причем, первый шаг происходит с к1, второй над полученным результатом с элементом к2 и т.д. по следующей схеме:
k1,k2,k3,k4,k5,k6,k7,k8,k1,k2,k3,k4,k5,k6,k7,k8,k1,k2,k3,k4,k5,k6,k7,k8k8,k7,k6,k5,k4,k3,k2,k1
Процесс расшифровывания 32–Р происходит аналогичным образом, но элементы ключа подаются в обратной последовательности:
k1,k2,k3,k4,k5,k6,k7,k8,k8,k7,k6,k5,k4,k3,k2,k1,k8,k7,k6,k5,k4,k3,k2,k1,k8,k7,k6,k5,k4,k3,k2,k1
Практика.
После того как мы познакомились с теорией о том, как шифровать информацию настало посмотреть, как же происходит шифрование на практике.
Исходные данные:
Возьмем блок информации N = 0102030405060708h, здесь части L и R равны:
L = 01020304h, R =05060708h, возьмем ключ:
K = ‘as28 zw37q839 7342ui23 8e2twqm2 ewp1’ (это ASCII – коды, для того, чтобы посмотреть шестнадцатеричное представление, можно открыть этот файл в режим просмотра в Total Commander нажав на клавишу «F3 » и далее клавишу «3 »). В этом ключе значения элементов будут:
k1 = ‘as28’, k2 = ‘zw37’, k3 = ‘q839’, k4 = ‘7342’
k5 = ‘ui23’, k6 = ‘8e2t’, k7 = ‘wqm2’, k8 = ‘ewp1’
Также возьмем следующую таблицу замен:
Рис. 3
Здесь строки нумеруются от 0 до 7, столбцы от 0 до F.
Предупреждение: Вся информация, в том числе и ключ с таблицей замен взята в качестве примера для рассмотрения алгоритма!
Используя «Исходные данные», необходимо получить результат действия основного шага криптопреобразования.
- Выбираем часть R = 05060708h и элемент ключа k1 = ‘as28’, в шестнадцатеричном виде элемент ключа будет выглядеть так: 61733238h. Теперь же делаем операцию суммирования по mod 2 32:
Рис. 4
Как видно на рисунке у нас не произошло переноса в 33 бит помеченный красным цветом и с показателем степени «32 ». А если бы у нас были бы другие значения R и элемента ключа – это вполне могло бы произойти, и тогда бы мы его проигнорировали, и в дальнейшем использовали только биты, помеченные желтым цветом.
Такую операцию я выполняю командой ассемблера add :
; eax = R, ebx = ‘as28’
Результат этой операции Smod = 66793940h
- Теперь самая заковыристая операция, но если присмотреться по внимательней, то она уже не такая страшная, как кажется в первое время. Представим Smod в следующем виде:
РИСУНОК НЕ СОХРАНЕН
Рис. 5
Я постарался наглядно представить элементы Smod на рисунке, но все равно поясню:
s0 = 0, s1 = 4, s2 = 9 и т.д.
Теперь начиная с младшего элемента s0, производим замену. Вспоминая пункт «3.2 Основной шаг криптопреобразования » i – строка, s i – столбец, ищем в нулевой строке и нулевом столбце значение:
Рис.6
Таким образом, текущее значение Smod, не 66793940 h, а 66793945 h.
Приступаем заменять s1, т.е. четверку. Используя первую строку и четвертый столбец (s1= 4!). Глядим на рисунок:
Рис. 7
Теперь уже значение Smod, не 6679394 5h, 6679392 5h. Я предполагаю, что теперь алгоритм замены читателю понятен, и я могу сказать, что после конечный результат Ssimple будет иметь следующее значение – 11e10325h.
О том, как это проще всего реализовать в виде команд ассемблера я расскажу позже в следующем пункте, после того, как расскажу о расширенной таблице.
- Полученное значение Ssimple мы должны сдвинуть на 11 бит влево.
Рис. 8
Как видно это действие довольно простое, и реализуется одной командой языка ассемблера – rol и результат этой операции Srol равен 0819288Fh.
- Теперь же остается часть L нашего блока информации поXORить со значением Srol. Я беру калькулятор от w2k sp4 и получаю Sxor = 091b2b8bh.
- Это действие итоговое и мы просто присваиваем, чисти R значение части L, а часть L инициализируем значением Sxor.
Конечный результат:
L = 091b2b8bh, R = 01020304h
4.2 Увеличения быстродействия алгоритма
Теперь же поговорим об оптимизации алгоритма по скорости. При процессе реализации, какого либо проекта, приходится учитывать, что программа, которая работает с регистрами чаще, чем с памятью работает наиболее быстрее и здесь это суждение тоже очень важно, т.к. над одним блоком информации целых 32 действия шифрации!
Когда я реализовывал алгоритм шифрования в своей программе, я поступил следующим образом:
- Выбрал часть блока L в регистр eax, а R в edx.
- В регистр esi инициализировал адресом расширенного ключа, об этом ниже.
- В регистр ebx присваивал значение адреса расширенной таблицы замен, об этом тоже ниже
- Передавал информацию пунктов 1,2, 3 в функцию базового цикла 32 – З или 32 – Р, в зависимости от ситуации.
Если посмотреть на схему подачи элементов ключа в пункте «Базовые циклы: “32-З”, “32-Р” », то наш ключ для базового цикла 32 – З можно представить в следующем:
К 32-З =
‘as28’,‘zw37’,‘q839’,‘7342’,‘ui23’,‘8e2t’,‘wqm2’,‘ewp1’,
‘as28’,‘zw37’,‘q839’,‘7342’,‘ui23’,‘8e2t’,‘wqm2’,‘ewp1’,
‘ewp1’,‘wqm2’,‘8e2t’,‘ui23’,‘7342’,‘q839’,‘zw37’,‘as28’
Т.е. с начала идут k1,k2,k3,k4,k5,k6,k7,k8 — ‘ as28’, ‘ zw37’, ‘ q839’, ‘7342’, ‘ ui23’, ‘8 e2 t’, ‘ wqm2’, ‘ ewp1’ три раза эта последовательность повторяется. Затем элементы идут в обратном порядке, т.е.: k8,k7,k6,k5,k4,k3,k2,k1 — ‘ewp1’, ‘wqm2’, ‘8e2t’,‘ui23’,‘7342’,‘q839’,‘zw37’,‘as28’ .
Я заранее расположил в массиве элементы в том порядке, как они должны подаваться в 32 – З. Тем самым я увеличил память, требуемую под ключ, но избавил себя от некоторых процессов мышления, которые мне были не нужны, и увеличил скорость работы алгоритма, за счет уменьшения времени обращения к памяти! Здесь я описал только ключ для 32 – З, для цикла 32 – Р я поступил аналогично, но используя другую схему подачи элементов, которую я тоже описывал в пункте «Базовые циклы: “32-З”, “32-Р ».
Настало время описать реализацию работы функции замен, как я обещал выше. Я не мог описать ранее, т.к. это требует ввода нового понятия – расширенная таблица замен. Я не смогу вам объяснить, что это такое. Вместо этого я вам покажу ее, а вы уж сами сформулируйте для себя, что же это такое – расширенная таблица замен?
Итак, для того чтобы разобраться, что такое расширенная таблица замен нам понадобится таблица замен, для примера возьму ту, что изображена на рис. 3.
К примеру, нам потребовалось заменить, число 66793940h. Представлю его в следующем виде:
РИСУНОК НЕ СОХРАНЕН
Рис. 9
Теперь если взять элементы s1,s0, т.е. младший байт, то результат функции замены будет равен 25h! Почитав статью Андрея Винокурова, которую я привел в пункте «Список используемой литературу », вы действительно обнаружите, что если взять две строки можно получить массив, позволяющий быстро находить элементы замены с помощью команды ассемблера xlat. Говорят можно и другим способом более быстрым, но Андрей Винокуров потратил на исследование быстрых алгоритмов для реализации ГОСТа около четырех лет! Думаю, не стоит изобретать велосипед, когда он уже есть.
Итак, о массиве:
Возьмем две первые строки нулевую и первую, создадим массив на 256 байт. Теперь наблюдаем одну особенность, что если надо преобразовать 00h, то результат будет 75h (опираемся на рис.3) – кладем это значение в массив на смещение 00h. Берем значение 01h, результат функции замен 79h, кладем его в массив на смещение 01 и так далее до 0FFh, которое нам даст 0FCh, которое мы положим в массив по смещение 0FFh. Вот мы и получили расширенную таблицу замен для первой группы строк: первой и нулевой. Но еще есть три группы: вторая стр.2, стр.3, третья стр.4, стр. 5, четвертая стр.6, стр.7. С этим тремя группами поступаем тем же способом, что и с первой. Результат – расширенная таблица замен!
Теперь можно реализовать алгоритм, который будет производить замену. Для этого берем исходные коды, которые выложил Андрей Винокуров на своей страничке, смотри «Список используемой литературы ».
lea ebx,extented_table_simple
mov eax,[положить число которое нужно заменить]
add ebx,100h ;переход к двум следующим узлам
sub ebx,300h ; чтобы в дальнейшем ebx показывал на таблицу
Теперь еще одна особенность, предыдущими действиями мы не только заменили, но и сдвинули число на 8 бит влево! Нам остается только сдвинуть число еще на 3 бита влево:
и мы получаем результат операции rol eax,11!
Больше я ничего не могу добавить по оптимизации, единственное, что могу подчеркнуть то, что я говорил выше – используйте регистры чаще, чем обращение к памяти. Думаю эти слова только для новичков, опытные и без моих слов это прекрасно понимают:).
Требования к ключевой информации.
Как сказано в статье Андрея Винокурова ключ выбирают по двум критериям:
— критерий равновероятного распределения битов между значениями 1 и 0. Обычно в качестве критерия равновероятного распределения битов – выступает критерий Пирсона («хи-квадрат»).
Это значит ключом, в принципе может любое число. То есть при формировании очередного бита ключа вероятность его инициализации единицей или нулем 50/50!
Прошу заметить, что ключ из восьми элементов, каждый по 32 бита, таким образом всего в ключе 32*8 = 256 битов и количество возможных ключей 2 256 ! Тебя это не поражает? 🙂
— критерий серий.
Если мы посмотрим на наш ключ, который я привел в пункте «4.1 Реализация основного шага криптопреобразования », то вы заметите, что справедлива следующая запись:
Рис. 10
Одной фразой значение k 1 не должно повториться не в k 2 , не в каком либо другом элементе ключа.
То есть ключ, который мы выбрали в качестве рассмотрения алгоритма шифрования, вполне соответствует двум приведенным выше критериям.
Теперь про выбор таблицы замен:
Теперь же поговорим о том, как правильно выбрать таблицу замен. Основное требование к выбору таблиц замен – это явление «неповторяемости» элементов, каждый из которых размером в 4 бита. Как вы уже видели выше, каждая строка таблицы замен состоит из значений 0h, 1h, 2h, 3h, …, 0fh. Так вот основное требование гласит о том, что в каждой строке есть значения 0h, 1h, 2h, … , 0fh и каждое такое значение в одном экземпляре. К примеру, последовательность:
1 2 3 4 5 6 7 8 9 A B C D E F
Вполне соответствует этому требованию, но все же! Такую последовательность в качестве строки выбирать не рекомендуется. Так как если вы подадите значение на вход функции, которая опирается на такую строку, то на выходе вы получите такое же значение! Не верите? Тогда возьмите число 332DA43Fh и восемь таких строк, в качестве таблицы замен. Проведите операцию замены, и уверяю вас, на выходе вы получите число 332DA43Fh! То есть такое же, что вы подали на вход операции! А это не является признаком хорошего тона при шифровании, да и являлось ли? 🙂
Это было одно требование, следующий критерий говорит о том, что – каждый бит выходного блока должен быть статистически независим от каждого бита входного блока!
Как это выглядит проще? А вот как, к примеру, мы выбрали из приведенного выше числа элемент s0 = 0Fh, 01111b. Вероятность того, что мы сейчас заменим первый бит единицей или нулем равна 0,5! Вероятность замены второго, третьего и четвертого бита, каждый бит, рассматриваем по отдельности, единицами или нулями тоже равна 0, 5. При выборе s1 = 0Eh, вероятность того, что мы нулевой бит, а это «0», заменим нулем или единицей тоже равна – 0,5! Таким образом, согласно этому критерию между заменой нулевых битов элементов s0, s1 нет никакой закономерности! Да, вы могли заменить единицами, но вы также могли поставить и нули. 🙂
Для оценки таблицы по этому критерию можно построить таблицу коэффициентов корреляции, рассчитанные по формуле:
— если p = 1, то значение бита j на выходе равно значению бита i на входе при любых комбинациях бит на входе;
— если p = -1, то значение бита j на выходе всегда является инверсией входного бита i;
— если p = 0, то выходной бит j с равной вероятностью принимает значения 0 и 1 при любом фиксированном значении входного бита i.
Возьмем пример одной строки:
| D | B | 4 | 1 | 3 | F | 5 | 9 | 0 | A | E | 7 | 6 | 8 | 2 | C | |
Разложим на «составляющие»:
Рассчитаем один коэффициент по формуле приведенной выше. Чтобы проще было понять, как это делается, поясню более подробно:
— берем 0-й бит 0-ого числа (0) на входе и 0-й бит 0-ого числа на выходе (1) проводим операцию 0 XOR 1 = 1.
— берем 0-й бит 1-ого числа (1) на входе и 0-й бит 1-ого числа на выходе (1) проводим операцию 1 XOR 1 = 0.
— берем 0-й бит 2-ого числа (0) на входе и 0-й бит 2-ого числа на выходе (0) проводим операцию 0 XOR 0 = 0.
— берем 0-й бит 3-ого числа (1) на входе и 0-й бит 3-ого числа на выходе (1) проводим операцию 1 XOR 1 = 0.
Проведя последовательно операции XOR в такой последовательности, подсчитываем количество всех ненулевых значений, получаем значение 6. Отсюда P 00 = 1-(6/2 4-1) = 0,25. Итак, выяснилось, что значение бита 0 на выходе равно значению бита 0 на входе в 4-х случаях из 16-ти;
Итоговая таблица коэффициентов:
Таблица коэффициентов будет следующая (кому не лениво может пересчитать)
| Вход | |||||
| Выход | 0 | 1 | 2 | 3 | |
| 0 | -0,25 | 0,00 | 0,00 | 0,00 | |
| 1 | 0,00 | 1,00 | 0,00 | 0,00 | |
| 2 | 0,00 | 0,00 | 1,00 | 0,00 | |
| 3 | 0,00 | 0,00 | 0,00 | -0,50 | |
Ну, в этой таблице дела обстоят еще хуже – биты 1 и 2 группы остаются неизменными! Криптоаналитику есть, где развернуться 🙂 С учетом всех этих требований простым перебором («в лоб») были найдены таблицы перестановки соответствующие указанной теории (на сегодняшний день – 1276 сочетаний) Вот некоторые из них:
| 09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B |
| 00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02 |
| 06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E |
| 04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05 |
| 04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00 |
| 07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05 |
| 06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07 |
| 0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D |
| 04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08 |
| 00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02 |
| 0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D |
| 0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02 |
| 0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E |
| 0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E |
| 02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03 |
Список использованной литературы.
- Статья Андрея Винокурова:
Алгоритм шифрования ГОСТ 28147-89, его использование и реализация
для компьютеров платформы Intel x86.
(можно найти по адресу: http://www.enlight.ru/crypto/frame.htm).
Тут же и исходные коды, по реализации алгоритма шифрования.
- Статья Хорста Файстеля:
Криптография и Компьютерная безопасность.
(можно найти по тому же адресу что и предыдущую статью)
- Ross N. Williams:
Элементарное руководство по CRC алгоритмам обнаружения ошибок
Выложена на сайте www. wasm. ru .
Благодарности.
Хотелось бы высказать благодарность всем посетителям форума www.wasm.ru. Но особо бы хотелось бы поблагодарить ChS, который в настоящий момент известен, как SteelRat, он помог мне понять такие вещи, чего я бы, наверное, никогда бы не понял, а так же помощь при написании пункта: «Требования к ключевой информации », основной часть данного пункта была написана им. Также глубоко признателен сотруднику КГТУ им. А.Н. Туполева Аникину Игорю Вячеславовичу и грех было бы не отметить Криса Касперски, за то, что он есть и Volodya / wasm.ru за его наставления. Ох, и достается мне от него:). Так же хочу отметить Sega-Zero / Callipso зато, что донес до моего разума некоторые математические дебри.
Это, пожалуй, все, что я хотел бы сказать вам.
Буду, признателен за критику или вопросы, связанные с этой статьей или просто советы. Мои контактные данные: [email protected], ICQ – 337310594.
С уважением Evil`s Interrupt.
P.S.: Этой статьей я не старался кого-то перещеголять. Она была написана с умыслом, облегчить изучение ГОСТа и если у вас получились трудности, то это не значит, что я повинен в этом. Будь разумны, и наберитесь терпения, всего вам доброго!
В нашей стране установлен единый алгоритм криптографического представления данных для систем обработки информации в сетях ЭВМ, отдельных вычислительных комплексов и ЭВМ, который определяется ГОСТ 28147-89 .
Этот алгоритм криптографического преобразования данных представляет собой 64-битовый блочный алгоритм с 256-битовым ключом, предназначен для аппаратной и программной реализации, удовлетворяет криптографическим требованиям и не накладывает ограничений на степень секретности защищаемой информации.
При описании алгоритма используются следующие обозначения:
L и R - последовательности битов;
LR - конкатенация последовательностей L и R, в которой биты
последовательности R следуют за битами последовательности L;
(+) - поразрядное сложение по модулю 2 (операция "исключающее ИЛИ");
[+] - сложение 32-разрядных чисел по модулю 2 32 ;
{+} - сложение 32-разрядных чисел по модулю 2 32 -1.
Числа суммируются по следующему правилу:
A [+] B = A + B, если A + B < 2 32 ,
A [+] B = A + B - 2 32 , если A + B >= 2 32 .
A {+} B = A + B , если A + B < 2^32 - 1,
A {+} B = A + B - (2^32 - 1), если A + B >= 2^32 - 1.
Алгоритм предусматривает четыре режима работы:
В любом случае для шифрования данных используется 256-битовый ключ K, который представляется в виде восьми 32-битовых подключей K i:
K = K 7 K 6 K 5 K 4 K 3 K 2 K 1 K 0 .
Расшифрование выполняется по тому же ключу, что и шифрование, но этот
процесс является инверсией процесса шифрования данных.
Режим простой замены
Первый и самый простой режим - замена . Данные, подлежащие шифрованию, разбивают на 64-битовые блоки. Процедура шифрования блока открытых данных T 0 включает 32 цикла (j=1...32).
Блок T 0 разделяется на две последовательности по 32 бита: В(0)A(0), где В(0) - левые или старшие биты, A(0) - правые или младшие биты.
Эти последовательности вводят в накопители N 1 и N 2 перед началом первого цикла шифрования.
Первый цикл (j=1) процедуры шифрования 64-битового блока данных описывается следующими формулами:
Здесь i обозначает номер итерации (i = 1, 2,..., 32).
Функция f называется функцией шифрования. Ее аргументом является сумма по модулю 2 32 числа A(i), полученного на предыдущем шаге итерации, и числа X(j) ключа (размерность каждого из этих чисел равна 32 знакам).
Функция шифрования включает две операции над полученной 32-разрядной суммой. Первая операция называется подстановкой К. Блок подстановки К состоит из 8 узлов замены К(1) ... К(8) с памятью 64 бит каждый. Поступающий на блок подстановки 32-разрядный вектор разбивается на 8 последовательно идущих 4-х разрядных векторов, каждый из которых преобразуется в 4-х разрядный вектор соответствующим узлом замены, представляющим собой таблицу из 16 целых чисел в диапазоне 0...15.
Входной вектор определяет адрес строки в таблице, число из которой является выходным вектором. Затем 4-х разрядные выходные векторы последовательно объединяются в 32-разрядный вектор. Таблицы блока подстановки К содержит ключевые элементы, общие для сети ЭВМ и редко изменяемые.
Вторая операция - циклический сдвиг влево 32-разрядного вектора, полученного в результате подстановки К. 64-разрядный блок зашифрованных данных Т ш представляется в виде Т ш =A(32)B(32).
Остальные блоки открытых данных в режиме простой замены зашифровываются аналогично.
Следует иметь в виду, что режим простой замены допустимо использовать для
шифрования данных только в ограниченных случаях. К этим случаям относится
выработка ключа и зашифрование его с обеспечением имитозащиты (защиты от
навязывания ложных данных) для передачи по каналам связи или хранения в памяти
ЭВМ.
Режим гаммирования
Открытые данные, разбитые на 64-разрядные блоки Т(i) (i=1, 2,..., m, где m определяется обьемом шифруемых данных), зашифровываются в режиме гаммирования путем поразрядного сложения по модулю 2 с гаммой шифра Г ш, которая вырабатывается блоками по 64 бит, то есть Г ш = (Г(1),Г(2),...,Г(i),...,Г(m)).
Уравнение зашифрования данных в режиме гаммирования может быть представлено в следующем виде:
Ш(i) = A (Y(i-1) [+] C2, Z(i-1) {+} C1) (+) T(i) = Г(i) (+) T(i) .
Здесь Ш(i) - 64-разрядный блок зашифрованного текста,
A - функция шифрования в режиме простой замены (аргументами этой функции
являются два 32-разрядных числа),
С1 и С2 - константы, заданные в ГОСТ 28147-89,
Y(i) и Z(i) - величины, которые определяются итерационно по мере формирования
гаммы следующим образом:
(Y(0), Z(0)) = A(S), где S - 64-разрядная двоичная последовательность
(синхропосылка);
(Y(i), Z(i)) = (Y(i-1) [+] C2, Z(i-1) {+} C1) для i = 1, 2,...,m.
Расшифрование данных возможно только при наличии синхропосылки, которая не
является секретным элементом шифра и может храниться в памяти ЭВМ или
передаваться по каналам связи вместе с зашированными данными.
Режим гаммирования с обратной связью
Режим гаммирования с обратной связью очень похож на режим гаммирования. Как в и режиме гаммирования открытые данные, разбитые на 64-разрядные блоки Т(i) (i=1, 2,..., m , где m определяется обьемом шифруемых данных), зашифровываются путем поразрядного сложения по модулю 2 с гаммой шифра Г ш, которая вырабатывается блоками по 64 бит:
Г ш = (Г(1),Г(2),...,Г(i),...,Г(m)).
Число двоичных разрядов в блоке Т(m) может быть меньше 64, при этом неиспользованная для шифрования часть гаммы шифра из блока Г(m) отбрасывается.
Уравнение зашифрования данных в режиме гаммирования с обратной связью может быть представлено в следующем виде:
Здесь Ш(i) - 64-разрядный блок зашифрованного текста,
A - функция шифрования в режиме простой замены. Аргументом функции на первом шаге итеративного алгоритма является 64-разрядная синхропосылка, а на всех последующих - предыдущий блок зашифрованных данных Ш(i-1).
Bыработки имитовставки
Процесс выработки имитовстаки единообразен для любого из режимов шифрования данных.
Имитовставка - это блок из р бит (имитовставка Ир), который вырабатывается либо перед шифрованием всего сообщения, либо параллельно с шифрованием по блокам. Первые блоки открытых данных, которые участвуют в выработке имитовставки, могут содержать служебную информацию (например, адресную часть, время, синхропосылку) и не зашифровываться. Значение параметра р (число двоичных разрядов в имитовставке) определяется криптографическими требованиями с учетом того, что вероятность навязывания ложных помех равна 1/2^р.
Для получения имитовставки открытые данные представляются в виде 64-разрядных блоков Т(i) (i = 1, 2,..., m , где m определяется объемом шифруемых данных). Первый блок открытых данных Т(1) подвергается преобразованию, соответствующему первым 16 циклам алгоритма зашифрования в режиме простой замены. Причем в качестве ключа для выработки имитовставки используется ключ, по которому шифруются данные.
Полученное после 16 циклов работы 64-разрядное число суммируется по модулю 2 со вторым блоком открытых данных Т(2). Результат суммирования снова подвергается преобразованию, соответствующему первым 16 циклам алгоритма зашифрования в режиме простой замены. Полученное 64-разрядное число суммируется по модулю 2 с третьим блоком открытых данных Т(3) и т.д. Последний блок Т(m) при необходимости дополненный до полного 64-разрядного блока нулями, суммируется по модулю 2 с результатом работы на шаге m-1, после чего зашифровывается в режиме простой замены по первым 16 циклам работы алгоритма. Из полученного 64-разрядного числа выбирается отрезок Ир длиной р бит.
Имитовставка Ир передается по каналу связи или в память ЭВМ после зашифрованных данных. Поступившие зашифрованные данные расшифровываются, и из полученных блоков открытых данных T(i) вырабатывается имитовставка Ир", которая затем сравнивается с имитовставкой Ир, полученной из канала связи или из памяти ЭВМ. В случае несовпадения имитовставок все расшифрованные данные считают ложными.
Известный исследователь, основоположник алгебраического криптоанализа Николя Куртуа утверждает, что блочный шифр ГОСТ, который в ближайшее время должен был стать международным стандартом, фактически взломан и ожидает в дальнейшем множества публикаций, которые должны развить его идеи о нестойкости этого алгоритма.
Далее приведены краткие выдержки из этой работы, которую можно рассматривать как алармистский выпад в разгаре международной стандартизации (схожими преувеличениями автор был известен и в отношении AES, однако его работы тогда оказали большое теоретическое влияние на криптоанализ, но так и не привели на сегодняшний момент к практическим атакам на сам AES). Но, возможно, это и реальное предупреждение о начале этапа "пикирующего в штопор самолёта", которое может закончиться крахом национального стандарта шифрования, как это было с алгоритмом хэширования SHA-1 и алгоритмом хэширования "де-факто" MD5.
ГОСТ 28147-89 был стандартизирован в 1989 году и впервые стал официальным стандартом защиты конфиденциальной информации, но спецификация шифра оставалась закрытой. В 1994 году стандарт был рассекречен, опубликован и переведён на английский язык. По аналогии с AES (и в отличие от DES), ГОСТ допущен к защите секретной информации без ограничений, в соответствии с тем, как это указано в российском стандарте. Т.о. ГОСТ — это не аналог DES, а конкурент 3-DES с тремя независимыми ключами или AES-256. Очевидно, что ГОСТ — это достаточно серьёзный шифр, удовлетворяющий военным критериям, созданный с расчётом на самые серьёзные применения. По крайней мере два набора S-блоков ГОСТа были идентифицированы на основе приложений, используемых российскими банками. Эти банки нуждаются в проведении секретных коммуникаций с сотнями филиалов и защите миллиардов долларов от мошеннических хищений.
ГОСТ — это блочный шифр с простой структурой Файстеля, с размером блока 64 бита, 256-битным ключом и 32 раундами. Каждый раунд содержит сложение с ключом по модулю 2^32, набор из восьми 4-битных S-блоков и простой циклический сдвиг на 11 битов. Особенностью ГОСТа является возможность хранения S-блоков в секрете, что можно представить как второй ключ, увеличивающий эффективный ключевой материал до 610 битов. Один набор S-блоков был опубликован в 1994 году в рамках спецификации хэш-функции ГОСТ-Р 34.11-94 и, как писал Шнайер, использовался Центральным Банком Российской Федерации. Он также вошёл в стандарт RFC4357 в части "id-GostR3411-94-CryptoProParamSet". В исходных кодах в конце книги Шнайера была ошибка (в порядке S-блоков). Наиболее точную эталонную реализацию исконно российского происхождения сейчас можно встретить в библиотеке OpenSSL. Если где-то применяются секретные S-блоки, то они могут быть извлечены из программных реализаций и из микросхем, по факту чего были опубликованы соответствующие работы.
ГОСТ — серьёзный конкурент
В дополнение к очень большому размеру ключа, GOST имеет значительно более низкую стоимость исполнения по сравнению с AES и какими-либо ещё сходными системами шифрования. В действительности, он стоит намного меньше AES, которому требуется в четыре раза больше аппаратных логических вентилей ради значительно меньшего заявленного уровня безопасности.
Неудивительно, что ГОСТ стал интернет-стандартом, в частности, он включён во многие криптобиблиотеки, такие как OpenSSL и Crypto++, и становится всё популярнее за пределами страны своего происхождения. В 2010 году ГОСТ был заявлен на стандартизацию ISO как всемирный стандарт шифрования. Крайне малое количество алгоритмов смогли стать международными стандартами. ISO/IEC 18033-3:2010 описывает следующие алгоритмы: четыре 64-битных шифра — TDEA, MISTY1, CAST-128, HIGHT — и три 128-битных шифра — AES, Camellia, SEED. ГОСТ предлагается добавить в этот же самый стандарт ISO/IEC 18033-3.
Впервые в истории промышленной стандартизации мы имеем дело со столь конкурентоспособным алгоритмом в терминах оптимальности между стоимостью и уровнем безопасности. ГОСТ имеет за собой 20 лет попыток криптоанализа и до недавних пор его безопасность военного уровня не подвергалась сомнению.
Как стало недавно известно автору из приватной переписки, большинство стран высказались против ГОСТа на голосовании ISO в Сингапуре, однако результаты этого голосования будут ещё рассматриваться на пленарном заседании ISO SC27, так что ГОСТ всё ещё находится в процессе стандартизации на момент публикации этой работы.
Мнения экспертов по поводу ГОСТ
Ничто из имеющихся сведений и литературы по поводу ГОСТа не даёт оснований полагать, что шифр может быть небезопасным. Наоборот, большой размер ключа и большое число раундов делают ГОСТ, на первый взгляд, подходящим для десятилетий использования.
Все, кому знаком закон Мура, понимают, что, в теории, 256-битные ключи останутся безопасными по крайней мере 200 лет. ГОСТ был широко исследован ведущими экспертами в области криптографии, известными в области анализа блочных шифров, такими как Шнайер, Бирюков, Данкельман, Вагнер, множеством австралийских, японских и российских учёных, экспертами по криптографии от ISO, и все исследователи высказывались, что всё выглядит так, что он он может быть или должен быть безопасным. Хотя широкого понимания достигло мнение, что сама по себе структура ГОСТа крайне слаба, например, по сравнению с DES, в частности, диффузия не настолько хороша, однако это всегда обуславливалось тем, что это должно компенсироваться большим числом раундов (32), а также дополнительной нелинейностью и диффузией, обеспечиваемой сложением по модулю.
Бирюков и Вагнер писали: "Большое число раундов (32) и хорошо изученная конструкция Фейстеля, сочетаемая с последовательными Шенноновскими подстановками-перестановками, обеспечивают солидную основу безопасности ГОСТ". В той же самой работе мы читаем: "после значительных затрат времени и усилий, никакого прогресса в криптоанализе стандарта в открытой литературе достигнуто не было". Таким образом, не было никаких существенных атак, которые позволяли бы дешифрование или восстановление ключа в реалистичном сценарии, когда ГОСТ используется в шифровании со множеством разных случайных ключей. В противоположность этому, известно очень много работ по атакам на слабые ключи в ГОСТ, атаки со связанными ключами, атаки на восстановление секретных S-блоков. На Crypto-2008 был представлен взлом хэш-функции, основанной на этом шифре. Во всех атаках атакующий имеет значительно больший уровень свободы, чем ему обычно допускается. В традиционных применениях шифрования с использованием случайно выбираемых ключей до настоящего момента никаких серьёзных криптографических атак на ГОСТ найдено не было, что в 2010 году выражалось итоговой фразой: "несмотря на существенные усилия криптоаналитиков за прошедшие 20 лет, ГОСТ всё ещё не взломан" (Axel Poschmann, San Ling, and Huaxiong Wang: 256 Bit Standardized Crypto for 650 GE GOST Revisited, In CHES 2010, LNCS 6225, pp. 219-233, 2010).
Линейный и дифференциальный анализ ГОСТ
В широкоизвестной книге Шнайера мы читаем: "Против дифференциального и линейного криптоанализа ГОСТ вероятно более устойчив, чем DES". Основную оценку безопасности ГОСТа дали в 2000 году Габидулин и др. Их результаты очень впечатляющи: при заложенном уровне безопасности 2^256, достаточно пяти раундов для защиты ГОСТа от линейного криптоанализа. Более того, даже при замене S-блоков на тождественные и единственной нелинейной операции шифра — сложения по модулю 2^32 — шифр всё равно стоек против линейного криптоанализа после 6 раундов из 32. Дифференциальный криптоанализ ГОСТа выглядит сравнительно более лёгким и привлекает больше внимания. Для 2^128 уровня безопасности исследователи (Vitaly V. Shorin, Vadim V. Jelezniakov and Ernst M. Gabidulin: Linear and Differential Cryptanalysis of Russian GOST, Preprint submitted to Elsevier Preprint, 4 April 2001) предполагали достаточную стойкость на уровне 7 раундов. По их утверждению, взлом ГОСТа более чем на пяти раундах "крайне труден". Более того, двое японских исследователей показали, что классическая прямая дифференциальная атака с одной дифференциальной характеристикой имеет крайне малую вероятность для прохождения через большое число раундов. На основе факта изучения достаточно "хорошей" итеративной дифференциальной характеристики для ограниченного числа раундов (которая сама по себе имеет вероятность прохождения не лучше 2-11.4 на раунд), получено значения множества подходящих ключей менее половины. Для полнораундового ГОСТа такая атака с единственной характеристикой будет работать лишь с ничтожно малой частью ключей порядка 2-62 (и даже в этой малой части она будет иметь вероятность прохождения не более 2-360).
Более сложные атаки включают множества дифференциалов, следующих определённым паттернам, например с использованием отдельных S-блоков, имеющих нулевые дифференциалы, в то время как на других битах имеются ненулевые. Речь об атаках-различителях, основанных на плохих диффузионных свойствах ГОСТа. Лучшая из таких атак работает против 17 раундов ГОСТа, зависит от ключа и имеет сама по себе на выходе крайне слабый различитель от случайных данных, чтобы его как-то можно было использовать для получения информации о ключе.
Атаки скольжения и отражения
Согласно Бирюкову и Вагнеру, структура ГОСТа, включающая обратный порядок подключей в последних раундах, делает его стойким против атак скольжения (т.н. "слайд-атаки"). Однако из-за наличия большой величины самоподобия в шифре, это позволяет проводить атаки инверсии ключей на комбинации неподвижных точек и свойства "отражения" (т.н. "рефлективные атаки") для определённых слабых ключей. Сложность этой атаки 2^192 и 2^32 подобранных открытых текстов.
Последние результаты
Новые атаки также используют отражение и фактически взломали ГОСТ, что и было представлено на конференции FSE 2011. Эти атаки также были открыты независимо автором данной работы. Атака требует 2^132 байтов памяти, что фактически хуже, чем более медленные атаки с меньшим требованием к памяти.
Множество новых атак на основе самоподобия работают против всех ключей ГОСТа и позволяют взламывать полнораундовый ГОСТ с 256-битным ключом, а не только для слабых ключей, как было ранее. Все эти атаки требуют значительно меньше памяти и они значительно быстрее.
Эти новые атаки могут рассматриваться как примеры новой общей парадигмы криптоанализа блочных шифров, называемой "редукция алгебраической сложности", с обобщением этих атак на множество частных случаев атак с известными неподвижными точками, скольжением, инволюциями и циклами. Важно, что среди семейства всех этих атак есть такие, которые позволяют проводить криптоанализ ГОСТ без всяких отражений и без каких-либо симметричных точек, которые проявляются в ходе вычислений. Одним из примеров является простая атака взлома ГОСТа без отражений в данной работе.
Алгебраический криптоанализ и атаки с небольшой сложностью данных на шифры с уменьшенным числом раундов
Алгебраические атаки на блочные и потоковые шифры могут быть представлены в виде проблемы решения большой системы Булевых алгебраических уравнений, которая следует геометрии и структуре частной криптографической схемы. Сама идея восходит к Шеннону. На практике была представлена для DES (впервые представлена автором данной работы) как метод формального кодирования и может взламывать 6 раундов всего на одном известном открытом тексте. Манипуляция с уравнениями происходит на основе алгоритмов XL, базисов Грёбнера, метода ElimLin, SAT-решателей.
На практике алгебраические атаки реализованы против очень малого числа раундов блочных шифров, но уже приводили к взломам потоковых шифров, также есть и успехи во взломе сверхлёгких шифров для микрооборудования. Из-за трудностей в объёмах памяти и оценках затрат на вычисления их комбинируют с другими атаками.
Как взломать ГОСТ?
Алгебраическая атака на полнораундовый ГОСТ более подробно представлена в рассматриваемой публикации. В предыдущей работе автор уже изложил 20 алгебраических атак на ГОСТ и ожидает большого их числа в ближайшем будущем. Атака, предложенная в данной работе — не лучшая из них, но открывает простой (по крайней мере для понимания криптографами) путь для последующих разработок для создания специфичной методологии к взлому ГОСТа.
Практический результат пока скромен: 2^64 известных открытых текста и 2^64 памяти для хранения пар "открытый текст/шифртекст" позволяют взломать ГОСТ в 2^8 быстрее, чем простой перебор. Но в плане криптоанализа это делает полностью справедливым утверждение о том, что "ГОСТ взломан".
Выводы
ГОСТ спроектирован на обеспечение военного уровня безопасности на 200 лет вперёд. Большинство ведущих экспертов, изучавших ГОСТ, приходили к соглашению о том, что "несмотря на значительные криптоаналитические усилия на протяжении 20 лет, ГОСТ всё ещё не взломан". В 2010 году ГОСТ продвигают в ISO 18033 в качестве мирового стандарта шифрования.
Основа идей об алгебраическом криптоанализе возникла более 60 лет назад. Но только лишь за последние 10 лет были разработаны эффективные программные средства (частичного) решения множества NP-полных проблем. Было взломано некоторое число потоковых шифров. Только один блочный шифр был взломан этим методом — сам по себе слабый KeeLoq. В этой работе автор взламывает важный, реально используемый шифр ГОСТ. Он отмечает, что это первый случай в истории, когда алгебраическим криптоанализом был взломан стандартизированный государственный шифр.
Простая атака "MITM с отражением" на ГОСТ уже представлена на конференции FSE 2011. В работе же, рассматриваемой в данной статье, представлена другая атака лишь для иллюстрации факта того, как много атак на ГОСТ уже появилось сейчас, многие из которых быстрее, а сама алгебраическая атака требует намного меньше памяти и открывает практически неисчерпаемое пространство возможностей для противника, атакующего шифр разными способами. Также в данной работе показано отсутствие необходимости использования свойства отражения для взлома.
Автор утверждает: очевидно, что ГОСТ имеет серьёзные изъяны и теперь не обеспечивает уровня стойкости, требуемого ISO. Множество атак на ГОСТ представлено в рамках подтверждения парадигмы редуцирования алгебраической сложности.
Напоследок исследователь особенно отмечает некоторые факты, которые пока недоступны читателю, но известны исследователю, являющиеся важными в ходе процесса стандартизации ISO. Данная атака — не просто "сертификационная" атака на ГОСТ, которая быстрее перебора грубой силой. Фактически, стандартизация ГОСТа сейчас была бы крайне опасной и безответственной. Это так потому, что некоторые из атак возможны к осуществлению на практике. Некоторые ключи ГОСТа на практике даже могут быть дешифрованы, будь они слабые ключи или ключи из частных реальных применений ГОСТа. В предыдущей работе автор приводит детальное рассмотрение случаев возможности практических атак. Важно также то, что "это первый случай в истории, когда серьёзный стандартизированный блочный шифр, созданный для защиты секретов военного уровня и предназначенный для защиты документов государственной тайны для правительств, крупных банков и других организаций, оказался взломан математической атакой".