ША-3

Безопасные алгоритмы хеширования
Концепции
хэш-функции , SHA , DSA
Основные стандарты
ША-0 , ША-1 , ША-2 , ША-3

ША-3
(Кечак)

Общий
Дизайнеры	Гвидо Бертони, Джоан Демен , Микаэль Питерс и Жиль ван Аш .
Впервые опубликовано	2016 ( 2016 )
Ряд	( ША-0 ), ША-1 , ША-2 , ША-3
Сертификация	ФИПС ПАБ 202
Деталь
Размеры дайджеста	произвольный
Структура	губка строительство
Скорость	12,6 cpb на типичной машине с процессором x86-64 для Keccak-f[1600] плюс XOR 1024 бит, что примерно соответствует SHA2-256.
Лучший публичный криптоанализ
Прообраз атаки на Кечак-512 уменьшен до 8 выстрелов, требуется 2 511.5 время и 2 508 память. Различители с нулевой суммой существуют для полного 24-раундового Keccak-f[1600], хотя их нельзя использовать для атаки на саму хэш-функцию.

SHA-3 ( алгоритм безопасного хеширования 3 ) является новейшим член семейства стандартов Secure Hash Algorithm , выпущенных NIST 5 августа 2015 г. Хотя SHA-3 входит в одну и ту же серию стандартов, он внутренне отличается от MD5 -подобной структуры SHA -1 и SHA-2 .

SHA-3 — это подмножество более широкого семейства криптографических примитивов Keccak ( / ˈ k ɛ tʃ æ k / или / ˈ k ɛ tʃ ɑː k / ), Разработан Гвидо Бертони , Джоан Демен , Микаэлем Петерсом и Жилем Ван Аше на основе RadioGatún . Авторы Кечака предложили дополнительные варианты использования этой функции, (пока) не стандартизированные NIST, включая поточный шифр , систему шифрования с аутентификацией , схему хеширования «дерево» для более быстрого хеширования на определенных архитектурах. а AEAD шифрует Кейака и Кетье.

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

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

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

История

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

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

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

Во время конкурса участникам разрешалось «настраивать» свои алгоритмы для решения обнаруженных проблем. Изменения, внесенные в Кечак:

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

2 октября 2012 года Кечак был признан победителем конкурса.

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

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

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

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

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

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

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

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

Позже он отказался от своего предыдущего заявления, заявив:

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

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

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

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

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

Дизайн

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

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

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

• дополните вход N с помощью функции Pad, получив дополненную битовую строку P с длиной, кратной $r$ (такой, что $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 также определен для меньших размеров слов степени 2 w до 1 бита (общее состояние 25 бит). Небольшие размеры состояний можно использовать для тестирования криптоаналитических атак, а промежуточные размеры состояний (от w = 8 200 бит до w = 32 800 бит) можно использовать в практических и легких приложениях.

Для экземпляров 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 . В этом случае к сообщению добавляется еще один блок, содержащий 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 [ i ][ j ][ k ] ← a [ i ][ j ][ k −( t +1)( t +2)/2] , где ${\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 ≤ ℓ , a [0][0][2 ^м −1] подвергается операции XOR с битом m + 7 n 8-й степени последовательности LFSR . Это нарушает симметрию, сохраняемую на других этапах.

Скорость

Скорость хеширования SHA-3 длинных сообщений определяется вычислением f = Keccak-f[1600] и выполнением операции XOR S с расширенным Pi _— операцией над 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] плюс XOR 1024 бит: что примерно соответствует SHA3-256:

• 57,4 cpb на IA-32, Intel Pentium 3
• 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 cb на ИА-64

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

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

По состоянию на 2018 год ARMv8 от ARM и архитектуры IBM s390x включают специальные инструкции, которые позволяют алгоритмам Keccak выполняться быстрее. Также были предложения по расширению RISC-V для добавления инструкций, специфичных для Keccak.

Экземпляры

Стандарт NIST определяет следующие экземпляры для сообщения M и длины вывода d :

Пример	Выход размер д	Оценить р = размер блока	Емкость c	Определение	Сила безопасности в битах сопротивления
					Столкновение	Прообраз	2-й прообраз
SHA3-224( М )	224	1152	448	Кечак[448]( М || 01, 224)	112	224	224
SHA3-256( М )	256	1088	512	Кечак[512]( М || 01, 256)	128	256	256
SHA3-384( М )	384	832	768	Кечак[768]( М || 01, 384)	192	384	384
SHA3-512( М )	512	576	1024	Кечак[1024]( М || 01, 512)	256	512	512
ВСтряска128( М , д )	д	1344	256	Кечак[256]( М || 1111, д )	мин( д /2,128)	≥мин( д ,128)	мин( д ,128)
ВСтряска256( М , д )	д	1088	512	Кечак[512]( М || 1111, д )	мин( д /2,256)	≥мин( д ,256)	мин( д ,256)

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

• Keccak[ c ]( N , d ) = губка[Keccak-f[1600], площадку10 ^* 1, р ]( Н , д )
• Кечак-f[1600] = Кечак-p[1600, 24]
• c - емкость
• r — ставка = 1600 − c
• N — входная битовая строка

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

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

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

Суффикс	Значение
...0	зарезервировано для будущего использования
01	ША-3
...11	RawSHAKE
1111	встряхнуть

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

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

Пример	Описание
cSHAKE128( Икс , Л , Н , С )	Версия SHAKE, поддерживающая явное разделение доменов с помощью параметров настройки.
cSHAKE256( Икс , Л , Н , С )
KMAC128( К , Икс , Л , С )	Ключевая хеш-функция, основанная на Keccak. Также может использоваться без ключа как обычная хэш-функция.
KMAC256( К , Икс , Л , С )
KMACXOF128( К , Икс , Л , С )
KMACXOF256( К , Икс , Л , С )
TupleHash128( X , L , S )	Функция для хеширования кортежей строк. Выходные данные этой функции зависят как от содержимого, так и от последовательности входных строк.
TupleHash256( X , L , S )
TupleHashXOF128( X , L , S )
ТуплеХашXOF256( X , L , S )
Параллельный хэш128( X , B , L , S )	Функция, предназначенная для использования параллелизма в современных процессорах для более быстрого хеширования. В отличие от KangarooTwelve, не использует Кечак с уменьшенным раундом.
ParallelHash256( X , B , L , S )
ParallelHashXOF128(ParallelHashXOF128 , B, L, (
ПараллельныйХэшXOF256( X , B , L , S )

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

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

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

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

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

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

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

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

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

Общий
Дизайнеры	Гвидо Бертони, Жоан Дэмен , Михаэль Питерс, Жиль Ван Аш , Ронни Ван Кир, Бенуа Вигье
Впервые опубликовано	10 августа 2016 г ( 10.08.2016 )
Получено из	Кечак
Деталь
Размеры дайджеста	произвольный
Структура	построение губки и перемешивание деревьев с помощью прыжков кенгуру
Раунды	12
Скорость	0,51 cpb на SkylakeX с AVX-512
Лучший публичный криптоанализ
То же, что и у Кечака

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

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

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

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

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

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

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

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

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

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

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

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

Пример	Сила безопасности в битах сопротивления
	Столкновение (Брассар и др.)	Столкновение (Бернштейн)	Прообраз	2-й прообраз
SHA3-224( М )	74 2 ⁄ 3	112	112	112
SHA3-256( М )	85 1 ⁄ 3	128	128	128
SHA3-384( М )	128	192	192	192
SHA3-512( М )	170 2 ⁄ 3	256	256	256
ВСтряска128( М , д )	мин( д /3,128)	мин( д /2,128)	≥мин( д /2,128)	мин( д /2,128)
ВСтряска256( М , д )	мин( д /3,256)	мин( д /2,256)	≥мин( д /2,256)	мин( д /2,256)

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

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

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

SHA3-224("")
6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7
SHA3-256("")
a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a
SHA3-384("")
0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004
SHA3-512("")
a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26
SHAKE128("", 256)
7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26
SHAKE256("", 512)
46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be

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

SHAKE128("The quick brown fox jumps over the lazy dog", 256)
f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e
SHAKE128("The quick brown fox jumps over the lazy dof", 256)
853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c

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

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

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

Алгоритм и вариант		Выходной размер (биты)	Внутренний размер штата (биты)	Размер блока (биты)	Раунды	Операции	Защита от столкновений (биты)	Защита от атак расширения длины (биты)	Производительность на Skylake (медиана cpb )		Впервые опубликовано
									Длинные сообщения	8 байт
MD5 (для справки)		128	128 (4 × 32)	512	4 (16 операций в каждом раунде)	И, Xor, Or, Rot, Add (мод 2 32 )	≤ 18 (обнаружены столкновения)	0	4.99	55.00	1992
ША-0		160	160 (5 × 32)	512	80	И, Xor, Or, Rot, Add (мод 2 32 )	< 34 (обнаружены столкновения)	0	≈ ША-1	≈ ША-1	1993
ША-1							< 63 (обнаружены столкновения)		3.47	52.00	1995
ША-2	ША-224 ША-256	224 256	256 (8 × 32)	512	64	И, Ксор, Или, Рот, Шр, Адд (мод 2 32 )	112 128	32 0	7.62 7.63	84.50 85.25	2004 2001
	ША-384	384	512 (8 × 64)	1024	80	И, Ксор, Или, Рот, Шр, Адд (мод 2 64 )	192	128	5.12	135.75	2001
	ША-512	512					256	0	5.06	135.50	2001
	ША-512/224 ША-512/256	224 256					112 128	288 256	≈ ША-384	≈ ША-384	2012
ША-3	SHA3-224 SHA3-256 SHA3-384 SHA3-512	224 256 384 512	1600 (5 × 5 × 64)	1152 1088 832 576	24	И, Ксор, Гниль, Не	112 128 192 256	448 512 768 1024	8.12 8.59 11.06 15.88	154.25 155.50 164.00 164.00	2015
	SHAKE128 SHAKE256	д (произвольно) д (произвольно)		1344 1088			мин( д /2, 128) мин( д /2, 256)	256 512	7.08 8.59	155.25 155.50

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

Реализации

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

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

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

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

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

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

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

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

См. также

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

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

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