SHA-3 - SHA-3
Безопасные алгоритмы хеширования | |
---|---|
Концепции | |
хэш-функции · SHA · DSA | |
Основные стандарты | |
SHA-0 · SHA-1 · SHA-2 · SHA-3 | |
Общий | |
---|---|
Дизайнеров | Гвидо Бертони, Джоан Дэемен , Микаэль Петерс и Жиль ван Аше . |
Впервые опубликовано | 2016 |
Серии | ( SHA-0 ), SHA-1 , SHA-2 , SHA-3 |
Сертификация | FIPS PUB 202 |
Деталь | |
Размеры дайджеста | произвольный |
Состав | конструкция из губки |
Скорость | 12,6 cpb на типичной машине на базе x86-64 для Keccak-f [1600] плюс XORing 1024 бит, что примерно соответствует SHA2-256. |
Лучший публичный криптоанализ | |
Атака прообраза на Keccak-512 уменьшена до 8 раундов, требующих 2 511,5 раз и 2 508 единиц памяти. Различители с нулевой суммой существуют для полного 24-раундового Keccak-f [1600], хотя их нельзя использовать для атаки на саму хеш-функцию. |
SHA-3 ( Secure Hash Algorithm 3 ) - последний член семейства стандартов Secure Hash Algorithm , выпущенный NIST 5 августа 2015 года. Хотя SHA-3 входит в ту же серию стандартов, он внутренне отличается от MD5 - как структуры из SHA-1 и SHA-2 .
SHA-3 представляет собой подмножество более широкой криптографической примитивного семейства Keccak ( / к ɛ tʃ æ к / или / K ɛ tʃ ɑː к / ), разработанный Guido Bertoni , Joan Daemen , Michaël Peeters и Жиля Ван Assche , здание на RadioGatún . Авторы Keccak в предложили дополнительные варианты использования функции, (пока) не стандартизирован NIST, включая потоковый шифр , с проверкой подлинности шифрования системы, «дерево» хэшированием схемы для более быстрого хэширования на некоторых архитектурах, и AEAD шифры Keyak и Ketje.
Keccak основан на новом подходе, который называется « строительство губки» . Конструкция губки основана на широкой случайной функции или случайной перестановке и позволяет вводить («поглощать» в терминологии губки) любое количество данных и выводить («сжимать») любое количество данных, действуя как псевдослучайная функция в отношении все предыдущие входы. Это приводит к большой гибкости.
NIST в настоящее время не планирует отменять SHA-2 или удалять его из пересмотренного стандарта Secure Hash Standard. Назначение SHA-3 состоит в том, что он может быть напрямую заменен на SHA-2 в текущих приложениях, если это необходимо, и значительно повысить надежность общего набора инструментов алгоритмов хеширования NIST.
Создатели алгоритмов Keccak и функций SHA-3 предлагают использовать более быструю функцию KangarooTwelve с настроенными параметрами и новый режим хеширования дерева без дополнительных накладных расходов для сообщений небольшого размера.
История
Алгоритм Keccak - это работа Гвидо Бертони, Джоан Дэемен (которая также совместно с Винсентом Рейменом разработала шифр Rijndael ), Майкла Петерса и Жиля Ван Аша . Он основан на ранее хэш - функции конструкции ПАНАМА и RadioGatún . PANAMA была разработана Daemen и Craig Clapp в 1998 году. RadioGatún, преемник PANAMA, была разработана Daemen, Peeters и Van Assche и была представлена на семинаре 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 года.
Во время конкурса участникам разрешалось «настраивать» свои алгоритмы для решения обнаруженных проблем. В Keccak внесены следующие изменения:
- Количество раундов было увеличено с 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. Это означает , что д выход -битный должен иметь д / 2-битное сопротивление столкновения атак и д сопротивление битового к прообразу атак , максимально достижимого для д бит выхода. Доказательство безопасности 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 внес «внутренние изменения» в алгоритм. Это было неаккуратно с моей стороны. Перестановка Keccak остается неизменной. NIST предложил уменьшить емкость хэш-функции во имя производительности. Одной из приятных особенностей Keccak является то, что он легко настраивается.
Пол Кроули, криптограф и старший разработчик в независимой компании по разработке программного обеспечения, выразил поддержку этому решению, заявив, что Keccak должен быть настраиваемым, и нет причин для разных уровней безопасности в одном примитиве. Он также добавил:
Да, это немного обидно для конкурентов, что они потребовали определенный уровень безопасности для участников, а затем пошли опубликовать стандарт с другим. Но сейчас ничего нельзя сделать, чтобы исправить это, кроме как возобновить соревнование. Требование, чтобы они придерживались своей ошибки, никому ничего не улучшает.
Была некоторая путаница в том, что в Keccak могли быть внесены внутренние изменения, которые были прояснены исходной командой, заявив, что предложение NIST для SHA-3 является подмножеством семейства Keccak, для которого можно генерировать тестовые векторы, используя их эталонный код. представили на конкурс, и что это предложение было результатом серии обсуждений между ними и хэш-командой NIST.
В ответ на разногласия в ноябре 2013 года Джон Келси из NIST предложил вернуться к исходному предложению c = 2 d для всех экземпляров оперативной замены SHA-2. Возврат был подтвержден последующими проектами и окончательным выпуском.
Дизайн
SHA-3 использует конструкцию губки , при которой данные «впитываются» губкой, а затем результат «выдавливается». В фазе поглощения блоки сообщений подвергаются операции XOR в подмножестве состояния, которое затем преобразуется как единое целое с использованием функции перестановки . В фазе «сжатия» выходные блоки считываются из одного и того же подмножества состояния, чередующегося с функцией преобразования состояния . Размер части состояния, которая записывается и читается, называется «скоростью» (обозначается ), а размер части, которая не затрагивается вводом / выводом, называется «емкостью» (обозначается ). Емкость определяет безопасность схемы. Максимальный уровень безопасности составляет половину емкости.
Учитывая входную битовую строку , функцию заполнения, функцию перестановки, которая работает с битовыми блоками ширины , скорости и выходной длины , у нас есть емкость, а конструкция губки , дающая битовую строку длины , работает следующим образом:
- заполнить вход N с помощью функции заполнения, в результате получится заполненная битовая строка P с длиной, делимой на (например, целое число)
- разбить P на n последовательных r -битных частей P 0 , ..., 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 бит) могут использоваться в практических, легких приложениях.
Для экземпляров 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 . В этом случае к сообщению добавляется еще один блок, содержащий 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] » , где .
- π (пи)
- Переставьте 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 бит, что примерно соответствует 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 cpb на типичной машине на базе x86-64
- 6–7 cpb на IA-64
Для точного SHA3-256 на x86-64 Бернштейн измеряет 11,7–12,25 cpb в зависимости от процессора. SHA-3 критиковали за медлительность в архитектурах с набором команд (ЦП), которые не имеют инструкций, специально предназначенных для более быстрого вычисления функций Keccak - SHA2-512 более чем в два раза быстрее, чем SHA3-512, а SHA-1 более чем в три раза быстрее на процессоре Intel Skylake с тактовой частотой 3,2 ГГц. Авторы отреагировали на эту критику, предложив использовать SHAKE128 и SHAKE256 вместо SHA3-256 и SHA3-512 за счет сокращения вдвое сопротивления прообраза (но при сохранении сопротивления столкновению). При этом производительность находится на уровне SHA2-256 и SHA2-512.
Однако в аппаратных реализациях SHA-3 заметно быстрее, чем все другие финалисты, а также быстрее, чем SHA-2 и SHA-1.
Архитектуры ARMv8 ARMv8 и IBM s390x уже (по состоянию на 2018 год) включают специальные инструкции, которые позволяют алгоритмам Keccak выполняться быстрее.
Экземпляры
Стандарт NIST определяет следующие экземпляры для сообщения M и выходной длины d :
Пример | Выходной размер d |
Скорость r = размер блока |
Емкость c | Определение | Сильные стороны безопасности в битах | ||
---|---|---|---|---|---|---|---|
Столкновение | Прообраз | 2-й прообраз | |||||
SHA3-224 ( M ) | 224 | 1152 | 448 | Кечак [448] ( M || 01, 224) | 112 | 224 | 224 |
SHA3-256 ( M ) | 256 | 1088 | 512 | Кечак [512] ( M || 01, 256) | 128 | 256 | 256 |
SHA3-384 ( M ) | 384 | 832 | 768 | Кечак [768] ( M || 01, 384) | 192 | 384 | 384 |
SHA3-512 ( M ) | 512 | 576 | 1024 | Кечак [1024] ( M || 01, 512) | 256 | 512 | 512 |
SHAKE128 ( M , d ) | d | 1344 | 256 | Кечак [256] ( M || 1111, d ) | мин ( д / 2,128) | ≥мин ( д , 128) | мин ( д , 128) |
SHAKE256 ( M , d ) | d | 1088 | 512 | Кечак [512] ( M || 1111, d ) | мин ( d / 2,256) | ≥мин ( д , 256) | мин ( д , 256) |
Со следующими определениями
- Keccak [ c ] ( N , d ) = губка [Keccak-f [1600], pad10 * 1, r ] ( N , d )
- Keccak-f [1600] = Keccak-p [1600, 24]
- 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 требуют, чтобы каждый выходной бит был таким же сильным, как и последний, тогда как для других хешей требуется только, чтобы весь хеш был сильным, в то время как подмножество могло быть слабым.
Все экземпляры добавляют к сообщению некоторые биты, крайний правый из которых представляет суффикс разделения домена. Это сделано для того, чтобы гарантировать невозможность создания сообщений, которые производят один и тот же хеш-вывод для разных приложений хеш-функции Keccak. Существуют следующие суффиксы разделения домена:
Суффикс | Имея в виду |
---|---|
... 0 | зарезервировано для использования в будущем |
01 | SHA-3 |
... 11 | Сырой ШЕЙК |
1111 | Трясти |
Дополнительные экземпляры
В декабре 2016 года NIST опубликовал новый документ NIST SP.800-185, описывающий дополнительные производные от SHA-3 функции:
Пример | Описание |
---|---|
cSHAKE128 ( X , L , N , S ) | Версия SHAKE, поддерживающая явное разделение доменов с помощью параметров настройки. |
cSHAKE256 ( X , L , N , S ) | |
KMAC128 ( K , X , L , S ) | Шпонкой хэш - функции на основе Keccak. Также может использоваться без ключа как обычная хеш-функция. |
KMAC256 ( K , X , L , S ) | |
KMACXOF128 ( K , X , L , S ) | |
KMACXOF256 ( K , X , L , S ) | |
TupleHash128 ( X , L , S ) | Функция для хеширования кортежей строк. Вывод этой функции зависит как от содержимого, так и от последовательности входных строк. |
TupleHash256 ( X , L , S ) | |
TupleHashXOF128 ( X , L , S ) | |
TupleHashXOF256 ( X , L , S ) | |
ParallelHash128 ( X , B , L , S ) | Функция, разработанная для использования параллелизма в современных процессорах для более быстрого хеширования. В отличие от KangarooTwelve, не использует Keccak с уменьшенным количеством раундов. |
ParallelHash256 ( X , B , L , S ) | |
ParallelHashXOF128 ( X , B , L , S ) | |
ParallelHashXOF256 ( X , B , L , S ) |
• X - основная входная битовая строка. Он может быть любой длины, в том числе нулевой.
• L - целое число, представляющее запрошенную длину вывода в битах.
• N - битовая строка имени функции, используемая NIST для определения функций на основе cSHAKE. Когда не требуется никакой другой функции, кроме cSHAKE, N устанавливается на пустую строку.
• S - строка битов настройки. Пользователь выбирает эту строку, чтобы определить вариант функции. Если настройка не требуется, S устанавливается в пустую строку.
• K - строка ключей любой длины, включая ноль.
• B - размер блока в байтах для параллельного хеширования. Это может быть любое целое число, такое что 0 <B <2 2040 .
Более поздние разработки
КенгуруДвенадцать
Общий | |
---|---|
Дизайнеров | Гвидо Бертони, Джоан Дэмен , Микаэль Петерс, Жиль Ван Аше , Ронни Ван Кир, Бенуа Вигье |
Впервые опубликовано | 10 августа 2016 г . |
Полученный из | Кечак |
Деталь | |
Размеры дайджеста | произвольный |
Состав | строительство губки и перемешивание деревьев с прыжком кенгуру |
Раундов | 12 |
Скорость | 0,51 cpb на SkylakeX с AVX-512 |
Лучший публичный криптоанализ | |
То же, что и у Кечака |
В 2016 году та же команда, которая разработала функции SHA-3 и алгоритм Keccak, представила альтернативы более быстрых сокращенных раундов (сокращенных до 12 и 14 раундов по сравнению с 24 в SHA-3), которые могут использовать доступность параллельного выполнения из-за использования дерева. хеширование : KangarooTwelve и MarsupilamiFourteen.
В отношении параллелизма эти функции отличаются от ParallelHash, стандартизированной параллелизируемой хеш-функции на основе FIPS на основе Keccak, тем, что они быстрее, чем ParallelHash, для сообщений небольшого размера.
Уменьшение количества раундов оправдано огромными криптоаналитическими усилиями, сосредоточенными на Keccak, которые не привели к практическим атакам на что-либо близкое к Keccak с двенадцатью раундами. Эти высокоскоростные алгоритмы не являются частью 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, экземпляр Фарфалле с помощью Keccak-р перестановку, а также два с проверкой подлинности алгоритмов шифрования Kravatte-сане и Kravatte-Санса
Хеширование дерева сакуры
RawSHAKE - это основа кода Sakura для хеширования дерева, которая еще не стандартизирована. Сакура использует суффикс 1111 для отдельных узлов, что эквивалентно SHAKE, и другие сгенерированные суффиксы в зависимости от формы дерева.
Защита от квантовых атак
Существует общий результат ( алгоритм Гровера ), в котором квантовые компьютеры могут выполнять атаку структурированного прообраза, в то время как классическая атака грубой силы требует 2 d . Атака структурированного прообраза подразумевает атаку второго прообраза и, следовательно, атаку столкновения . Квантовый компьютер также может выполнять атаку по случаю дня рождения , тем самым нарушая сопротивление столкновениям (хотя это оспаривается). Учитывая, что максимальная сила может быть , это дает следующие верхние границы квантовой безопасности SHA-3:
Пример | Сильные стороны безопасности в битах | |||
---|---|---|---|---|
Столкновение (Брассард и др.) |
Столкновение (Бернштейн) |
Прообраз | 2-й прообраз | |
SHA3-224 ( M ) | 74⅔ | 112 | 112 | 112 |
SHA3-256 ( M ) | 85⅓ | 128 | 128 | 128 |
SHA3-384 ( M ) | 128 | 192 | 192 | 192 |
SHA3-512 ( M ) | 170⅔ | 256 | 256 | 256 |
SHAKE128 ( M , d ) | мин ( д / 3,128) | мин ( д / 2,128) | ≥мин ( d / 2,128) | мин ( д / 2,128) |
SHAKE256 ( M , d ) | мин ( d / 3,256) | мин ( d / 2,256) | ≥ мин ( d / 2,256) | мин ( d / 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
В таблице ниже внутреннее состояние означает количество битов, которые переносятся в следующий блок.
Алгоритм и вариант | Размер вывода (бит) |
Размер внутреннего состояния (биты) |
Размер блока (бит) |
Раундов | Операции | Защита от коллизионных атак (биты) |
Защита от атак с увеличением длины (в битах) |
Производительность на Skylake (средняя цена за клик ) | Впервые опубликовано | ||
---|---|---|---|---|---|---|---|---|---|---|---|
Длинные сообщения | 8 байт | ||||||||||
MD5 (как ссылка) | 128 | 128 (4 × 32) |
512 | 64 | And, Xor, Rot, Add (mod 2 32 ), Или | ≤ 18 (обнаружены коллизии) |
0 | 4,99 | 55.00 | 1992 г. | |
SHA-0 | 160 | 160 (5 × 32) |
512 | 80 | And, Xor, Rot, Add (mod 2 32 ), Или | <34 (обнаружены коллизии) |
0 | ≈ SHA-1 | ≈ SHA-1 | 1993 г. | |
SHA-1 | <63 (обнаружены коллизии) |
3,47 | 52,00 | 1995 г. | |||||||
SHA-2 |
SHA-224 SHA-256 |
224 256 |
256 (8 × 32) |
512 | 64 | And, Xor, Rot, Add (mod 2 32 ), Or, Shr | 112 128 |
32 0 |
7,62 7,63 |
84,50 85,25 |
2004 2001 |
SHA-384 SHA-512 |
384 512 |
512 (8 × 64) |
1024 | 80 | And, Xor, Rot, Add (mod 2 64 ), Or, Shr | 192 256 |
128 (≤ 384) 0 |
5,12 5,06 |
135,75 135,50 |
2001 г. | |
SHA-512/224 SHA-512/256 |
224 256 |
112 128 |
288 256 |
≈ SHA-384 | ≈ SHA-384 | 2012 г. | |||||
SHA-3 |
SHA3-224 SHA3-256 SHA3-384 SHA3-512 |
224 256 384 512 |
1600 (5 × 5 × 64) |
1152 1088 832 576 |
24 | И, Xor, Rot, Not | 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 |
d (произвольно) d (произвольно) |
1344 1088 |
мин ( д / 2, 128) мин ( д / 2, 256) |
256 512 |
7,08 8,59 |
155,25 155,50 |
Оптимизированная реализация с использованием AVX-512VL (то есть из OpenSSL , работающего на процессорах Skylake-X ) SHA3-256 действительно достигает примерно 6,4 цикла на байт для больших сообщений и около 7,8 цикла на байт при использовании AVX2 на процессорах Skylake . Производительность на других процессорах x86, Power и ARM в зависимости от используемых инструкций и точной модели процессора варьируется от 8 до 15 циклов на байт, с некоторыми более старыми процессорами x86 до 25-40 циклов на байт.
Реализации
Ниже приведен список библиотек криптографии, поддерживающих SHA-3:
- Русте SHA-3
- Ботан
- Надувной Замок
- Крипто ++
- Libgcrypt
- Крапива
- OpenSSL
- wolfSSL
- SDK криптографии MIRACL
- Golang's x / crypto / sha3
- libkeccak
Аппаратное ускорение
Шестиядерные процессорные ядра SoC Apple A13 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 реализация , однако , может быть ускорена с помощью СВА и SVE2 инструкции вектора; они доступны, например, в процессоре Fujitsu A64FX .
Использование в протоколах
Смотрите также
- Ethash - еще один хеш на основе Keccak