Алгоритмы хэширования 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}1536. Подлежащее преобразованию двоичное слово разбивается на 24 машинных слова длины 64. Эти слова записываются в матрицу 3 x 8:

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

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

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

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

Новости
24.02.2020
План семинара весна 2020
20.10.2019
План семинара осень 2019
01.10.2019
XII Международная научная конференция
18.04.2019
Школа по компьютерным наукам
18.04.2019
Computer Science Summer
01.04.2019
AgatCTF-2019
07.03.2019
CDAM’2019
04.03.2019
План семинара весна 2019
12.09.2018
План семинара осень 2018