Третье пришествие ГОСТ 28147-89
Или «Русская рулетка»
До середины 60годов прошлого века, в эпоху арифмометров и логарифмических линеек, криптографические системы разрабатывали инженеры. Тогда роль математиков сводилась к криптоанализу и внедрению в алгоритмы скрытых бэкдоров.
С появлением ЭВМ, математики полностью оккупировали тему криптографии, цифровое представление данных их вотчина.
Но прогресс не стоит на месте, появились квантовые вычислители и квантовая передача данных, и там данные представляются не в виде чисел, а в виде квантовых состояний, это означает приход в тему обработки информации физиков.
Пока реальные квантовые вычисления находятся в области «заоблачной дали», но это не значит что к ним рано готовится, вполне возможно что уже даже поздно. Но лучше поздно, чем никогда.
Пока же, математики слабо разбираются в тонкостях программирования, что-то выдумывают, а потом программист должен это реализовать в программном коде, что далеко не всегда возможно сделать эффективно.
Примером такого подхода является алгоритм симметричного шифрования «Кузнечик», реализовать его эффективно в программных кодах х86-64 невозможно.
Сделаем все наоборот и посмотрим, что получится...
Программист, знающий как работает процессор, займется разработкой алгоритма максимально эффективно реализуемого на современных процессорах, а физик подскажет как его сделать стойким к методам квантового криптоанализа.
Криптографы, как в старые добрые времена, пускай занимаются своей основной работой,- криптоанализом получившегося решения.
Будем действовать осторожно, по принципу «Лучшее-враг хорошему», возьмем за основу «хорошее» - ГОСТ 28147-89. Затем по врачебному принципу «Не навреди» усилим его методами многопоточных вычислений.
Что значит «усилить» говорилось в статье «Многопоточные криптографические алгоритмы», вот что было сделано конкретно:
- Увеличен размер ключа до 256байт.
- Увеличен размер блока данных до 256байт.
- Улучшены статистические параметры шифротекста.
Увеличение размеров ключа и блока данных сводятся к повышению расчетной и алгоритмической сложности криптоанализа. Требование максимального соответствия шифротекста параметрам случайной последовательности ранее было вторичным, но в настоящее время это уже неприемлемо.
Статистические характеристики шифротекста в постквантовую эпоху становятся основными параметрами, определяющими криптостойкость.
Любые нарушения случайности это скрытые закономерности, которые криптографы могут свести к линейным функциям. А линейные функции любой сложности вскрываются квантовыми методами. Поэтому статистике уделялось основное внимание при разработке многопоточного алгоритма шифрования на основе ГОСТ 28147-89.
Было сделано следующее:
- Нелинейная операция подстановки тетрад заменена нелинейной операцией перестановки байт в блоке данных. Всего используется 16 фиксированных перестановок
- В линейном преобразовании циклического сдвига внедрена нелинейная операция инвертирования групп бит.
- Сеть Фейстеля модифицирована в кольцевую сеть собственного изготовления с сохранением базовых преобразований ГОСТ 28147-89. Это сделано для устранения обратимости преобразования.
- Ввод ключей выполнен в виде обратимого криптографического преобразования перестановки бит.
Преобразование перестановки бит осуществляет разбиение 256 байтового блока на куски произвольной длины (в соответствии с ключевой информацией) и перестановки их также в зависимости от ключевой информации. Ключи в этом преобразовании не влияют на содержимое блока данных (не меняют числа нулей и едениц), только перемешивают блок данных «внешним» воздействием.
Как анализировать данное преобразование не понятно. Математического аппарата для анализа произвольных перестановок в бинарных блоках, выполняемых над произвольными фрагментами этого блока, не существует…
Модифицированная сеть Фейстеля работает в режиме необратимого гаммирования. Это гарантирует, что даже зная ключи и некоторую последовательность блоков гаммы невозможно вычислить значения блоков гаммы за пределами этой известной последовательности блоков.
Для вычислений значений блока гаммы за пределами известной последовательности требуется провести вычисление из начальной точки гаммирования.
Практическая реализация
Пока все это было «сказкой» и благими пожеланиями, пора превратить их в «быль», и вот как она выглядит:
Сначала главное, статистические параметры
Это типичный результат тестов NIST нового криптопреобразования на основе ГОСТ 28147-89. Результаты тестов на любых случайных ключах и первоначальных заполнениях всегда укладываются в статистические параметры случайной последовательности.
Для сокращения времени тестирования, применялась упрощенная методика. Сначала проводился эксперимент на ста блоках длиной один миллион бит в гамме длинной 24мегабайт (используется первая половина гаммы).
В случае неуспешного эксперимента (выпадения из диапазона допустимых пропорций), та же гамма, уже в полном объеме, тестировалась на ста блоках длиной два миллиона бит. Для таких экспериментов все запуски теста были успешными (в серии из 100 экспериментов).
Понятно, что и тесты с блоком длиной два миллиона бит тоже должны приводить иногда к выпадению из диапазона пропорций, но из-за ограничений по числу экспериментов таких случаев не встретилось.
Эти статистические параметры гаммы гораздо лучше гаммы вырабатываемой классическим ГОСТ, в нем часто встречаются ключи, на которых тесты NIST не проходят в принципе. Шифр AES, в аналогичных экспериментах не сильно отличается от традиционного ГОСТ.
Полученные в экспериментах по нормам 8 байтного блочного шифра статистические параметры для блочного шифра с размером блока 256 байт это фантастика.
Это все равно что, к примеру, подбросив монетку 12 раз и получив равное выпадение «орла» и «орешки», требовать, чтобы кубик, тоже брошенный 12 раз, выпал на каждую грань обязательно по два раза…
Такое теоретически возможно только при очень высокой дифференциальной энтропии между смежными блоками и характеризует уровень сложности блочного шифра.
И самое интересное, эти параметры получены при одном раунде преобразования. Других блочных шифров удовлетворяющих требованиям случайности при использовании всего одного раунда больше не существует.
Максимальная криптографическая мощность этого шифра достигается уже на 16 раундах, но для текущего уровня криптоанализа это явно избыточно.
Теперь про скорость.
Это скриншот реализации многопоточного криптопреобразования на основе ГОСТ 28147-89 в программе FastSecurityBoxes, тестирование проводилось по методике описанной в статье «Второе пришествие ГОСТ».
Как видно на скриншоте скорость копирования достигла предела для тестовых SSD дисков и составляет 453мБайт/сек. при загрузке процессора всего 6 процентов.
Теоретически, в тестах чистой криптографии, скорость шифрования для режима гаммирования составляет 12 ГигаБайт/сек. на одно физическое ядро процессора (моделей Skylake и выше) работающее на частоте от 3гГерц и выше.
Скорость шифрования определяется уже не частотой процессора, а пропускной способностью оперативной памяти вычислительной системы.
© Русская Рулетка, 2017 и его будущее применение.
В последнее время, с легкой руки ФСБ, шифры у нас стали получать звучные названия, типа «Магма», «Кузнечик», продолжим эту традицию.
Будем называть этот блочный шифр «Русская рулетка».
Почему «Русская», надеюсь всем понятно. А «рулетка», потому как шифр построен на вращениях (кольцевых сдвигах) бинарных последовательностей. Таких сдвигов там только в явном виде 192 штуки за один раунд.
Кстати, русские офицеры, игравшие в Русскую рулетку, были хоть и безбашенными, но далеко не глупцами. Они тщательно чистили свои наганы, и хорошо знали физику, а потому держали наган при вращении барабана строго горизонтально…
Барабан с одной/пятью пулями из шести становится несбалансированным, и всегда стремиться встать пустым патронником напротив ствола.
Так что случайностью была только возможности заклинивания барабана от разных соринок/волосинок, попадание на пустой патронник было «псевдослучайным» и имело строгий, прогнозируемый результат.
Ранее, при внедрении параллельного метода реализации ГОСТ 28147-89 пришлось его полностью описать, поскольку он проходил официальную сертификацию ФСБ.
Сейчас ситуация другая, никакого официоза не предполагается. Поэтому подробного описания алгоритма «Русская рулетка» не будет, это своеобразная копирайт защита. Если интересно станет профессионалам, пускай обращаются к своим коллегам, - реверс программистам. Вот кому придется поломать голову…
Короче говоря, алгоритм Русской рулетки будет проприетарным и скоро появится вот это: © Русская Рулетка, 2017.
Закрытый от исследования алгоритм шифрования,- это конечно нонсенс, поскольку отсутствует доверие к надежности шифрования.
Но Русская рулетка не система шифрования, не нужны нам терки с регулятором.
Пускай в меня первым кинет камень тот, кто скажет, что это шифр, это не система шифрования, легким движением руки сделан ход конем, и алгоритм превращен в скоростную систему хеширования и коррекции ошибок, ведь в первую очередь нужно заботится о целостности данных…
Самодельная циклическая сеть Фейстеля идеально удовлетворяет требованиям «турбокода» для исправления ошибок, я это не специально, «он сам пришел»...
Стандартное гаммирование с обратной связью превращается в Хеш функцию, если ключи связать с ранее обработанными данными…
Ну а то, что в результате данные будут еще и надежно защищены от просмотра и модификации, - так извините, побочный эффект работы системы хеширования и коррекции ошибок.
Пока представлен криптографический «движок» этой будущей системы, его можно оценить на тестовых гаммах с точки зрения статистики и криптостойкости.
В дальнейшем же предстоит сделать то, что не удалось сделать Крылову.
С помощью Русской рулетки запряжем в «телегу» ответственного архивирования трех персонажей его басни,- «лебедя» приватности, «рака» достоверности и «щуку» надежности. При этом, заставим их тянуть «телегу» с бешеной скоростью…
Сложная задача, но решаемая.
Практическая реализация криптофункции
Алгоритм «Русская рулетка» встроен в демонстрационную версию программы FastSecurityBoxes в частично обрезанном виде. Пока, для тестирования, реализовано только базовое преобразование работающее в режиме гаммирования. Используется один раунд, этого достаточно для надежного прохождения тестов NIST и криптостойкости на уровне 2256*8 (вариант прямой атаки методом перебора).
Ключи пересчитываются после выдачи 64килобайт гаммы.
Сам алгоритм реализован на AVX командах с использованием YMM регистров, поэтому эффективно этот алгоритм может работать только на самых последних процессорах Интел (Skylake и выше).
На процессорах AMD, даже самых новых, алгоритм Русской рулетки будет работать медленно, поскольку операции использующие YMM регистры реализованы в них микропрограмно а не аппаратно.
Чтобы в дальнейшем программа FastSecurityBoxes была востребована для практической работы, она имеет «полезную нагрузку» в виде функции создания резервных копий логических дисков (естественно восстановление дисков там тоже есть).
Выбор прикладной задачи обусловлен с одной стороны актуальностью темы, а с другой стороны наглядностью результата. Создание резервных копий дисков естественно было «заточено» под скоростные SSD диски, которые уже сегодня на интерфейсе NVMe могут работать со скоростью 2-3 Гигабайта в секунду. На таких скоростях шифровать данные до сих пор никто не умел, но теперь это уже реальность.
Помимо нового, пока экзотического многопоточного алгоритма, FastSecurityBoxes реализует шифрование по классическому ГОСТ 28147-89 в 8 параллельных потоков (для старых процессоров) и 16 параллельных потоков (для «скайлейка» и выше). Эти паралельные методы шифрования сертифицированы ФСБ.
Шифрование в 8 и 16 потоков включены в состав программы для предметного сравнения результатов, чтоб чувствовалась разница...
Видимо я запутал читателей терминами «многопоточный» и «параллельный», поэтому поясню.
Параллельный метод реализации ГОСТ 28147-89 это сертифицированный ФСБ метод. Параллельность предполагает выполнение стандартных криптопроцедур одновременно на 4-8-16 независимых физических устройствах. При этом ключи шифрования, блоки замен везде одинаковые, но входные и выходные данные разные. Ускорение работы достигается за счет одновременной работы нескольких независимых друг от друга физических устройств.
Термин «независимое физическое устройство» применительно к процессору это понятие условное, в реальности у процессора имеется набор регистров, на которых одновременно (одной командой процессора) выполняются одинаковые преобразования. Но для простоты понимания будем считать их независимыми физическими устройствами, работающими строго параллельно и синхронно.
Многопоточный метод реализованный в алгоритме «Русская рулетка» существенно отличается от параллельного, вот его главные отличия:
1. Имеется единственный блочный раундовый преобразователь.
2. Длина блока (пока) 256байт и может масштабироваться.
3. Фрагменты блока (по два байта) обрабатываются в независимых потоках.
4. Объединение фрагментов производится в дополнительном преобразовании.
Многопоточный метод позволяет увеличить размер ключевых данных и размер входного блока данных. При этом изменение любого из 2048 бит входного блока приводит к гарантированному изменению всех 2048 выходных бит после десяти раундов преобразования.
Сейчас шифр содержит 128 потоков, когда появятся процессора с набором команд AVX-512, можно будет увеличить количество потоков до 512 (блок данных будет иметь размер 1Кбайт) и в два раза поднять скорость.
А пока, в сухом остатке
Скорость на уровне 12 ГигаБайт в секунду для процессора с частотой 3гГерц, не с чем сравнивать. Скорость реализации алгоритма «Русская рулетка» в режиме гаммирования «несравненная».
Это самый скоростной генератор псевдослучайных последовательностей из известных, удовлетворяющий требованиям тестов NIST.
Математическая сложность криптоанализа базового преобразования «Русская рулетка» определяется размерностью ключа, в нашем случае она равна 2256*8.
Алгоритмическая сложность криптоанализа с учетом известных методов взлома для базового преобразования «Русская рулетка» как минимум не меньше родительского преобразования ГОСТ 28147-89.
Больше статью не буду перегружать информацией об этом новом алгоритме, пока пускай заинтересованные лица проверят сказанное в тестовой программе.
Скачать программу FastSecurityBoxes можно здесь https://yadi.sk/d/qubrbH1s3KdAHx
Для тестирования в ней предусмотрена функция выдачи «чистой» гамммы. В этом режиме создаются тестовые псевдослучайные файлы для преобразований по ГОСТ 28147-89 и «Русской рулетки».
P.S.
Программа FastSecurityBoxes (ФорсированныеСекретныеОбразы если по русски) скоро превратится в пригодную для массового использования программу ответственного архивирования, а затем, надеюсь, в полнофункциональный коммерческий продукт. Соответственно интересно сравнить ее с корифеями рынка коммерческого резервного копирования по скорости копирования и загрузке процессора.
Скоростные параметры FastSecurityBoxes уже приводились в статье «Второе пришествие ГОСТ», посмотрим в качестве примера, что может сделать Акронис в тех же режимах работы, на той же самой аппаратной платформе.
Вот как он создает посекторный дамп без шифрования и сжатия:
Программа выполняет посекторное копирование на скорости 368 МБ/сек.. Видимо используется синхронный однопоточный ввод-вывод с циклами ожидания окончания операции ввода/вывода. Иначе не объяснить слишком большой загрузки процессора на операциях ввода/вывода, составляющей 20%. Явно устаревшее решение из прошлого тысячелетия.
На этой же конфигурации оборудования тестовая программа FastSecurityBoxes обеспечивала скорость дампирования 450 МБ/сек. при загрузке процессора на уровне 6 процентов.
Вот что Акронис выдает на посекторном копировании (без сжатия) с шифрованием дампа по ГОСТ 28147-89:
Скорость снизилась почти в десять раз, до 42 МБ/сек. используя 17 процентов вычислительных ресурсов процессора, FastSecurityBoxes обеспечивала в этом режиме скорость 330 МБ/сек, при этом используя 10 процентов вычислительных ресурсов, думаю комментарии излишни…
А вывод очевиден, Акронис использует устаревшую классическую реализацию ГОСТ 28147-89 на РОН регистрах процессора, поэтому такая низкая скорость.
Вот что получается у Акрониса с шифрованием дампа по самому «легкому» алгоритму AES -128, опять без сжатия. Этот алгоритм по криптостойкости хуже ГОСТ 28147-89, но реализация его самая скоростная из-за сокращенного количества раундов.
Скорость возросла до 80 МБ/сек, но все равно это катастрофически мало, Битлокер обеспечивал в этом режиме скорость около 360 МБ/сек. Очевидно используется устаревшая криптобиблиотека без поддержки аппаратного криптоускорителя Интел.
Как то все это бледно смотрится на фоне современных технологий…