SHA-3

7 хв читання
19 мовами

Keccak (англ. Secure Hash Algorithms-3, SHA-3) — (вимовляється як «кечак») — алгоритм гешування змінної розрядності, розроблений групою авторів на чолі з Йоаном Дайменом, співавтором 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 + $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$ . Потім $S$ обрізається до довжини $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[i][j][k]$ розміром 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:

$(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])$

Крок $\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]$

Крок $\iota$

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

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

Якщо $t{\bmod {2}}55=0$ , то повертається 1
Нехай $R=[10000000]$
Для t від 1 до 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]$
Повертати $R[0]$ $RC[2^{i}-1]=rc(i+7i_{r})$

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

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

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

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

Переклад рядка $S$ в масив $A$
Для $i_{r}$ від $12+2l-n_{r}$ до $12+2l-1$ $A'=\iota (\chi (\pi (\rho (\theta (A)))),i_{r})$
Переклад масиву $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)	Параметризується версія SHAKE
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 раунди