SHA-3

SHA-3 ( Secure Hash Algorithm 3 ) - последний член семейства стандартов Secure Hash Algorithm , выпущенный NIST 5 августа 2015 года. ^{[4] [5] [6]} Несмотря на то, что он является частью той же серии стандартов, SHA -3 внутренне отличается от MD5 -подобной структуры из SHA-1 и SHA-2 .

SHA-3 представляет собой подмножество более широкой криптографической примитивного семейства Keccak ( / к ɛ tʃ æ к / или / K ɛ tʃ ɑː к / ), ^{[7] [8]} разработан Guido Bertoni , Joan Daemen , Майкл Петерс, и Жиль Ван Аше , основанный на RadioGatún . Авторы Кеккака предложили дополнительные варианты использования этой функции, (пока) не стандартизированные NIST, в том числе потоковый шифр , аутентифицированное шифрование.система, «древовидная» схема хеширования для более быстрого хеширования на определенных архитектурах, ^{[9] [10]} и шифры AEAD Keyak и Ketje. ^{[11] [12]}

Keccak основан на новом подходе, который называется « строительство губки» . ^[13] Конструкция губки основана на широкой случайной функции или случайной перестановке и позволяет вводить («поглощать» в терминологии губки) любое количество данных и выводить («сжимать») любое количество данных, действуя как псевдослучайная функция. что касается всех предыдущих входов. Это приводит к большой гибкости.

NIST в настоящее время не планирует отменять SHA-2 или удалять его из пересмотренного стандарта Secure Hash Standard. Назначение SHA-3 состоит в том, что он может быть напрямую заменен на SHA-2 в текущих приложениях, если это необходимо, и значительно повысить надежность общего набора инструментов алгоритмов хеширования NIST. ^[14]

Создатели алгоритмов Keccak и функций SHA-3 предлагают использовать более быструю функцию KangarooTwelve с настроенными параметрами и новый режим хеширования дерева без дополнительных накладных расходов для сообщений небольшого размера.

История [ править ]

Алгоритм Keccak работа Гвидо Бертони, Джоан Daemen (который также совместно спроектировал Rijndael шифра с Винсентом Rijmen ), Майкл Питерс, и Жиль Ван Аше . Он основан на ранее хэш - функции конструкции ПАНАМА и RadioGatún . ПАНАМА был разработан Daemen и Крейг Клапп в 1998 году RadioGatún, преемник ПАНАМА, был разработан Daemen, Петерс и Ван Аше, и был представлен на NIST Hash семинара в 2006 году ^[15] эталонная реализация исходный код был посвящен в общественное достояние через отказ от CC0 . ^[16]

В 2006 году NIST начал организовывать конкурс хэш-функций NIST для создания нового стандарта хеширования SHA-3. SHA-3 не предназначен для замены SHA-2 , поскольку не было продемонстрировано никаких серьезных атак на SHA-2. Из-за успешных атак на MD5 , SHA-0 и SHA-1 , ^{[17] [18]} NIST почувствовал потребность в альтернативном, непохожем криптографическом хэше, который стал SHA-3.

По истечении подготовительного периода заявки должны были быть поданы до конца 2008 года. Кечак был принят в качестве одного из 51 кандидата. В июле 2009 года для второго тура было отобрано 14 алгоритмов. Кечак прошел в последний раунд в декабре 2010 года. ^[19]

Во время конкурса участникам разрешалось «настраивать» свои алгоритмы для решения обнаруженных проблем. В Keccak были внесены следующие изменения: ^{[20] [21]}

• Количество раундов было увеличено с 12 + ℓ до 12 + 2ℓ из соображений безопасности.
• Заполнение сообщений было изменено с более сложной схемы на простой шаблон 10 ^* 1, описанный ниже.
• Скорость r была увеличена до предела безопасности, а не округлялась до ближайшей степени 2.

2 октября 2012 года Кечак был выбран победителем конкурса. ^[7]

В 2014 году NIST опубликовал проект FIPS 202 «Стандарт SHA-3: хеширование на основе перестановок и функции расширяемого вывода». ^[22] FIPS 202 был утвержден 5 августа 2015 г. ^[23]

5 августа 2015 года NIST объявил, что SHA-3 стал стандартом хеширования. ^[24]

Ослабление противоречий [ править ]

В начале 2013 года NIST объявил, что выберет разные значения для «емкости», параметра общей силы и скорости для стандарта SHA-3, по сравнению с представленным. ^{[25] [26]} Изменения вызвали некоторую суматоху.

Соревнование хэш-функций потребовало, чтобы хеш-функции были не менее безопасными, чем экземпляры SHA-2. Это означает , что д выход -битный должен иметь д / 2-битное сопротивление столкновения атак и д сопротивление битового к прообразу атак , максимально достижимого для д бит выхода. Доказательство безопасности Keccak позволяет настраивать уровень безопасности на основе «емкости» c , обеспечивая c / 2-битную устойчивость как к столкновениям, так и к атакам с использованием прообраза. Чтобы соответствовать первоначальным правилам конкурса, авторы Кеккака предложили c = 2 d . Объявленное изменение заключалось в том, чтобы принять тот же d/ 2-битная безопасность для всех форм атак и стандартизация c = d . Это ускорило бы Keccak, позволив хешировать дополнительные d битов ввода на каждой итерации. Однако хеш-функции больше не были бы заменой с таким же сопротивлением прообразу, как SHA-2; он был бы сокращен вдвое, что сделало бы его уязвимым для достижений квантовых вычислений, которые фактически сократили бы его вдвое еще раз. ^[27]

В сентябре 2013 года Дэниел Дж. Бернстайн предложил в списке рассылки хэш-форума NIST ^[28] усилить безопасность до 576-битной емкости, которая первоначально была предложена в качестве Keccak по умолчанию в дополнение к SHA-3 и не включена в нее. технические характеристики. ^[29] Это обеспечило бы как минимум SHA3-224 и SHA3-256 такое же сопротивление прообразу, что и их предшественники SHA-2, но SHA3-384 и SHA3-512 имели бы значительно меньшее сопротивление прообразу, чем их предшественники SHA-2. . В конце сентября команда Keccak ответила, заявив, что они предложили 128-битную безопасность, установив c = 256 в качестве опции уже в своем предложении SHA-3. ^[30]Хотя, по их мнению, уменьшение емкости было оправданным, в свете отрицательного ответа они предложили увеличить емкость до c = 512 бит для всех экземпляров. Он будет таким же, как любой предыдущий стандарт, вплоть до уровня безопасности 256 бит, при этом обеспечивая разумную эффективность ^[31], но не сопротивление 384/512 битам прообраза, предлагаемое SHA2-384 и SHA2-512. Авторы заявили, что «утверждать или полагаться на уровни безопасности выше 256 бит бессмысленно».

В начале октября 2013 года Брюс Шнайер раскритиковал решение NIST на основании его возможных пагубных последствий для принятия алгоритма, заявив:

В воздухе витает слишком много недоверия. NIST рискует опубликовать алгоритм, которому никто не будет доверять и который никто (кроме тех, кто вынужден) не будет использовать. ^[32]

Позже он отказался от своего более раннего заявления, сказав:

Я оговорился, когда написал, что NIST внес «внутренние изменения» в алгоритм. Это было неаккуратно с моей стороны. Перестановка Keccak остается неизменной. NIST предложил уменьшить емкость хэш-функции во имя производительности. Одной из приятных особенностей Keccak является то, что он легко настраивается. ^[32]

Пол Кроули, криптограф и старший разработчик в независимой компании по разработке программного обеспечения, выразил поддержку этому решению, заявив, что Keccak должен быть настраиваемым, и нет причин для разных уровней безопасности в одном примитиве. Он также добавил:

Да, это немного обидно для конкурентов, что они потребовали определенный уровень безопасности для участников, а затем пошли опубликовать стандарт с другим. Но сейчас ничего нельзя сделать, чтобы исправить это, кроме как возобновить соревнование. Требование, чтобы они придерживались своей ошибки, никому ничего не улучшает. ^[33]

Была некоторая путаница в том, что в Keccak могли быть внесены внутренние изменения, которые были прояснены исходной командой, заявив, что предложение NIST для SHA-3 является подмножеством семейства Keccak, для которого можно генерировать тестовые векторы, используя их эталонный код. представили на конкурс, и что это предложение было результатом серии обсуждений между ними и хэш-командой NIST. ^[34]

В ответ на разногласия в ноябре 2013 года Джон Келси из NIST предложил вернуться к исходному предложению c = 2 d для всех экземпляров оперативной замены SHA-2. ^[35] Возврат был подтвержден последующими проектами ^[36] и окончательной версией. ^[4]

Дизайн [ править ]

SHA-3 использует губки строительные , ^[13] , в котором данные «всасывается» в губку, затем результат «выдавливается» аут. В фазе поглощения блоки сообщений подвергаются операции XOR в подмножестве состояния, которое затем преобразуется как единое целое с использованием функции перестановки . В фазе «сжатия» выходные блоки считываются из одного и того же подмножества состояния, чередующегося с функцией преобразования состояния . Размер части состояния, которая записывается и читается, называется «скоростью» (обозначается ), а размер части, которая не затрагивается вводом / выводом, называется «емкостью» (обозначается ). Емкость определяет безопасность схемы.Максимальный уровень безопасности составляет половину емкости.${\ displaystyle f}$${\ displaystyle f}$${\ displaystyle r}$${\ displaystyle c}$

Учитывая входную битовую строку , функцию заполнения, функцию перестановки, которая работает с битовыми блоками ширины , скорости и выходной длины , у нас есть емкость, а конструкция губки , дающая битовую строку длины , работает следующим образом: ^{[5] : 18}${\ displaystyle N}$${\ displaystyle pad}$${\ displaystyle f}$${\ displaystyle b}$${\ displaystyle r}$${\ displaystyle d}$${\ displaystyle c = br}$${\ displaystyle Z = {\ text {sponge}} [f, pad, r] (N, d)}$${\ displaystyle Z}$${\ displaystyle d}$

• заполните вход N с помощью функции заполнения, в результате чего будет получена заполненная битовая строка P с длиной, делимой на (например, целое число)${\ displaystyle r}$${\displaystyle n={\text{len}}(P)/r}$
• разбить P на n последовательных r -битных частей P ₀ , ..., P _{n −1}
• инициализировать состояние S строкой из b нулевых битов
• поглощают ввод в состояние: для каждого блока P _i :
  • расширить P _i в конце строкой из c нулевых битов, получив в результате один длиной b
  • XOR, что с S
  • применить к результату блочную перестановку f , получив новое состояние S
• инициализировать Z как пустую строку
• а длина Z меньше d :
  • добавить первые r битов S к Z
  • если длина Z все еще меньше d битов, примените f к S , получив новое состояние S
• усечь Z до d бит

Тот факт, что внутреннее состояние S содержит c дополнительных битов информации в дополнение к тому, что выводится в Z, предотвращает атаки на расширение длины, которым подвержены SHA-2, SHA-1, MD5 и другие хэши, основанные на конструкции Меркла – Дамгарда .

В SHA-3 состояние S состоит из массива 5 × 5 w -битных слов (с w = 64), b = 5 × 5 × w = 5 × 5 × 64 = всего 1600 бит. Keccak также определен для меньших размеров слова w, равного степени 2, вплоть до 1 бита (общее состояние 25 бит). Небольшие размеры состояний могут использоваться для тестирования криптоаналитических атак, а размеры промежуточных состояний (от w = 8 , 200 бит до w = 32 , 800 бит) могут использоваться в практических, легких приложениях. ^{[11] [12]}

Для экземпляров SHA-3-224, SHA-3-256, SHA-3-384 и SHA-3-512 r больше d , поэтому нет необходимости в дополнительных перестановках блоков в фазе сжатия; ведущие d бит состояния - это желаемый хэш. Однако SHAKE-128 и SHAKE-256 допускают произвольную длину вывода, что полезно в таких приложениях, как оптимальное заполнение асимметричного шифрования .

Заполнение [ править ]

Чтобы гарантировать, что сообщение может быть равномерно разделено на r- битовые блоки, требуется заполнение. SHA-3 использует шаблон 10 ^* 1 в своей функции заполнения: 1 бит, за которым следует ноль или более 0 бит (максимум r - 1 ) и последний 1 бит.

Максимум r - 1 нулевых битов возникает, когда длина последнего блока сообщения составляет r - 1 бит. Затем после начального 1 бита добавляется еще один блок, содержащий r - 1 нулевых битов перед последним 1 битом.

Два бита 1 будут добавлены, даже если длина сообщения уже делится на r . ^{[5] : 5.1} В этом случае к сообщению добавляется еще один блок, содержащий 1 бит, за которым следует блок из r - 2 нулевых бита и еще 1 бит. Это необходимо для того, чтобы сообщение с длиной, кратной r, заканчивающейся чем-то похожим на заполнение, не создавало такой же хэш, как сообщение с удаленными битами.

Требуется начальный 1 бит, поэтому сообщения, различающиеся лишь несколькими дополнительными 0 битами в конце, не создают одинаковый хэш.

Положение последнего бита 1 указывает, какая скорость r была использована (многоскоростное заполнение), что требуется для работы доказательства безопасности для различных вариантов хеширования. Без него разные варианты хеширования одного и того же короткого сообщения были бы одинаковыми до усечения.

Перестановка блоков [ править ]

Блочное преобразование f , которое представляет собой Keccak-f [1600] для SHA-3, представляет собой перестановку, которая использует операции XOR , AND и NOT , и предназначена для простой реализации как в программном, так и в аппаратном обеспечении.

Она определяется для любой мощности из-двух слов размера, W = 2 ^л битов. В основном представлении SHA-3 используются 64-битные слова, ℓ = 6 .

Состояние можно рассматривать как массив бит 5 × 5 × w . Пусть a [ i ] [  j ] [ k ] будет битом (5 i + j ) × w + k ввода, используя соглашение о нумерации битов с прямым порядком байтов и индексирование по старшим строкам . Т.е. я выбирает строку, j - столбец, а k - бит.

Индексная арифметика выполняется по модулю 5 для первых двух измерений и по модулю w для третьего.

Базовая функция перестановки блоков состоит из 12 + 2 ℓ раундов по пять шагов:

θ (тета)

Вычислите четность каждого из 5 w (320, когда w = 64 ) 5-битных столбцов, а также четность двух соседних столбцов в обычном шаблоне. Чтобы быть точным, a [ i ] [  j ] [ k ] ← a [ i ] [  j ] [ k ] четность (a [0 ... 4] [  j −1] [ k ]] »четность (a [ 0 ... 4] [  j +1] [ k −1])

ρ (ро)

Побитовое вращение каждого из 25 слов на другое треугольное число 0, 1, 3, 6, 10, 15, .... Чтобы быть точным, a [0] [0] не вращается, и для всех 0 ≤ t < 24 , a [ i ] [  j ] [ k ] ← a [ i ] [  j ] [ k - ( t +1) ( t +2) / 2] » , где .${\displaystyle {\begin{pmatrix}i\\j\end{pmatrix}}={\begin{pmatrix}3&2\\1&0\end{pmatrix}}^{t}{\begin{pmatrix}0\\1\end{pmatrix}}}$

π (пи)

Переставьте 25 слов по фиксированному шаблону. a [3 i +2 j ] [ i ] ← a [  i ] [ j ] .

χ (чи)

Побитовое объединение по строкам, используя x ← x ⊕ (¬ y & z ) . Чтобы быть точным, a [ i ] [  j ] [ k ] ← a [ i ] [  j ] [ k ] ⊕ (¬ a [ i ] [  j + 1 ] [ k ] & a [ i ] [  j + 2 ] » [ k ]) . Это единственная нелинейная операция в SHA-3.

ι (йота)

Эксклюзивная или округленная константа в одно слово состояния. Чтобы быть точными, в круглом п , для 0 ≤ т ≤ л , [0] [0] [2 ^м -1] является операция XOR с битом м + 7 п градуса 8- LFSR последовательности. Это нарушает симметрию, сохраняемую на других этапах.

Скорость [ править ]

Скорость хеширования длинных сообщений SHA-3 определяется вычислением f = Keccak-f [1600] и XORing S с расширенным P _i , операцией над b = 1600 битами. Однако, поскольку последние c бит расширенного P _i в любом случае равны 0, а XOR с 0 является NOP, достаточно выполнить операции XOR только для r бит ( r = 1600 - 2 × 224 = 1152 бит для SHA3-224 , 1088 бит для SHA3-256, 832 бит для SHA3-384 и 576 бит для SHA3-512). Чем меньше r (и, наоборот, чем больше c = b - r = 1600 - r), тем менее эффективным, но более безопасным становится хеширование, поскольку меньшее количество битов сообщения может быть преобразовано в состояние XOR (быстрая операция) перед каждым применением дорогостоящего в вычислительном отношении f . Авторы сообщают о следующих скоростях программных реализаций Keccak-f [1600] плюс XORing 1024 бит ^[1], что примерно соответствует SHA3-256:

• 57,4 ц / бит на IA-32, Intel Pentium 3 ^[37]
• 41 cpb на IA-32 + MMX, Intel Pentium 3
• 20 cpb на IA-32 + SSE, Intel Core 2 Duo или AMD Athlon 64
• 12,6 cpb на типичной машине на базе x86-64
• 6–7 cpb на IA-64 ^[38]

Для точного SHA3-256 на x86-64 Бернштейн измеряет 11,7–12,25 cpb в зависимости от процессора. ^{[39] : 7} SHA-3 подвергался критике за то, что он медленный на архитектурах с набором команд (ЦП), которые не имеют инструкций, специально предназначенных для более быстрого вычисления функций Keccak - SHA2-512 более чем в два раза быстрее, чем SHA3-512, а SHA -1 более чем в три раза быстрее процессора Intel Skylake с тактовой частотой 3,2 ГГц. ^[40] Авторы отреагировали на эту критику, предложив использовать SHAKE128 и SHAKE256 вместо SHA3-256 и SHA3-512 за счет сокращения вдвое сопротивления прообраза (но при сохранении сопротивления столкновению). При этом производительность находится на уровне SHA2-256 и SHA2-512.

Однако в аппаратных реализациях SHA-3 заметно быстрее, чем все другие финалисты ^[41], а также быстрее, чем SHA-2 и SHA-1. ^[40]

Архитектуры ARMv8 ^[42] и IBM s390x уже (по состоянию на 2018 год) включают специальные инструкции, которые позволяют алгоритмам Keccak выполняться быстрее.

Экземпляры [ править ]

Стандарт NIST определяет следующие экземпляры для сообщения M и выходной длины d : ^{[5] : 20,23}

Со следующими определениями

• Keccak [ c ] ( N , d ) = губка [Keccak-f [1600], pad10 ^* 1, r ] ( N , d ) ^{[5] : 20}
• Keccak-f [1600] = Keccak-p [1600, 24] ^{[5] : 17}
• c - емкость
• r - ставка = 1600 - c
• N - входная битовая строка

Экземпляры SHA-3 являются заменой SHA-2 и имеют идентичные свойства безопасности.

SHAKE будет генерировать столько битов из своей губки, сколько требуется, называемых XOF (расширяемые функции вывода). Например, SHAKE128 (M, 256) может использоваться как хэш-функция с потоком битов 256 символов с уровнем безопасности 128 бит. В качестве генераторов псевдослучайных чисел можно использовать произвольно большие длины. В качестве альтернативы SHAKE256 (M, 128) может использоваться как хэш-функция с длиной 128 бит и сопротивлением 128 бит, но в отличие от усеченного вывода функций семейств MD и SHA, включая SHA-3, сохранит свои свойства безопасности в любой момент. данный размер. Функции SHAKE требуют, чтобы каждый выходной бит был таким же сильным, как и последний, тогда как для других хешей требуется только, чтобы весь хеш был сильным, в то время как подмножество могло быть слабым. ^[5]

Все экземпляры добавляют к сообщению некоторые биты, крайний правый из которых представляет суффикс разделения домена. Это делается для того, чтобы гарантировать невозможность создания сообщений, которые производят один и тот же хеш-вывод для разных приложений хеш-функции Keccak. Существуют следующие суффиксы разделения домена: ^{[5] [43]}

Дополнительные экземпляры [ править ]

В декабре 2016 года NIST опубликовал новый документ, NIST SP.800-185, ^[44], описывающий дополнительные производные от SHA-3 функции:

• X - основная входная битовая строка. Он может быть любой длины, в том числе нулевой.

• L - целое число, представляющее запрашиваемую длину вывода в битах.

• N - битовая строка имени функции, используемая NIST для определения функций на основе cSHAKE. Когда не требуется никакой другой функции, кроме cSHAKE, N устанавливается на пустую строку.

• S - строка битов настройки. Пользователь выбирает эту строку, чтобы определить вариант функции. Если настройка не требуется, S устанавливается в пустую строку.

• K - строка ключей любой длины, включая ноль.

• B - размер блока в байтах для параллельного хеширования. Это может быть любое целое число, такое что 0 <B <2 ²⁰⁴⁰ .

Более поздние разработки [ править ]

KangarooTwelve [ править ]

В 2016 году та же команда, которая разработала функции SHA-3 и алгоритм Keccak, представила альтернативы более быстрых сокращенных раундов (уменьшенных до 12 и 14 раундов по сравнению с 24 в SHA-3), которые могут использовать доступность параллельного выполнения из-за использования дерева хеширование: KangarooTwelve и MarsupilamiFourteen. ^[46]

В отношении параллелизма эти функции отличаются от ParallelHash, стандартизированной параллелизируемой хеш-функции на основе FIPS на основе Keccak, тем, что они быстрее, чем ParallelHash, для сообщений небольшого размера.

Уменьшение количества раундов оправдано огромными криптоаналитическими усилиями, сосредоточенными на Keccak, которые не привели к практическим атакам на что-либо близкое к Keccak с двенадцатью раундами. Эти высокоскоростные алгоритмы не являются частью SHA-3 (поскольку они являются более поздней разработкой) и, следовательно, не совместимы с FIPS; но поскольку они используют ту же перестановку Keccak, они безопасны до тех пор, пока нет атак на SHA-3, сокращенных до 12 раундов. ^[46]

KangarooTwelve - это высокопроизводительная версия Keccak с сокращенным циклом (от 24 до 12 раундов), которая утверждает, что имеет 128 бит безопасности ^[47], а производительность составляет 0,55 цикла на байт на процессоре Skylake . ^[48] Этот алгоритм является черновиком IETF RFC . ^[49]

MarsupilamiFourteen, небольшая вариация на KangarooTwelve, использует 14 раундов перестановки Keccak и требует 256 бит безопасности. Обратите внимание, что 256-битная безопасность не более полезна на практике, чем 128-битная безопасность, но может потребоваться по некоторым стандартам. ^[47] 128 бит уже достаточно, чтобы отразить атаки грубой силы на текущее оборудование, поэтому наличие 256-битной защиты не добавляет практической ценности, если пользователь не беспокоится о значительном улучшении скорости классических компьютеров. Информацию о сопротивлении квантовым компьютерам см. Ниже.

KangarooTwelve и MarsupilamiFourteen - это функции расширяемого вывода, аналогичные SHAKE, поэтому они генерируют тесно связанный вывод для общего сообщения с разной длиной вывода (более длинный вывод является расширением более короткого вывода). Такое свойство не проявляется в хэш-функциях, таких как SHA-3 или ParallelHash (кроме вариантов XOF). ^[5]

Строительство Фарфалле [ править ]

В 2016 году команда Keccak выпустила другую конструкцию, названную конструкцией Farfalle, и Kravatte, экземпляр Farfalle, использующий перестановку Keccak-p ^[50], а также два аутентифицированных алгоритма шифрования Kravatte-SANE и Kravatte-SANSE ^[51]

Хеширование дерева сакуры [ править ]

RawSHAKE - это основа кода Sakura для хеширования дерева, которая еще не стандартизирована. Сакура использует суффикс 1111 для отдельных узлов, что эквивалентно SHAKE, и другие сгенерированные суффиксы в зависимости от формы дерева. ^{[43] : 16}

Защита от квантовых атак [ править ]

Существует общий результат ( алгоритм Гровера ), в котором квантовые компьютеры могут выполнять атаку структурированного прообраза, в то время как классическая атака грубой силы требует 2 ^d . Атака структурированного прообраза подразумевает атаку второго прообраза ^[27] и, следовательно, атаку столкновения . Квантовый компьютер также может выполнять атаку по случаю дня рождения , таким образом нарушая сопротивление столкновениям в ^[52] (хотя это оспаривается ^[53] ). Учитывая, что максимальная сила может быть , это дает следующие верхние ^[54] границы квантовой безопасности SHA-3:${\displaystyle {\sqrt {2^{d}}}=2^{d/2}}$${\displaystyle {\sqrt[{3}]{2^{d}}}=2^{d/3}}$${\displaystyle c/2}$

Было показано, что конструкция Меркла-Дамгарда, используемая в SHA-2, разрушается и, как следствие, устойчива к квантовым столкновениям ^[55], но для конструкции губки, используемой в SHA-3, авторы предоставляют доказательства только для случай, когда блочная функция f не является эффективно обратимой; Keccak-f [1600], однако, эффективно обратим, и поэтому их доказательство неприменимо. ^[56]

Примеры вариантов SHA-3 [ править ]

Следующие хеш-значения взяты с сайта NIST.gov: ^[57]

SHA3-224 ("")6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7SHA3-256 ("")a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434aSHA3-384 ("")0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004SHA3-512 ("")a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26SHAKE128 ("", 256)7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26SHAKE256 ("", 512)46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be

Изменение одного бита приводит к тому, что каждый бит на выходе изменяется с вероятностью 50%, демонстрируя лавинный эффект :

SHAKE128 («Быстрая коричневая лисица перепрыгивает через ленивого пса», 256)f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66eSHAKE128 («Быстрая коричневая лиса перепрыгивает через ленивого до ф », 256)853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c

Сравнение функций SHA [ править ]

В таблице ниже внутреннее состояние означает количество битов, которые переносятся в следующий блок.

Оптимизированная реализация с использованием AVX-512VL (то есть из OpenSSL , работающего на процессорах Skylake-X ) SHA3-256 действительно достигает примерно 6,4 цикла на байт для больших сообщений ^[63] и около 7,8 цикла на байт при использовании AVX2 на процессорах Skylake . ^[64] Производительность на других процессорах x86, Power и ARM в зависимости от используемых инструкций, а точная модель процессора варьируется от 8 до 15 циклов на байт ^[65] , ^{[66] [67]} с некоторыми более старыми процессорами x86 до 25-40 циклов на байт. ^[68]

Реализации [ править ]

Ниже приведен список библиотек криптографии, поддерживающих SHA-3:

• Русте SHA-3
• Ботан
• Надувной Замок
• Крипто ++
• Libgcrypt
• Крапива
• OpenSSL
• wolfSSL
• MIRACL Cryptographic SDK
• Golang's x / crypto / sha3

Аппаратное ускорение [ править ]

Шестиядерные процессорные ядра SoC Apple A13 ARMv8 поддерживают ^[69] ускорение SHA-3 (и SHA-512) с использованием специализированных инструкций (EOR3, RAX1, XAR, BCAX) из набора криптографических расширений ARMv8.2-SHA. ^[70]

Некоторые программные библиотеки используют средства векторизации ЦП для ускорения использования SHA-3. Например, Crypto ++ может использовать SSE2 на x86 для ускорения SHA3 ^[71], а OpenSSL может также использовать MMX , AVX-512 или AVX-512VL на многих системах x86. ^[72] Также процессоры POWER8 реализуют 2x64-битное вращение вектора, определенное в PowerISA 2.07, что может каким-то образом ускорить реализацию SHA-3. ^{[73] В} большинстве реализаций для ARM не используются векторные инструкции Neon, поскольку они медленнее, чем скалярный код , однако его можно ускорить с помощью SVE.и векторные инструкции SVE2 (например, на процессоре Fujitsu A64FX ). ^[74]

Использование в протоколах [ править ]

• Эфириум § Эфир

См. Также [ править ]

• Ethash - еще один хеш на основе Keccak

Ссылки [ править ]

Внешние ссылки [ править ]

• Веб-сайт Keccak