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 + до 12 + 2
- Padding був змінений зі складної форми на більш просту, описану нижче
- Швидкість (rate) r була збільшена до межі безпеки (раніше округлялася вниз до найближчого ступеня 2)
Алгоритм
Геш-функції сімейства SHA-3 побудовані на основі конструкції криптографічної губки, в якій дані спочатку «вбираються» в губку, при якому початкове повідомлення піддається багатораундовим перестановкам , потім результат «віджимається» з губки. На етапі «вбирання» блоки повідомлення додаються за модулем 2 з підмножиною стану, який потім перетвориться з допомогою функції перестановки . На етапі «віджимання» вихідні блоки зчитуються з одного і того ж підмножинного стану, зміненого функцією перестановок . Розмір частини стану, який записується і зчитується, називається «швидкістю» (англ. rate) і позначається , а розмір частки, яка незаймана введенням / виведенням, називається «ємністю» (англ. capacity) і позначається .
Алгоритм отримання значення хеш-функції можна розділити на кілька етапів:
- Вихідне повідомлення додається до рядка довжини, кратній ,за допомогою функції доповнення (pad-функції).
- Рядок ділиться на блоків довжини :
- «Всмоктування»: кожен блок доповнюється нулями до рядка довжини біт і підсумовується по модулю 2 з рядком стану , де — рядок довжини біт ( = + ). Перед використанням цієї функції всі елементи дорівнюють нулю. Для кожного наступного блоку стан — рядок, отриманий застосуванням функції перестановок до результату попереднього кроку.
- «Віджимання»: поки довжина менша ( — кількість біт в результаті геш-функції), до додається перших біт стану , після кожного додавання до , застосовується функція перестановок . Потім обрізається до довжини біт
- Рядок довжини біт повертається в якості результату
Завдяки тому, що стан містить додаткових біт, алгоритм стійкий до атаки подовженням повідомлення, до якої прийняті алгоритми SHA-1 і SHA-2.
У SHA-3 стан — це масив 5 × 5 слів довжиною = 64 біта, всього 5 × 5 × 64 = 1600 біт. Також в Keccak можуть використовуватися довжини , рівні меншим ступенями 2 (від = 1 до = 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 ступеня . В основній реалізації SHA-3 ().
Стан можна подати у вигляді тривимірного масиву розміром 5 × 5 × . Тоді елемент масиву - це біт рядка стану .
Функція містить кілька кроків: , , , , , які виконуються декілька раундів. На кожному кроці позначимо вхідний масив A, вихідний масив A'.
Крок
Для всіх і таких, що , , покладемо
Для всіх таких, що , , ,
Крок
Для всіх , таких, як ,
Нехай на початку . Для від 0 до 23:
- , таких, що , ,
Крок
Для всіх таких, що ,
Крок
Для всіх , таких, що , ,
Крок
Введемо додаткову функцію , де вхід — ціле число , а на виході біт.
Алгоритм
- Якщо , то повертається 1
- Нехай
- Для t від 1 до 255:
- R = 0 || R
- Повертати
Алгоритм
— номер раунду.
- Для всіх , таких, як , ,
- Нехай — масив довжини , заповнений нулями.
- Для від 0 до :
- Для всіх , таких, як ,
Алгоритм перестановок
- Переклад рядка в масив
- Для від до
- Переклад масиву в рядок довжини
Гешування повідомлення довільної довжини
Основою функції стиснення алгоритму є функція f, яка виконує перемішування внутрішнього стану алгоритму. Стан (позначимо його A) представляється у вигляді масиву 5×5, елементами якого є 64-бітові слова, ініційовані нульовими бітами (тобто, розмір стану складає 1600 бітів). Функція f виконує 24 раунди, в кожному з яких проводяться наступні дії:
C[x] = A[x, 0] A[x, 1] A[x, 2] A[x, 3] A[x, 4], x = 0…4; D[x] = C[x — 1] (С[x + 1] >>> 1), x = 0…4; A[x, y] = A[x, y] 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] (~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 раунди | ||
Перестановки | Диференційна властивість | Все | 8 раундів | ||
Геш-функція | Атака-розрізнювач | 224, 256 | 4 раунди | ||
Геш-функція | Колізія | 224, 256 | 2 раунди | ||
Геш-функція | Знаходження другого прообразу | 224, 256 | 2 раунди | ||
Геш-функція | Знаходження другого прообразу | 512 | 6 раундів | ||
Геш-функція | Знаходження другого прообразу | 512 | 7 раундів | ||
Геш-функція | Знаходження другого прообразу | 512 | 8 раундів | ||
Геш-функція | Колізія | 224, 256 | 4 раунди |
Примітки
- . Архів оригіналу за 5 жовтня 2012. Процитовано 19 квітня 2018.
- . Архів оригіналу за 17 серпня 2015. Процитовано 19 квітня 2018.
- . Архів оригіналу за 12 серпня 2015. Процитовано 19 квітня 2018.
- Shu-jen Chang, Ray Perlner, William E. Burr, Meltem Sonmez Turan, John M. Kelsey. Third-Round Report of the SHA-3 Cryptographic Hash Algorithm Competition. — DOI:10.6028/nist.ir.7896.
- (англ.). keccak.team. Архів оригіналу за 16 грудня 2017. Процитовано 15 грудня 2017.
- . csrc.nist.gov. Архів оригіналу за 20 листопада 2017. Процитовано 7 листопада 2017.
- . Архів оригіналу за 17 серпня 2015. Процитовано 19 квітня 2018.
- . NIST. 2 жовтня 2012. Архів оригіналу за 30 квітня 2017. Процитовано 2 жовтня 2012.
- Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche. The Road from Panama to Keccak via RadioGatún : [ 22 грудня 2017] // Symmetric Cryptography. — Dagstuhl, Germany : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2009.
- . keccak.team. Архів оригіналу за 13 листопада 2017. Процитовано 12 листопада 2017.
- . keccak.team. Архів оригіналу за 13 листопада 2017. Процитовано 12 листопада 2017.
- Morris J. Dworkin. SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. — DOI:10.6028/nist.fips.202.
- Will Keccak = SHA-3?. 1 жовтня 2013. Процитовано 20 грудня 2013.
- What the heck is going on with NIST’s cryptographic standard, SHA-3? (англ.). 24 вересня 2013. Процитовано 20 грудня 2013.
- Yes, this is Keccak!. 4 жовтня 2013. Процитовано 20 грудня 2013. — ответное заявление от авторов Keccak
- The Keccak sponge function family. 17 січня 2011. Процитовано 30 вересня 2015. — изменение алгоритма заполнения в 3-м раунде конкурса
- SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash
Посилання
- 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: Перестановка-Based Hash and Extendable-Output Functions | NIST [ 17 вересня 2017 у Wayback Machine.] (англ.)
- . https://keccak.team/. The Keccak team. Архів оригіналу за 7 грудня 2017. Процитовано 6 грудня 2017.
- Java implementation, Pitaya
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Keccak angl Secure Hash Algorithms 3 SHA 3 vimovlyayetsya yak kechak algoritm geshuvannya zminnoyi rozryadnosti rozroblenij grupoyu avtoriv na choli z Joanom Dajmenom spivavtorom Rijndael avtorom shifriv MMB SHARK Noekeon SQUARE i BaseKing 2 zhovtnya 2012 roku Keccak stav peremozhcem konkursu kriptografichnih algoritmiv provedenim Nacionalnim institutom standartiv i tehnologij SShA 5 serpnya 2015 roku algoritm zatverdzheno ta opublikovano v yakosti standartu FIPS 202 U programnij realizaciyi avtori zayavlyayut pro 12 5 ciklah na bajt pri vikonanni na PK z procesorom Intel Core 2 Prote v aparatnih realizaciyah Keccak viyavivsya nabagato shvidshim nizh vsi inshi finalisti Konstrukciya funkciyi gubki vikoristana v gesh funkciyi Pi vhidni bloki Zj vihid algoritmu Nevikoristanij dlya vivedennya nabir bitiv c capacity povinen mati znachnij rozmir dlya dosyagnennya stijkosti do atak Algoritm SHA 3 pobudovanij za principom kriptografichnoyi gubki dana struktura kriptografichnih algoritmiv bula zaproponovana avtorami algoritmu Keccak ranishe IstoriyaU 2004 2005 rokah kilka algoritmiv geshuvannya buli atakovani v tomu chisli buli opublikovani serjozni ataki proti algoritmu SHA 1 zatverdzhenogo Nacionalnim institutom standartiv i tehnologij NIST U vidpovid NIST proviv vidkriti seminari ta 2 listopada 2007 roku anonsuvav konkurs na rozrobku novogo algoritmu geshuvannya 2 zhovtnya 2012 roku peremozhcem konkursu stav algoritm Keccak i buv sertifikovanij yak novij algoritm SHA 3 5 serpnya 2015 roku algoritm zatverdzheno ta opublikovano v yakosti standartu FIPS 202 Algoritm buv rozroblenij Joanom Dajmenom Zhilem Van Ashe z STMicroelectronics i Mikaelem Pitersom z NXP Algoritm zasnovanij na bilsh rannih gesh funkciyah Panama i RadioGatun Panama buv rozroblenij Dzhoanom Dajmenom i Krejgom Kleppom v 1998 roci RadioGatun buv realizovanij na osnovi Panama Dajmenom Pitersom i Van Ashe u 2006 roci V hodi konkursu uchasnikam dozvolyalosya vnositi zmini u svij algoritm dlya vipravlennya znajdenih problem Zmini vneseni v algoritm Keccak Kilkist raundiv bulo zbilsheno z 12 l displaystyle l do 12 2l displaystyle l Padding buv zminenij zi skladnoyi formi na bilsh prostu opisanu nizhche Shvidkist rate r bula zbilshena do mezhi bezpeki ranishe okruglyalasya vniz do najblizhchogo stupenya 2 AlgoritmGesh funkciyi simejstva SHA 3 pobudovani na osnovi konstrukciyi kriptografichnoyi gubki v yakij dani spochatku vbirayutsya v gubku pri yakomu pochatkove povidomlennya M displaystyle M piddayetsya bagatoraundovim perestanovkam f displaystyle f potim rezultat Z displaystyle Z vidzhimayetsya z gubki Na etapi vbirannya bloki povidomlennya dodayutsya za modulem 2 z pidmnozhinoyu stanu yakij potim peretvoritsya z dopomogoyu funkciyi perestanovki f displaystyle f Na etapi vidzhimannya vihidni bloki zchituyutsya z odnogo i togo zh pidmnozhinnogo stanu zminenogo funkciyeyu perestanovok f displaystyle f Rozmir chastini stanu yakij zapisuyetsya i zchituyetsya nazivayetsya shvidkistyu angl rate i poznachayetsya r displaystyle r a rozmir chastki yaka nezajmana vvedennyam vivedennyam nazivayetsya yemnistyu angl capacity i poznachayetsya c displaystyle c Algoritm otrimannya znachennya hesh funkciyi mozhna rozdiliti na kilka etapiv Vihidne povidomlennya M displaystyle M dodayetsya do ryadka P displaystyle P dovzhini kratnij r displaystyle r za dopomogoyu funkciyi dopovnennya pad funkciyi Ryadok P displaystyle P dilitsya na n displaystyle n blokiv dovzhini r displaystyle r P 0 P 1 P n 1 displaystyle P 0 P 1 P n 1 Vsmoktuvannya kozhen blok P i displaystyle P i dopovnyuyetsya nulyami do ryadka dovzhini b displaystyle b bit i pidsumovuyetsya po modulyu 2 z ryadkom stanu S displaystyle S de S displaystyle S ryadok dovzhini b displaystyle b bit b displaystyle b r displaystyle r c displaystyle c Pered vikoristannyam ciyeyi funkciyi vsi elementi S displaystyle S dorivnyuyut nulyu Dlya kozhnogo nastupnogo bloku stan ryadok otrimanij zastosuvannyam funkciyi perestanovok f displaystyle f do rezultatu poperednogo kroku Vidzhimannya poki dovzhina Z displaystyle Z mensha d displaystyle d d displaystyle d kilkist bit v rezultati gesh funkciyi do Z displaystyle Z dodayetsya r displaystyle r pershih bit stanu S displaystyle S pislya kozhnogo dodavannya do S displaystyle S zastosovuyetsya funkciya perestanovok f displaystyle f Potim S displaystyle S obrizayetsya do dovzhini d displaystyle d bit Ryadok Z displaystyle Z dovzhini d displaystyle d bit povertayetsya v yakosti rezultatu Zavdyaki tomu sho stan mistit c displaystyle c dodatkovih bit algoritm stijkij do ataki podovzhennyam povidomlennya do yakoyi prijnyati algoritmi SHA 1 i SHA 2 U SHA 3 stan S displaystyle S ce masiv 5 5 sliv dovzhinoyu w displaystyle w 64 bita vsogo 5 5 64 1600 bit Takozh v Keccak mozhut vikoristovuvatisya dovzhini w displaystyle w rivni menshim stupenyami 2 vid w displaystyle w 1 do w displaystyle w 32 DodatokDlya togo shob vihidne povidomlennya M mozhna bulo rozdiliti na bloki dovzhini r neobhidno dopovnennya U SHA 3 vikoristovuyetsya patern pad10 1 do povidomlennya dodayetsya 1 pislya nogo 0 abo bilshe nulovih bitiv do r 1 v kinci 1 r 1 nulovih bitiv mozhe buti dodano koli ostannij blok povidomlennya maye dovzhinu r 1 bit Cej blok dopovnyuyetsya odiniceyu nastupnij blok skladatimetsya z r 1 nuliv i odinic Dva odinichni biti dodayutsya i v tomu vipadku yaksho dovzhina vihidnogo povidomlennya M dilitsya na r U comu vipadku do povidomlennya dodayetsya blok yakij pochinayetsya i zakinchuyetsya odinicyami mizh yakimi r 2 nulovih bitiv Ce neobhidno dlya togo shob povidomlennya sho zakinchuyetsya poslidovnistyu bitiv yak u funkciyi dopovnennya i dlya povidomlennya bez cih bitiv znachennya gesh funkciyi buli rizni Pershij odinichnij bit neobhidnij dlya togo shob rezultati gesh funkciyi vid povidomlen sho vidriznyayutsya kilkoma nulovimi bitami v kinci buli riznimi Funkciya perestanovokFunkciya perestanovok vikoristovuvana v SHA 3 vklyuchaye v sebe viklyuchne ABO XOR pobitove I AND i pobitove zaperechennya NOT Funkciya viznachena dlya ryadkiv dovzhini 2 stupenya w 2 l displaystyle w 2 l V osnovnij realizaciyi SHA 3 w 64 displaystyle w 64 l 6 displaystyle l 6 Stan S displaystyle S mozhna podati u viglyadi trivimirnogo masivu A i j k displaystyle A i j k rozmirom 5 5 w displaystyle w Todi element masivu A i j k displaystyle A i j k ce 5 i j w k displaystyle 5i j times w k bit ryadka stanu S displaystyle S Funkciya mistit kilka krokiv 8 displaystyle theta r displaystyle rho p displaystyle pi x displaystyle chi i displaystyle iota yaki vikonuyutsya dekilka raundiv Na kozhnomu kroci poznachimo vhidnij masiv A vihidnij masiv A Krok 8 displaystyle theta Dlya vsih i displaystyle i i k displaystyle k takih sho 0 i lt 5 displaystyle 0 leqslant i lt 5 0 k lt w displaystyle 0 leqslant k lt w poklademo C i k A i 0 k A i 1 k A i 2 k A i 3 k A i 4 k 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 D i k C i 1 mod 5 k C i 1 mod 5 k 1 mod w displaystyle D i k C i 1 bmod 5 k oplus C i 1 bmod 5 k 1 bmod w Dlya vsih i j k displaystyle i j k takih sho 0 i lt 5 displaystyle 0 leqslant i lt 5 0 j lt 5 displaystyle 0 leqslant j lt 5 0 k lt w displaystyle 0 leqslant k lt w A i j k A i j k D i k displaystyle A i j k A i j k oplus D i k Krok r displaystyle rho Dlya vsih k displaystyle k takih yak 0 k lt w displaystyle 0 leqslant k lt w A 0 0 k A 0 0 k displaystyle A 0 0 k A 0 0 k Nehaj na pochatku i j 1 0 displaystyle i j 1 0 Dlya t displaystyle t vid 0 do 23 i j k displaystyle i j k takih sho 0 i lt 5 displaystyle 0 leqslant i lt 5 0 j lt 5 displaystyle 0 leqslant j lt 5 0 k lt w displaystyle 0 leqslant k lt w A i j k A i 3 j mod 5 i k displaystyle A i j k A i 3j bmod 5 i k Krok x displaystyle chi Dlya vsih i j k displaystyle i j k takih sho 0 i lt 5 displaystyle 0 leqslant i lt 5 0 j lt 5 displaystyle 0 leqslant j lt 5 A i j k A i j k A i 1 mod 5 j k 1 A i 2 mod 5 j k 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 Krok p displaystyle pi Dlya vsih i j k displaystyle i j k takih sho 0 i lt 5 displaystyle 0 leqslant i lt 5 0 j lt 5 displaystyle 0 leqslant j lt 5 0 k lt w displaystyle 0 leqslant k lt w A i j k A i 3 j mod 5 i k displaystyle A i j k A i 3j bmod 5 i k Krok i displaystyle iota Vvedemo dodatkovu funkciyu r c t displaystyle rc t de vhid cile chislo t displaystyle t a na vihodi bit Algoritm r c t displaystyle rc t Yaksho t mod 2 55 0 displaystyle t bmod 2 55 0 to povertayetsya 1 Nehaj R 10000000 displaystyle R 10000000 Dlya t vid 1 do 255 R 0 R R 0 R 0 R 8 displaystyle R 0 R 0 oplus R 8 R 4 R 4 R 8 displaystyle R 4 R 4 oplus R 8 R 5 R 5 R 8 displaystyle R 5 R 5 oplus R 8 R 6 R 6 R 8 displaystyle R 6 R 6 oplus R 8 R T r u n c 8 R displaystyle R Trunc 8 R Povertati R 0 displaystyle R 0 R C 2 i 1 r c i 7 i r displaystyle RC 2 i 1 rc i 7i r Algoritm i A i r displaystyle iota A i r i r displaystyle i r nomer raundu Dlya vsih i j k displaystyle i j k takih yak 0 i lt 5 displaystyle 0 leqslant i lt 5 0 j lt 5 displaystyle 0 leqslant j lt 5 0 k lt w displaystyle 0 leqslant k lt w A i j k A i j k displaystyle A i j k A i j k Nehaj R C displaystyle RC masiv dovzhini w displaystyle w zapovnenij nulyami Dlya i displaystyle i vid 0 do l displaystyle l R C 2 i 1 r c i 7 i r displaystyle RC 2 i 1 rc i 7i r Dlya vsih k displaystyle k takih yak 0 k lt w displaystyle 0 leqslant k lt w A 0 0 k A 0 0 k R C k displaystyle A 0 0 k A 0 0 k oplus RC k Algoritm perestanovok Pereklad ryadka S displaystyle S v masiv A displaystyle A Dlya i r displaystyle i r vid 12 2 l n r displaystyle 12 2l n r do 12 2 l 1 displaystyle 12 2l 1 A i x p r 8 A i r displaystyle A iota chi pi rho theta A i r Pereklad masivu A displaystyle A v ryadok S displaystyle S dovzhini b displaystyle b Geshuvannya povidomlennya dovilnoyi dovzhiniOsnovoyu funkciyi stisnennya algoritmu ye funkciya f yaka vikonuye peremishuvannya vnutrishnogo stanu algoritmu Stan poznachimo jogo A predstavlyayetsya u viglyadi masivu 5 5 elementami yakogo ye 64 bitovi slova inicijovani nulovimi bitami tobto rozmir stanu skladaye 1600 bitiv Funkciya f vikonuye 24 raundi v kozhnomu z yakih provodyatsya nastupni diyi 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 S x 1 gt gt gt 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 gt gt gt r x y x 0 4 y 0 4 A x y B x y displaystyle oplus B x 1 y amp B x 2 y x 0 4 y 0 4 B timchasovij masiv analogichnij za strukturoyu masivu stanu C ta D timchasovi masivi sho mistyat po p yat 64 bitnih sliv r masiv sho viznachaye velichinu ciklichnogo zsuvu dlya kozhnogo slova stanu x porozryadnij dodatok do x ta operaciyi z indeksami masivu vikonuyutsya po modulyu 5 Krim navedenih vishe operacij v kozhnomu raundi takozh vikonuyetsya nakladennya operaciyeyu XOR raundovoyi konstanti na slovo A 0 0 Pered vikonannyam funkciyi stiskannya nakladayetsya operaciya XOR fragmentiv vihidnogo povidomlennya z fragmentami vihidnogo stanu Rezultat obroblyayetsya funkciyeyu f Dane nakladennya v sukupnosti z funkciyeyu stiskannya sho vikonuyutsya dlya kozhnogo bloku vhidnih danih yavlyayut soboyu vbirayuchu absorbing fazu kriptografichnogo gubki Varto zaznachiti sho funkciya f vikoristovuye lishe operaciyi stijki do atak sho vikoristovuyut vitik danih po pobichnih kanalah Rezultuyuche gesh znachennya obchislyuyetsya v procesi vikonannya vichavlen squeezing fazi kriptografichnoyi gubki osnovu yakoyi stanovit opisana vishe funkciya f Mozhlivi rozmiri gesh znachen 224 256 384 512 bit NalashtuvannyaOriginalnij algoritm Keccak maye bezlich parametriv sho nalashtovuyutsya z metoyu zabezpechennya optimalnogo spivvidnoshennya kriptostijkosti i shvidkodiyi dlya pevnogo zastosuvannya algoritmu na pevnij platformi Regulovanimi velichinami ye rozmir bloku danih rozmir stanu algoritmu kilkist raundiv u funkciyi f ta inshi Protyagom konkursu geshuvannya Nacionalnogo institutu standartiv i tehnologij uchasniki mali pravo nalashtovuvati svoyi algoritmi dlya virishennya vinikayuchih problem Tak buli vneseni deyaki zmini v Keccak kilkist raundiv bulo zbilsheno z 18 do 24 z metoyu zbilshennya zapasu bezpeki Avtori Keccak zasnuvali ryad priziv za dosyagnennya v kriptoanalizi danogo algoritmu Versiya algoritmu prijnyata v yakosti ostatochnogo standartu SHA 3 maye kilka neznachnih vidminnostej vid originalnoyi propoziciyi Keccak na konkurs Zokrema buli obmezheni deyaki parametri vidkinuti povilni rezhimi c 768 i c 1024 v tomu chisli dlya zbilshennya produktivnosti Takozh u standarti buli vvedeni funkciyi z podovzhuvanim rezultatom XOF Extendable Output Functions SHAKE128 i SHAKE256 dlya chogo geshovane povidomlennya neobhidno bulo dopovnyuvati sufiksom z 2 abo 4 bit v zalezhnosti vid tipu funkciyi Funkciya Formula 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 Dodatkovi funkciyiU grudni 2016 roku Nacionalnij institut standartiv i tehnologij SShA opublikuvav novij dokument NIST SP 800 185 sho opisuye dodatkovi funkciyi na osnovi SHA 3 Funkciya Opis cSHAKE128 X L N S Parametrizuyetsya versiya SHAKE cSHAKE256 X L N S KMAC128 K X L S Imitovstavka na osnovi Keccak KMAC256 K X L S KMACXOF128 K X L S KMACXOF256 K X L S TupleHash128 X L S Geshuvannya kortezhu ryadkiv TupleHash256 X L S TupleHashXOF128 X L S TupleHashXOF256 X L S ParallelHash128 X B L S Paralelizovana gesh funkciya na osnovi Keccak ParallelHash256 X B L S ParallelHashXOF128 X B L S ParallelHashXOF256 X B L S Testovi vektoriZnachennya riznih variantiv geshiv vid porozhnogo ryadka SHA3 224 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7 SHA3 256 a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a SHA3 384 0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004 SHA3 512 a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26 SHAKE128 256 7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26 SHAKE256 512 46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be Mala zmina povidomlennya prizvodit do znachnih zmin u znachenni gesh funkciyi zavdyaki lavinnomu efektu yak pokazano v nastupnih prikladah 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 853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10cKriptoanalizRezultati kriptoanalizu pid chas konkursu Cil Tip ataki Vihid Variant CF Call Pam yat Gesh funkciya Koliziya 160 r 240 640 1440 c 160 1 2 raundi Gesh funkciya Znahodzhennya proobrazu 80 r 240 640 1440 c 160 1 2 raundi Perestanovki Ataka rozriznyuvach Vsi 24 raundi 2 1579 displaystyle 2 1579 Perestanovki Diferencijna vlastivist Vse 8 raundiv 2 491 47 displaystyle 2 491 47 Gesh funkciya Ataka rozriznyuvach 224 256 4 raundi 2 25 displaystyle 2 25 Gesh funkciya Koliziya 224 256 2 raundi 2 33 displaystyle 2 33 Gesh funkciya Znahodzhennya drugogo proobrazu 224 256 2 raundi 2 33 displaystyle 2 33 2 29 displaystyle 2 29 Gesh funkciya Znahodzhennya drugogo proobrazu 512 6 raundiv 2 506 displaystyle 2 506 2 176 displaystyle 2 176 Gesh funkciya Znahodzhennya drugogo proobrazu 512 7 raundiv 2 507 displaystyle 2 507 2 320 displaystyle 2 320 Gesh funkciya Znahodzhennya drugogo proobrazu 512 8 raundiv 2 511 5 displaystyle 2 511 5 2 508 displaystyle 2 508 Gesh funkciya Koliziya 224 256 4 raundiPrimitki Arhiv originalu za 5 zhovtnya 2012 Procitovano 19 kvitnya 2018 Arhiv originalu za 17 serpnya 2015 Procitovano 19 kvitnya 2018 Arhiv originalu za 12 serpnya 2015 Procitovano 19 kvitnya 2018 Shu jen Chang Ray Perlner William E Burr Meltem Sonmez Turan John M Kelsey Third Round Report of the SHA 3 Cryptographic Hash Algorithm Competition DOI 10 6028 nist ir 7896 angl keccak team Arhiv originalu za 16 grudnya 2017 Procitovano 15 grudnya 2017 csrc nist gov Arhiv originalu za 20 listopada 2017 Procitovano 7 listopada 2017 Arhiv originalu za 17 serpnya 2015 Procitovano 19 kvitnya 2018 NIST 2 zhovtnya 2012 Arhiv originalu za 30 kvitnya 2017 Procitovano 2 zhovtnya 2012 Guido Bertoni Joan Daemen Michael Peeters Gilles Van Assche The Road from Panama to Keccak via RadioGatun 22 grudnya 2017 Symmetric Cryptography Dagstuhl Germany Schloss Dagstuhl Leibniz Zentrum fuer Informatik Germany 2009 keccak team Arhiv originalu za 13 listopada 2017 Procitovano 12 listopada 2017 keccak team Arhiv originalu za 13 listopada 2017 Procitovano 12 listopada 2017 Morris J Dworkin SHA 3 Standard Permutation Based Hash and Extendable Output Functions DOI 10 6028 nist fips 202 Will Keccak SHA 3 1 zhovtnya 2013 Procitovano 20 grudnya 2013 What the heck is going on with NIST s cryptographic standard SHA 3 angl 24 veresnya 2013 Procitovano 20 grudnya 2013 Yes this is Keccak 4 zhovtnya 2013 Procitovano 20 grudnya 2013 otvetnoe zayavlenie ot avtorov Keccak The Keccak sponge function family 17 sichnya 2011 Procitovano 30 veresnya 2015 izmenenie algoritma zapolneniya v 3 m raunde konkursa SHA 3 Derived Functions cSHAKE KMAC TupleHash and ParallelHashPosilannyaNIST Selects Winner of Secure Hash Algorithm SHA 3 Competition 5 zhovtnya 2012 u Wayback Machine NIST October 2012 angl The Keccak sponge function family 12 zhovtnya 2016 u Wayback Machine Sajt Noekeon 2015 10 15 Oficijna storinka hesh funkciyi Keccak angl Hesh funkciya Keccak i konstrukciya Sponge yak universalnij kriptoprimitiv 23 chervnya 2013 u Wayback Machine pgpru com 2010 2013 pereklad materialu z noekon org SHA 3 Standard Perestanovka Based Hash and Extendable Output Functions NIST 17 veresnya 2017 u Wayback Machine angl https keccak team The Keccak team Arhiv originalu za 7 grudnya 2017 Procitovano 6 grudnya 2017 Java implementation Pitaya