ECHO

ECHO — хеш-функция, выдвинутая как кандидат на конкурс SHA-3, проводимый Национальным институтом стандартов и технологий (США). Алгоритм разработан в Orange Labs, его авторы:

Ryad Benadjila
Olivier Billet
Henri Gilbert
Gilles Macario-Rat

Thomas Peyrin
Matt Robshaw
Yannick Seurin

Краткий обзор

В качестве аргументов для хеш-функции выступают сообщение и «соль» (которая далее обозначается как $SALT$ ). Длина последнего аргумента составляет 128 бит, при этом по умолчанию его значение принимается равным 0. Размер выхода ECHO может меняться от 128 до 512 бит.

Алгоритм вычисления ECHO основан на построении Меркле-Дамгаарда и, в соответствии с этим построением, представляет собой последовательное применение функции сжатия (определена ниже), зависящей от переменной цепочки $V_{i - 1}$ , блока сообщения $M_{i}$ и, возможно, других параметров. При определении самой функции сжатия в ECHO используются операции AES.

Обозначения

ECHO работает со 128-битными словами, поэтому любое сообщение $M$ перед вычислением хеш-функции дополняется так, чтобы его длина была кратна 128. Дополненное сообщение $M^{'}$ можно представить битовой строкой длины $n$

$b_{0} b_{1} ... b_{n - 2} b_{n - 1}$

или последовательностью из $s = \frac{n}{8}$ байт ( $‖$ обозначает конкатенацию)

$B_{0}$	$=$	$b_{0} ‖ b_{1} ‖ ... ‖ b_{7}$
$B_{1}$	$=$	$b_{8} ‖ b_{9} ‖ ... ‖ b_{15}$
$⋮$
$B_{s - 1}$	$=$	$b_{n - 8} ‖ b_{n - 7} ‖ ... ‖ b_{n - 1}$

ECHO использует операции из AES, которые работают с байтовыми массивами размером 4 на 4. Соответственно, принимается следующая упаковка строки байт в массив:

B_{0} ‖ B_{1} ‖ ... ‖ B_{15} ⟶

$B_{0}$	$B_{4}$	$B_{8}$	$B_{12}$
$B_{1}$	$B_{5}$	$B_{9}$	$B_{13}$
$B_{2}$	$B_{6}$	$B_{10}$	$B_{14}$
$B_{3}$	$B_{7}$	$B_{11}$	$B_{15}$

Аналогично, входное сообщение можно представить как последовательность $r = \frac{n}{128}$ 128-битовых слов

$w_{0}$	$=$	$B_{0} ‖ B_{1} ‖ ... ‖ B_{15}$	$=$	$b_{0} ‖ b_{1} ‖ ... ‖ b_{127}$
$w_{1}$	$=$	$B_{16} ‖ B_{17} ‖ ... ‖ B_{31}$	$=$	$b_{128} ‖ b_{129} ‖ ... ‖ b_{255}$
	$⋮$		$⋮$
$w_{r - 1}$	$=$	$B_{s - 16} ‖ B_{s - 15} ‖ ... ‖ B_{s - 1}$	$=$	$b_{n - 128} ‖ b_{n - 127} ‖ ... ‖ b_{n - 1}$

Упаковка шестнадцати 128-битных слов в массив:

w_{0} ‖ w_{1} ‖ ... ‖ w_{15} ⟶

$w_{0}$	$w_{4}$	$w_{8}$	$w_{12}$
$w_{1}$	$w_{5}$	$w_{9}$	$w_{13}$
$w_{2}$	$w_{6}$	$w_{10}$	$w_{14}$
$w_{3}$	$w_{7}$	$w_{11}$	$w_{15}$

Функция сжатия

В зависимости от желаемой битовой длины $HSIZE$ результата хеширования в ECHO применяются две функции сжатия: ${COMPRESS}_{512}$ и ${COMPRESS}_{1024}$ . Нижний индекс равен длине $CSIZE$ переменной цепочки. На итерации $i$ обе функции принимают 4 параметра:

Текущее значение переменной цепочки $V_{i - 1}$ с битовой длиной $CSIZE$ .
Текущий блок сообщения с битовой длиной $MSIZE = 2048 - CSIZE$ .
Полное число $C_{i}$ бит сообщения, обработанных к концу данной итерации. Если текущий блок $M$ — последний, то $C_{i}$ может оказаться меньше или равно значению $i * MSIZE$ . В противном случае выполняется равенство $C_{i} = i * MSIZE$ . Размер счётчик $C_{i}$ можно выбрать равным 64 или 128 битам.
$SALT$ .

То, какая функция сжатия используется, зависит от выбранной битовой длины значения хеш-функции. Для $HSIZE$ от 128 до 256 бит применяется ${COMPRESS}_{512}$ :

$V_{i} = {COMPRESS}_{512} (V_{i - 1}, M_{i}, C_{i}, SALT)$ ,

для $HSIZE$ от 257 до 512 бит переменная цепочки вычисляется по формуле

$V_{i} = {COMPRESS}_{1024} (V_{i - 1}, M_{i}, C_{i}, SALT)$

Результатом работы обеих функций является некоторое значение с фиксированной битовой длиной. Поэтому для получения величин размера $HSIZE$ конечный результат сокращается на необходимое число бит.

Инициализация

В начале хеширования счетчик $C$ устанавливается в 0: $C_{0} = 0$ . Начальное значение переменной цепочки устанавливается таким образом, что каждое её слово является 128 битовым представлением числа $HSIZE$ , то есть размера результата хеширования. В том случае, когда используется ${COMPRESS}_{512}$ ( $HSIZE$ лежит в пределах от 128 до 256 бит) переменная цепочки $V_{0}$ состоит из 4 слов:

$V_{0} = (v_{0}^{0}, v_{0}^{1}, v_{0}^{2}, v_{0}^{3}),$

$v_{0}^{i} = {\begin{matrix} E0000000 00000000 00000000 00000000, & HSIZE = 224 \\ 00010000 00000000 00000000 00000000, & HSIZE = 256 \end{matrix}, 0 \leq i \leq 3$

Когда применяется ${COMPRESS}_{1024}$ ( $HSIZE$ от 257 до 512 бит),

$V_{0} = (v_{0}^{0}, v_{0}^{1}, v_{0}^{2}, v_{0}^{3}, v_{0}^{4}, v_{0}^{5}, v_{0}^{6}, v_{0}^{7}),$

$v_{0}^{i} = {\begin{matrix} 80010000 00000000 00000000 00000000, & HSIZE = 384 \\ 00020000 00000000 00000000 00000000, & HSIZE = 512 \end{matrix}, 0 \leq i \leq 7$

Дополнение сообщения

Результатом дополнения сообщения $M$ является сообщение $M^{'}$ , длина которого кратна 128. Обозначим через $L$ длину исходного сообщения. Тогда $M^{'}$ получается в несколько шагов:

К концу сообщения $M$ приписать бит «1».
Приписать $x$ битов «0», где $x = MSIZE - ((L + 144) mod MSIZE) - 1$
Приписать 16-битное представление числа $HSIZE$
Наконец, приписать 128-битное представление числа $L$

Дополненное сообщение $M^{'}$ записывается в виде

$M^{'} = \overset{L}{\overset{⏞}{M}} ‖ 1 ‖ \overset{x}{\overset{⏞}{0.....0}} ‖ \overset{16}{\overset{⏞}{HSIZE}} ‖ \overset{128}{\overset{⏞}{L}}$

COMPRESS₅₁₂

Дополненное сообщение $M^{'}$ делится на $t$ блоков $M_{1} ... M_{t}$ , каждый длиной $MSIZE = 1536$ бит. Эти блоки друг за другом подаются на вход функции ${COMPRESS}_{512}$ , при этом в итоге вычисляется $t + 1$ значений переменной цепочки:

$V_{i} = {COMPRESS}_{512} (V_{i - 1}, M_{i}, C_{i}, SALT), 0 \leq i \leq t$

Каждый блок $M_{i}$ можно представить в виде двенадцати 128-битовых слов:

$M_{i} = m_{i}^{0} ‖ m_{i}^{1} ‖ m_{i}^{2} ‖ m_{i}^{3} ‖ m_{i}^{4} ‖ m_{i}^{5} ‖ m_{i}^{6} ‖ m_{i}^{7} ‖ m_{i}^{8} ‖ m_{i}^{9} ‖ m_{i}^{10} ‖ m_{i}^{11}$

Переменная цепочки $V_{i - 1}$ аналогичным образом записывается в виде последовательности из 4 слов:

$V_{i - 1} = v_{i - 1}^{0} ‖ v_{i - 1}^{1} ‖ v_{i - 1}^{2} ‖ v_{i - 1}^{3}$

Дальнейшие операции проводятся над матрицей состояния $S$ из 4 строк и 4 столбцов:

S

=

$w_{0}$	$w_{4}$	$w_{8}$	$w_{12}$
$w_{1}$	$w_{5}$	$w_{9}$	$w_{13}$
$w_{2}$	$w_{6}$	$w_{10}$	$w_{14}$
$w_{3}$	$w_{7}$	$w_{11}$	$w_{15}$

В начале $i$ -ой итерации вычисления значения ${COMPRESS}_{512}$ $V_{i}$ и $M_{i}$ упаковываются в матрицу $S$ следующим образом:

S

=

$v_{i - 1}^{0}$	$m_{i}^{0}$	$m_{i}^{4}$	$m_{i}^{8}$
$v_{i - 1}^{1}$	$m_{i}^{1}$	$m_{i}^{5}$	$m_{i}^{9}$
$v_{i - 1}^{2}$	$m_{i}^{2}$	$m_{i}^{6}$	$m_{i}^{10}$
$v_{i - 1}^{3}$	$m_{i}^{3}$	$m_{i}^{7}$	$m_{i}^{11}$

Вычисление ${COMPRESS}_{512}$ происходит в 8 раундов, называемых в ECHO $BIG.ROUND$ . Каждый такой раунд состоит из последовательного применения 3 функций:

$BIG.SUBWORDS (S, SALT, κ)$

$BIG.SHIFTROWS (S)$

$BIG.MIXCOLUMNS (S)$

BIG.SUBWORDS(S, SALT, κ)

$BIG.SUBWORDS (S, SALT, κ)$ — это 2 AES раунда. Обозначим действие одного раунда AES с ключом $k$ на 128-битное слово $w$ как

$w^{'} = AES (w, k)$

Здесь $AES$ состоит из операций $SubBytes$ , $ShiftRows$ , $MixColumns$ и $AddRoundKey$ . Ключи $k$ для вычисления $w^{'}$ создаются из параметров $SALT$ и $κ$ . Последний представляет собой внутренний счетчик, который инициализируется значением $C_{i}$ и увеличивается во время вычисления ${COMPRESS}_{512}$ . Важно заметить, что, если в последнем блоке $M_{t}$ биты исходного сообщения отсутствуют (что могло случится, например, при длине сообщения $L$ , кратной $MSIZE$ ), то $C_{t}$ полагается равным 0.

Значения ключей для двух раундов AES получаются следующим образом:

$k_{1} = κ ‖ \overset{64}{\overset{⏞}{0..0}}, k_{2} = SALT,$

если счетчик $C_{i}$ выбран 64-битным, и

$k_{1} = κ, k_{2} = SALT$

для 128-битного счетчика.

Операцию $BIG.SUBWORDS (S, SALT, κ)$ можно описать равенствами

${w_{0^{'}}}^{'} = A E S (A E S (w_{0}, k_{1}), k_{2})$ , увеличить $κ$ на 1 по модулю $2^{64}$ ( $2^{128}$ )

${w_{1^{'}}}^{'} = A E S (A E S (w_{1}, k_{1}), k_{2})$ , увеличить $κ$ на 1 по модулю $2^{64}$ ( $2^{128}$ )

$...$

${w_{15^{'}}}^{'} = A E S (A E S (w_{15}, k_{1}), k_{2})$ , увеличить $κ$ на 1 по модулю $2^{64}$ ( $2^{128}$ )

Счетчик $κ$ увеличивается на протяжении всех восьми раундов (которые выше названы $BIG.ROUND$ ), то есть, например, в начале второго раунда $κ = C_{i} + 16$ .

BIG.SHIFTROWS(S)

Операция $BIG.SHIFTROWS (S)$ проводит циклический сдвиг влево строк матрицы состояния $S$ :

${w_{i^{'} + 4 j}}^{'} = w_{i + 4 ((i + j) mod 4)}, 0 \leq i, j \leq 3$ .

Более наглядно:

$w_{0}$	$w_{4}$	$w_{8}$	$w_{12}$
$w_{1}$	$w_{5}$	$w_{9}$	$w_{13}$
$w_{2}$	$w_{6}$	$w_{10}$	$w_{14}$
$w_{3}$	$w_{7}$	$w_{11}$	$w_{15}$

⟶

$w_{0}$	$w_{4}$	$w_{8}$	$w_{12}$
$w_{5}$	$w_{9}$	$w_{13}$	$w_{1}$
$w_{10}$	$w_{14}$	$w_{2}$	$w_{6}$
$w_{15}$	$w_{3}$	$w_{7}$	$w_{11}$

BIG.MIXCOLUMNS(S)

$BIG.MIXCOLUMNS (S)$ состоит из последовательного применения операции $MixColumns$ , определенной в AES. Рассмотрим столбцы матрицы $S$ , состоящие из 128-битных слов $w_{i}, ..., w_{i + 3}$ , где $i \in {0, 4, 8, 12}$ . Элементы столбцов можно представить в виде байтовых строк:

$w_{i}$	$=$	$(B_{16 i}, B_{16 i + 1}, ..., B_{16 i + 15})$
$w_{i + 1}$	$=$	$(B_{16 i + 16}, B_{16 i + 17}, ..., B_{16 i + 31})$
$w_{i + 2}$	$=$	$(B_{16 i + 32}, B_{16 i + 33}, ..., B_{16 i + 47})$
$w_{i + 3}$	$=$	$(B_{16 i + 48}, B_{16 i + 49}, ..., B_{16 i + 63})$

Тогда $BIG.MIXCOLUMNS (S)$ вычисляется как

$(\begin{matrix} {B_{16^{'} i + j}}^{'} \\ {B_{16^{'} i + 16 + j}}^{'} \\ {B_{16^{'} i + 32 + j}}^{'} \\ {B_{16^{'} i + 48 + j}}^{'} \end{matrix}) = (\begin{matrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{matrix}) \cdot (\begin{matrix} B_{16 i + j} \\ B_{16 i + 16 + j} \\ B_{16 i + 32 + j} \\ B_{16 i + 48 + j} \end{matrix}), i \in {0, 4, 8, 12}, 0 \leq j \leq 15$

Последняя формула представляет собой операцию $MixColumns$ , в которой сложение и умножение определены в поле $G F (2^{8})$ по модулю многочлена $x^{8} + x^{4} + x^{3} + x + 1$ .

Окончание вычисления COMPRESS₅₁₂

Функцию ${COMPRESS}_{512}$ можно описать, используя определенные выше операции:

$for i:= 1 to 8 do$

begin

BIG.SUBWORDS (S, SALT, κ)

BIG.SHIFTROWS (S)

BIG.MIXCOLUMNS (S)

end

BIG.FINAL

Операция $BIG.FINAL$ вычисляет значение переменной цепочки $V_{i}$ , используя полученную в результате применения 8 раундов матрицу состояния $S$ , блок сообщения $M_{i}$ и предыдущее значение переменной цепочки $V_{i - 1}$ :

$v_{i}^{0}$	$=$	$v_{i - 1}^{0} \oplus m_{i}^{0} \oplus m_{i}^{4} \oplus m_{i}^{8} \oplus w_{0} \oplus w_{4} \oplus w_{8} \oplus w_{12}$
$v_{i}^{1}$	$=$	$v_{i - 1}^{1} \oplus m_{i}^{1} \oplus m_{i}^{5} \oplus m_{i}^{8} \oplus w_{1} \oplus w_{5} \oplus w_{9} \oplus w_{13}$
$v_{i}^{2}$	$=$	$v_{i - 1}^{2} \oplus m_{i}^{2} \oplus m_{i}^{6} \oplus m_{i}^{9} \oplus w_{2} \oplus w_{6} \oplus w_{10} \oplus w_{14}$
$v_{i}^{3}$	$=$	$v_{i - 1}^{3} \oplus m_{i}^{3} \oplus m_{i}^{7} \oplus m_{i}^{10} \oplus w_{3} \oplus w_{7} \oplus w_{11} \oplus w_{15}$

Здесь за $w_{0}, ..., w_{15}$ обозначены элементы матрицы $S$ , $\oplus$ — операция исключающего ИЛИ.

Конечное значение хеш-функции

Конечное значение переменной цепочки — это строка из 512 бит:

$v_{t}^{0} ‖ v_{t}^{1} ‖ v_{t}^{2} ‖ v_{t}^{3}$

Результатом хеширования с битовой длиной $HSIZE$ , принимающей значения от 128 до 256, являются $HSIZE$ крайних левых бит переменной цепочки. Например, для значения хеш-функции $h$ с длиной $HSIZE = 256$ :

$h = v_{t}^{0} ‖ v_{t}^{1} .$

COMPRESS₁₀₂₄

Для значений $HSIZE$ , больших 256 (но не превышающих 512) бит применяется функция сжатия ${COMPRESS}_{1024}$ . Операции в ${COMPRESS}_{1024}$ совпадают с операциями в ${COMPRESS}_{512}$ , за исключением нескольких отличий:

1. Дополненное сообщение

M^{'}

разбивается на

t

блоков

M_{1} ... M_{t}

, каждый из которых имеет длину 1024 бит.

2. Переменная цепочки состоит из восьми 128-битовых слов

V_{i} = v_{i}^{0} ... v_{i}^{7}

и инициализируется так, как описано выше.

3. В начале сжатия переменная цепочки и блок сообщения упаковываются в матрицу 4 на 4 следующим образом:

$v_{i - 1}^{0}$	$v_{i - 1}^{4}$	$m_{i}^{0}$	$m_{i}^{4}$
$v_{i - 1}^{1}$	$v_{i - 1}^{5}$	$m_{i}^{1}$	$m_{i}^{5}$
$v_{i - 1}^{2}$	$v_{i - 1}^{6}$	$m_{i}^{2}$	$m_{i}^{6}$
$v_{i - 1}^{3}$	$v_{i - 1}^{7}$	$m_{i}^{3}$	$m_{i}^{7}$

4. Вычисление состоит из десяти итераций

BIG.ROUND

(а не из восьми, как в

{COMPRESS}_{512}

).

5. Операция

BIG.FINAL

для

{COMPRESS}_{1024}

переопределяется следующим образом:

$v_{i}^{0}$	$=$	$v_{i - 1}^{0} \oplus m_{i}^{0} \oplus w_{0} \oplus w_{8}$	$v_{i}^{4}$	$=$	$v_{i - 1}^{4} \oplus m_{i}^{4} \oplus w_{4} \oplus w_{12}$
$v_{i}^{1}$	$=$	$v_{i - 1}^{1} \oplus m_{i}^{1} \oplus w_{1} \oplus w_{9}$	$v_{i}^{5}$	$=$	$v_{i - 1}^{5} \oplus m_{i}^{5} \oplus w_{5} \oplus w_{13}$
$v_{i}^{2}$	$=$	$v_{i - 1}^{2} \oplus m_{i}^{2} \oplus w_{2} \oplus w_{10}$	$v_{i}^{6}$	$=$	$v_{i - 1}^{6} \oplus m_{i}^{6} \oplus w_{6} \oplus w_{14}$
$v_{i}^{3}$	$=$	$v_{i - 1}^{3} \oplus m_{i}^{3} \oplus w_{3} \oplus w_{11}$	$v_{i}^{7}$	$=$	$v_{i - 1}^{7} \oplus m_{i}^{7} \oplus w_{7} \oplus w_{15}$

Конечное значение хеш-функции

Длина переменной цепочки для ${COMPRESS}_{1024}$ — 1024 бит, поэтому её конечное значение:

$V_{t} = v_{t}^{0} ‖ v_{t}^{1} ‖ v_{t}^{2} ‖ v_{t}^{3} ‖ v_{t}^{4} ‖ v_{t}^{5} ‖ v_{t}^{6} ‖ v_{t}^{7}$

Как и в ${COMPRESS}_{512}$ , результатом хеширования $h$ являются $HSIZE$ крайних левых бит $V_{t}$ . Например, для $HSIZE = 384$

$h = v_{t}^{0} ‖ v_{t}^{1} ‖ v_{t}^{2} ‖ v_{t}^{3}$

Источники

Кандидаты SHA-3, прошедшие во второй раунд (англ.). Архивировано из оригинала 10 апреля 2012 года.

Страничка хеш-функции ECHO (англ.). Архивировано из оригинала 10 апреля 2012 года.

Ссылки

Конкурс SHA-3 (англ.). Архивировано из оригинала 10 апреля 2012 года.

HAIFA (англ.). — HAsh Iterative FrAmework. Архивировано из оригинала 10 апреля 2012 года.

Хеш-функции
Общего назначения	Adler-32 CRC Контрольная сумма Флетчера FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH-Дерево хешей Jenkins hash Хеш-сумма
Криптографические	ГОСТ Р 34.11-94 Стрибог BelT BLAKE Blue Midnight Wish CubeHash ECHO Edonkey2k FSB Fugue Grøstl HAVAL Hamsi JH Kupyna LM-хеш Luffa MASH-1 MD2 MD4 MD5 MD6 N-Hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 SHA-3 (Keccak) SHABAL SHAvite-3 SIMD SWIFFT Skein Snefru Tiger Whirlpool
Функции формирования ключа	bcrypt PBKDF2 scrypt Argon2 Lyra2
Контрольное число (сравнение)	Контрольная сумма Алгоритм Верхуффа Алгоритм Дамма Алгоритм Луна Штрих-код Банковских счетов Банковских карт ISIN СНИЛС ОКПО ИНН ОКАТО ISBN ОГРН и ОГРНИП VIN
Применение хешей	Сравнение контрольных чисел Коллизия хеш-функции Протоколы аутентификации Сравнение штрихкодов Криптография Magnet-ссылка Подпись Меркла ed2k URN

Краткий обзор

Обозначения

Функция сжатия

Инициализация

Дополнение сообщения

COMPRESS512

BIG.SUBWORDS(S, SALT, κ)

BIG.SHIFTROWS(S)

BIG.MIXCOLUMNS(S)

Окончание вычисления COMPRESS512

Конечное значение хеш-функции

COMPRESS1024

Конечное значение хеш-функции

Источники

Ссылки

COMPRESS₅₁₂

Окончание вычисления COMPRESS₅₁₂

COMPRESS₁₀₂₄