). Одновременно с этим в российских СМИ и блогах российских пользователей растет число заметок о данном алгоритме: как освещающих различной степени достоверности результаты атак на российский стандарт, так и содержащих мнения о его эксплуатационных характеристиках. У авторов (а, следовательно, и читателей) данных заметок зачастую складывается впечатление, что отечественный алгоритм шифрования является морально устаревшим, медленным и обладающим уязвимостями, делающими его подверженным атакам в существенной мере больше, чем зарубежные алгоритмы шифрования с аналогичной длиной ключа. Данной серией заметок мы хотели бы в доступной форме рассказать о настоящем положении дел с российским стандартом. В первой части будут освещены все известные международной криптографической общественности атаки на ГОСТ 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 не позволяет определять ключ с трудоемкостью меньшей полного перебора.

Алгоритм ГОСТ 28147-89 и шифр «Магма» (ГОСТ Р 34.12-2015)

Общая схема алгоритма. Алгоритм, описанный ГОСТ 28147-89 «Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования», является отечественным стандартом симметричного шифрования (до 1 января 2016 г.) и обязателен для реализации в сертифицированных средствах криптографической защиты информации, применяемых в государственных информационных системах и, в некоторых случаях, в коммерческих системах. Сертификация средств криптографической защиты информации требуется для защиты сведений, составляющих государственную тайну РФ, и сведений, конфиденциальность которых требуется обеспечить согласно действующему законодательству. Также в Российской Федерации применение алгоритма ГОСТ 28147-89 рекомендовано для защиты банковских информационных систем.

Алгоритм ГОСТ 28147-89 (рис. 2.21) базируется на схеме Фейстеля и шифрует информацию блоками по 64 бит, которые разбиваются на два подблока по 32 бита (I, и R). Подблок R, обрабатывается функцией раундового преобразования, после чего его значение складывается со значением подблока Lj, затем подблоки меняются местами. Алгоритм имеет 16 или 32 раунда в зависимости от режима шифрования (вычисление имитовставки или другие режимы шифрования).

Рис. 2.21.

В каждом раунде алгоритма выполняются следующие преобразования.

1. Наложение ключа. Содержание подблока R i складывается по модулю 2 32 с ключом раунда К. Kj - это 32-битовая часть исходного ключа, используемая в качестве раундового. Алгоритм ГОСТ 28147-89 нс использует процедуру расширения ключа, исходный 256-битный ключ шифрования представляется в виде конкатенации (сцепления) восьми 32-битовых подключей (рис. 2.22): К 0 , К { , К т К, К А, К 5 , К 6 , К 7 .

В процессе шифрования используется один из этих подключей К

С 1-го по 24-й раунд - в прямой последовательности:

С 25-го но 32-й раунд - в обратной последовательности:

Рис. 2.22. Строение ключа шифрования алгоритма ГОСТ 28147-89

2. Табличная замена. После наложения ключа подблок R i разбивается на восемь частей но 4 бита, значение каждой из которых по отдельности заменяется в соответствии со своей таблицей замены (S-блоком). Всего используется восемь S-блоков - S 0 , S, S 2 , S 3 , S 4 , S 5 , S 6 , S 7 . Каждый S-блок алгоритма ГОСТ 28147-89 представляет собой вектор (одномерный массив) с ^элементами, пронумерованными от 0 до 15. Значениями S-блока являются 4-битовые числа, т.е. целые числа от 0 до 15.

Из таблицы S-блока берется элемент, порядковый номер которого совпадает со значением, пришедшим на вход подстановки.

Пример 2.6.

Пусть имеется S-блок следующего вида:

Пусть на вход этого S-блока подано значение 0100 2 = 4. Выходом S-блока будет 4-й элемент таблицы замен, т.е. 15 = 1111 2 (нумерация элементов начинается с нуля).

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

К сожалению, алгоритм ГОСТ 28147-89 имеет «слабые» таблицы замен, при использовании которых алгоритм может быть достаточно легко раскрыт криптоаналитическими методами. К числу «слабых» относится, например, тривиальная таблица замен, в которой вход равен выходу (табл. 2.16).

Таблица 2.16

Пример слабого S-блока

Считается, что конкретные значения таблиц замен должны храниться в секрете и являются долговременным ключевым элементом, т.е. действуют в течение гораздо более длительного срока, чем отдельные ключи. Однако секретные значения таблиц замен не являются частью ключа и не могут увеличить его эффективную длину.

Действительно, секретные таблицы замен могут быть вычислены с помощью следующей атаки, которую возможно применять на практике:

• устанавливается нулевой ключ и выполняется поиск «нулевого вектора», т.е. значения z = F(0), где F - функция раундового преобразования алгоритма. Это требует порядка 2 32 тестовых операций шифрования;
• с помощью нулевого вектора вычисляются значения таблиц замен, что занимает не более 2 11 операций.

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

Предполагается также, что таблицы замен являются общими для всех узлов шифрования в рамках одной системы криптографической защиты.

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

В современных алгоритмах S-блоки обычно представляют собой вектор (одномерный массив), содержащий 2" т- битовых элементов. Вход блока определяет номер элемента, значение которого служит выходом S-блока.

Для проектирования S-блоков был выдвинут целый ряд критериев. Таблица замен должна удовлетворять:

• строгому лавинному критерию;
• критерию независимости битов;
• требованию нелинейности от входных значений.

Для выполнения последнего требования было предложено задавать линейную комбинацию i битов (i = 1, ..., т) значений таблицы замен бентфункциями (англ, bent - отклоняющийся, в данном случае - от линейных функций). Бент-функции образуют специальный класс булевых функций, характеризующихся высшим классом нелинейности и соответствием строгому лавинному критерию.

В некоторых работах для S-блоков предлагается проверка выполнения гарантированного лавинного эффекта порядка у - при изменении одного входного бита меняется, по крайней мере, у выходных бит S-блока. Свойство гарантированного лавинного эффекта порядка у от 2 до 5 обеспечивает достаточно хорошие диффузионные характеристики S-блоков для любого алгоритма шифрования.

При проектировании достаточно больших таблиц замен могут быть использованы следующие подходы:

• случайный выбор (для S-блоков небольшого размера может привести к созданию слабых таблиц замен);
• случайный выбор с последующей проверкой на соответствие различным критериям и отбраковкой слабых S-блоков;
• ручной выбор (для S-блоков больших размеров слишком трудоемок);
• математический подход, например генерация с использованием бент- функций (этот подход применен в алгоритме CAST).

Можно предложить следующий порядок проектирования отдельных S- блоков алгоритма ГОСТ 28147-89:

• каждый S-блок может быть описан четверкой логических функций, каждая из функций должна иметь четыре логических аргумента;
• необходимо, чтобы эти функции были достаточно сложными. Это требование сложности невозможно выразить формально, однако в качестве необходимого условия можно потребовать, чтобы соответствующие логические функции, записанные в минимальной форме (т.е. с минимально возможной длиной выражения) с использованием основных логических операций, не были короче некоторого необходимого значения;
• отдельные функции, даже используемые в разных таблицах замен, должны различаться между собой в достаточной степени.

В 2011 г. предложена новая атака «рефлексивная встреча посередине», незначительно снижающая стойкость ГОСТ 28147-89 (с 2256 до 2225) . Лучший результата криптоанализа алгоритма по состоянию на 2012 г. позволяет снизить его стойкость до 2 192 , требуя относительно большого размера шифротекста и объема предварительно сформированных данных . Несмотря на предложенные атаки, на современном уровне развития вычислительной техники ГОСТ 28147-89 сохраняет практическую стойкость.

Шифр «Магма» (ГОСТ Р 34.12-2015). Стандарт ГОСТ 28147-89 действовал в России более 25 лет. За это время он показал достаточную стойкость и хорошую эффективность программных и аппаратных реализаций, в том числе и на низкоресурсных устройствах. Хотя и были предложены криптоаналитические атаки, снижающие оценки его стойкости (лучшая - до 2 192), они далеки от возможности практической реализации. Поэтому было принято решение о включении алгоритма ГОСТ 28147-89 во вновь разрабатываемый стандарт симметричного шифрования.

В шопе 2015 г. приняты два новых национальных криптографических стандарта: ГОСТ Р 34.12-2015 «Информационная технология. Криптографическая защита информации. Блочные шифры» и ГОСТ Р 34.13-2015 «Информационная технология. Криптографическая защита информации. Режимы работы блочных шифров», которые вступают в действие с 1 января 2016 г.

Стандарт ГОСТ Р 34.12-2015 содержит описание двух блочных шифров с длиной блока 128 и 64 бит. Шифр ГОСТ 28147-89 с зафиксированными блоками нелинейной подстановки включен в новый ГОСТ Р 34.12-2015 в качестве 64-битового шифра под названием «Магма» («Magma»).

Ниже приведены закрепленные в стандарте блоки замен:

Приведенный в стандарте набор S-блоков обеспечивает наилучшие характеристики, определяющие стойкость криптоалгоритма к дифференциальному и линейному криптоанализу.

По мнению технического комитета по стандартизации «Криптографическая защита информации» (ТК 26), фиксация блоков нелинейной подстановки сделает алгоритм ГОСТ 28147-89 более унифицированным и поможет исключить использование «слабых» блоков нелинейной подстановки. Кроме того, фиксация в стандарте всех долговременных параметров шифра отвечает принятой международной практике. Новый стандарт ГОСТ Р 34.12-2015 терминологически и концептуально связан с международными стандартами ИСО/МЭК 10116 «Информационные технологии. Методы обеспечения безопасности. Режимы работы для «-битовых блочных шифров» (ISO/IEC 10116:2006 Information technology - Security techniques - Modes of operation for an n-bit block cipher) и серии ИСО/МЭК 18033 «Информационные технологии. Методы и средства обеспечения безопасности. Алгоритмы шифрования»: ИСО/МЭК 18033-1:2005 «Часть 1. Общие положения» (ISO/IEC 18033-1:2005 Information technology - Security techniques - Encryption algorithms - Part 1: General) и ИСО/МЭК 18033-3:2010 «Часть 3. Блочные шифры» (ISO/IEC 18033-3:2010 (Information technology - Security techniques - Encryption algorithms - Part 3: Block ciphers)).

В стандарт ГОСТ P 34.12-2015 включен также новый блочный шифр («Кузнечик») с размером блока 128 бит. Ожидается, что этот шифр будет устойчив ко всем известным на сегодняшний день атакам на блочные шифры.

Режимы работы блочных шифров (простой замены, гаммирования, гам- мирования с обратной связью по выходу, гаммирования с обратной связью по шифротексту, простой замены с зацеплением и выработки имитовстав- ки) выведены в отдельный стандарт ГОСТ Р 34.13-2015, что соответствует принятой международной практике. Эти режимы применимы как к шифру «Магма», так и к новому шифру «Кузнечик».

• Осуществляется побитовый циклический сдвиг влево на 11 битов. Расшифрование осуществляется по этой же схеме, но с другим расписаниемиспользования ключей: с 1-го по 8-й раунд расшифровки - в прямом порядке: с 9-го по 32-й раунд расшифровки - в обратном порядке: По сравнению с шифром DES у ГОСТ 28147-89 есть следующие достоинства: существенно более длинный ключ (256 бит против 56 у шифра DES),атака на который путем полного перебора ключевого множества на данныймомент представляется невыполнимой; простое расписание использования ключа, что упрощает реализациюалгоритма и повышает скорость вычислений. Проектирование S-блоков ГОСТ 28147-89. Очевидно, что схема алгоритма ГОСТ 28147-89 весьма проста. Это означает, что наибольшая нагрузка по шифрованию ложится именно на таблицы замен. Значения таб-
• Панасепко С. П. Алгоритмы шифрования: специальный справочник. СПб.: БХВ-Петер-бург, 2009.
• Kara О. Reflection Attacks on Product Ciphers. URL: http://eprint.iacr.org/2007/043.pdf
• Российский стандарт шифрования: стойкость снижена. URL: http://cryptofaq.ru/index.php/2010-12-23-18-20-21/2010-12-23-18-22-09/90-2011-02-01-07-47-27
• Ачексеев Е. К., Смышляев С. В. ГОСТ 28147-89: «Не спеши его хоронить».

«Пока ты жив, не умирай, на этот мир взгляни.
У многих здесь душа мертва – они мертвы внутри.
Но ходят и смеются, не зная, что их нет,
Не торопи свой смертный час» – она сказала мне.

Ария, «Там высоко»

1. Введение

1. Предварительные сведения о блочных шифрах

2.1 Сети Файстеля.
2.2 Блочный шифр ГОСТ 28147-89

1. Теоретический минимум

3.1 Ключевая информация
3.2 Основной шаг криптопреобразования

3.3 Базовые циклы: “ 32-З ” , “ 32-Р ” .

1. Практика

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

Получить шифрограмму

1. (R + K) mod 2 4 = Smod, Smod = 0100b
2. (Smod + L) mod 2 = Sxor, Sxor = 1010b
3. L = R, R = Sxor

L = 0101b, R = 1010b

Поясним наши действия:

1. Эта операция сложение по mod 2 4 . На практике такая операция сводится к простому сложению, где мы должны сложить два числа и проигнорировать перенос в 5й разряд. Так как, если проставить над разрядами двоичного представления числа проставить показатели степени, над пятым разрядом как раз будет показатель четыре, взглянем на рисунок ниже, где изображены действия нашей операции:

Рис. 2

Здесь я стрелкой указал на показатели степени, как видно, результат должен был получиться 10100, но так как при операции mod 2 4 игнорируется перенос, мы получаем 0100.

1. Эта операция в литературе называется mod 2, на языке ассемблера реализуется командой XOR . Но ее более правильное название mod 2 1 . Без этой уникальной операции вряд ли можно построить быстрый, легко реализуемый алгоритм шифрования и при этом, чтобы он был еще довольно криптостойким. Уникальность этой операции заключается в том, что она сама себе обратная! К примеру, если число А поXORить с числом Б, в результате получим В, в дальнейшем достаточно переXORить числа Б и В между собой, чтобы получить прежнее значение А!

В этой операции мы получили 1010 имея числа 1110 и 0100, чтобы получить обратно 1110, достаточно переXORрить между собой числа 0100 и 1010! Более подробно об этой операции можно почитать в статье, которая вложена на сайте www.wasm.ru , «Элементарное руководство по CRC_алгоритмам обнаружения ошибок » автор, которой Ross N. Williams . В этом труде есть пункт — «5. Двоичная арифметика без учета переносов ». Вот именно в этой статье и описана операция xor! Я восклицаю потому что в этой статье эта операция так расписана, что читатель не просто понимает как работает эта операция, он даже начинает ее видеть, слышать и чувствовать!

1. Это действие необходимо, чтобы при расшифровывании из шифрограммы можно было получить исходные значения.

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 бита каждая. Выбирают элемент ключа и только потом подают эти две части блока, элемент ключа таблицу замен в функцию основного шага, результат основного шага это одна итерация базового цикла, о котором речь пойдет в следующем пункте. Основной шаг состоит из следующих действий:

1. Сложение часть блока R суммируется с элементом ключа K по mod 2 32 . О подобной операции я описал выше, здесь тоже самое только показатель степени не «4», а «32» — результат этой операции в дальнейшем буду обозначать Smod.
2. Полученный ранее результат Smod делим на четырех битные элементы s7,s6,s5,s4,s3,s2,s1,s0 и подаем в функцию замены. Замена происходит следующим образом: выбирается элемент Smod — s i , с начала начинаем с младшего элемента, и заменяем значением из таблицы замен по i — той строке и столбцу, на который указывает значение элемента s i . Переходим к s i +1 элементу и поступаем аналогичным образом и продолжаем так, пока не заменим значение последнего элемента Smod – результат этой операции будем обозначать как, Ssimple.
3. В этой операции значение Ssimple сдвигаем циклически влево на 11 бит и получаем Srol.
4. Выбираем вторую часть блока L и складываем по mod 2 с Srol, в итоге имеем Sxor.
5. На этой стадии часть блока 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.

Предупреждение: Вся информация, в том числе и ключ с таблицей замен взята в качестве примера для рассмотрения алгоритма!

Используя «Исходные данные», необходимо получить результат действия основного шага криптопреобразования.

1. Выбираем часть R = 05060708h и элемент ключа k1 = ‘as28’, в шестнадцатеричном виде элемент ключа будет выглядеть так: 61733238h. Теперь же делаем операцию суммирования по mod 2 32:

Рис. 4

Как видно на рисунке у нас не произошло переноса в 33 бит помеченный красным цветом и с показателем степени «32 ». А если бы у нас были бы другие значения R и элемента ключа – это вполне могло бы произойти, и тогда бы мы его проигнорировали, и в дальнейшем использовали только биты, помеченные желтым цветом.

Такую операцию я выполняю командой ассемблера add :

; eax = R, ebx = ‘as28’

Результат этой операции Smod = 66793940h

1. Теперь самая заковыристая операция, но если присмотреться по внимательней, то она уже не такая страшная, как кажется в первое время. Представим 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.

О том, как это проще всего реализовать в виде команд ассемблера я расскажу позже в следующем пункте, после того, как расскажу о расширенной таблице.

1. Полученное значение Ssimple мы должны сдвинуть на 11 бит влево.

Рис. 8

Как видно это действие довольно простое, и реализуется одной командой языка ассемблера – rol и результат этой операции Srol равен 0819288Fh.

1. Теперь же остается часть L нашего блока информации поXORить со значением Srol. Я беру калькулятор от w2k sp4 и получаю Sxor = 091b2b8bh.
2. Это действие итоговое и мы просто присваиваем, чисти R значение части L, а часть L инициализируем значением Sxor.

Конечный результат:

L = 091b2b8bh, R = 01020304h

4.2 Увеличения быстродействия алгоритма

Теперь же поговорим об оптимизации алгоритма по скорости. При процессе реализации, какого либо проекта, приходится учитывать, что программа, которая работает с регистрами чаще, чем с памятью работает наиболее быстрее и здесь это суждение тоже очень важно, т.к. над одним блоком информации целых 32 действия шифрации!

Когда я реализовывал алгоритм шифрования в своей программе, я поступил следующим образом:

1. Выбрал часть блока L в регистр eax, а R в edx.
2. В регистр esi инициализировал адресом расширенного ключа, об этом ниже.
3. В регистр ebx присваивал значение адреса расширенной таблицы замен, об этом тоже ниже
4. Передавал информацию пунктов 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

Список использованной литературы.

1. Статья Андрея Винокурова:

Алгоритм шифрования ГОСТ 28147-89, его использование и реализация

для компьютеров платформы Intel x86.

(можно найти по адресу: http://www.enlight.ru/crypto/frame.htm).

Тут же и исходные коды, по реализации алгоритма шифрования.

1. Статья Хорста Файстеля:

Криптография и Компьютерная безопасность.

(можно найти по тому же адресу что и предыдущую статью)

1. 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.: Этой статьей я не старался кого-то перещеголять. Она была написана с умыслом, облегчить изучение ГОСТа и если у вас получились трудности, то это не значит, что я повинен в этом. Будь разумны, и наберитесь терпения, всего вам доброго!

Известный в обществе термин «производительность процессора» представляет собой объективный, вычисляемый параметр, который меряют во флопах. Впрочем, большинство измеряет его в гигагерцах, по наивности полагая, что это одно и то же. Термин «производительность кода» не знает никто, и сразу объясню почему.

Причина в том, что я его только недавно придумал и пока никому об этом не рассказывал. Однако производительность кода, так же как и производительность процессора, имеет объективные характеристики, которые поддаются измерениям. Эта статья - именно о производительности кода, выполняемого процессорным ядром.

В чем измеряется производительность кода? Поскольку я первый об этом заговорил, то по праву первооткрывателя буду его измерять в RTT-шках;).

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

Студент ответит - одну, его преподаватель подумает и скажет, что четыре, профессионал - что пока только двенадцать операций.

Так вот, программный код, который загружает все исполнительные устройства процессора одновременно на протяжении всего времени исполнения кода, будет иметь производительность 12 RTT-шек. Максимум! Честно признаюсь, такого кода я раньше не писал, но в этой статье попытаюсь сделать над собой усилие.

Я докажу, что код с одновременным выполнением двенадцати 32-битных операций - возможен

Программный код, который использует в процессорном ядре одно исполнительное устройство, естественно, будет иметь производительность в 1 RTT-шку. Такой производительностью кода могут «похвастаться» программы, генерируемые компиляторами языков высокого уровня, и интерпретаторы виртуальных машин. Не нужно считать, что показатель загрузки процессора, который можно увидеть в диспетчере задач ОС, может служить объективным критерием эффективности кода. Загрузка ядра процессора может быть 100%, но при этом программный код будет использовать одно исполнительное устройство в нем (производительность 1 RTT). В этом случае при 100%-й загрузке процессорное ядро будет работать в 1/12 своей максимальной производительности. Другими словами, когда в диспетчере задач ОС Windows показывается максимальная загрузка процессора, его реальная производительность может варьироваться от 1 до 12 RTT. Увидев в окне производительности 100%-ю загрузку на каком-либо процессорном ядре, неправильно считать, что в этом ядре работают все исполнительные устройства, отнюдь!

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

Традиционная реализация ГОСТ 28147-89

Я не профессионал в области информационной безопасности, но все же знаком с темой шифрования. Заняться конкретно симметричным поточным шифрованием меня подвигли разговоры с профессиональным криптографом, которого я глубоко уважаю. И, занявшись этой темой, я постарался сделать именно хорошо, и не просто хорошо, а еще и быстро, выполняя максимальное число операций за единицу времени. Другими словами, передо мной встала задача написать программный код с максимальным значением RTT.

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

В настоящее время повсеместно применяется программная реализация данного ГОСТа на РОН центрального процессора. В известных методах реализации ГОСТа вся секретная информация (ключи шифрования, блоки замен) размещаются в оперативной памяти. Это снижает надежность шифрования, поскольку, имея дамп оперативной памяти, можно полностью выявить все секретные элементы криптопреобразования. Кроме этого, метод имеет ограничения по быстродействию, обусловленные расположением основных объектов криптопреобразования в ОП и неполной загрузкой исполнительных устройств ALU. Современные процессоры, реализуя криптопроцедуру по известному методу, могут обеспечить скорость шифрования на уровне 40–60 мегабайт в секунду. И если уж разбираться до конца, то причиной низкого быстродействия и слабой защищенности криптопреобразования является программная реализация блока подстановок. Описание его в ГОСТе см. на рис. 1.

По п. 1.2 ГОСТа этот блок реализует тетрадные (по четыре бита) перестановки в 32-битном слове, но архитектура процессора х86/64 и его система команд не способна эффективно манипулировать тетрадами.

Для программной реализации блока подстановок используют специальные таблицы в оперативной памяти, подготавливаемые на этапе инициализации криптофункции. Эти таблицы объединяют узлы замен смежных тетрад в байтовые таблицы размером 8 × 8 бит, таким образом, в оперативной памяти размещается четыре 256-байтных таблицы.

В более продвинутых реализациях эти таблицы имеют размер 1024 байта (256 слов по четыре байта). Это сделано для того, чтобы реализовать в таблицах дополнительно циклический сдвиг на 11 позиций полученного в результате подстановки 32-битного слова (следующая операция алгоритма преобразования по ГОСТу). Пример реализации ГОСТа по данному методу показан в приложении 1 (на диске).

Информация блока подстановок является секретным компонентом криптофункции (как это сформулировано в ГОСТе, см. на рис. 2).

Размещение этих таблиц с ключами блока подстановок в ОП противоречит требованиям ГОСТа (п. 1.7), поскольку секретная информация становится доступной для сторонних программ, работающих на вычислительной установке. ФСБ, сертифицирующая в том числе и программные реализации шифрования по ГОСТу, на данное нарушение смотрит, мягко говоря, снисходительно. Если для размещения ключей в ОП ФСБ еще требует наличия «фигового листочка» - маскирования ключей операцией XOR, то для блоков замен в ОП ничего не требуется, они хранятся в открытом виде.

Короче говоря, ФСБ пропускает такие программные реализации криптопроцедуры, несмотря на явное снижение стойкости такого решения и прямое нарушение собственных требований по ГОСТу (п. 1.7). И это несмотря на общеизвестные методы взлома шифров через съем дампа памяти…

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

Но хватит лирики, важно в рамках рассматриваемой темы то, что этот программный код имеет производительность в 1 RTT-шку. Теперь напишем код с производительностью 2 RTT-шки.

Многопоточная реализация ГОСТ 28147-89

Единственной возможностью ускорить криптопроцедуры в известном алгоритме является введение многопоточности. Смысл такого изменения реализации алгоритма заключается в том, чтобы обсчитывать сразу несколько блоков данных параллельно.

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

Однако существует и иной вариант параллельной обработки данных на одном- единственном ядре процессора. Поясню эту неочевидную мысль.

Современные процессоры имеют в своем составе как минимум два, а то и три-шесть арифметико-логических устройств. Эти АЛУ (FPU, блоки адресной арифметики и так далее) могут работать независимо друг от друга, единственным условием их параллельной работы является непересекающиеся программные объекты, которыми они оперируют. Другими словами, в командах, которые одновременно выполняют АЛУ, адреса памяти и номера регистров должны быть разными. Либо в общие регистры и адреса памяти, к которым обращаются различные исполнительные устройства процессора, не должно выполняться операций записи.

Загрузкой работой всех АЛУ управляет специальный аппаратный блок внутри процессорного ядра - планировщик, который просматривает исполняемый код форвардно, на глубину до 32–64 байт. Если планировщик обнаруживает команды, которые можно запускать на АЛУ без конфликтов, то он их запускает одновременно на разных исполнительных устройствах. При этом счетчик выполненных команд указывает на ту исполняемую команду (их в такой схеме несколько), после которой все команды уже выполнены.

Большинство программных последовательностей, генерируемых автоматически (компиляторами), не могут загрузить все АЛУ и FPU, находящиеся в ядре процессора. В этом случае оборудование процессора простаивает, что значительно снижает его результирующую производительность. Разработчики процессоров это понимают и вводят режимы увеличения частоты ядра, когда оборудование используется не полностью. Также для этого предназначены системы гипертрейдинга, и эту систему я буду использовать для «прессования» кода по максимуму в дальнейшем.

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

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

Но можно поступить и иначе: чередовать команды, относящиеся к обработке разных блоков данных. Графически эти варианты представлены на рис. 3.

На рисунке верхний пример показывает обычный порядок выполнения обработки двух независимых блоков данных. Сначала обрабатывается первый блок, затем процессор переходит к обработке второго блока. Естественно, результирующее время равно удвоенному времени, которое необходимо для обработки одного блока, а исполнительные устройства ядра процессора загружены не полностью.

Далее показан пример с чередованием команд из разных потоков обработки. В этом случае команды, относящиеся к разным блокам данных, чередуются. Планировщик выбирает независимые друг от друга команды и передает их на выполнение в АЛУ1 и АЛУ2. Группировка команд первого и второго потока на этих АЛУ осуществляется автоматически, поскольку в алгоритм работы планировщика заложена группировка команд с зацеплением по общим данным на одном и том же исполнительном устройстве.

Чтобы такой программный код работал без простоев АЛУ, необходимо, чтобы каждый программный поток работал со своим набором регистров. Кеш в этой схеме становится узким местом (у него только два порта выдачи данных), поэтому ключи храним в MMX-регистрах. Поскольку в данном случае узлы замены (и сдвига) в памяти только читаются, то они могут быть общими для обоих программных потоков.

Это, конечно, очень упрощенное объяснение принципа параллельного выполнения программных потоков на единственном ядре, реально все гораздо сложнее. На практике нужно учитывать конвейерную архитектуру исполнительных устройств, ограничения на одновременный доступ в кеш и блок регистров РОН, наличие узлов адресной арифметики, коммутаторов и много еще чего… Так что это - тема для профессионалов, которых можно пересчитать по пальцам… одной руки.

Метод параллельного шифрования эффективно реализуется только для 64-битного режима работы процессора, поскольку в этом режиме имеется достаточное количество РОН (целых 16 штук!). Пример реализации ГОСТа по данному методу показан в приложении 2 (на диске).

Ясно, что данная реализация ГОСТа имеет производительность кода 2 RTT-шки. А теперь посмотрим, как это сказывается на времени выполнения.

Цикл шифрования для одного потока (приложение 1) составляет 352 такта, и за это время обсчитывается 8 байт данных, для двухпоточной реализации ГОСТа (приложение 2) требуется 416 тактов процессора, но при этом обсчитывается 16 байт. Таким образом, результирующая скорость преобразования повышается с 80 до 144 мегабайт для процессора частотой 3,6 ГГц.

Интересная получается картина: код содержит ровно в два раза больше команд, а выполняется всего на 15% дольше, но, думаю, читатели уже поняли причину этого феномена…

Теоретически код из второго примера должен выполняться за такое же количество тактов, что и код из первого примера, но узел планировщика разрабатывают хоть и инженеры фирмы Intel, но тоже люди, а мы все далеки от совершенства. Так что имеется возможность оценить эффективность их творения. Этот код будет работать и на процессоре AMD, и можно сравнить их результаты.

Если кто мне не верит на слово, то для таких неверующих на диске прилагаются тестовые программы с счетчиками тактов. Программы в исходных кодах, естественно на ассемблере, так что есть возможность проверить мои слова, а заодно и подсмотреть некоторые хитрости профессионального кодинга.

Использование SSE-регистров и AVX-команд современных процессоров для реализации ГОСТ 28147-89

Современные процессоры архитектуры х86/64 имеют в своем составе набор регистров SSE размером 16 байт и специализированные FPU (как минимум два) для выполнения различных операций над этими регистрами. Возможна реализация ГОСТа на этом оборудовании, причем в этом случае узлы замены можно размещать не в виде таблиц в оперативной памяти, а непосредственно на выделенных SSE-регистрах.

На одном SSE-регистре можно разместить сразу две таблицы из 16 строк. Таким образом, четыре SSE-регистра позволят полностью разместить все таблицы замен. Единственным условием такого размещения является требование чередования, согласно которому тетрады одного байта должны помещаться в разные SSE-регистры. Кроме этого, целесообразно размещать младшие и старшие тетрады входных байтов соответственно в младших и старших тетрадах байтов SSE-регистров.

Эти требования обуславливаются оптимизацией под имеющийся набор AVX-команд. Таким образом, каждый байт SSE-регистра будет содержать две тетрады, относящиеся к разным байтам входного регистра блока подстановок, при этом позиция байта на SSE-регистре однозначно соответствует индексу в таблице замены блока подстановки.

Схема одного из возможных размещений узлов замены на SSE-регистрах показана на рис. 4.

Размещение секретной информации узлов замен на SSE-регистрах повышает защищенность криптопроцедуры, но полная изоляция этой секретной информации возможна при соблюдении следующих условий:

• Ядро процессора переведено в режим хоста гипервизора, и в нем принудительно отключен блок прерываний (APIC). В этом случае ядро процессора полностью изолировано от ОС и приложений, функционирующих на вычислительной установке.
• Загрузка SSE-регистров и изоляция вычислительного ядра производится до начала старта ОС, оптимальным является выполнение этих процедур с модуля доверенной загрузки (МДЗ).
• Программы криптопроцедур по ГОСТу размещаются в немодифицируемой области памяти вычислительной установки (либо БИОС, либо в флеш-памяти МДЗ).

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

Для эффективной выборки из SSE-регистров тетрад используются имеющиеся в составе блоков FPU многовходовые байтовые коммутаторы. Эти коммутаторы позволяют осуществлять пересылки из любого байта источника в любой байт приемника, по индексам, находящимся в специальном индексном SSE-регистре. Причем параллельно выполняется пересылка для всех 16 байт SSE-регистра-приемника.

Имея узлы хранения подстановок на SSE-регистрах и многовходовый коммутатор в блоках FPU, можно организовать следующее преобразование в блоке подстановок (рис. 5).

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

• Создать соответствующий дизайн чипа, но это для нас фантастика.
• Перепрограммировать микрокод и создать собственную процессорную команду для реализации этой функции на существующих процессорах - это уже не фантастика, но, к сожалению, нереально в нынешних условиях.
• Написать программу на официальных командах AVX. Вариант пускай и не очень эффективный, но зато осуществим «здесь и сейчас». Так что этим и займемся далее.

Работой коммутаторов управляет специальная трехадресная команда AVX VPSHUFB. Ее первый операнд является приемником информации из коммутаторов, второй - источником, к которому подключены входы коммутаторов. Третий операнд является управляющим регистром для коммутаторов, каждый байт которого ассоциирован с соответствующим коммутатором; значение в нем задает номер направления, с которого коммутатор считывает информацию. Описание этой команды из официальной документации Intel см. на рис. 5. На рис. 6 приведена схема работы этой команды - изображена только половина SSE-регистров, для второй половины все аналогично.

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

Программа с выборкой тетрад через коммутаторы FPU была написана, но я даже не стал помещать ее в приложение - слишком убого. Иметь регистр размером 128 бит и использовать в нем только 32 бита - непрофессионально.

Как говорится, «Наш финиш - горизонт», поэтому выжимать так выжимать... будем прессовать и складывать в пакеты!

Это не игра слов, а суровая FPUшная реальность - регистры SSE можно разбивать на равные части и выполнять над этими частями одинаковые преобразования одной командой. Для того чтобы процессор это понял, имеется магическая буковка «Р» - пакет, которая ставится перед мнемоникой команды, и не менее магические буковки «Q», «D», «W», «B», которые ставятся в конце и объявляют, на какие части разбиты в этой команде регистры SSE.

Нас интересует пакетный режим с разбивкой SSE-регистра на четыре 32-битных блока; соответственно, все команды будут иметь префикс «P», а в конце - символ «D». Это дает возможность одной процессорной командой параллельно обрабатывать сразу четыре блока по 32 бита, то есть в параллель рассчитывать четыре блока данных.

Программа, реализующая этот метод, имеется в приложении 3, там же - все пояснения.

Впрочем, прессовать так прессовать! В современных процессорах имеется как минимум два блока FPU, и для их полной загрузки можно использовать два потока независимых команд. Если грамотно чередовать команды из независимых потоков, то можно загрузить работой оба блока FPU полностью и получить сразу восемь параллельно обрабатываемых потоков данных. Такая программка была написана, и ее можно посмотреть в приложении 4, только смотреть нужно осторожно - можно слететь с катушек. Это, что называется, «код не для всех...».

Цена вопроса

Использование SSE-регистров для хранения узлов замены понятно - оно дает некую гарантию изоляции секретной информации, а вот смысл расчета самой криптофункции на FPU неочевиден. Поэтому были проведены замеры времени выполнения стандартных процедур по методу прямой замены в соответствии с ГОСТом для четырех и для восьми потоков.

Для четырех потоков была получена скорость выполнения 472 процессорных такта. Таким образом, для процессора с частотой 3,6 ГГц один поток считается со скоростью 59 мегабайт в секунду, а четыре потока соответственно со скоростью 236 мегабайт в секунду.

Для восьми потоков была получена скорость выполнения 580 процессорных тактов. Таким образом, для процессора с частотой 3,6 ГГц один поток считается со скоростью 49 мегабайт в секунду, а восемь потоков со скоростью 392 мегабайта в секунду.

Как может заметить читатель, код в примере № 3 имеет производительность 4 RTT, а код в примере № 4 имеет производительность 8 RTT. В этих примерах на SSE-регистрах закономерности те же, что и при использовании РОН, только планировщик снизил свою эффективность. Сейчас он обеспечивает 20%-е увеличение длительности при двукратном увеличении длины кода.

Причем эти результаты были получены с использованием универсальных AVX-команд, имеющихся как в процессорах Intel, так и в процессорах AMD. Если выполнить оптимизацию под процессор AMD, результат будет значительно лучше. Звучит поперек тренда, но тем не менее это правда, и вот почему: процессоры AMD имеют дополнительный набор команд, так называемое XOP-расширение, и в этом дополнительном наборе команд есть такие, которые значительно упрощают реализацию алгоритма ГОСТа.

Имеются в виду команды логического пакетного сдвига байтов и пакетного циклического сдвига двойных слов. В примерах, приведенных в приложениях 3 и 4, используются последовательности универсальных команд, реализующих необходимое преобразование: в первом случае одна «лишняя» команда, а в другом случае сразу четыре лишних команды. Так что резервы оптимизации есть, и немалые.

Если речь зашла о дальнейшей оптимизации, нелишне помнить о наличии 256-битных регистров (YMM-регистры), используя которые можно теоретически еще удвоить скорость вычислений. Но пока это только перспектива, на данный момент процессоры очень сильно замедляются, когда выполняют 256-битные инструкции (FPU имеют ширину тракта 128 бит). Эксперименты показали, что на современных процессорах счет в 16 потоков на YMM-регистрах выигрыша не дает. Но это только пока, на новых моделях процессоров, несомненно, будет увеличено быстродействие 256-битных команд, и тогда использование 16 параллельных потоков станет целесообразно и приведет к еще большему увеличению скорости работы криптопроцедуры.

Теоретически можно рассчитывать на скорость 600–700 мегабайт в секунду при наличии в процессоре двух FPU с шириной рабочего тракта 256 бит каждый. В этом случае можно говорить о написании кода с эффективностью 16 RTT, и это не фантастика, а ближайшая перспектива.

Смешанный режим

Опять встает вопрос количества регистров, их не хватает, чтобы раскрутить такой алгоритм. Но нам поможет режим гипертрейдинга. У процессорного ядра имеется второй набор регистров, доступных в режиме логических процессоров. Поэтому будем выполнять один и тот же код сразу на двух логических процессорах. В этом режиме исполнительных устройств у нас, конечно, не прибавится, но за счет чередования можно получить полную загрузку всех исполнительных устройств.

Рассчитывать на прибавку в 50% здесь не приходится, узким местом становится кеш-память, где хранятся технологические маски, но прибавку в 100 дополнительных мегабайт все же получить можно. Этот вариант не приведен в приложениях (макросы аналогичны используемым в коде на 8 RTT), но он имеется в программных файлах. Так что если кто не верит в возможность шифрования со скоростью 500 мегабайт в секунду на одном процессорном ядре, пусть запустит тестовые файлы. Там же есть и тексты с комментариями, чтобы никто не подумал, что я лукавлю.

Такой фокус возможен только на процессорах Intel, у AMD только два блока FPU на два процессорных модуля (аналог режима гипертрейдинг). Но зато имеется еще четыре АЛУ, которые грех не использовать.

Можно загнать процессорные модули «Бульдозера» в режим, аналогичный режиму гипертрейдинга, но запускать на разных модулях в одном потоке преобразование на РОН, а в другом потоке на SSE-регистрах и получить те же 12 RTT. Этот вариант я не проверял, но, думаю, на AMD код в 12 RTT будет работать более эффективно. Желающие могут попробовать, тестовые программы можно подкорректировать для работы на «Бульдозерах» достаточно легко.

Кому это нужно?

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

Причем, как это ни странно, встроенное в процессоры шифрование по AES-алгоритму оказывается значительно медленнее, тесты показывают скорость на уровне 100–150 мегабайт в секунду, и это при аппаратной реализации алгоритма! Проблема заключается в однопоточном счете и блоке замен, который оперирует байтами (таблица из 256 строк). Так что ГОСТ оказывается эффективнее в реализации на архитектуре х86/64, кто бы мог подумать…

Это если говорить о достигнутом уровне скорости шифрования. А если иметь в виду теоретические изыски в области повышения эффективности кода, то скорее всего это никому не нужно. Специалистов уровня 3–6 RTT практически нет, компиляторы вообще генерят код на уровне 1–2,5 RTT, а основная масса программистов не знает ассемблера, а если и знает его правописание, то не понимает устройства современного процессора. А без этих знаний что ассемблер, что какой-нибудь там СИ-шарп - без разницы.

Но не все так печально: в «сухом остатке» после недели бессонных ночей имеется новый алгоритм реализации ГОСТа, который грех не запатентовать. И заявки на патенты (целых три) уже оформлены и поданы, так что, господа коммерсанты, выстраивайтесь в очередь - женщинам и детям скидка.

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

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

Режим простой замены . Этот режим использования блочного шифра аналогичен рассмотренному в лекции 4 режиму простой поблочной замены ( ECB ). В этом режиме каждый блок исходных данных шифруется независимо от остальных блоков, с применением одного и того же ключа шифрования. Особенностью этого режима является то, что одинаковые блоки исходного текста преобразуются в одинаковый шифротекст. Поэтому ГОСТ 28147-89 рекомендует использовать режим простой замены только для шифрования ключей.

Режимы гаммирования и гаммирования с обратной связью могут использоваться для шифрования данных произвольного размера.

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

Так как все элементы гаммы различны для реальных шифруемых массивов, то результат зашифрования даже двух одинаковых блоков в одном массиве данных будет различным. Кроме того, хотя элементы гаммы и вырабатываются одинаковыми порциями в 64 бита, использоваться может и часть такого блока с размером, равным размеру шифруемого блока. Именно это дает возможность шифрования неполных блоков данных.

Режим гаммирования с обратной связью похож на режим гаммирования и отличается от него только способом выработки элементов гаммы. При гаммировании с обратной связью очередной 64-битный элемент гаммы вырабатывается как результат преобразования по базовому циклу алгоритма ГОСТ 28147-89 предыдущего блока зашифрованных данных. Для зашифрования первого блока массива данных элемент гаммы вырабатывается как результат преобразования по тому же циклу синхропосылки. Этим достигается зацепление блоков – каждый блок шифротекста в этом режиме зависит от соответствующего и всех предыдущих блоков открытого текста. Поэтому данный режим иногда называется гаммированием с зацеплением блоков . На стойкость шифра факт зацепления блоков не оказывает никакого влияния.

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

где f – базовый цикл по ГОСТ 28147-89; X i – 64-разрядный блок исходного текста; K – ключ .

В качестве имитовставки берется часть блока Y n , полученного на выходе, обычно 32 его младших бита.

Таким образом, злоумышленник , не владея ключом шифрования, не может вычислить имитовставку для заданного открытого массива информации, а также подобрать открытые данные под заданную имитовставку.

Отличия алгоритмов шифрования по ГОСТ 28147-89 и DES

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

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

В шифре, реализуемом в ГОСТ 28147-89, используется 256-битовый ключ , и объем ключевого пространства составляет 2 256 . Даже если, как и в "Алгоритмы шифрования DES и AES" , предположить, что на взлом шифра брошены все силы вычислительного комплекса с возможностью перебора 10 12 (это примерно равно 2 40) ключей в одну секунду, то на полный перебор всех 2 256 ключей потребуется 2 216 секунд (это время составляет более миллиарда лет).

К уже отмеченным отличиям между алгоритмами DES и ГОСТ 28147 можно добавить также следующее. В основном раунде DES применяются нерегулярные перестановки исходного сообщения, в ГОСТ 28147 используется 11-битный циклический сдвиг влево. Последняя операция гораздо удобнее для программной реализации. Однако перестановка DES увеличивает лавинный эффект. В ГОСТ 28147 изменение одного входного бита влияет на один 4-битовый блок при замене в одном раунде, который затем влияет на два 4-битовых блока следующего раунда, три блока следующего и т.д. В ГОСТ 28147 требуется 8 раундов прежде, чем изменение одного входного бита повлияет на каждый бит результата; DES для этого нужно только 5 раундов.

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

Ключевые термины

ГОСТ 28147-89 – российский стандарт на блочный алгоритм симметричного шифрования .

Краткие итоги

В России принят ГОСТ 28147-89, рекомендуемый к использованию для криптографической защиты данных. ГОСТ 28147-89 является блочным шифром с закрытым ключом. Основные параметры алгоритма ГОСТ 28147-89 следующие: размер блока – 64 бита, размер ключа – 256 бит , количество раундов – 32. Алгоритм представляет собой классическую сеть Фейштеля.

Набор для практики

Вопросы для самопроверки

1. Для каких целей может использоваться алгоритм криптографического преобразования данных по ГОСТ 28147-89?
2. Перечислите основные параметры алгоритма симметричного шифрования по ГОСТ 28147-89.
3. Какие операции используются в блочном алгоритме шифрования по ГОСТ 28147-89?
4. Каковы основные отличия алгоритма шифрования по ГОСТ 28147-89 от алгоритма DES?
5. Какая информация, помимо секретного ключа, при условии использования стандартных алгоритмов ГОСТ 28147 -89 необходима для расшифровки сообщения?
6. В каких режимах может производиться шифрование данных с помощью алгоритма криптографического преобразования по ГОСТ 28147-89?
7. Что такое имитовставка ? Для каких целей может быть использована имитовставка ?

Упражнения для самопроверки

1. Пусть каждые три бита входного сообщения заменяются по следующей таблице замен: