SHA-3

SHA-3, Keccak
Разработчики	Гвидо Бертони, Йоан Даймен, Микаел Питерс, Жиль Ван Аше
Создан	2008
Опубликован	2008
Предшественник	SHA-2
Размер хеша	224, 256, 384, 512 (переменный, 0<d≤264-1)
Число раундов	24 (по умолчанию)
Тип	хеш-функция

SHA-3 (Keccak — произносится как «кечак») — алгоритм хеширования переменной разрядности, разработанный группой авторов во главе с Йоаном Дайменом, соавтором Rijndael, автором шифров MMB, SHARK, Noekeon, SQUARE и BaseKing. 2 октября 2012 года Keccak стал победителем конкурса криптографических алгоритмов, проводимого Национальным институтом стандартов и технологий США. 5 августа 2015 года алгоритм утверждён и опубликован в качестве стандарта FIPS 202. В программной реализации авторы заявляют о 12,5 циклах на байт при выполнении на ПК с процессором Intel Core 2. Однако в аппаратных реализациях Keccak оказался намного быстрее, чем все другие финалисты.

Конструкция функции губки, использованная в хеш-функции. P_i — входные блоки, Z_j — выход алгоритма. Размер c («capacity») неиспользуемого для вывода набора битов должен быть значительным для достижения устойчивости к атакам

Алгоритм SHA-3 построен по принципу криптографической губки (данная структура криптографических алгоритмов была предложена авторами алгоритма Keccak ранее).

История

В 2004—2005 годах несколько алгоритмов хеширования были атакованы, в том числе были опубликованы серьезные атаки против алгоритма SHA-1, утвержденного Национальным институтом стандартов и технологий (NIST). В ответ NIST провел открытые семинары и 2 ноября 2007 года анонсировал конкурс на разработку нового алгоритма хеширования. 2 октября 2012 года победителем конкурса стал алгоритм Keccak и был стандартизован как новый алгоритм SHA-3. 5 августа 2015 года алгоритм утвержден и опубликован в качестве стандарта FIPS 202.

Алгоритм был разработан Гвидо Бертони, Йоаном Дайменом, Жилем Ван Аше из STMicroelectronics и Микаэлем Питерсом из NXP.

Алгоритм основан на более ранних хеш-функциях Panama и RadioGatún. Panama был разработан Дайменом и Крейгом Клэппом в 1998 году, RadioGatún был реализован на основе Panama Дайменом, Питерсом и Ван Аше в 2006 году.

В ходе конкурса конкурсантам разрешалось вносить изменения в свой алгоритм для исправления обнаруживающихся проблем. Изменения, внесенные в алгоритм Keccak:

• Количество раундов было увеличено с 12 + $l$ до 12 + 2$l$
• Padding был изменён со сложной формы на более простую, описанную ниже
• Скорость (rate) r была увеличена до предела безопасности (ранее округлялась вниз до ближайшей степени 2)

Алгоритм

Хеш-функции семейства SHA-3 построены на основе конструкции криптографической губки, в которой данные сначала «впитываются» в губку, при котором исходное сообщение $M$ подвергается многораундовым перестановкам $f$, затем результат $Z$ «отжимается» из губки. На этапе «впитывания» блоки сообщения суммируются по модулю 2 с подмножеством состояния, после чего всё состояние преобразуется с помощью функции перестановки $f$. На этапе «отжимания» выходные блоки считываются из одного и того же подмножества состояния, изменённого функцией перестановок $f$. Размер части состояния, который записывается и считывается, называется «скоростью» (англ. rate) и обозначается $r$, а размер части, которая нетронута вводом / выводом, называется «ёмкостью» (англ. capacity) и обозначается $c$.

Алгоритм получения значения хеш-функции можно разделить на несколько этапов:

• Исходное сообщение $M$ дополняется до строки $P$ длины, кратной $r$, с помощью функции дополнения (pad-функции);
• Строка $P$ делится на $n$ блоков длины $r$: $P_{0},P_{1},...,P_{n-1}$;
• «Впитывание»: каждый блок $P_{i}$ дополняется нулями до строки длины $b$ бит и суммируется по модулю 2 со строкой состояния $S$, где $S$ — строка длины $b$ бит ($b$ = $r$ + $c$). Перед началом работы функции все элементы $S$ равны нулю. Для каждого следующего блока состояние — строка, полученная применением функции перестановок $f$ к результату предыдущего шага;
• «Отжимание»: пока длина $Z$ меньше $d$ ($d$ — количество бит в результате хеш-функции), к $Z$ добавляется $r$ первых бит состояния $S$, после каждого прибавления к $S$ применяется функция перестановок $f$. Затем $Z$ обрезается до длины $d$ бит;
• Строка $Z$ длины $d$ бит возвращается в качестве результата.

Благодаря тому, что состояние содержит $c$ дополнительных бит, алгоритм устойчив к атаке удлинением сообщения, к которой восприимчивы алгоритмы SHA-1 и SHA-2.

В SHA-3 состояние $S$ — это массив 5 × 5 слов длиной $w$ = 64 бита, всего 5 × 5 × 64 = 1600 бит. Также в Keccak могут использоваться длины $w$, равные меньшим степеням 2 (от $w$ = 1 до $w$ = 32).

Дополнение

Для того, чтобы исходное сообщение M можно было разделить на блоки длины r, необходимо дополнение. В SHA-3 используется паттерн pad10*1: к сообщению добавляется 1, после него — 0 или больше нулевых битов (до r-1), в конце — 1.

r-1 нулевых битов может быть добавлено, когда последний блок сообщения имеет длину r-1 бит. Этот блок дополняется единицей, следующий блок будет состоять из r-1 нулей и единицы.

Два единичных бита добавляются и в том случае, если длина исходного сообщения M делится на r. В этом случае к сообщению добавляется блок, начинающийся и оканчивающийся единицами, между которыми r-2 нулевых битов. Это необходимо для того, чтобы для сообщения, оканчивающегося последовательностью битов как в функции дополнения, и для сообщения без этих битов значения хеш-функции были различны.

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

Функция перестановок

Функция перестановок, используемая в SHA-3, включает в себя исключающее «ИЛИ» (XOR), побитовое «И» (AND) и побитовое отрицание (NOT). Функция определена для строк длины-степени 2 $w=2^{l}$. В основной реализации SHA-3 $w=64$ ($l=6$).

Состояние $S$ можно представить в виде трёхмерного массива $A$ размером 5 × 5 × $w$. Тогда элемент массива $A[i][j][k]$ - это $(5i+j)\times w+k$ бит строки состояния $S$.

Функция содержит несколько шагов: $\theta$, $\rho$, $\pi$, $\chi$, $\iota$, которые выполняются несколько раундов. На каждом шаге обозначим входной массив A, выходной массив A'.

Шаг $\theta$

Для всех $i$ и $k$, таких, что $0\leqslant i<5$, $0\leqslant k<w$, положим

$C(i,k)=A[i,0,k]\oplus A[i,1,k]\oplus A[i,2,k]\oplus A[i,3,k]\oplus A[i,4,k]$

$D(i,k)=C[(i-1){\bmod {5}},k]\oplus C[(i+1){\bmod {5}},(k-1){\bmod {w}}]$

Для всех $(i,j,k)$, таких, что $0\leqslant i<5$, $0\leqslant j<5$, $0\leqslant k<w$,

$A'[i,j,k]=A[i,j,k]\oplus D[i,k]$

Шаг $\rho$

Для всех $k$, таких, что $0\leqslant k<w$, $A'[0,0,k]=A[0,0,k]$

Пусть в начале $(i,j)=(1,0)$. Для $t$ от 0 до 23:

1. Для всех $k$, таких, что $0\leqslant k<w$, $A'[i,j,k]=A[i,j,(k-(t+1)(t+2)/2){\bmod {w}}]$
2. $(i,j)=(j,(2i+3j){\bmod {5}})$

Шаг $\pi$

Для всех $(i,j,k)$, таких, что $0\leqslant i<5$, $0\leqslant j<5$, $0\leqslant k<w$

$A'[i,j,k]=A[(i+3j){\bmod {5}},i,k]$

Шаг $\chi$

Для всех $(i,j,k)$, таких, что $0\leqslant i<5$, $0\leqslant j<5$,

$A'[i,j,k]=A[i,j,k]\oplus ((A[(i+1){\bmod {5}},j,k]\oplus 1)\cdot A[(i+2){\bmod {5}},j,k])$

Шаг $\iota$

Введем дополнительную функцию $rc(t)$, где вход — целое число $t$, а на выходе — бит.

Алгоритм $rc(t)$

1. Если $t{\bmod {2}}55=0$, то возвращается 1
2. Пусть $R=[10000000]$
3. Для i от 1 до t mod 255:
   1. R = 0 || R
   2. $R[0]=R[0]\oplus R[8]$
   3. $R[4]=R[4]\oplus R[8]$
   4. $R[5]=R[5]\oplus R[8]$
   5. $R[6]=R[6]\oplus R[8]$
   6. $R=Trunc_{8}[R]$
4. Возвращается $R[0]$$.$

Алгоритм $\iota (A,i_{r})$

$i_{r}$ — номер раунда.

1. Для всех $(i,j,k)$, таких, что $0\leqslant i<5$, $0\leqslant j<5$, $0\leqslant k<w$ $A'[i,j,k]=A[i,j,k]$
2. Пусть $RC$ — массив длины $w$, заполненный нулями.
3. Для $i$ от 0 до $l$: $RC[2^{i}-1]=rc(i+7i_{r})$
4. Для всех $k$, таких, что $0\leqslant k<w$, $A'[0,0,k]=A'[0,0,k]\oplus RC[k]$

Алгоритм перестановок

1. Перевод строки $S$ в массив $A$
2. Для $i_{r}$ от $12+2l-n_{r}$ до $12+2l-1$ $A'=\iota (\chi (\pi (\rho (\theta (A)))),i_{r})$
3. Перевод массива $A'$ в строку $S'$ длины $b$

Хеширование сообщений произвольной длины

Основой функции сжатия алгоритма является функция f, выполняющая перемешивание внутреннего состояния алгоритма. Состояние (обозначим его A) представляется в виде массива 5×5, элементами которого являются 64-битные слова, инициализированные нулевыми битами (то есть, размер состояния составляет 1600 битов). Функция f выполняет 24 раунда, в каждом из которых производятся следующие действия:

 C[x] = A[x, 0] $\oplus$ A[x, 1] $\oplus$ A[x, 2] $\oplus$ A[x, 3] $\oplus$ A[x, 4], x = 0…4;
 D[x] = C[x — 1] $\oplus$ (С[x + 1] >>> 1), x = 0…4;
 A[x, y] = A[x, y] $\oplus$ D[x], x = 0…4, y = 0…4;
 B[y, 2x + 3y] = A[x, y] >>> r[x, y], x = 0…4, y = 0…4;
 A[x, y] = B[x, y] $\oplus$ (~B[x + 1, y] & B[x + 2, y]), x = 0…4, y = 0…4, 

Где:

B — временный массив, аналогичный по структуре массиву состояния;

C и D — временные массивы, содержащие по пять 64-битных слов;

r — массив, определяющий величину циклического сдвига для каждого слова состояния;

~x — поразрядное дополнение к x;

и операции с индексами массива выполняются по модулю 5.

Кроме приведенных выше операций, в каждом раунде также выполняется наложение операцией XOR раундовой константы на слово A[0, 0].

Перед выполнением функции сжимания накладывается операция XOR фрагментов исходного сообщения с фрагментами исходного состояния. Результат обрабатывается функцией f. Данное наложение в совокупности с функцией сжимания, выполняемые для каждого блока входных данных, представляют собой «впитывающую» (absorbing) фазу криптографической губки.

Стоит отметить, что функция f использует только операции, стойкие к атакам, использующим утечки данных по побочным каналам.

Результирующее хеш-значение вычисляется в процессе выполнения «выжимающей» (squeezing) фазы криптографической губки, основу которой также составляет описанная выше функция f. Возможные размеры хеш-значений — 224, 256, 384 и 512 бит.

Настройки

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

На протяжения конкурса хеширования Национального института стандартов и технологий участники имели право настраивать свои алгоритмы для решения возникших проблем. Так, были внесены некоторые изменения в Keccak: количество раундов было увеличено с 18 до 24 с целью увеличения запаса безопасности.

Авторы Keccak учредили ряд призов за достижения в криптоанализе данного алгоритма.

Версия алгоритма, принятая в качестве окончательного стандарта SHA-3, имеет несколько незначительных отличий от оригинального предложения Keccak на конкурс. В частности, были ограничены некоторые параметры (отброшены медленные режимы c=768 и c=1024), в том числе для увеличения производительности. Также в стандарте были введены «функции с удлиняемым результатом» (XOF, Extendable Output Functions) SHAKE128 и SHAKE256, для чего хешируемое сообщение стало необходимо дополнять «суффиксом» из 2 или 4 бит, в зависимости от типа функции.

Функция	Формула
SHA3-224(M)	Keccak[448](M||01, 224)
SHA3-256(M)	Keccak[512](M||01, 256)
SHA3-384(M)	Keccak[768](M||01, 384)
SHA3-512(M)	Keccak[1024](M||01, 512)
SHAKE128(M, d)	Keccak[256](M||1111, d)
SHAKE256(M, d)	Keccak[512](M||1111, d)

Дополнительные функции

В декабре 2016 года Национальный институт стандартов и технологий США опубликовал новый документ, NIST SP.800-185, описывающий дополнительные функции на основе SHA-3:

Функция	Описание
cSHAKE128(X, L, N, S)	Параметризованная версия SHAKE
cSHAKE256(X, L, N, S)
KMAC128(K, X, L, S)	Имитовставка на основе Keccak
KMAC256(K, X, L, S)
KMACXOF128(K, X, L, S)
KMACXOF256(K, X, L, S)
TupleHash128(X, L, S)	Хеширование кортежа строк
TupleHash256(X, L, S)
TupleHashXOF128(X, L, S)
TupleHashXOF256(X, L, S)
ParallelHash128(X, B, L, S)	Параллелизуемая хеш-функция на основе Keccak
ParallelHash256(X, B, L, S)
ParallelHashXOF128(X, B, L, S)
ParallelHashXOF256(X, B, L, S)

Тестовые векторы

Значения разных вариантов хеша от пустой строки.

SHA3-224("")
6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7
SHA3-256("")
a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a
SHA3-384("")
0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004
SHA3-512("")
a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26
SHAKE128("", 256)
7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26
SHAKE256("", 512)
46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be

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

SHA3-224("The quick brown fox jumps over the lazy dog")
d15dadceaa4d5d7bb3b48f446421d542e08ad8887305e28d58335795
SHA3-224("The quick brown fox jumps over the lazy dog.")
2d0708903833afabdd232a20201176e8b58c5be8a6fe74265ac54db0

SHA3-256("The quick brown fox jumps over the lazy dog")
69070dda01975c8c120c3aada1b282394e7f032fa9cf32f4cb2259a0897dfc04
SHA3-256("The quick brown fox jumps over the lazy dog.")
a80f839cd4f83f6c3dafc87feae470045e4eb0d366397d5c6ce34ba1739f734d

SHA3-384("The quick brown fox jumps over the lazy dog")
7063465e08a93bce31cd89d2e3ca8f602498696e253592ed26f07bf7e703cf328581e1471a7ba7ab119b1a9ebdf8be41
SHA3-384("The quick brown fox jumps over the lazy dog.")
1a34d81695b622df178bc74df7124fe12fac0f64ba5250b78b99c1273d4b080168e10652894ecad5f1f4d5b965437fb9

SHA3-512("The quick brown fox jumps over the lazy dog")
01dedd5de4ef14642445ba5f5b97c15e47b9ad931326e4b0727cd94cefc44fff23f07bf543139939b49128caf436dc1bdee54fcb24023a08d9403f9b4bf0d450
SHA3-512("The quick brown fox jumps over the lazy dog.")
18f4f4bd419603f95538837003d9d254c26c23765565162247483f65c50303597bc9ce4d289f21d1c2f1f458828e33dc442100331b35e7eb031b5d38ba6460f8

SHAKE128("The quick brown fox jumps over the lazy dog", 256)
f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e
SHAKE128("The quick brown fox jumps over the lazy dof", 256)
853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c

Криптоанализ

Результаты криптоанализа во время конкурса.

Цель	Тип атаки	Выход	Вариант	CF Call	Память
Хеш-функция	Коллизия	160	r = {240, 640, 1440}, c = 160, 1, 2 раунда
Хеш-функция	Нахождение прообраза	80	r = {240, 640, 1440}, c = 160, 1, 2 раунда
Перестановки	Атака-различитель	Все	24 раунда	$2^{1579}$
Перестановки	Дифференциальное свойство	Все	8 раундов	$2^{491.47}$
Хеш-функция	Атака-различитель	224, 256	4 раунда	$2^{25}$
Хеш-функция	Коллизия	224, 256	2 раунда	$2^{33}$
Хеш-функция	Нахождение второго прообраза	224, 256	2 раунда	$2^{33}$	$2^{29}$
Хеш-функция	Нахождение второго прообраза	512	6 раундов	$2^{506}$	$2^{176}$
Хеш-функция	Нахождение второго прообраза	512	7 раундов	$2^{507}$	$2^{320}$
Хеш-функция	Нахождение второго прообраза	512	8 раундов	$2^{511.5}$	$2^{508}$
Хеш-функция	Коллизия	224, 256	4 раунда

Ссылки

• NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition Архивная копия от 5 октября 2012 на Wayback Machine / NIST, October 2012 (англ.)
• The Keccak sponge function family Архивная копия от 12 октября 2016 на Wayback Machine / Сайт Noekeon, 2015-10-15 — Официальная страница хеш-функции Keccak (англ.)
• Хеш-функция Keccak и конструкция Sponge как универсальный криптопримитив Архивная копия от 23 июня 2013 на Wayback Machine, pgpru.com, 2010—2013 (перевод материала с noekon.org)
• SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions | NIST Архивная копия от 17 сентября 2017 на Wayback Machine (англ.)

Реализации:

• Software resources (англ.). https://keccak.team/. The Keccak team. Дата обращения: 6 декабря 2017. Архивировано 7 декабря 2017 года.
• Java implementation, Pitaya