Bash (хэш-функция)

Bash — государственный стандарт, описывающий алгоритмы хэширования стандартизированные в Республики Беларусь. Полное название стандарта — СТБ 34.101.77-2016 «Информационные технологии и безопасность. Алгоритмы хэширования».

Описание

Назначение

Настоящий стандарт определяет семейство криптографических алгоритмов хэширования, предназначенных для контроля целостности и необратимого сжатия данных. Обрабатываемыми данными являются двоичные слова (сообщения).

Алгоритм хэширования по сообщению произвольной длины строит хэш-значение — слово фиксированной длины. Стороны могут организовать контроль целостности сообщений путем сравнения их хэш-значений с достоверными контрольными хэш-значениями. Изменение сообщения с высокой вероятностью приводит к изменению соответствующего хэш-значения, и поэтому хэш-значения могут использоваться вместо самих сообщений, например в системах ЭЦП.

Алгоритмы хэширования могут дополнительно использоваться при построении систем имитозащиты, генераторов случайных и псевдослучайных чисел, протоколов аутентификации, доказательств вычислительной работы и др.

Примечание: Алгоритм хэширования установлен также в СТБ 34.101.31. Переход от алгоритма СТБ 34.101.31 к алгоритмам настоящего стандарта позволит увеличить скорость хэширования по крайней мере на паритетном уровне стойкости и на 64-разрядных аппаратных платформах. Кроме этого, алгоритмы хэширования настоящего стандарта поддерживают все три уровня стойкости алгоритмов ЭЦП, определенных в СТБ 34.101.45, в то время как алгоритм СТБ 34.101.31 поддерживает только первый уровень.

Шаговая функция

Алгоритмы хэширования построены по схеме sponge (губка). Ядром схемы является шаговая функция, которая определяет сложное биективное преобразование слов большой длины.

В настоящем стандарте шаговая функция действует на слова длины 1536. Действие задается алгоритмом bash-f.

Шаговая функция bash-f имеет самостоятельное значение и может использоваться за пределами настоящего стандарта для построения других криптографических алгоритмов.

Уровень стойкости

Алгоритмы хэширования настоящего стандарта отличаются уровнем стойкости 𝑙. Это натуральное число, кратное 16 и не превосходящее 256. Алгоритм уровня 𝑙 вычисляет хэш-значения длины 2𝑙, обрабатывая входные слова блоками длины 1536 − 4𝑙. Уровни 𝑙 = 128, 𝑙 = 192 и 𝑙 = 256 являются стандартными, им следует отдавать предпочтение.

При выборе 𝑙 следует учитывать, что для определения сообщения с заданным хэш-значением требуется выполнить порядка $2^{2l}$ операций, а для определения двух различных сообщений с одинаковыми хэш-значениями требуется выполнить порядка $2^{l}$ операций.

Следует учитывать также, что с ростом 𝑙, кроме повышения стойкости, снижается быстродействие алгоритмов. В частности, хэширование на уровне 𝑙 = 256 выполняется примерно в 2 раза медленнее, чем на уровне 𝑙 = 128.

Хэш-значение

Длина хэш-значения регулируется уровнем стойкости 𝑙. Если при фиксированном 𝑙 требуются не все, а 𝑛 < 2𝑙 символов хэш-значения, то должны использоваться первые 𝑛 символов.

Все обозначение определены в стандарте (раздел 4).

Вспомогательные алгоритмы

Алгоритм bash-s

Входные и выходные данные

Входными данными алгоритма bash-s являются слова $W_{0},W_{1},W_{2}\in {\{0,1\}}^{64}$ и числа $m_{1},n_{1},m_{2},n_{2}\in \{1,2,...,63\}$. Выходными данными являются преобразованные слова $W_{0},W_{1},W_{2}.$

Переменные

Используются переменные $T_{0},T_{1},T_{2}\in \{0,1\}^{64}$.

Шаги алгоритма

Преобразование слов $W_{0},W_{1},W_{2}$ состоит в выполнении следующих шагов:

1. $T_{0}\leftarrow RotHi^{m_{1}}(W_{0})$
2. $W_{0}\leftarrow W_{0}\oplus W_{1}\oplus W_{2}$
3. $T_{1}\leftarrow W_{1}\oplus RotHi^{n_{1}}(W_{0})$
4. $W_{1}\leftarrow T_{0}\oplus T_{1}$
5. $W_{2}\leftarrow W_{2}\oplus RotHi^{m_{2}}(W_{2})\oplus RotHi^{n_{2}}(T_{1})$
6. $T_{0}\leftarrow \urcorner W_{2}$
7. $T_{1}\leftarrow W_{0}\vee W_{2}$
8. $T_{2}\leftarrow W_{0}\land W_{1}$
9. $T_{0}\leftarrow T_{0}\vee W_{1}$
10. $W_{1}\leftarrow W_{1}\oplus T_{1}$
11. $W_{2}\leftarrow W_{2}\oplus T_{2}$
12. $W_{0}\leftarrow W_{0}\oplus T_{0}$
13. Возвратить $(W_{0},W_{1},W_{2})$

Алгоритм bash-f

Входные и выходные данные

Входными данными алгоритма bash-f является слово $S\in \{0,1\}^{1536}$ .

Выходными данными является преобразованное слово 𝑆.

Слово 𝑆 записывается в виде $S=S_{0}||S_{1}||...||S_{23},S_{i}\in \{0,1\}^{64}$

Переменные

Используются переменные $C\in \{0,1\}^{64}$ и $m_{1},n_{1},m_{2},n_{2}\in \{1,2,...,63\}$

Шаги алгоритма

Преобразование слова 𝑆 состоит в выполнении следующих шагов:

1. $C\leftarrow {B194BAC80A08F53B}_{16}$.

2. Для i = 1, 2,…, 24 выполнить:

1) $(m_{1},n_{1},m_{2},n_{2})\leftarrow (8,53,14,1)$;

2) для j = 0, 1,…, 7:

a)$(S_{j},S_{8+j},S_{16+j})\leftarrow bash-s(S_{j},S_{8+j},S_{16+j},m_{1},n_{1},m_{2},n_{2})$;

b)$(m_{1},n_{1},m_{2},n_{2})\leftarrow (7m_{1}\ mod\ 64,7n_{1}\ mod\ 64,7m_{2}\ mod\ 64,7n_{2}\ mod\ 64)$;

3) $S\leftarrow S_{15}||S_{10}||S_{9}||S_{12}||S_{11}||S_{14}||S_{13}||S_{8}||S_{17}||S_{16}||S_{19}||S_{18}||S_{21}||S_{20}||S_{23}||S_{22}||S_{6}||S_{3}||S_{0}||S_{5}||S_{2}||S_{7}||S_{4}||S_{1}$

4) $S_{23}\leftarrow S_{23}\oplus C$;

5) если ${\overline {C}}$ — четное, то $C\leftarrow ShLo(C)$;

иначе $C\leftarrow ShLo(C)\oplus {AED8E07F99E12BDC}_{16}$.

3. Возвратить S.

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

Входные и выходные данные

Входными данными алгоритма хэширования уровня стойкости 𝑙 является сообщение $X\in \{0,1\}^{*}$

Выходными данными является слово $Y\in \{0,1\}^{2l}$ — хэш-значение сообщения $X$.

Вспомогательные преобразования и переменные

Используются алгоритм bash-f, и переменная $S\in \{0,1\}^{1536}$

Шаги алгоритма

Хэширование сообщения $X$ на уровне стойкости 𝑙 состоит в выполнении следующих шагов:

1. Дописать к $X$ сначала слово $01$, а затем $t$ символов $0$, где $t$ — минимальное неотрицательное целое, для которого $|X|+2+t$ кратно $1536-4l$.

2. Полученное слово $X||01||0^{t}$ записать в виде $X_{1}||X_{2}||X_{n},X_{i}\in \{0,1\}^{1536-4l}$

3. $S\leftarrow 0^{1472}||\left\langle l/4\right\rangle _{64}$.

4. Для i = 1, 2,…, n выполнить:

1) $Lo_{1536-4l}(S)\leftarrow X_{i}$;

2) $S\leftarrow$ bash-f$(S)$.

5. $Y\leftarrow Lo_{2l}(S)$

6. Возвратить $Y$.