Алгоритмы хэширования Bash

В информационных системах республики для управления электронными цифровыми подписями (ЭЦП) используется СТБ 34.101.45 «Информационные технологии и безопасность. Алгоритмы электронной цифровой подписи на основе эллиптических кривых».  Этот стандарт определяет три уровня стойкости: l = 128, l = 192 и l =256. Для того, чтобы поддержать уровень l, требуется использовать функцию хэширования с 2l-битовыми значениями. СТБ 34.101.31 определяет 256-битовую хэш-функцию belt-hash, но 384- и 512-битовые функции хэширования пока в нашей стране не стандартизованы. Отметим, что ЭЦП на высоких уровнях стойкости востребованы уже сейчас. Например, сверхнадежные подписи нужны для построения долговременных архивных хранилищ.

Для поддержки ЭЦП на уровнях l = 192 и l = 256 было решено разработать  семейство алгоритмов хэширования. Это семейство получило рабочее название Bash (Hash c заменой H на B). 

Алгоритмы Bash строятся по схеме sponge (губка),  предложенной Г. Бертони, Дж. Дэменом, М. Питерсом и Ж. Ван Ашем.  Базовым композиционным элементом Bash является шаговая функция Bash-f. Эта функция обновляет хэш-состояние по очередному блоку обрабатываемых данных. Функция строится с помощью логических операций (¬, ∨, ∧) над 64-разрядными словами, циклических сдвигов этих слов и поразрядных исключающих сложений (⊕). Таким образом, функция относится к классу LRX (Logical + Rotation + Xor).

Выбранная платформа sponge + LRX была с успехом применена в алгоритмах хэширования Keccak (SHA-3). Эти алгоритмы стандартизированы в США в 2015 году. Считая семейство Keccak творческой удачей и с уважением относясь к многочисленным криптографическим находкам его разработчиков, мы, тем не менее, решили продолжить традицию национальной криптографии и разработать собственное семейство. По нашим оценкам, производительность Bash близка к производительности Keccak. Текущие гарантии стойкости, выраженные в оценках снизу для числа активных S-блоков, для Bash и Keccak также сопоставимы. 

Уровни стойкости алгоритмов Bash не исчерпываются числами 192 и 256 – разрешены любые значения из множества {16, 32, 48,…, 256}. Алгоритм уровня l обрабатывает данные блоками из 1536 – 4l битов и возвращает хэш-значение длины 2l.

Схема sponge в Bash настроена следующим образом:

• длина хэш-состояния (capacity) выбрана равной 1536;
• в начальном состоянии указывается уровень l;
• блоки данных обрабатываются в режиме перезаписи (а не в обычном Xor-режиме, как в Keccak);
• использован sponge-совместимый паддинг: к хэшируемому слову добавляется сначала бит 0, затем бит 1, а затем снова нулевые биты до тех пор, пока не будет достигнута граница блока.

Шаговая функция Bash-f представляет собой биекцию на {0,1}¹⁵³⁶. Подлежащее преобразованию двоичное слово разбивается на 24 машинных слова длины 64. Эти слова записываются в матрицу 3 x 8:

Столбцы матрицы называются вертикальными плоскостями, строки – горизонтальными. Действие Bash-f состоит в 24-кратном применении тактовых подстановок. Тактовая  подстановка действует следующим образом:

1. К вертикальным плоскостям применяются линейные преобразования L3. Для обработки каждой плоскости требуются  4 циклических сдвига слов плоскости и 6 сложений ⊕. Наборы величин сдвигов для разных плоскостей различны. Эти наборы получаются друг из друга умножением на 7 по модулю 64.
   
2. К каждой вертикальной плоскости применяется нелинейное преобразование S3. Оно задается одной операцией ¬, двумя операциями ∨, одной ∧ и тремя ⊕ (всего 7 операций с машинными словами).
3. Перестановка P меняет слова матрицы местами: сдвигает горизонтальные плоскости вверх и одновременно переставляет слова в плоскостях.
4. К последнему (правому нижнему) слову матрицы добавляется тактовая константа. Константы не повторяются, что делает тактовые преобразования разными (неоднородными).

Композиционные элементы Bash-f мы выбирали в соответствии с криптографическим принципом, который часто называют rigidity и который можно описать известным рекламным слоганом: "при всем богатстве выбора другой альтернативы нет". Мы последовательно исключали различные конфигурации композиционных элементов, используя разумные критерии их качества. В конце концов мы оставляли несколько подходящих конфигураций и всякий раз выбирали первую из них.

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