Скоростное хеширование на базе нового криптографического алгоритма
К сожалению, математики слабо разбираются в тонкостях программирования, они что-то выдумывают, а потом программист должен это реализовать в программном коде. Далеко не всегда возможно реализовать их алгоритмы эффективно.
Особенно явно это проявляется в Российской симметричной криптографии последнего времени, «Стриборг» и «Кузнечик»… Эти алгоритмы реализовать эффективно в программных кодах х86/64 невозможно, нужен специализированный криптопроцессор.
Сделаем все наоборот и посмотрим, что получится.
Программист, знающий как работает современный процессор х86/64, займется разработкой максимально эффективного алгоритма симметричного шифрования, а математики, как в старые добрые времена, пускай занимаются своей основной работой,- криптоанализом получившегося решения.
Помня, что «Лучшее-враг хорошему», возьмем за основу «хорошее» — ГОСТ 28147-89. Затем по врачебному принципу «Не навреди» усилим его методами многопоточных вычислений.
Было сделано следующее:
- Увеличен размер ключа до 256байт.
- Увеличен размер блока данных до 256байт.
- Операция подстановки заменена операцией перестановки.
- В циклическом сдвиге внедрена операция инвертирования групп бит.
- Ввод ключей выполнен в виде перестановки бит.
- Сеть Фейстеля модифицирована в кольцевую сеть из восьми сегментов.
- Используется режим гаммирования с обратной связью, в два прохода по шифруемым данным.
- Проходы производятся с разными перестановками и кольцевыми сдвигами он с одинаковыми ключами.
- Перед шифрацией из шифруемого текста удаляется избыточность с помощью компрессора.
Тестовая реализация
Алгоритм реализован, и первое что тестируется, это его статистические параметры при генерации псевдослучайной последовательности (компрессор отключен), вот как они выглядит:
![image](https://habrastorage.org/getpro/habr/post_images/9cb/f41/7b9/9cbf417b94fe0ea9939c0cb6fbdd57be.png)
Это типичный результат тестов NIST нового криптопреобразования. Результаты тестов на любых случайных ключах и первоначальных заполнениях всегда укладываются в статистические параметры случайной последовательности.
Полученные в экспериментах по нормам 8 байтного блочного шифра статистические параметры для блочного шифра с размером блока 256 байт это фантастика.
Это все равно что, к примеру, подбросив монетку 12 раз и получив равное выпадение «орла» и «орешки», требовать, чтобы кубик, тоже брошенный 12 раз, выпал на каждую грань обязательно по два раза…
Такое теоретически возможно только при очень высокой дифференциальной энтропии между смежными блоками и характеризует уровень сложности блочного шифра.
Эти параметры гаммы получены при одном раунде преобразования. Алгоритм имеет особенность,- скорость гаммирования зависит от производительности оперативной памяти и кеша, а не от быстродействия процессора.
Русская Рулетка, 2018 и его применение
В последнее время криптографические алгоритмы у нас стали получать звучные названия, типа «Магма», «Кузнечик», «Стрибог», продолжим эту традицию.
Будем называть этот блочный шифр «Русская рулетка» или сокращенно РУ2, в честь первого чисто русского генератора случайных бинарных последовательностей,- вращающегося барабана револьвера…
Ну и кроме того, криптопреобразование построено на вращениях (кольцевых сдвигах) бинарных последовательностей. Таких сдвигов там только в явном виде 192 штуки за один раунд.
Так что прямая аналогия с барабаном револьвера очевидна.
Ранее, при внедрении параллельного метода реализации ГОСТ 28147-89 на XMM/YMM регистрах пришлось его полностью описать, поскольку он проходил официальную сертификацию ФСБ.
Сейчас ситуация другая, никакого официоза не предполагается. Поэтому подробного описания алгоритма «Русская рулетка» не будет, это своеобразная копирайт защита. Короче говоря, алгоритм «Русской Рулетки» пока будет проприетарным и соответственно его полное обозначение Русская Рулетка, 2018 или сокращенно РУ2.
Закрытый от исследования алгоритм шифрования,- это конечно нонсенс, поскольку отсутствует доверие к надежности шифрования.
Но ничто не мешает использовать алгоритм РУ2 для конвертации шифруемого текста в последовательность удовлетворяющей требованиям псевдослучайности.
Затем полученную псевдослучайную последовательность можно шифровать известными и «надежными» алгоритмами, собственно так и построены все серьезные криптографические систем.
Пока же «Русская Рулетка» используется для скоростного хеширования с произвольным размером результата хеш-функции. Это важно в задачах резервного копирования и контроля целостности.
Стандартное гаммирование с обратной связью превращается в Хэш-функцию если провести второй проход по зашифрованным данным. Именно так изначально реализован алгоритм РУ2.
Двойное гаммирование с обратной связью не рассматривалось ранее как вариант реализации хеш-функции видимо из-за низкой скорости работы, хотя обладает более надежными параметрами свертки. Это касается в первую очередь лавинного эффекта, он действует не только на последующие раунды свертки, но и на предыдущие.
Причем полученные характеристики хэш-функции надежно проверяются статистическими тестами, ведь весь полученный шифротекст, являющийся надежной псевдослучайной гаммой, становится хэшем.
Из этой гаммы можно вырезать произвольные куски для хранения значения хэш-функции. Сейчас используется блок размером 1024Байт, это гораздо надежнее чем блок из 64Байт в самом «продвинутом» стандарте SHA3-512.
Хеширование РУ2 защищает данные от просмотра/модификации, но пока криптографы не убедились в стойкости алгоритма будем его считать парольной защитой данных для ограничения доступа.
Практическая реализация РУ2
Алгоритм «Русская рулетка» встроен в криминалистический дубликатор HDD и SDD дисков. Алгоритм используется там для создания дифференциальных бэкапов, контроля целостности, ограничения доступа на основе пароля и сжатия информации.
О компрессоре для удаления избыточности уже писалось ранее в статье «Новый алгоритм скоростной компрессии данных», хеширование используется для подтверждения целостности скопированных данных, а в случае ввода пароля еще и для «парольной защиты» полученных дампов от просмотра/модификации.
Вот скоростные характеристики РУ2 полученные в реальной работе по созданию дифференциального бэкапа:
![image](https://habrastorage.org/getpro/habr/post_images/38b/d30/35c/38bd3035c8d28a7c2fca035c8e482563.png)
Скорость копирования ограничена параметрами устройства чтения, большую скорость чтения SSD диск подключенный через мост USB 3.0-SATA обеспечить не может.
На скорости входного потока 360МегаБайт/сек. алгоритм РУ2 грузит процессор всего на 5% при сниженной частоте работы 1.4ГигаГерца. При этом обеспечивается сжатие информации, ее хеширование и шифрация (парольная защита) дампа.
Традиционные системы хеширования такую производительность обеспечить не могут. Для сравнения, вот как работает система хеширования встроенная в «Акронис» при создании дифференциального бэкапа того же диска:
![image](https://habrastorage.org/getpro/habr/post_images/704/397/456/7043974564b3e9d898112a4d44dd3929.png)
Процессор хеширует входной поток данных со скоростью 340МегаБайт/сек., работает при этом на частоте 3.8ГигаГерца и загружен на 28%.
Если пересчитать полученные результаты в предельные параметры для двухядерного процессора работающего на частоте 3.8ГигаГерца, то система хеширования «Акрониса» может обеспечить пропускную способность в 1.4ГигаБайт/сек.
Гораздо более загруженный задачами (хеширование+сжатие+«парольная защита») алгоритм «Русской Рулетки» обеспечивает скорость 21ГигаБайт/сек.
Другими словами, хеширование РУ2 работает на порядок быстрее чем стандартное хеширование реализованное в «Акронисе».
Кроме того, «Русская Рулетка» обеспечивает скорость генерации псевдослучайных чисел на уровне 12 ГигаБайт в секунду. Это самый скоростной генератор псевдослучайных последовательностей из известных, удовлетворяющий требованиям официальных тестов NIST.
Генерация случайных чисел, хеширование, парольная защита, пока этого для «Русской Рулетки» хватит.
«…Ну а криптография?, — а криптография потом….».