SHA-3: различия между версиями
[непроверенная версия] | [непроверенная версия] |
Алгоритм, уточнение |
MBH (обсуждение | вклад) м откат правок 185.120.190.34 (обс.) к версии Ryzhulya86bit Метка: откат |
||
(не показана 41 промежуточная версия 19 участников) | |||
Строка 1: | Строка 1: | ||
{{Карточка хеш |
{{Карточка хеш-функции |
||
|название = SHA-3, Keccak |
|название = SHA-3, Keccak |
||
|разработчики = Гвидо Бертони, [[Йоан Даймен]], Микаел Питерс, Жиль Ван Аше |
|разработчики = Гвидо Бертони, [[Йоан Даймен]], Микаел Питерс, Жиль Ван Аше |
||
Строка 8: | Строка 8: | ||
|тип = [[хеш-функция]] |
|тип = [[хеш-функция]] |
||
}} |
}} |
||
'''SHA-3''' (''Keccak'' — произносится как «кечак») — алгоритм [[хеширование|хеширования]] переменной разрядности, разработанный группой авторов во главе с [[Йоан Даймен|Йоаном Дайменом]], соавтором [[Rijndael]], автором шифров [[MMB]], [[SHARK]], [[Noekeon]], [[SQUARE]] и [[BaseKing]]. 2 октября [[2012]] |
'''SHA-3''' (''Keccak'' — произносится как «кечак») — алгоритм [[хеширование|хеширования]] переменной разрядности, разработанный группой авторов во главе с [[Йоан Даймен|Йоаном Дайменом]], соавтором [[Rijndael]], автором шифров [[MMB]], [[SHARK]], [[Noekeon]], [[SQUARE]] и [[BaseKing]]. 2 октября [[2012 год]]а Keccak стал победителем [[SHA-3 (конкурс)|конкурса криптографических алгоритмов]], проводимого [[Национальный институт стандартов и технологий|Национальным институтом стандартов и технологий США]]<ref>{{Cite web |url=http://www.nist.gov/itl/csd/sha-100212.cfm |title=NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition |access-date=2012-10-03 |archive-date=2012-10-05 |archive-url=https://web.archive.org/web/20121005031201/http://www.nist.gov/itl/csd/sha-100212.cfm |deadlink=no }}</ref>. 5 августа [[2015 год]]а алгоритм утверждён и опубликован в качестве стандарта [[FIPS]] 202<ref name="nist.gov">{{Cite web |url=http://www.nist.gov/itl/csd/201508_sha3.cfm |title=NIST Releases SHA-3 Cryptographic Hash Standard<!-- Заголовок добавлен ботом --> |access-date=2016-01-21 |archive-date=2015-08-17 |archive-url=https://web.archive.org/web/20150817005537/http://www.nist.gov/itl/csd/201508_sha3.cfm |deadlink=no }}</ref><ref name="автоссылка1">{{Cite web |url=http://www.nist.gov/manuscript-publication-search.cfm?pub_id=919061 |title=NIST Manuscript Publication Search<!-- Заголовок добавлен ботом --> |access-date=2016-01-21 |archive-date=2015-08-12 |archive-url=https://web.archive.org/web/20150812222834/http://www.nist.gov/manuscript-publication-search.cfm?pub_id=919061 |deadlink=no }}</ref>. В программной реализации авторы заявляют о 12,5 циклах на байт при выполнении на [[персональный компьютер|ПК]] с процессором [[Core 2|Intel Core 2]]. Однако в аппаратных реализациях Keccak оказался намного быстрее, чем все другие финалисты.<ref name=":3">{{Статья|автор=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|ссылка=http://dx.doi.org/10.6028/NIST.IR.7896|doi=10.6028/nist.ir.7896}}</ref> |
||
[[Файл:SpongeConstruction.svg|мини|справа|Конструкция |
[[Файл:SpongeConstruction.svg|мини|справа|Конструкция [[Функция губки|функции губки]], использованная в хеш-функции. ''P<sub>i</sub>'' — входные блоки, ''Z<sub>j</sub>'' — выход алгоритма. Размер ''c'' («capacity») неиспользуемого для вывода набора битов должен быть значительным для достижения устойчивости к атакам]] |
||
Алгоритм SHA-3 построен по принципу [[ |
Алгоритм SHA-3 построен по принципу [[функция губки|криптографической губки]] (данная структура криптографических алгоритмов была предложена авторами алгоритма Keccak ранее)<ref name=":2">{{Cite web|url=https://keccak.team/sponge_duplex.html|title=Keccak Team|publisher=keccak.team|lang=en|accessdate=2017-12-15|archive-date=2017-12-16|archive-url=https://web.archive.org/web/20171216034719/https://keccak.team/sponge_duplex.html|deadlink=no}}</ref>. |
||
== История == |
== История == |
||
В |
В 2004—2005 годах несколько алгоритмов хеширования были атакованы, в том числе были опубликованы серьезные атаки против алгоритма SHA-1, утвержденного [[Национальный институт стандартов и технологий|Национальным институтом стандартов и технологий (NIST)]]. В ответ NIST провел открытые семинары и 2 ноября [[2007 год]]а анонсировал конкурс на разработку нового алгоритма хеширования. 2 октября [[2012 год]]а победителем конкурса стал алгоритм Keccak и был стандартизован как новый алгоритм SHA-3<ref>{{Cite web|url=https://csrc.nist.gov/projects/hash-functions/sha-3-project|title=SHA-3 Project - Hash Functions {{!}} CSRC|publisher=csrc.nist.gov|accessdate=2017-11-07|archive-date=2017-11-20|archive-url=https://web.archive.org/web/20171120152059/https://csrc.nist.gov/projects/hash-functions/sha-3-project|deadlink=no}}</ref>. 5 августа [[2015 год]]а алгоритм утвержден и опубликован в качестве стандарта [[FIPS]] 202<ref name="nist.gov" /><ref name="автоссылка1" />. |
||
Алгоритм был разработан {{iw|Гвидо Бертони||en|Guido Bertoni}}, [[Даймен, Йоан|Йоаном Дайменом]], {{iw|Жиль Ван Аше|Жилем Ван Аше|en|Gilles Van Assche}} из [[STMicroelectronics]] и {{iw|Микаэль Питерс|Микаэлем Питерсом|en|Michaël Peeters}} из [[NXP Semiconductors|NXP]]<ref name="NIST">{{cite web|url=https://www.nist.gov/news-events/news/2012/10/nist-selects-winner-secure-hash-algorithm-sha-3-competition|title=NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition|publisher=NIST|date=2012-10-02|accessdate=2012-10-02|archive-date=2017-04-30|archive-url=https://web.archive.org/web/20170430014715/https://www.nist.gov/news-events/news/2012/10/nist-selects-winner-secure-hash-algorithm-sha-3-competition|deadlink=no}}</ref>. |
|||
В ходе конкурса конкурсантам разрешалось вносить изменения в свой алгоритм для исправления обнаруживающихся проблем. Изменения, внесенные в алгоритм Keccak:<ref>{{Cite web|url=https://keccak.team/2009/version_2.0.html|title=Keccak Team|publisher=keccak.team|lang=en|accessdate=2017-11-12}}</ref><ref>{{Cite web|url=https://keccak.team/2011/version_3.0.html|title=Keccak Team|publisher=keccak.team|lang=en|accessdate=2017-11-12}}</ref> |
|||
* Количество раундов было увеличено с 12 + <math>l</math> до 12 + 2<math>l</math> |
|||
Алгоритм основан на более ранних хеш-функциях [[Panama (хеш-функция)|Panama]] и RadioGatún<ref name=":1">{{Статья|автор=Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche|заглавие=The Road from Panama to Keccak via RadioGatún|ссылка=http://drops.dagstuhl.de/opus/volltexte/2009/1958|ответственный=Helena Handschuh, Stefan Lucks, Bart Preneel, Phillip Rogaway|издание=Symmetric Cryptography|место=Dagstuhl, Germany|издательство=Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany|год=2009|archivedate=2017-12-22|archiveurl=https://web.archive.org/web/20171222020045/http://drops.dagstuhl.de/opus/volltexte/2009/1958/}}</ref>. Panama был разработан Дайменом и Крейгом Клэппом в 1998 году, RadioGatún был реализован на основе Panama Дайменом, Питерсом и Ван Аше в 2006 году<ref name=":1" />. |
|||
* Padding был изменен со сложной формы на более простую, описанную ниже |
|||
* Скорость (rate) r была увеличена до предела безопасности (ранее округлялась вниз до ближайшей степени 2) |
|||
В ходе конкурса конкурсантам разрешалось вносить изменения в свой алгоритм для исправления обнаруживающихся проблем. Изменения, внесенные в алгоритм Keccak<ref>{{Cite web|url=https://keccak.team/2009/version_2.0.html|title=Keccak Team|publisher=keccak.team|lang=en|accessdate=2017-11-12|archive-date=2017-11-13|archive-url=https://web.archive.org/web/20171113003333/https://keccak.team/2009/version_2.0.html|deadlink=no}}</ref><ref>{{Cite web|url=https://keccak.team/2011/version_3.0.html|title=Keccak Team|publisher=keccak.team|lang=en|accessdate=2017-11-12|archive-date=2017-11-13|archive-url=https://web.archive.org/web/20171113003453/https://keccak.team/2011/version_3.0.html|deadlink=no}}</ref>: |
|||
* Количество раундов было увеличено с 12 + <math>l</math> до 12 + 2<math>l</math> |
|||
* Padding был изменён со сложной формы на более простую, описанную ниже |
|||
* Скорость (rate) ''r'' была увеличена до предела безопасности (ранее округлялась вниз до ближайшей степени 2) |
|||
== Алгоритм == |
== Алгоритм == |
||
Хеш-функции семейства ''SHA-3'' построены на основе конструкции [[Функция губки|криптографической губки]], в которой данные сначала |
Хеш-функции семейства ''SHA-3'' построены на основе конструкции [[Функция губки|криптографической губки]]<ref name=":2" />, в которой данные сначала «впитываются» в губку, при котором исходное сообщение <math>M</math> подвергается многораундовым перестановкам <math>f</math>, затем результат <math>Z</math> «отжимается» из губки. На этапе «впитывания» блоки сообщения суммируются по модулю 2 с подмножеством состояния, после чего всё состояние преобразуется с помощью функции перестановки <math>f</math>. На этапе «отжимания» выходные блоки считываются из одного и того же подмножества состояния, изменённого функцией перестановок <math>f</math>. Размер части состояния, который записывается и считывается, называется «скоростью» (''англ. rate'') и обозначается <math>r</math>, а размер части, которая нетронута вводом / выводом, называется «ёмкостью» (''англ. capacity'') и обозначается <math>c</math>. |
||
Алгоритм получения значения хеш-функции можно разделить на несколько этапов<ref name=":0" />: |
|||
* Исходное сообщение M дополняется до строки P длины, кратной <math>r</math>, с помощью функции дополнения (pad-функции) |
* Исходное сообщение <math>M</math> дополняется до строки <math>P</math> длины, кратной <math>r</math>, с помощью функции дополнения (pad-функции); |
||
* Строка P делится на n блоков длины r: <math>P_0, P_1, ... , P_{n-1}</math> |
* Строка <math>P</math> делится на <math>n</math> блоков длины <math>r</math>: <math>P_0, P_1, ... , P_{n-1}</math>; |
||
* |
* «Впитывание»: каждый блок <math>P_i</math> дополняется нулями до строки длины <math>b</math> бит и [[Исключающее «или»|суммируется по модулю 2]] со строкой состояния <math>S</math>, где <math>S</math> — строка длины <math>b</math> бит (<math>b</math> = <math>r</math> + <math>c</math>). Перед началом работы функции все элементы <math>S</math> равны нулю. Для каждого следующего блока состояние — строка, полученная применением функции перестановок <math>f</math> к результату предыдущего шага; |
||
* «Отжимание»: пока длина <math>Z</math> меньше <math>d</math> (<math>d</math> — количество бит в результате хеш-функции), к <math>Z</math> добавляется <math>r</math> первых бит состояния <math>S</math>, после каждого прибавления к <math>S</math> применяется функция перестановок <math>f</math>. Затем <math>Z</math> обрезается до длины <math>d</math> бит; |
|||
* К полученным в результате данным N раз применяется функция f. Набором начальных состояний S для блока <math>P{i+1}</math> будет результат последнего раунда блока <math>P_i</math>. |
|||
* Строка <math>Z</math> длины <math>d</math> бит возвращается в качестве результата. |
|||
* После того как все блоки M<sub>i</sub> закончатся взять итоговый результат и вернуть его в качестве хеш-значения. |
|||
Благодаря тому, что состояние содержит <math>c</math> дополнительных бит, алгоритм устойчив к [[Атака удлинением сообщения|атаке удлинением сообщения]], к которой восприимчивы алгоритмы [[SHA-1]] и [[SHA-2]]. |
|||
В SHA-3 состояние <math>S</math> — это массив 5 × 5 слов длиной <math>w</math> = 64 бита, всего 5 × 5 × 64 = 1600 бит. Также в Keccak могут использоваться длины <math>w</math>, равные меньшим степеням 2 (от <math>w</math> = 1 до <math>w</math> = 32). |
|||
== Дополнение == |
|||
Для того, чтобы исходное сообщение ''M'' можно было разделить на блоки длины ''r'', необходимо [[Дополнение (криптография)|дополнение]]. В SHA-3 используется паттерн pad10*1<ref name=":0">{{Статья|автор=Morris J. Dworkin|заглавие=SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions|ссылка=http://dx.doi.org/10.6028/NIST.FIPS.202|doi=10.6028/nist.fips.202}}</ref>: к сообщению добавляется 1, после него — 0 или больше нулевых битов (до ''r-1''), в конце — 1. |
|||
''r-1'' нулевых битов может быть добавлено, когда последний блок сообщения имеет длину ''r-1'' бит. Этот блок дополняется единицей, следующий блок будет состоять из ''r-1'' нулей и единицы. |
|||
Два единичных бита добавляются и в том случае, если длина исходного сообщения ''M'' делится на ''r''<ref name=":0" />. В этом случае к сообщению добавляется блок, начинающийся и оканчивающийся единицами, между которыми ''r-2'' нулевых битов. Это необходимо для того, чтобы для сообщения, оканчивающегося последовательностью битов как в функции дополнения, и для сообщения без этих битов значения хеш-функции были различны. |
|||
Первый единичный бит необходим для того, чтобы результаты хеш-функции от сообщений, различающихся несколькими нулевыми битами в конце, были различны<ref name=":0" />. |
|||
== Функция перестановок == |
|||
Функция перестановок, используемая в SHA-3, включает в себя '''[[Битовые операции#Исключающее «ИЛИ» (XOR)|исключающее «ИЛИ» (XOR)]]''', '''[[Битовые операции#Побитовое «И» (AND)|побитовое «И» (AND)]]''' и '''[[Битовые операции#Побитовое отрицание (NOT)|побитовое отрицание (NOT)]]'''. Функция определена для строк длины-степени 2 <math>w = 2^l</math>. В основной реализации SHA-3 <math>w = 64</math> (<math>l = 6</math>). |
|||
Состояние <math>S</math> можно представить в виде трёхмерного массива <math>A</math> размером 5 × 5 × <math>w</math>. Тогда элемент массива <math>A[i][j][k]</math> - это <math>(5i + j) \times w + k</math> бит строки состояния <math>S</math>. |
|||
Функция содержит несколько шагов: <math>\theta</math>, <math>\rho</math>, <math>\pi</math>, <math>\chi</math>, <math>\iota</math>, которые выполняются несколько раундов<ref name=":0" />. На каждом шаге обозначим входной массив A, выходной массив A'. |
|||
=== Шаг <math>\theta</math> === |
|||
Для всех <math>i</math> и <math>k</math>, таких, что <math>0 \leqslant i < 5</math>, <math>0 \leqslant k < w</math>, положим |
|||
<math>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]</math> |
|||
<math>D(i, k) = C[(i-1) \bmod 5, k] \oplus C[(i+1) \bmod 5, (k-1) \bmod w]</math> |
|||
Для всех <math>(i, j, k)</math>, таких, что <math>0 \leqslant i < 5</math>, <math>0 \leqslant j < 5</math>, <math>0 \leqslant k < w</math>, |
|||
<math>A'[i, j,k] = A[i, j, k] \oplus D[i, k]</math> |
|||
=== Шаг <math>\rho</math> === |
|||
Для всех <math>k</math>, таких, что <math>0 \leqslant k < w</math>, <math>A'[0,0,k] = A[0,0,k]</math> |
|||
Пусть в начале <math>(i, j) = (1, 0)</math>. Для <math>t</math> от 0 до 23: |
|||
# Для всех <math>k</math>, таких, что <math>0 \leqslant k < w</math>, <math>A'[i,j, k] = A[i, j, (k-(t+1)(t+2)/2) \bmod w]</math> |
|||
# <math>(i, j) = (j, (2i + 3j) \bmod 5)</math> |
|||
=== Шаг <math>\pi</math> === |
|||
Для всех <math>(i, j, k)</math>, таких, что <math>0 \leqslant i < 5</math>, <math>0 \leqslant j < 5</math>, <math>0 \leqslant k < w</math> |
|||
<math>A'[i,j,k] = A[(i + 3j) \bmod 5, i, k]</math> |
|||
=== Шаг <math>\chi</math> === |
|||
Для всех <math>(i, j, k)</math>, таких, что <math>0 \leqslant i < 5</math>, <math>0 \leqslant j < 5</math>, |
|||
<math>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])</math> |
|||
=== Шаг <math>\iota</math> === |
|||
Введем дополнительную функцию <math>rc(t)</math>, где вход — целое число <math>t</math>, а на выходе — бит. |
|||
==== Алгоритм <math>rc(t)</math> ==== |
|||
# Если <math>t \bmod 255 = 0</math>, то возвращается 1 |
|||
# Пусть <math>R = [1 0 0 0 0 0 0 0]</math> |
|||
# Для i от 1 до t mod 255: |
|||
## R = 0 || R |
|||
## <math>R[0] = R[0] \oplus R[8]</math> |
|||
## <math>R[4] = R[4] \oplus R[8]</math> |
|||
## <math>R[5] = R[5] \oplus R[8]</math> |
|||
## <math>R[6] = R[6] \oplus R[8]</math> |
|||
## <math>R = Trunc_8[R]</math> |
|||
# Возвращается <math>R[0]</math><math>.</math> |
|||
==== Алгоритм <math>\iota(A, i_r)</math> ==== |
|||
<math>i_r</math> — номер раунда. |
|||
# Для всех <math>(i, j, k)</math>, таких, что <math>0 \leqslant i < 5</math>, <math>0 \leqslant j < 5</math>, <math>0 \leqslant k < w</math> <math>A'[i,j,k] = A[i,j,k]</math> |
|||
# Пусть <math>RC</math> — массив длины <math>w</math>, заполненный нулями. |
|||
# Для <math>i</math> от 0 до <math>l</math>: <math>RC[2^i - 1] = rc(i + 7i_r)</math> |
|||
# Для всех <math>k</math>, таких, что <math>0 \leqslant k < w</math>, <math>A'[0,0,k] = A'[0,0,k] \oplus RC[k]</math> |
|||
=== Алгоритм перестановок === |
|||
# Перевод строки <math>S</math> в массив <math>A</math> |
|||
# Для <math>i_r</math> от <math>12 + 2l - n_r</math> до <math>12 + 2l - 1</math> <math>A' = \iota(\chi(\pi(\rho(\theta(A)))), i_r)</math> |
|||
# Перевод массива <math>A'</math> в строку <math>S'</math> длины <math>b</math> |
|||
== Хеширование сообщений произвольной длины == |
== Хеширование сообщений произвольной длины == |
||
Строка 38: | Строка 118: | ||
Где: |
Где: |
||
:''B'' — временный массив, аналогичный по структуре массиву состояния; |
|||
:''C'' и ''D'' — временные массивы, содержащие по пять 64-битных слов; |
|||
:''r'' — массив, определяющий величину циклического сдвига для каждого слова состояния; |
|||
:''~x'' — [[поразрядное дополнение]] к ''x''; |
|||
: и операции с индексами массива выполняются по модулю 5. |
|||
операции с индексами массива выполняются по модулю 5. |
|||
Кроме приведенных выше операций, в каждом раунде также выполняется наложение операцией XOR раундовой константы на слово A[0, 0]. |
Кроме приведенных выше операций, в каждом раунде также выполняется наложение операцией XOR раундовой константы на слово A[0, 0]. |
||
Перед выполнением функции сжимания накладывается операция XOR фрагментов исходного сообщения с фрагментами исходного состояния. Результат обрабатывается функцией f. Данное наложение в совокупности с функцией сжимания, выполняемые для каждого блока входных данных, представляют собой «впитывающую» (absorbing) фазу криптографической губки. |
Перед выполнением функции сжимания накладывается операция XOR фрагментов исходного сообщения с фрагментами исходного состояния. Результат обрабатывается функцией ''f''. Данное наложение в совокупности с функцией сжимания, выполняемые для каждого блока входных данных, представляют собой «впитывающую» (absorbing) фазу криптографической губки. |
||
Стоит отметить, что функция f использует только операции, стойкие к атакам, использующим утечки данных по побочным каналам. |
Стоит отметить, что функция ''f'' использует только операции, стойкие к атакам, использующим утечки данных по побочным каналам. |
||
Результирующее хеш-значение вычисляется в процессе выполнения «выжимающей» (squeezing) фазы криптографической губки, основу которой также составляет описанная выше функция f. Возможные размеры хеш-значений — 224, 256, 384 и 512 бит. |
Результирующее хеш-значение вычисляется в процессе выполнения «выжимающей» (squeezing) фазы криптографической губки, основу которой также составляет описанная выше функция ''f''. Возможные размеры хеш-значений — 224, 256, 384 и 512 бит. |
||
== Настройки == |
== Настройки == |
||
Оригинальный алгоритм Keccak имеет множество настраиваемых параметров с целью обеспечения оптимального соотношения [[Криптостойкость|криптостойкости]] и быстродействия для |
Оригинальный алгоритм Keccak имеет множество настраиваемых параметров<ref name=":0" /> с целью обеспечения оптимального соотношения [[Криптостойкость|криптостойкости]] и быстродействия для определённого применения алгоритма на определённой платформе. Настраиваемыми величинами являются: размер блока данных, размер состояния алгоритма, количество раундов в функции ''f()'' и другие. |
||
На протяжения конкурса хеширования [[Национальный институт стандартов и технологий|Национального института стандартов и технологий]] участники имели право настраивать свои алгоритмы для решения возникших проблем. Так, были внесены некоторые изменения в Keccak: количество раундов было увеличено с 18 до 24 с целью увеличения запаса безопасности. |
На протяжения конкурса хеширования [[Национальный институт стандартов и технологий|Национального института стандартов и технологий]] участники имели право настраивать свои алгоритмы для решения возникших проблем. Так, были внесены некоторые изменения в Keccak: количество раундов было увеличено с 18 до 24 с целью увеличения запаса безопасности. |
||
Строка 58: | Строка 139: | ||
Авторы Keccak учредили ряд призов за достижения в [[криптоанализ]]е данного алгоритма. |
Авторы Keccak учредили ряд призов за достижения в [[криптоанализ]]е данного алгоритма. |
||
Версия алгоритма, принятая в качестве окончательного стандарта SHA-3, имеет несколько незначительных отличий от оригинального предложения Keccak на конкурс. В частности, были ограничены некоторые параметры (отброшены медленные режимы c=768 и c=1024), в том числе для увеличения производительности |
Версия алгоритма, принятая в качестве окончательного стандарта SHA-3, имеет несколько незначительных отличий от оригинального предложения Keccak на конкурс. В частности, были ограничены некоторые параметры (отброшены медленные режимы c=768 и c=1024), в том числе для увеличения производительности<ref>{{cite web|url=https://www.schneier.com/blog/archives/2013/10/will_keccak_sha-3.html|title=Will Keccak = SHA-3?|date=2013-10-01|accessdate=2013-12-20|archive-date=2014-01-30|archive-url=https://web.archive.org/web/20140130011800/https://www.schneier.com/blog/archives/2013/10/will_keccak_sha-3.html|deadlink=no}}</ref><ref>{{cite news|url=https://www.cdt.org/blogs/joseph-lorenzo-hall/2409-nist-sha-3|title=What the heck is going on with NIST’s cryptographic standard, SHA-3?|date=2013-09-24|lang=en|accessdate=2013-12-20|archivedate=2014-01-25|archiveurl=https://web.archive.org/web/20140125143053/https://www.cdt.org/blogs/joseph-lorenzo-hall/2409-nist-sha-3}}</ref><ref>{{cite web|url=http://keccak.noekeon.org/yes_this_is_keccak.html|title=Yes, this is Keccak!|date=2013-10-04|accessdate=2013-12-20|archive-date=2013-12-08|archive-url=https://web.archive.org/web/20131208032038/http://keccak.noekeon.org/yes_this_is_keccak.html|deadlink=no}} — ответное заявление от авторов Keccak</ref><ref>{{cite web|url=http://keccak.noekeon.org/version_3.0.html|title=The Keccak sponge function family|date=2011-01-17|accessdate=2015-09-30|archive-date=2015-09-12|archive-url=https://web.archive.org/web/20150912004943/http://keccak.noekeon.org/version_3.0.html|deadlink=no}} — изменение алгоритма заполнения в 3-м раунде конкурса</ref>. Также в стандарте были введены «функции с удлиняемым результатом» (XOF, Extendable Output Functions) SHAKE128 и SHAKE256, для чего хешируемое сообщение стало необходимо дополнять «[[суффикс]]ом» из 2 или 4 бит, в зависимости от типа функции. |
||
{| class="wikitable" |
{| class="wikitable" |
||
Строка 78: | Строка 159: | ||
== Дополнительные функции == |
== Дополнительные функции == |
||
В декабре 2016 года [[Национальный институт стандартов и технологий]] США опубликовал новый документ, NIST SP.800-185<ref>{{Cite web |url=http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-185.pdf |title=SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash |access-date=2017-10-31 |archive-date=2017-10-31 |archive-url=https://web.archive.org/web/20171031131054/http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-185.pdf |deadlink=no }}</ref>, описывающий дополнительные функции на основе SHA-3: |
|||
В декабре 2016 года [[Национальный институт стандартов и технологий]] США опубликовал новый документ, NIST SP.800-185<ref>[http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-185.pdf SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash</ref>, описывающий дополнительные функции на основе SHA-3: |
|||
{| class="wikitable" |
{| class="wikitable" |
||
Строка 97: | Строка 177: | ||
| KMACXOF256(''K'', ''X'', ''L'', ''S'') |
| KMACXOF256(''K'', ''X'', ''L'', ''S'') |
||
|- |
|- |
||
| TupleHash128(''X'', ''L'', ''S'') ||rowspan="4" |Хеширование [[Кортеж (информатика)| |
| TupleHash128(''X'', ''L'', ''S'') ||rowspan="4" |Хеширование [[Кортеж (информатика)|кортежа]] строк |
||
|- |
|- |
||
| TupleHash256(''X'', ''L'', ''S'') |
| TupleHash256(''X'', ''L'', ''S'') |
||
Строка 129: | Строка 209: | ||
46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be |
46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be |
||
Малое изменение сообщения приводит к значительным изменениям в значении хеш-функции благодаря [[Лавинный эффект|лавинному эффекту]] как показано в следующих примерах: |
Малое изменение сообщения приводит к значительным изменениям в значении хеш-функции благодаря [[Лавинный эффект|лавинному эффекту]], как показано в следующих примерах: |
||
<span style="color: green;">SHA3-224("[[The quick brown fox jumps over the lazy dog]]")</span> |
<span style="color: green;">SHA3-224("[[The quick brown fox jumps over the lazy dog]]")</span> |
||
d15dadceaa4d5d7bb3b48f446421d542e08ad8887305e28d58335795 |
d15dadceaa4d5d7bb3b48f446421d542e08ad8887305e28d58335795 |
||
<span style="color: green;">SHA3-224("The quick brown fox jumps over the lazy dog<span style="color: red;">.</span>")</span> |
<span style="color: green;">SHA3-224("The quick brown fox jumps over the lazy dog<span style="color: red;">.</span>")</span> |
||
2d0708903833afabdd232a20201176e8b58c5be8a6fe74265ac54db0 |
2d0708903833afabdd232a20201176e8b58c5be8a6fe74265ac54db0 |
||
<span style="color: green;">SHA3-256("The quick brown fox jumps over the lazy dog")</span> |
<span style="color: green;">SHA3-256("The quick brown fox jumps over the lazy dog")</span> |
||
69070dda01975c8c120c3aada1b282394e7f032fa9cf32f4cb2259a0897dfc04 |
69070dda01975c8c120c3aada1b282394e7f032fa9cf32f4cb2259a0897dfc04 |
||
<span style="color: green;">SHA3-256("The quick brown fox jumps over the lazy dog<span style="color: red;">.</span>")</span> |
<span style="color: green;">SHA3-256("The quick brown fox jumps over the lazy dog<span style="color: red;">.</span>")</span> |
||
a80f839cd4f83f6c3dafc87feae470045e4eb0d366397d5c6ce34ba1739f734d |
a80f839cd4f83f6c3dafc87feae470045e4eb0d366397d5c6ce34ba1739f734d |
||
<span style="color: green;">SHA3-384("The quick brown fox jumps over the lazy dog")</span> |
<span style="color: green;">SHA3-384("The quick brown fox jumps over the lazy dog")</span> |
||
7063465e08a93bce31cd89d2e3ca8f602498696e253592ed26f07bf7e703cf328581e1471a7ba7ab119b1a9ebdf8be41 |
7063465e08a93bce31cd89d2e3ca8f602498696e253592ed26f07bf7e703cf328581e1471a7ba7ab119b1a9ebdf8be41 |
||
<span style="color: green;">SHA3-384("The quick brown fox jumps over the lazy dog<span style="color: red;">.</span>")</span> |
<span style="color: green;">SHA3-384("The quick brown fox jumps over the lazy dog<span style="color: red;">.</span>")</span> |
||
1a34d81695b622df178bc74df7124fe12fac0f64ba5250b78b99c1273d4b080168e10652894ecad5f1f4d5b965437fb9 |
1a34d81695b622df178bc74df7124fe12fac0f64ba5250b78b99c1273d4b080168e10652894ecad5f1f4d5b965437fb9 |
||
<span style="color: green;">SHA3-512("The quick brown fox jumps over the lazy dog")</span> |
<span style="color: green;">SHA3-512("The quick brown fox jumps over the lazy dog")</span> |
||
01dedd5de4ef14642445ba5f5b97c15e47b9ad931326e4b0727cd94cefc44fff23f07bf543139939b49128caf436dc1bdee54fcb24023a08d9403f9b4bf0d450 |
01dedd5de4ef14642445ba5f5b97c15e47b9ad931326e4b0727cd94cefc44fff23f07bf543139939b49128caf436dc1bdee54fcb24023a08d9403f9b4bf0d450 |
||
<span style="color: green;">SHA3-512("The quick brown fox jumps over the lazy dog<span style="color: red;">.</span>")</span> |
<span style="color: green;">SHA3-512("The quick brown fox jumps over the lazy dog<span style="color: red;">.</span>")</span> |
||
18f4f4bd419603f95538837003d9d254c26c23765565162247483f65c50303597bc9ce4d289f21d1c2f1f458828e33dc442100331b35e7eb031b5d38ba6460f8 |
18f4f4bd419603f95538837003d9d254c26c23765565162247483f65c50303597bc9ce4d289f21d1c2f1f458828e33dc442100331b35e7eb031b5d38ba6460f8 |
||
<span style="color: green;">SHAKE128("The quick brown fox jumps over the lazy dog", 256)</span> |
<span style="color: green;">SHAKE128("The quick brown fox jumps over the lazy dog", 256)</span> |
||
f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e |
f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e |
||
<span style="color: green;">SHAKE128("The quick brown fox jumps over the lazy do<span style="color: red;">f</span>", 256)</span> |
<span style="color: green;">SHAKE128("The quick brown fox jumps over the lazy do<span style="color: red;">f</span>", 256)</span> |
||
853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c |
853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c |
||
== Криптоанализ == |
|||
{| class="wikitable" |
|||
|+Результаты криптоанализа во время конкурса<ref name=":3" />. |
|||
!Цель |
|||
!Тип атаки |
|||
!Выход |
|||
!Вариант |
|||
!CF Call |
|||
!Память |
|||
|- |
|||
|Хеш-функция |
|||
|Коллизия |
|||
|160 |
|||
|r = {240, 640, 1440}, |
|||
c = 160, |
|||
1, 2 раунда |
|||
| |
|||
| |
|||
|- |
|||
|Хеш-функция |
|||
|Нахождение прообраза |
|||
|80 |
|||
|r = {240, 640, 1440}, |
|||
c = 160, |
|||
1, 2 раунда |
|||
| |
|||
| |
|||
|- |
|||
|Перестановки |
|||
|Атака-различитель |
|||
|Все |
|||
|24 раунда |
|||
|<math>2^{1579}</math> |
|||
| |
|||
|- |
|||
|Перестановки |
|||
|Дифференциальное свойство |
|||
|Все |
|||
|8 раундов |
|||
|<math>2^{491.47}</math> |
|||
| |
|||
|- |
|||
|Хеш-функция |
|||
|Атака-различитель |
|||
|224, 256 |
|||
|4 раунда |
|||
|<math>2^{25}</math> |
|||
| |
|||
|- |
|||
|Хеш-функция |
|||
|Коллизия |
|||
|224, 256 |
|||
|2 раунда |
|||
|<math>2^{33}</math> |
|||
| |
|||
|- |
|||
|Хеш-функция |
|||
|Нахождение второго прообраза |
|||
|224, 256 |
|||
|2 раунда |
|||
|<math>2^{33}</math> |
|||
|<math>2^{29}</math> |
|||
|- |
|||
|Хеш-функция |
|||
|Нахождение второго прообраза |
|||
|512 |
|||
|6 раундов |
|||
|<math>2^{506}</math> |
|||
|<math>2^{176}</math> |
|||
|- |
|||
|Хеш-функция |
|||
|Нахождение второго прообраза |
|||
|512 |
|||
|7 раундов |
|||
|<math>2^{507}</math> |
|||
|<math>2^{320}</math> |
|||
|- |
|||
|Хеш-функция |
|||
|Нахождение второго прообраза |
|||
|512 |
|||
|8 раундов |
|||
|<math>2^{511.5}</math> |
|||
|<math>2^{508}</math> |
|||
|- |
|||
|Хеш-функция |
|||
|Коллизия |
|||
|224, 256 |
|||
|4 раунда |
|||
| |
|||
| |
|||
|} |
|||
== Примечания == |
== Примечания == |
||
{{примечания}} |
{{примечания|2}} |
||
== Ссылки == |
== Ссылки == |
||
* [http://www.nist.gov/itl/csd/sha-100212.cfm NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition] / NIST, October 2012{{ref-en}} |
* [http://www.nist.gov/itl/csd/sha-100212.cfm NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition] {{Wayback|url=http://www.nist.gov/itl/csd/sha-100212.cfm |date=20121005031201 }} / NIST, October 2012{{ref-en}} |
||
* [http://keccak.noekeon.org/ The Keccak sponge function family] / Сайт Noekeon, 2015-10-15 |
* [http://keccak.noekeon.org/ The Keccak sponge function family] {{Wayback|url=http://keccak.noekeon.org/ |date=20161012055221 }} / Сайт Noekeon, 2015-10-15 — Официальная страница хеш-функции Keccak{{ref-en}} |
||
* [https://www.pgpru.com/biblioteka/statji/keccaksponge |
* [https://www.pgpru.com/biblioteka/statji/keccaksponge Хеш-функция Keccak и конструкция Sponge как универсальный криптопримитив] {{Wayback|url=https://www.pgpru.com/biblioteka/statji/keccaksponge |date=20130623003021 }}, pgpru.com, 2010—2013 (перевод материала с noekon.org) |
||
* [https://www.nist.gov/publications/sha-3-standard-permutation-based-hash-and-extendable-output-functions?pub_id=919061 SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions | NIST] {{Wayback|url=https://www.nist.gov/publications/sha-3-standard-permutation-based-hash-and-extendable-output-functions?pub_id=919061 |date=20170917124233 }}{{ref-en}} |
|||
* [http://en.wikipedia.org/wiki/SHA-3#cite_note-5 SHA-3]{{уточнить}}{{не АИ|23|01|2016}} |
|||
Реализации: |
Реализации: |
||
* {{cite web |
|||
* [http://keccak.noekeon.org/KeccakInPython-3.0.zip Python implementation], Noekon, 2011-01 |
|||
|url = https://keccak.team/software.html |
|||
* [https://github.com/kocakosm/pitaya/blob/master/src/org/kocakosm/pitaya/security/Keccak.java Java implementation], Pitaya <!-- не каталог сторонних реализаций --> |
|||
|title = Software resources |
|||
|author = |
|||
|date = |
|||
|website = https://keccak.team/ |
|||
|publisher = The Keccak team |
|||
|accessdate = 2017-12-06 |
|||
|lang = en |
|||
|archive-date = 2017-12-07 |
|||
|archive-url = https://web.archive.org/web/20171207012651/https://keccak.team/software.html |
|||
|deadlink = no |
|||
}} |
|||
* [https://github.com/kocakosm/pitaya/blob/master/src/org/kocakosm/pitaya/security/Keccak.java Java implementation], Pitaya |
|||
<!-- не каталог сторонних реализаций --> |
|||
{{Перевести|en|SHA-3}} |
{{Перевести|en|SHA-3}} |
Текущая версия от 11:36, 24 мая 2024
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 стал победителем конкурса криптографических алгоритмов, проводимого Национальным институтом стандартов и технологий США[1]. 5 августа 2015 года алгоритм утверждён и опубликован в качестве стандарта FIPS 202[2][3]. В программной реализации авторы заявляют о 12,5 циклах на байт при выполнении на ПК с процессором Intel Core 2. Однако в аппаратных реализациях Keccak оказался намного быстрее, чем все другие финалисты.[4]
Алгоритм SHA-3 построен по принципу криптографической губки (данная структура криптографических алгоритмов была предложена авторами алгоритма Keccak ранее)[5].
История
[править | править код]В 2004—2005 годах несколько алгоритмов хеширования были атакованы, в том числе были опубликованы серьезные атаки против алгоритма SHA-1, утвержденного Национальным институтом стандартов и технологий (NIST). В ответ NIST провел открытые семинары и 2 ноября 2007 года анонсировал конкурс на разработку нового алгоритма хеширования. 2 октября 2012 года победителем конкурса стал алгоритм Keccak и был стандартизован как новый алгоритм SHA-3[6]. 5 августа 2015 года алгоритм утвержден и опубликован в качестве стандарта FIPS 202[2][3].
Алгоритм был разработан Гвидо Бертони[англ.], Йоаном Дайменом, Жилем Ван Аше[англ.] из STMicroelectronics и Микаэлем Питерсом[англ.] из NXP[7].
Алгоритм основан на более ранних хеш-функциях Panama и RadioGatún[8]. Panama был разработан Дайменом и Крейгом Клэппом в 1998 году, RadioGatún был реализован на основе Panama Дайменом, Питерсом и Ван Аше в 2006 году[8].
В ходе конкурса конкурсантам разрешалось вносить изменения в свой алгоритм для исправления обнаруживающихся проблем. Изменения, внесенные в алгоритм Keccak[9][10]:
- Количество раундов было увеличено с 12 + до 12 + 2
- Padding был изменён со сложной формы на более простую, описанную ниже
- Скорость (rate) r была увеличена до предела безопасности (ранее округлялась вниз до ближайшей степени 2)
Алгоритм
[править | править код]Хеш-функции семейства SHA-3 построены на основе конструкции криптографической губки[5], в которой данные сначала «впитываются» в губку, при котором исходное сообщение подвергается многораундовым перестановкам , затем результат «отжимается» из губки. На этапе «впитывания» блоки сообщения суммируются по модулю 2 с подмножеством состояния, после чего всё состояние преобразуется с помощью функции перестановки . На этапе «отжимания» выходные блоки считываются из одного и того же подмножества состояния, изменённого функцией перестановок . Размер части состояния, который записывается и считывается, называется «скоростью» (англ. rate) и обозначается , а размер части, которая нетронута вводом / выводом, называется «ёмкостью» (англ. capacity) и обозначается .
Алгоритм получения значения хеш-функции можно разделить на несколько этапов[11]:
- Исходное сообщение дополняется до строки длины, кратной , с помощью функции дополнения (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[11]: к сообщению добавляется 1, после него — 0 или больше нулевых битов (до r-1), в конце — 1.
r-1 нулевых битов может быть добавлено, когда последний блок сообщения имеет длину r-1 бит. Этот блок дополняется единицей, следующий блок будет состоять из r-1 нулей и единицы.
Два единичных бита добавляются и в том случае, если длина исходного сообщения M делится на r[11]. В этом случае к сообщению добавляется блок, начинающийся и оканчивающийся единицами, между которыми r-2 нулевых битов. Это необходимо для того, чтобы для сообщения, оканчивающегося последовательностью битов как в функции дополнения, и для сообщения без этих битов значения хеш-функции были различны.
Первый единичный бит необходим для того, чтобы результаты хеш-функции от сообщений, различающихся несколькими нулевыми битами в конце, были различны[11].
Функция перестановок
[править | править код]Функция перестановок, используемая в SHA-3, включает в себя исключающее «ИЛИ» (XOR), побитовое «И» (AND) и побитовое отрицание (NOT). Функция определена для строк длины-степени 2 . В основной реализации SHA-3 ().
Состояние можно представить в виде трёхмерного массива размером 5 × 5 × . Тогда элемент массива - это бит строки состояния .
Функция содержит несколько шагов: , , , , , которые выполняются несколько раундов[11]. На каждом шаге обозначим входной массив A, выходной массив A'.
Шаг
[править | править код]Для всех и , таких, что , , положим
Для всех , таких, что , , ,
Шаг
[править | править код]Для всех , таких, что ,
Пусть в начале . Для от 0 до 23:
- Для всех , таких, что ,
Шаг
[править | править код]Для всех , таких, что , ,
Шаг
[править | править код]Для всех , таких, что , ,
Шаг
[править | править код]Введем дополнительную функцию , где вход — целое число , а на выходе — бит.
Алгоритм
[править | править код]- Если , то возвращается 1
- Пусть
- Для i от 1 до t mod 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 имеет множество настраиваемых параметров[11] с целью обеспечения оптимального соотношения криптостойкости и быстродействия для определённого применения алгоритма на определённой платформе. Настраиваемыми величинами являются: размер блока данных, размер состояния алгоритма, количество раундов в функции f() и другие.
На протяжения конкурса хеширования Национального института стандартов и технологий участники имели право настраивать свои алгоритмы для решения возникших проблем. Так, были внесены некоторые изменения в Keccak: количество раундов было увеличено с 18 до 24 с целью увеличения запаса безопасности.
Авторы Keccak учредили ряд призов за достижения в криптоанализе данного алгоритма.
Версия алгоритма, принятая в качестве окончательного стандарта SHA-3, имеет несколько незначительных отличий от оригинального предложения Keccak на конкурс. В частности, были ограничены некоторые параметры (отброшены медленные режимы c=768 и c=1024), в том числе для увеличения производительности[12][13][14][15]. Также в стандарте были введены «функции с удлиняемым результатом» (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[16], описывающий дополнительные функции на основе 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 раунда |
Примечания
[править | править код]- ↑ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition . Дата обращения: 3 октября 2012. Архивировано 5 октября 2012 года.
- ↑ 1 2 NIST Releases SHA-3 Cryptographic Hash Standard . Дата обращения: 21 января 2016. Архивировано 17 августа 2015 года.
- ↑ 1 2 NIST Manuscript Publication Search . Дата обращения: 21 января 2016. Архивировано 12 августа 2015 года.
- ↑ 1 2 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.
- ↑ 1 2 Keccak Team (англ.). keccak.team. Дата обращения: 15 декабря 2017. Архивировано 16 декабря 2017 года.
- ↑ SHA-3 Project - Hash Functions | CSRC . csrc.nist.gov. Дата обращения: 7 ноября 2017. Архивировано 20 ноября 2017 года.
- ↑ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition . NIST (2 октября 2012). Дата обращения: 2 октября 2012. Архивировано 30 апреля 2017 года.
- ↑ 1 2 Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche. The Road from Panama to Keccak via RadioGatún // Symmetric Cryptography / Helena Handschuh, Stefan Lucks, Bart Preneel, Phillip Rogaway. — Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2009. Архивировано 22 декабря 2017 года.
- ↑ Keccak Team (англ.). keccak.team. Дата обращения: 12 ноября 2017. Архивировано 13 ноября 2017 года.
- ↑ Keccak Team (англ.). keccak.team. Дата обращения: 12 ноября 2017. Архивировано 13 ноября 2017 года.
- ↑ 1 2 3 4 5 6 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. Архивировано 30 января 2014 года.
- ↑ "What the heck is going on with NIST's cryptographic standard, SHA-3?" (англ.). 2013-09-24. Архивировано 25 января 2014. Дата обращения: 20 декабря 2013.
- ↑ Yes, this is Keccak! (4 октября 2013). Дата обращения: 20 декабря 2013. Архивировано 8 декабря 2013 года. — ответное заявление от авторов Keccak
- ↑ The Keccak sponge function family (17 января 2011). Дата обращения: 30 сентября 2015. Архивировано 12 сентября 2015 года. — изменение алгоритма заполнения в 3-м раунде конкурса
- ↑ SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash . Дата обращения: 31 октября 2017. Архивировано 31 октября 2017 года.
Ссылки
[править | править код]- 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
В другом языковом разделе есть более полная статья SHA-3 (англ.). |