Особенности национальной криптографии

Автор: R_T_T

Техническая часть

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

Реально, была достигнута скорость обработки в районе 350 мБайт/сек. для одного процессорного ядра с частотой 3.6гГц. Старые методы реализации алгоритма, с использованием РОН не давали скорости большей 35мБайт/сек.

После этого использование для преобразования по ГОСТ 28147-89  алгоритмов с применением регистров общего назначения (РОН) стало бессмысленным.

Теоретически, если реализовать алгоритм не на 128 битных ХММ регистрах, а на 256 битных УММ регистрах, по скорость преобразования можно было поднять еще в два раза.

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

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

И вот, по прошествии более трех лет, Интел выпустила процессора с архитектурой Skylake. Арифметические устройства этого процессора (три штуки) стали 256 битными.

Как и ожидалось, процессора Skylake выполняют команды использующие УММ регистры с той же скоростью что и команды с использованием ХММ регистров. Соответственно, появилась возможность ускорить реализацию алгоритма преобразования по ГОСТ 28147-89 ровно в два раза, за счет увеличения количества одновременно обрабатываемых блоков данных с 8 до 16.

Как и любая «хорошо» сделанная вещь, новая реализация алгоритма ГОСТ 28147-89 работает «всегда».

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

После чего скорость преобразования увеличилась вдвое автоматически.

Но вдвое, это существенно меньше, чем заветные 1гбайт/сек., потому пришлось еще «немного» оптимизировать алгоритм. Теперь он выглядит для одного вычислительного потока так (всего потоков два):

ymm12-ymm15 - регистры хранения блоков замен
; ymm11 - маска сборки байт
; ymm5 - маска старших тетрад
; ymm0,ymm1 -  регистры чередующихся накопителей первого потока
; ymm2-ymm4 -  регистры промежуточных вычислений первого потока
 
;/////подготовка блока замен
 vpsrlw ymm2,ymm0,4;                старшие тетрады в младшие
  vpand ymm2,ymm2,ymm5;             сбросить старшие тетрады
   vpand ymm0,ymm0,ymm5;            сбросить старшие тетрады
 
;////////////////совместить выборку актуальных тетрад
vpblendw ymm3,ymm0,ymm2,0aah;    замена 1-2байт м.тетрады и 3-4байт с.тетрады
 vpblendw ymm0,ymm0,ymm2,055h;   замена 1-2байт с.тетрады и 3-4байт м.тетрады
 
;////////////блок замен
 vpshufb ymm4,ymm12,ymm3;
  vpshufb ymm3,ymm13,ymm3;
   vpblendvb ymm4,ymm4,ymm3,ymm11;  совместить актуальные байты
 
 vpshufb ymm2,ymm14,ymm0;
  vpshufb ymm0,ymm15,ymm0;
   vpblendvb ymm0,ymm0,ymm2,ymm11;  совместить актуальные байты
 
;////////сборка результата
 vpand ymm4,ymm4,[rsp];                   очистить неиспользуемые тетрады
  vpand ymm0,ymm0,[rsp+20h];              очистить неиспользуемые тетрады
   vpor ymm0,ymm0,ymm4;                   собрать результат замены
 
;/////циклический сдвиг на 11 влево
 vpslld ymm2,ymm0,11;
  vpsrld ymm3,ymm0,21;
   vpxor ymm0,ymm1,ymm2;
    vpxor ymm0,ymm1,ymm3;                 суммирование накопителей
  vpaddd ymm1,ymm0,[rsp+40h+kl*32];    сложить накопитель с ключом

Цикл преобразования теперь выполняется за 460 тактов. Код примера из первых статей выполнялся за 520 тактов, так что удалось практически на 15% увеличить скорость преобразования только за счет более эффективного «коддинга».

460 тактов для обработки 16 потоков по 8 байт дает более чем 1гБайт/сек., правда для процессора частотой в 3.8гГерца…

Пример можно использовать и для преобразования на ХММ регистрах, для старых процессоров, это актуально с точки зрения увеличения скорости преобразования. Для этого нужно только заменить  в названиях регистров букву «У» на букву «Х».

Лирическая часть

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

И кроме этого в него, включили дополнительно новый блочный шифр, называемый несколько легкомысленно: «кузнечик»...  По сути это тот же американский AES. Чтобы не говорили его авторы, сейчас он уже не конкурент ГОСТ 28147-89, но об этом чуть позже.

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

Фактически пытались сделать тоже самое, что сделали с криптографическими ТРМ модулями. Если кому интересно, об этом можно почитать в статье «Виртуализация ТРМ модуля». Ну а если кому интересно, к чему это приводит, то можно почитать статью «Голый король».

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

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

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

Но, как и ожидалось, наплевать коммерсантам на эти патенты, ни одна из фирм внедривших этот метод, не соизволила даже поставить в известность об этом автора и хотя бы сказать спасибо.

Ну, это еще можно перетерпеть, а вот некоторые, кроме этого, сразу поспешили к нашим «потенциальным противникам», это уже совсем «нехорошо».

Второе пришествие.

    Пресловутый «кузнечик», это мертворожденное дитя, никто использовать его по доброй воле не будет, объясню «на пальцах», почему:

- Из-за наличия в нем блока замен для байт (8бит) а не тетрад (4 бита), таблицу замен из 256 байт приходится размещать в Кеше процессора, а не в регистровом блоке. Соответственно скорость преобразования для «кузнечика» заведомо ниже скорости преобразования по ГОСТ 28147-89, где блок замен размещен в УММ (ХММ) регистрах.

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

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

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

Единственное, на что можно «попенять» ГОСТу 28147-89, это размерность блока, 64бита (8байт) это конечно «маловато будет»  по нынешним временам…

Ну, так давайте, «легким движением руки», сделаем его 128битным, (блоки 16 байт).

Для этого нужно заменить все операции с 32битных на 64битные, только и всего.

При этом все накопители становятся размером 64 бита, ключи становятся тоже 64битными, и появляется блок замен с 16 подстановками (S – боксы), вместо 8, в нынешнем виде.

 Реализация ГОСТ 28147-89 на УММ регистрах, как и любая «хорошо» сделанная вещь, позволяет перейти на 128битное преобразование по ГОСТ 28147-89 без потери быстродействия, и практически ничего не меняя в коде.

В примере, приведенном выше, нужно в модуле циклического сдвига выполнять операции с 64битными блоками, а не с 32битными, как сейчас.

Вот как это будет выглядеть для 128битного преобразования:

;/////циклический сдвиг на 11 влево
 vpsllq ymm2,ymm0,11;
  vpsrlq ymm3,ymm0,21;
   vpxor ymm0,ymm1,ymm2;
    vpxor ymm0,ymm1,ymm3;                 суммирование накопителей
  vpaddq ymm1,ymm0,[rsp+40h+kl*32];    сложить накопитель с ключем

Как видите, в трех командах изменилась всего лишь последняя буква, «d» - 32битная операция, заменена на «q» - 64битная операция.

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

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

Если снижать число итераций до 16, то скорость преобразования по ГОСТУ128бит увеличится в два раза, а это уже 2гБайта/сек., есть из-за чего «попариться»…

А на последок я скажу…

Автор не наивен, и понимает, что публично изложенная в этой статье идея врядли найдет отклик у сотрудников «Центра защиты информации и специальной связи ФСБ России», они меня, мягко говоря, «не любят».

Но в силу своего независимого статуса,  «рюмку чая», автору иногда приходится выпивать в самых разных кабинетах с ковровыми дорожками, так что на самом деле ситуация непредсказуемая…

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

Видимо следующее обращение к теме произойдет после появления процессоров с набором команд AVX-512, эта спецификация уже опубликована. Операционные регистры этих команд (ZMM0 – ZMM31) имеют длину 512 бит.

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

На данный момент, имея три независимых арифметических устройства, удается сформировать только два независимых вычислительных потока. Третье арифметическое устройство при этом простаивает, что ни есть «хорошо».

Причина этого в недостаточном количестве регистров, их «всего» 16 штук. Если бы их стало 32, то можно было бы с легкостью загрузить неиспользуемое пока арифметическое устройство третьим вычислительным потоком и перевести в регистры технологические маски, которые пока приходится хранить в Кеше, поскольку для них не осталось регистров.

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

P.S.

Начав писать, тяжело остановиться, и как говорится, «Остапа понесло…».

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