SHA-3: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Содержимое удалено Содержимое добавлено
Алгоритм, уточнение
м откат правок 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]] года Keccak стал победителем [[SHA-3 (конкурс)|конкурса криптографических алгоритмов]], проводимым [[Национальный институт стандартов и технологий|Национальным институтом стандартов и технологий США]].<ref>[http://www.nist.gov/itl/csd/sha-100212.cfm NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition]</ref> 5 августа [[2015]] года алгоритм утверждён и опубликован в качестве стандарта [[FIPS]] 202.<ref name="nist.gov">[http://www.nist.gov/itl/csd/201508_sha3.cfm NIST Releases SHA-3 Cryptographic Hash Standard<!-- Заголовок добавлен ботом -->]</ref><ref>[http://www.nist.gov/manuscript-publication-search.cfm?pub_id=919061 NIST Manuscript Publication Search<!-- Заголовок добавлен ботом -->]</ref> В программной реализации авторы заявляют о 12,5 циклах на байт при выполнении на [[персональный компьютер|ПК]] с процессором [[Core 2|Intel Core 2]]. Однако в аппаратных реализациях Keccak оказался намного быстрее, чем все другие финалисты.
'''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|мини|справа|Конструкция Губка, использованная в хеш-функции. pi — входные блоки, zj — выход алгоритма. Неиспользуемый для вывода набор битов c («capacity») должен иметь значительный размер для достижения устойчивости к атакам]]
[[Файл:SpongeConstruction.svg|мини|справа|Конструкция [[Функция губки|функции губки]], использованная в хеш-функции. ''P<sub>i</sub>'' — входные блоки, ''Z<sub>j</sub>'' — выход алгоритма. Размер ''c'' («capacity») неиспользуемого для вывода набора битов должен быть значительным для достижения устойчивости к атакам]]
Алгоритм SHA-3 построен по принципу [[Функция Губка|криптографической губки]] (данная структура криптографических алгоритмов была предложена авторами алгоритма Keccak ранее).
Алгоритм 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 год|2007]] года анонсировал конкурс на разработку нового алгоритма хеширования. 2 октября [[2012 год|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}}</ref> 5 августа [[2015 год|2015]] года алгоритм утвержден и опубликован в качестве стандарта [[FIPS]] 202.<ref name="nist.gov">[http://www.nist.gov/itl/csd/201508_sha3.cfm NIST Releases SHA-3 Cryptographic Hash Standard<!-- Заголовок добавлен ботом -->]</ref><ref>[http://www.nist.gov/manuscript-publication-search.cfm?pub_id=919061 NIST Manuscript Publication Search<!-- Заголовок добавлен ботом -->]</ref> Алгоритм был разработан Гвидо Бертони, Йоаном Дайменом, Жилем Ван Аше из STMicroelectronics и Микаэлем Питерсом из NXP Semiconductors. Алгоритм основан на более ранних хеш-функциях [[Хеш-функция Panama|PANAMA]] и RadioGatún. Panama был разработан Дайменом и Крейгом Клэппом в 1998 году. RadioGatún был реализован на основе Panama Дайменом, Питерсом и Ван Аше в 2006 году.
В 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'' построены на основе конструкции [[Функция губки|криптографической губки]], в которой данные сначала "впитываются" в губку, при котором исходное сообщение M подвергается многораундовым перестановкам f, затем результат Z "отжимается" из губки. На этапе "впитывания" блоки сообщения суммируются по модулю 2 с подмножеством состояния, которое затем преобразуется с помощью функции перестановки f. На этапе "отжимания" выходные блоки считываются из одного и того же подмножества состояния, чередующегося с функцией перестановок f. Размер части состояния, который записывается и считывается, называется "скоростью" (англ. rate) и обозначается r, а размер части, которая нетронута вводом / выводом, называется "емкостью" (англ. capacity) и обозначается c. Алгоритм получения значения хеш-функции можно разделить на несколько этапов:
Хеш-функции семейства ''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> длинной r бит суммируется по модулю 2 с первыми r-битами набора начальных состояний S. Перед началом работы функции все элементы S равны нулю.
* «Впитывание»: каждый блок <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'' — временный массив, аналогичный по структуре массиву состояния;

B — временный массив, аналогичный по структуре массиву состояния; <br />C и D — временные массивы, содержащие по пять 64-битных слов;<br />r — массив, определяющий величину циклического сдвига для каждого слова состояния; <br />~x — [[поразрядное дополнение]] к x;
:''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 имеет множество настраиваемых параметров с целью обеспечения оптимального соотношения [[Криптостойкость|криптостойкости]] и быстродействия для определенного применения алгоритма на определенной платформе. Настраиваемыми величинами являются: размер блока данных, размер состояния алгоритма, количество раундов в функции f() и другие.
Оригинальный алгоритм Keccak имеет множество настраиваемых параметров<ref name=":0" /> с целью обеспечения оптимального соотношения [[Криптостойкость|криптостойкости]] и быстродействия для определённого применения алгоритма на определённой платформе. Настраиваемыми величинами являются: размер блока данных, размер состояния алгоритма, количество раундов в функции ''f()'' и другие.


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


Версия алгоритма, принятая в качестве окончательного стандарта SHA-3, имеет несколько незначительных отличий от оригинального предложения Keccak на конкурс. В частности, были ограничены некоторые параметры (отброшены медленные режимы c=768 и c=1024), в том числе для увеличения производительности, а также изменён алгоритм заполнения (padding) на более простой.<ref>{{cite web|url=https://www.schneier.com/blog/archives/2013/10/will_keccak_sha-3.html|title=Will Keccak = SHA-3?|date=October 1, 2013|accessdate=2013-12-20}}</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=September 24, 2013|lang=en|accessdate=2013-12-20}}</ref><ref>{{cite web|url=http://keccak.noekeon.org/yes_this_is_keccak.html|title=Yes, this is Keccak!|date=4 October 2013|accessdate=2013-12-20}} — ответное заявление от авторов Keccak</ref><ref>{{cite web|url=http://keccak.noekeon.org/version_3.0.html|title=The Keccak sponge function family|date=January 17, 2011|accessdate=2015-09-30}} — изменение алгоритма заполнения в 3-м раунде конкурса</ref> Также в стандарте были введены «функции с удлиняемым результатом» (XOF, Extendable Output Functions) SHAKE128 и SHAKE256, для чего хешируемое сообщение стало необходимо дополнять «[[Суффикс|суффиксом]]» из 2 или 4 бит, в зависимости от типа функции.
Версия алгоритма, принятая в качестве окончательного стандарта 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 - Официальная страница хэш-функции Keccak {{ref-en}}
* [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 Хэш-функция Keccak и конструкция Sponge как универсальный криптопримитив], pgpru.com, 2010-2013 (перевод материала с noekon.org)
* [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]

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

Алгоритм 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. Для всех , таких, что ,

Шаг

[править | править код]

Для всех , таких, что , ,

Шаг

[править | править код]

Для всех , таких, что , ,

Шаг

[править | править код]

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

Алгоритм

[править | править код]
  1. Если , то возвращается 1
  2. Пусть
  3. Для i от 1 до t mod 255:
    1. R = 0 || R
  4. Возвращается

Алгоритм

[править | править код]

 — номер раунда.

  1. Для всех , таких, что , ,
  2. Пусть  — массив длины , заполненный нулями.
  3. Для от 0 до :
  4. Для всех , таких, что ,

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

[править | править код]
  1. Перевод строки в массив
  2. Для от до
  3. Перевод массива в строку длины

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

[править | править код]

Основой функции сжатия алгоритма является функция 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

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

[править | править код]
Результаты криптоанализа во время конкурса[4].
Цель Тип атаки Выход Вариант 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 раунда

Примечания

[править | править код]
  1. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. Дата обращения: 3 октября 2012. Архивировано 5 октября 2012 года.
  2. 1 2 NIST Releases SHA-3 Cryptographic Hash Standard. Дата обращения: 21 января 2016. Архивировано 17 августа 2015 года.
  3. 1 2 NIST Manuscript Publication Search. Дата обращения: 21 января 2016. Архивировано 12 августа 2015 года.
  4. 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.
  5. 1 2 Keccak Team (англ.). keccak.team. Дата обращения: 15 декабря 2017. Архивировано 16 декабря 2017 года.
  6. SHA-3 Project - Hash Functions | CSRC. csrc.nist.gov. Дата обращения: 7 ноября 2017. Архивировано 20 ноября 2017 года.
  7. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST (2 октября 2012). Дата обращения: 2 октября 2012. Архивировано 30 апреля 2017 года.
  8. 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 года.
  9. Keccak Team (англ.). keccak.team. Дата обращения: 12 ноября 2017. Архивировано 13 ноября 2017 года.
  10. Keccak Team (англ.). keccak.team. Дата обращения: 12 ноября 2017. Архивировано 13 ноября 2017 года.
  11. 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.
  12. Will Keccak = SHA-3? (1 октября 2013). Дата обращения: 20 декабря 2013. Архивировано 30 января 2014 года.
  13. "What the heck is going on with NIST's cryptographic standard, SHA-3?" (англ.). 2013-09-24. Архивировано 25 января 2014. Дата обращения: 20 декабря 2013.
  14. Yes, this is Keccak! (4 октября 2013). Дата обращения: 20 декабря 2013. Архивировано 8 декабря 2013 года. — ответное заявление от авторов Keccak
  15. The Keccak sponge function family (17 января 2011). Дата обращения: 30 сентября 2015. Архивировано 12 сентября 2015 года. — изменение алгоритма заполнения в 3-м раунде конкурса
  16. SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash. Дата обращения: 31 октября 2017. Архивировано 31 октября 2017 года.

Реализации: