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

Алгоритм 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 + ${\displaystyle l}$ до 12 + 2 ${\displaystyle l}$
• Padding был изменён со сложной формы на более простую, описанную ниже
• Скорость (rate) r была увеличена до предела безопасности (ранее округлялась вниз до ближайшей степени 2)

Алгоритм

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

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

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

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

В SHA-3 состояние ${\displaystyle S}$ — это массив 5 × 5 слов длиной ${\displaystyle w}$ = 64 бита, всего 5 × 5 × 64 = 1600 бит. Также в Keccak могут использоваться длины ${\displaystyle w}$ , равные меньшим степеням 2 (от ${\displaystyle w}$ = 1 до ${\displaystyle 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 ${\displaystyle w=2^{l}}$ . В основной реализации SHA-3 ${\displaystyle w=64}$ ( ${\displaystyle l=6}$ ).

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

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

Шаг ${\displaystyle \theta }$

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

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

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

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

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

Шаг ${\displaystyle \rho }$

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

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

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

Шаг ${\displaystyle \pi }$

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

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

Шаг ${\displaystyle \chi }$

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

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

Шаг ${\displaystyle \iota }$

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

Алгоритм ${\displaystyle rc(t)}$

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

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

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

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

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

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

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

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

 C[x] = A[x, 0] ${\displaystyle \oplus }$ A[x, 1] ${\displaystyle \oplus }$ A[x, 2] ${\displaystyle \oplus }$ A[x, 3] ${\displaystyle \oplus }$ A[x, 4], x = 0…4;
 D[x] = C[x — 1] ${\displaystyle \oplus }$ (С[x + 1] >>> 1), x = 0…4;
 A[x, y] = A[x, y] ${\displaystyle \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] ${\displaystyle \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 раунда	${\displaystyle 2^{1579}}$
Перестановки	Дифференциальное свойство	Все	8 раундов	${\displaystyle 2^{491.47}}$
Хеш-функция	Атака-различитель	224, 256	4 раунда	${\displaystyle 2^{25}}$
Хеш-функция	Коллизия	224, 256	2 раунда	${\displaystyle 2^{33}}$
Хеш-функция	Нахождение второго прообраза	224, 256	2 раунда	${\displaystyle 2^{33}}$	${\displaystyle 2^{29}}$
Хеш-функция	Нахождение второго прообраза	512	6 раундов	${\displaystyle 2^{506}}$	${\displaystyle 2^{176}}$
Хеш-функция	Нахождение второго прообраза	512	7 раундов	${\displaystyle 2^{507}}$	${\displaystyle 2^{320}}$
Хеш-функция	Нахождение второго прообраза	512	8 раундов	${\displaystyle 2^{511.5}}$	${\displaystyle 2^{508}}$
Хеш-функция	Коллизия	224, 256	4 раунда

Примечания

Ссылки

• от 5 октября 2012 на Wayback Machine / NIST, October 2012 (англ.)
• от 12 октября 2016 на Wayback Machine / Сайт Noekeon, 2015-10-15 — Официальная страница хеш-функции Keccak (англ.)
• от 23 июня 2013 на Wayback Machine , pgpru.com, 2010—2013 (перевод материала с noekon.org)
• от 17 сентября 2017 на Wayback Machine (англ.)

Реализации:

• (англ.) . . The Keccak team. Дата обращения: 6 декабря 2017. 7 декабря 2017 года.
• , Pitaya