ША-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 ( / ˈ k ɛ tʃ æ k / или / ˈ k ɛ tʃ ɑː k / ), ^{[7] [8]} , разработанное Гвидо Бертони, Джоан Деймен , Микаэлем Питерсом, и Жиль Ван Аш , опирающийся на RadioGatun . Авторы Кечака предложили дополнительные варианты использования этой функции, (пока) не стандартизированные NIST, включая поточный шифр , систему шифрования с аутентификацией , схему «дерева» хеширования для более быстрого хеширования на определенных архитектурах, ^{[9] [10]} и шифры AEAD . Кейак и Кетье. ^{[11] [12]}

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

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

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

История

Алгоритм Кеккак — это работа Гвидо Бертони, Джоан Демен (которая также разработала шифр Рейндала совместно с Винсентом Рейменом ), Микаэля Петерса и Жиля Ван Аша . Он основан на более ранних разработках хэш-функций PANAMA и RadioGatún . PANAMA была разработана Дэменом и Крейгом Клэппом в 1998 году. RadioGatún, преемник PANAMA, был разработан Дэменом, Петерсом и Ван Ашем и был представлен на семинаре NIST Hash Workshop в 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 года ^.

Во время конкурса участникам разрешалось «настраивать» свои алгоритмы для решения обнаруженных проблем. Изменения, внесенные в Кечак: ^{[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. Это означает, что d -битный выход должен иметь d /2-битную устойчивость к атакам коллизий и d -битную устойчивость к атакам на прообразы , максимум, достижимый для d бит вывода. Доказательство безопасности 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 внес в алгоритм «внутренние изменения». Это было неряшливо с моей стороны. Перестановка Кечака остается неизменной. NIST предложил уменьшить мощность хеш-функции во имя производительности. Одной из приятных особенностей Keccak является то, что он легко настраивается. ^[32]

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

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

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

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

Дизайн

Конструкция губки для хэш-функций. P _i — входные данные, Z _i — хешированные выходные данные. Неиспользованная «емкость» c должна быть в два раза больше желаемой устойчивости к коллизиям или атакам прообразов .

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

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

• дополните вход N с помощью функции Pad, получив дополненную битовую строку 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 состоит из массива w -битных слов размером 5 × 5 (с w = 64), b = 5 × 5 × w = 5 × 5 × 64 = всего 1600 бит. Keccak также определен для меньших размеров слов степени 2 w до 1 бита (общее состояние 25 бит). Небольшие размеры состояний можно использовать для тестирования криптоаналитических атак, а промежуточные размеры состояний (от w = 8 200 бит до w = 32 800 бит) можно использовать в практических и легких приложениях. ^{[11] [12]}

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

Заполнение

Чтобы гарантировать, что сообщение может быть равномерно разделено на блоки 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 входных данных, используя соглашение о нумерации битов с прямым порядком байтов и индексацию по строкам . Т.е. i выбирает строку, 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 [ я ][  j ][ k ] ← a [ я ][  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 слов по фиксированному шаблону. а [3 я +2 j ][ я ] ← а [  я ][ j ] .

х (чи)

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

ι (йота)

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

Скорость

Скорость хеширования SHA-3 длинных сообщений определяется вычислением f = Keccak-f[1600] и выполнением операции XOR S с расширенным Pi _— операцией над b = 1600 бит. Однако, поскольку последние c бит расширенного Pi в любом случае равны 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 ), тем менее эффективным, но более безопасным становится хеширование, поскольку перед каждым применение вычислительно затратного f . Авторы сообщают о следующих скоростях программных реализаций Keccak-f[1600] плюс XOR 1024 бита, ^[1] что примерно соответствует SHA3-256:

• 57,4 cpb на 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 ЦПБ на типичной машине с процессором x86-64
• 6–7 cpb на ИА-64 ^[1]

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

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

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

Экземпляры

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

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

• Keccak[ c ]( N , d ) = губка[Keccak-f[1600], площадку10 ^* 1, r ]( N , d ) ^{[5] : 20}
• Кечак-f[1600] = Кечак-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 бит. ^[5]

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

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

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

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

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

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

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

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

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

Более поздние события

КенгуруДвенадцать

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

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

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

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

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

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

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

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

Хеширование дерева сакуры

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

Защита от квантовых атак

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

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

Примеры вариантов SHA-3

Следующие значения хеш-функции взяты из NIST.gov: ^[56]

SHA3-224("")6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7SHA3-256("")a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434aSHA3-384("")0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004SHA3-512("")a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26ВСтряска128("", 256)7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26ВСтряска256("", 512)46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be

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

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

Сравнение функций SHA

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

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

Реализации

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

• Ша3 Раста
• Ботан
• Надувной замок
• Крипто++
• Libgcrypt
• Крапива
• OpenSSL
• волкSSL
• Криптографический SDK MIRACL
• x/crypto/sha3 Голанга
• libkeccak

Аппаратное ускорение

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

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

IBM z/Architecture поддерживает SHA-3 с 2017 года как часть расширения Message-Security-Assist Extension 6. ^[74] Процессоры поддерживают полную реализацию всех алгоритмов SHA-3 и SHAKE с помощью инструкций KIMD и KLMD с использованием аппаратного обеспечения. Вспомогательный двигатель встроен в каждое ядро.

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

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

Смотрите также

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

Рекомендации

1. Бертони, Гвидо; Дэмен, Джоан ; Питерс, Майкл; ван Аш, Жиль (29 мая 2012 г.). «Обзор реализации Keccak» (PDF) . п. 25 . Проверено 27 марта 2023 г.
2. Моравецкий, Павел; Пепшик, Йозеф; Сребрный, Мариан (2013). «Ротационный криптоанализ Кечака с уменьшенным раундом» (PDF) . В Мориай, С. (ред.). Быстрое программное шифрование . Конспекты лекций по быстрому программному шифрованию по информатике. Том. 8424. стр. 241–262. дои : 10.1007/978-3-662-43933-3_13. ISBN 978-3-662-43932-6. Архивировано (PDF) из оригинала 8 января 2013 г. Проверено 8 февраля 2019 г.
3. Бертони, Гвидо; Дэмен, Джоан; Питерс, Майкл; ван Аш, Джайлз (14 января 2011 г.). «Представление Keccak SHA-3» (PDF) . keccak.team . Архивировано (PDF) из оригинала 19 августа 2011 г. Проверено 27 марта 2023 г.
4. «Хеш-функции». НИСТ . 22 июня 2020 г. Проверено 17 февраля 2021 г.
5. Лаборатория информационных технологий (август 2015 г.). Стандарт SHA-3: хеширование на основе перестановок и функции расширяемого вывода (PDF) . Национальный институт стандартов и технологий . doi : 10.6028/NIST.FIPS.202. S2CID  64734386. Публикация 202 Федерального стандарта обработки информации . Проверено 29 февраля 2020 г.
6. Дворкин, Моррис Дж. (4 августа 2015 г.). «Стандарт SHA-3: хэш на основе перестановок и функции расширяемого вывода». Федеральные стандарты обработки информации (НИСТ ФИПС).
7. «NIST выбирает победителя конкурса алгоритмов безопасного хеширования (SHA-3)» . НИСТ . 2 октября 2012 года . Проверено 2 октября 2012 г.
8. Круз, Хосе RC (7 мая 2013 г.). «Кеккак: новый стандарт шифрования SHA-3». Доктор Доббс .
9. Бертони, Гвидо; Дэмен, Джоан; Питерс, Майкл; Ван Аш, Жиль. «Сводка технических характеристик Keccak» . Проверено 27 марта 2023 г.
10. Чанг, Шу-джен; Перлнер, Рэй; Берр, Уильям Э.; Сонмез Туран, Мельтем; Келси, Джон М.; Пол, Сурадьюти; Бэшем, Лоуренс Э. (ноябрь 2012 г.). Отчет третьего раунда конкурса алгоритмов криптографического хеширования SHA-3 (PDF) . doi : 10.6028/NIST.IR.7896 . Проверено 29 февраля 2020 г.Разделы 5.1.2.1 (упоминание «режим дерева»), 6.2 («другие функции», упоминание аутентифицированного шифрования) и 7 (упоминание «дополнительных возможностей» могут быть стандартизированы в будущем).
11. Бертони, Гвидо; Дэмен, Джоан; Питерс, Майкл; Ван Аш, Жиль; Ван Кир, Ронни (13 марта 2014 г.). «Представление CAESAR: Ketje v1» (PDF) . Проверено 29 февраля 2020 г.
12. Бертони, Гвидо; Дэмен, Джоан; Питерс, Майкл; Ван Аш, Жиль; Ван Кир, Ронни (13 марта 2014 г.). «Представление CAESAR: Keyak v1» (PDF) . Проверено 29 февраля 2020 г.
13. Бертони, Гвидо; Дэмен, Джоан; Питерс, Майкл; ван Аш, Джайлз. «Губка и дуплексные конструкции» . Проверено 27 марта 2023 г.
14. «Объявление запроса о выдвижении кандидатов на алгоритмы для нового семейства алгоритмов криптографического хеширования (SHA-3) [Федеральный реестр США, том 72, № 212)]» (PDF) . 2 ноября 2007 г. Архивировано (PDF) из оригинала 31 марта 2011 г. . Проверено 18 июля 2017 г.
15. Бертони, Гвидо; Дэмен, Джоан; Питерс, Майкл; Ван Аш, Жиль. «Дорога из Панамы в Кечак через РадиоГатун» (PDF) . Проверено 27 марта 2023 г.
16. KeccakReferenceAndOptimized-3.2.zip mainReference.c «Функция губки Keccak, разработанная Гвидо Бертони, Джоан Даемен, Микаэлем Питерсом и Жилем Ван Ашем. Для получения дополнительной информации, отзывов или вопросов посетите наш веб-сайт: http://keccak. noekeon.org/Implementation ^{[ постоянная неработающая ссылка ]} разработчиками, именуемыми в настоящем документе «разработчиками». Насколько это возможно по закону, разработчик отказался от всех авторских и смежных или смежных прав на исходный код в этом файле. https: //creativecommons.org/publicdomain/zero/1.0/"
17. Стивенс, Марк; Бурштейн, Эли; Карпман, Пьер; Альбертини, Анж; Марков, Ярик. «Первое столкновение для полного SHA-1» (PDF) . Проверено 23 февраля 2017 г.
18. Леран, Гаэтан; Пейрин, Томас. «SHA-1 — это руины» . Проверено 8 января 2020 г.
19. «Отдел компьютерной безопасности NIST – Конкурс алгоритмов криптографического хеширования SHA-3, ноябрь 2007 г. – октябрь 2012 г.» . 4 января 2017 г.
20. «Изменение параметров Кечака для второго раунда» . Команда Кечак . 22 сентября 2009 года. Архивировано из оригинала 13 ноября 2017 года . Проверено 29 февраля 2020 г.
21. «Упрощение правила заполнения Кечака для раунда 3» . Команда Кечак . 17 января 2011 года . Проверено 27 марта 2023 г.
22. «Стандартизация SHA-3» . НИСТ . Проверено 16 апреля 2015 г.
23. Национальный институт стандартов и технологий (5 августа 2015 г.). «Федеральные стандарты обработки информации: хеш-функции на основе перестановок, функции расширяемого вывода и т. д.» . Проверено 5 августа 2015 г.
24. «Объявление об утверждении Федерального стандарта обработки информации (FIPS) 202, Стандарт SHA-3: хеширование на основе перестановок и функции расширяемого вывода, а также пересмотр пункта о применимости FIPS 180-4, Стандарт безопасного хеширования» . 5 августа 2015 г.
25. Келси, Джон. «SHA3, Где мы были, Куда мы идем» (PDF) . Конференция ЮАР 2013.
26. Келси, Джон. «SHA3, прошлое, настоящее и будущее». ЧЭС 2013.
27. «Аннотация» (PDF) . cr.yp.to .
28. "Список рассылки хэш-форума NIST" . 4 января 2017 г.
29. "Представление Keccak SHA-3" (PDF) . 14 января 2011 года . Проверено 27 марта 2023 г.
30. «О 128-битной безопасности». 2 октября 2013 года . Проверено 27 марта 2023 г.
31. «Конкретное предложение». 2 октября 2013 года . Проверено 27 марта 2023 г.
32. «Шнайер по безопасности: Уилл Кекчак = SHA-3?».
33. «LShift: Почему я поддерживаю правительство США, ослабляющее стандарт криптографии» .
34. «Да, это Кечак!». 4 октября 2013 года . Проверено 27 марта 2023 г.
35. «Движение вперед с SHA-3» (PDF) .
36. Отдел компьютерной безопасности NIST (CSD). «Стандарт SHA-3: хэш на основе перестановок и функции расширяемого вывода» (PDF) . НИСТ.
37. «около 41 цикла на байт [...] представляет собой ускорение на 40% по сравнению с реализацией, использующей только 32-битные инструкции». По формуле получаем ${\displaystyle {\frac {1}{x}}\times 1.40={\frac {1}{41}}}$ ${\displaystyle x=57.4}$
38. Бернштейн, Дэниел Дж. (4 января 2012 г.). «Ошибки оптимизации в программном обеспечении SHA-3» (PDF) . cr.yp.to . Проверено 29 февраля 2020 г.
39. «SHA-3 медленный?». 12 июня 2017 г. Проверено 27 марта 2023 г.
40. Го, Сюй; Хуан, Синан; Нажандали, Лейла; Шаумонт, Патрик (август 2010 г.), «Справедливая и всесторонняя оценка производительности 14 реализаций ASIC SHA-3 второго раунда» (PDF) , 2-я конференция кандидатов SHA-3 NIST : 12 , получено 18 февраля 2011 г.Кечак уступает только Луффе, которая не прошла в финальный раунд.
41. Корпорация ARM, Справочное руководство по архитектуре ARM ARMv8, для профиля архитектуры ARMv8-A, документ ARM DDI 0487C.a (ID121917), https://www.arm.com
42. «Сакура: гибкое кодирование для хеширования деревьев» (PDF) . Команда Кечак . 2014 . Проверено 29 февраля 2020 г.
43. Производные функции SHA-3: cSHAKE, KMAC, TupleHash и ParallelHash. В эту статью включен текст из этого источника, который находится в открытом доступе .
44. «Показатели производительности программного обеспечения» .
45. "Команда Кечак: KangarooTwelve" . Команда Кечак.
46. «KangarooTwelve: быстрое хеширование на основе Keccak-p» (PDF) . Международная ассоциация криптологических исследований . 2016.
47. «Двенадцать слайдов Kangaroo, представленные на ACNS 2018» (PDF) . Команда Кечак.
48. "draft-irtf-cfrg-kangarootwelve-00 - KangarooTwelve" . Ietf Datatracker . IETF . Проверено 17 января 2020 г.
49. Бертони, Гвидо; Дэмен, Джоан; Хофферт, Сет; Питерс, Майкл; Ван Аш, Жиль; Ван Кир, Ронни (29 декабря 2016 г.). «Фарфалле: параллельная криптография на основе перестановок». Архив электронной печати по криптологии .
50. Гвидо Бертони; Джоан Дэмен; Сет Хофферт; Майкл Питерс; Жиль Ван Аш; Ронни Ван Кир (12 октября 2018 г.). «Аутентифицированные схемы шифрования Kravatte-SANE и Kravatte-SANSE». Архив электронной печати по криптологии .
51. Брассар, Жиль; Хойер, Питер; Тапп, Ален (1998). «Квантовый криптоанализ хэш-функций и функций без когтей». Абстрактный . Конспекты лекций по информатике. Том. 1380. стр. 163–169. arXiv : Quant-ph/9705002 . дои : 10.1007/BFb0054319. ISBN 978-3-540-64275-6. S2CID  118940551.
52. «Анализ затрат» (PDF) . cr.yp.to .
53. «Проблема столкновения» (PDF) . scottaaronson.com .
54. «Бумага» (PDF) . eprint.iacr.org . 2016.
55. «Аннотация» (PDF) . eprint.iacr.org . 2017.
56. "NIST.gov - Отдел компьютерной безопасности - Ресурсный центр компьютерной безопасности" . 29 декабря 2016 г.
57. «Таблица измерений». скамейка.cr.yp.to .
58. Тао, Се; Лю, Фаньбао; Фэн, Дэнго (2013). Быстрая атака столкновений на MD5 (PDF) . Архив криптологии ePrint (Технический отчет). МАКР .
59. Стивенс, Марк ; Бурштейн, Эли ; Карпман, Пьер; Альбертини, Анж; Марков, Ярик. Первое столкновение для полного SHA-1 (PDF) (Технический отчет). Google Исследования .
    • Марк Стивенс; Эли Бурштейн; Пьер Карпман; Анж Альбертини; Ярик Марков; Алекс Пети Бьянко; Клеман Байс (23 февраля 2017 г.). «Анонсируем первое столкновение SHA1». Блог Google по безопасности .
60. Без усечения известно полное внутреннее состояние хеш-функции, независимо от устойчивости к коллизиям. Если выходные данные усекаются, удаленную часть состояния необходимо найти и найти, прежде чем можно будет возобновить хеш-функцию, что позволит продолжить атаку.
61. "Семейство функций губки Кеккак" . Проверено 27 января 2016 г.
62. "openssl/openssl – kecak1600-avx512vl.pl". Гитхаб . Проверено 25 июня 2020 г.
63. "openssl/openssl – keccak1600-avx2.pl" . Гитхаб . Ноябрь 2021 г.
64. "openssl/openssl – keccak1600-x86_64.pl". Гитхаб . Проверено 25 июня 2020 г.
65. "openssl/openssl – keccak1600-armv8.pl" . Гитхаб . Ноябрь 2021 г.
66. "openssl/openssl – keccak1600-ppc64.pl" . Гитхаб . Проверено 25 июня 2020 г.
67. "openssl/openssl – kccak1600-mmx.pl" . Гитхаб . Проверено 25 июня 2020 г.
68. "llvm/llvm-проект - AArch64.td" . Гитхаб . Проверено 24 июня 2020 г.
69. «ARMv8 – ARM – WikiChip» . ru.wikichip.org . Проверено 24 июня 2020 г.
70. "weidai11/cryptopp". Гитхаб . Проверено 25 июня 2020 г.
71. "openssl/openssl". Гитхаб . Проверено 25 июня 2020 г.
72. "openssl/openssl". Гитхаб . Ноябрь 2021 г.
73. "apple/llvm-project – lib/Target/AArch64/AArch64SVEInstrInfo.td". Гитхаб . Проверено 25 июня 2020 г.
74. Принципы работы IBM z/Architecture, номер публикации SA22-7832. См. инструкции KIMD и KLMD в главе 7.

Внешние ссылки

• Веб-сайт Кечака
• Стандарт SHA-3