ECHO

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}),}$ 

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

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

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

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

${\displaystyle M'=\overbrace {M} ^{L}\|1\|\overbrace {0.....0} ^{x}\|\overbrace {\mbox{HSIZE}} ^{16}\|\overbrace {L} ^{128}}$ 

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

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

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

${\displaystyle 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}}$ 

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

${\displaystyle V_{i-1}=v_{i-1}^{0}\|v_{i-1}^{1}\|v_{i-1}^{2}\|v_{i-1}^{3}}$ 

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

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

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

${\displaystyle {\mbox{BIG.SUBWORDS}}(S,{\mbox{ SALT}},{\mbox{ }}\kappa )}$ 

${\displaystyle {\mbox{BIG.SHIFTROWS}}(S)}$ 

${\displaystyle {\mbox{BIG.MIXCOLUMNS}}(S)}$ 

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

${\displaystyle w'={\mbox{AES}}(w,k)}$ 

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

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

${\displaystyle k_{1}=\kappa \|\overbrace {0..0} ^{64}{\mbox{, }}k_{2}={\mbox{SALT}},}$ 

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

${\displaystyle k_{1}=\kappa {\mbox{ , }}k_{2}={\mbox{SALT}}}$ 

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

Операцию ${\displaystyle {\mbox{BIG.SUBWORDS}}(S,{\mbox{ SALT}},{\mbox{ }}\kappa )}$  можно описать равенствами

${\displaystyle w_{0}'=AES(AES(w_{0},k_{1}),k_{2})}$ , увеличить ${\displaystyle \kappa }$  на 1 по модулю ${\displaystyle 2^{64}}$  (${\displaystyle 2^{128}}$ )

${\displaystyle w_{1}'=AES(AES(w_{1},k_{1}),k_{2})}$ , увеличить ${\displaystyle \kappa }$  на 1 по модулю ${\displaystyle 2^{64}}$  (${\displaystyle 2^{128}}$ )

${\displaystyle ...}$ 

${\displaystyle w_{15}'=AES(AES(w_{15},k_{1}),k_{2})}$ , увеличить ${\displaystyle \kappa }$  на 1 по модулю ${\displaystyle 2^{64}}$  (${\displaystyle 2^{128}}$ )

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

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

${\displaystyle w_{i+4j}'=w_{i+4((i+j){\bmod {4}})},{\mbox{ }}0\leq i,j\leq 3}$ .

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

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

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

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

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

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

${\displaystyle {\mbox{for i := 1 to 8 do}}}$ 

${\displaystyle {\mbox{begin}}}$ 

${\displaystyle {\mbox{BIG.SUBWORDS}}(S,{\mbox{ SALT}},{\mbox{ }}\kappa )}$ 

${\displaystyle {\mbox{BIG.SHIFTROWS}}(S)}$ 

${\displaystyle {\mbox{BIG.MIXCOLUMNS}}(S)}$ 

${\displaystyle {\mbox{end}}}$ 

${\displaystyle {\mbox{BIG.FINAL}}}$ 

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

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

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

${\displaystyle v_{t}^{0}\|v_{t}^{1}\|v_{t}^{2}\|v_{t}^{3}}$ 

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

${\displaystyle h=v_{t}^{0}\|v_{t}^{1}.}$ 

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

1.  Дополненное сообщение ${\displaystyle M'}$  разбивается на ${\displaystyle t}$  блоков ${\displaystyle M_{1}...M_{t}}$ , каждый из которых имеет длину 1024 бит.

2.  Переменная цепочки состоит из восьми 128-битовых слов ${\displaystyle V_{i}=v_{i}^{0}...v_{i}^{7}}$  и инициализируется так, как описано выше.

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

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

4.  Вычисление состоит из десяти итераций ${\displaystyle {\mbox{BIG.ROUND}}}$  (а не из восьми, как в ${\displaystyle {\mbox{COMPRESS}}_{512}}$ ).

5.  Операция ${\displaystyle {\mbox{BIG.FINAL}}}$  для ${\displaystyle {\mbox{COMPRESS}}_{1024}}$  переопределяется следующим образом:

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

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

${\displaystyle 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}}$ 

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

${\displaystyle 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 года.