Алгоритмы хэширования 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.

Новости
23.05.2017
XХII научно-практическая конференция «Комплексная защита информации»
31.03.2017
ITSecurity-2017
22.02.2017
Ввод в действие новой редакции СТБ 34.101.47
21.02.2017
План семинара весна 2017
20.01.2017
Итоги NSUCRYPTO-2016
24.10.2016
План семинара осень 2016
29.08.2016
Ввод в действие СТБ 34.101.77
15.06.2016
CTCrypt-2016
19.04.2016
Криптографические стандарты: планы на 2016 год