SHA-3

редактировать

набор криптографических хеш-функций

[Хеш-алгоритмы]
Основные понятия
хэш-функции ·SHA ·DSA
Основные стандарты
SHA-0 ·SHA-1 ·SHA-2 ·SHA-3

SHA-3. (Keccak)
Общие
Дизайнеры	Гвидо Бертони, Джоан Дэмен, Микаэль Петерс и Жиль Ван Аше.
Впервые опубликовано	2015
Серия	(SHA -0 ), SHA-1, SHA-2, SHA-3
Сертификация	FIPS PUB 202
Подробности
Размеры дайджеста	произвольно
Структура	конструкция губки
Скорость	12,6 cpb на типичной машине на базе x86-64 для Keccak-f [1600] plus XORing 1024 бита, что примерно соответствует SHA2-256.
Лучший публичный криптоанализ
Атака по прообразу на Keccak-512 сокращена до 8 раундов, требуя 2 времени и 2 памяти. Различители с нулевой суммой существуют для полного 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 (или ), разработанный Джоан Дэемен, Микаэль Петерс и Жиль Ван Аше, основанный на RadioGatún. Авторы Кеккака предложили дополнительные варианты использования функции, которая (пока) не стандартизована NIST, включая потоковый шифр , аутентифицированную систему шифрования, схему хеширования «дерево» для более быстрого хеширования на определенные архитектуры и AEAD шифры Keyak и Ketje.

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

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

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

Содержание

1 История
2 Дизайн
3 Заполнение
4 Перестановка блоков
5 Скорость
6 Экземпляры
7 Дополнительные экземпляры
8 Более поздние разработки
- 8.1 Хеширование дерева
- 8.2 Конструкция Фарфалла
9 Защита от квантовых атак
10 Споры об изменении емкости
11 Примеры вариантов SHA-3
12 Сравнение функций SHA
13 Реализации
14 Аппаратное ускорение
15 Использование в протоколах
16 См. Также
17 Ссылки
18 Внешние ссылки

История

Алгоритм Keccak - это работа Гвидо Бертони, Джоан Дэемен (которая также участвовала в разработке шифра Rijndael с Винсентом Рейменом ), Майклом Питерсом и Жилем Ван Аше. Он основан на более ранних разработках хэш-функций PANAMA и 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 алгоритмов. Keccak прошел в последний раунд в декабре 2010 года.

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

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

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

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

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

Дизайн

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

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

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

дополняет вход N используя функцию заполнения, в результате получается дополненная битовая строка P с длиной, кратной $r {\ displaystyle r}$ $р$ (так, что $n = len (P) / r {\ displaystyle n = {\ text {len}} (P) / r}$ ${\ displaystyle n = {\ text {len}} (P) / r}$ является целым числом)
разбить 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 использует шаблон 101 в своей функции заполнения: 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] будет битом (5i + j) × w + k ввода, используя соглашение о нумерации битов little-endian и мажор строки индексация. Т.е. i выбирает строку, j столбец и k бит.

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

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

θ (тета): Вычислить четность каждого из 5w (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])
ρ (rho): Побитовое вращение каждого из 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], where $(ij) = (3 2 1 0) T (0 1) {\ Displaystyle {\ begin {pmatrix} я \\ j \ end {pmatrix}} = {\ begin {pmatrix} 3 2 \\ 1 0 \ end {pmatrix}} ^ {t} {\ begin { pmatrix} 0 \\ 1 \ end {pmatrix}}}$ ${\ begin {pmatrix} i \\ j \ end {pmatrix}} = {\ begin {pmatrix} 3 2 \\ 1 0 \ end {pmatrix}} ^ {t} {\ begin {pmatrix} 0 \\ 1 \ end {pmatrix}}$ .
π (pi): Перестановка 25 слов в фиксированном шаблоне. a [3i + 2j] [i] ← a [i] [j].
χ (chi): Побитовое объединение по строкам, используя x ← x ⊕ (¬y z). Чтобы быть точным, a [i] [j] [k] ← a [i] [j] [k] ⊕ (¬a [i] [j + 1] [k] a [i] [j + 2] » [k]). Это единственная нелинейная операция в SHA-3.
ι (iota): Исключающая - или округление константы в одно слово состояния. Чтобы быть точным, в раунде n для 0 ≤ m ≤ a [0] [0] [2-1] подвергается операции XOR с битом m + 7n последовательности степени 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 подвергался критике за то, что он медленный на архитектурах набора команд (CPU), которые не имеют инструкций, специально предназначенных для более быстрого вычисления функций 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 и Архитектуры IBM s390x уже (по состоянию на 2018 год) включают специальные инструкции, которые позволяют алгоритмам Keccak выполняться быстрее.

Экземпляры

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

Экземпляр	Вывод. размер d	Скорость r. = размер блока	Емкость c	Определение	Степень защиты в битах
Экземпляр	Вывод. размер d	Скорость r. = размер блока	Емкость c	Определение	Коллизия	Прообраз	2-й прообраз
SHA3-224(M)	224	1152	448	Keccak [448] (M \|\| 01, 224)	112	224	224
SHA3-256(M)	256	1088	512	Keccak [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	Keccak [1024] (M \|\| 01, 512)	256	512	512
SHAKE128 (M, d)	d	1344	256	Keccak [256] (M \|\| 1111, d)	min (d / 2,128)	≥min (d, 128)	min ( d, 128)
SHAKE256 (M, d)	d	1088	512	Кечак [512] (M \|\| 1111, d)	min (d / 2,256)	≥min (d, 256)	min (d, 256)

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

Keccak [c] (N, d) = губка [Keccak-f [1600], pad101, 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 бит.

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

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

RawSHAKE - это основа кода Sakura для хеширования дерева, которая еще не стандартизирована. Однако суффикс SHAKE был тщательно выбран, чтобы он был совместим с Сакурой. Сакура добавляет 0 для скачка цепочки или 1 для сообщения, затем 100 для нефинального (внутреннего) узла или 1 для конечного узла, прежде чем применить RawSHAKE. Последовательное хеширование соответствует дереву переходов с одним узлом сообщения, что означает, что 11 добавляется к сообщению до применения RawSHAKE. Таким образом, SHAKE XOF добавляют 1111 к сообщению, т. Е. 1 для сообщения, 1 для конечного узла и 11 для суффикса разделения домена RawSHAKE.

Поскольку заполнение 101 всегда добавляет как минимум два бита в байтах: В выровненных библиотеках всегда есть шесть неиспользуемых нулевых битов. Поэтому эти добавленные дополнительные биты никогда не увеличивают длину дополненного сообщения.

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

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

Экземпляр	Описание
cSHAKE128 (X, L, N, S)	Версия SHAKE, поддерживающая явное разделение доменов с помощью параметров настройки.
cSHAKE256 (X, L, N, S)
KMAC128 (K, X, L, S)	A хэш-функция с ключом на основе Keccak. Также может использоваться без ключа как обычная хеш-функция.
KMAC256 (K, X, L, S)
KMACXOF128 (K, X, L, S)
KMACXOF256 (K, X, L, S)
TupleHash128 (X, L, S)	Функция для хеширования кортежей строк. Вывод этой функции зависит как от содержимого, так и от последовательности входных строк.
TupleHasdiv class="ht"56 (X, L, S)
TupleHashXOF128 (X, L, S)
TupleHashXOF256 (X, L, S)
ParallelHash128 (X, B, L, S)	Функция, разработанная для использования параллелизма в современных процессорах для более быстрого хеширования. В отличие от KangarooTwelve, не использует Keccak с уменьшенным количеством раундов.
ParallelHasdiv class="ht"56 (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.

Более поздние разработки

Хеширование дерева

В 2016 году та же команда, которая разработала функции SHA-3 и алгоритм Кеккака, представила более быстрые сокращенные - альтернативы раундов (сокращено до 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 выпустила другую конструкцию под названием, и Kravatte, экземпляр Farfalle, использующий перестановку Keccak-p., А также два аутентифицированных алгоритма шифрования Kravatte-SANE и Kravatte-SANSE

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

Общий результат ( алгоритм Гровера ), что квантовые компьютеры могут выполнять структурированную атаку по прообразу за $2 d = 2 d / 2 {\ displaystyle {\ sqrt {2 ^ {d}}} = 2 ^ {d / 2}}$ ${\ displaystyle {\ sqrt {2 ^ {d}}} = 2 ^ {d / 2}}$ , тогда как классическая атака грубой силой требует 2. Атака структурированного прообраза подразумевает вторую атаку прообраза и, следовательно, атаку коллизии. Квантовый компьютер также может выполнить атаку дня рождения, таким образом нарушив сопротивление столкновениям в $2 d 3 = 2 d / 3 {\ displaystyle {\ sqrt [{3}] {2 ^ {d} }} = 2 ^ {d / 3}}$ ${\ displaystyle {\ sqrt [{3}] {2 ^ {d}}} = 2 ^ {d / 3}}$ (хотя это оспаривается). Учитывая, что максимальная сила может быть $c / 2 {\ displaystyle c / 2}$ $c / 2$ , это дает следующие верхние границы квантовой безопасности 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)	min (d / 3,128)	min (d / 2,128)	≥min (d / 2,128)	min (d / 2,128)
SHAKE256 (M, d)	мин (d / 3,256)	мин (d / 2,256)	≥min (d / 2,256)	мин (d / 2,256)

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

Споры об изменении емкости

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

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

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

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

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

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

В ответ на возникшие противоречия в ноябре 2013 года Джон Келси из NIST предложил вернуться к исходному предложению c = 2d для всех экземпляров drop-in замены SHA-2. Возврат был подтвержден в апрельском проекте 2014 года. Это предложение было реализовано в стандарте окончательной версии в августе 2015 года.

Формы с уменьшенной емкостью были опубликованы как SHAKE128 и SHAKE256, где число указывает уровень безопасности, а количество битов вывода является переменным, но должно быть вдвое больше требуемого сопротивления столкновению.

Примеры ША-3-х вариантах

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

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

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

SHAKE128 («Быстрая коричневая лисица перепрыгивает через ленивого пса», 256) f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0E3e866e SHAKE («Быстрая коричневая лиса перепрыгивает через ленивую глубину резкости», 256) 853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c

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

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

Сравнение функций SHA
view
talk
Алгоритм и вариант		Размер вывода. (биты)	Размер внутреннего состояния. (биты)	Размер блока. (биты)	Округляет	Операции	Безопасность (в битах) против коллизионных атак	Емкость. против атак с расширением длины	Производительность на Skylake (медиана cpb )		Первые опубликованные
Алгоритм и вариант		Размер вывода. (биты)	Размер внутреннего состояния. (биты)	Размер блока. (биты)	Округляет	Операции	Безопасность (в битах) против коллизионных атак	Емкость. против атак с расширением длины	длинные сообщения	8 байтов	Первые опубликованные
MD5 (в качестве ссылки)		128	128. (4 × 32)	512	64	And, Xor, Rot, Add (mod 2), Или	≤18. (обнаружены коллизии)	0	4,99	55,00	1992
SHA-0		160	160. (5 × 32)	512	80	And, Xor, Rot, Add (mod 2) или	<34. (обнаружены коллизии)	0	≈ SHA-1	≈ SHA-1	1993
SHA-1		160	160. (5 × 32)	512	80	And, Xor, Rot, Add (mod 2) или	<63. (обнаружены коллизии)	0	3,47	52,00	1995
SHA-2	SHA-224. SHA-256	224. 256	256. (8 × 32)	512	64	And, Xor, Rot, Add (mod 2), 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), Or, Shr	192. 256	128 (≤ 384). 0	5,12. 5,06	135,75. 135,50	2001
	SHA -512/224. SHA-512/256	224. 256	512. (8 × 64)	1024	80	And, Xor, Rot, Add (mod 2), Or, Shr	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	And, 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
SHA-3	SHAKE128. SHAKE256	d (произвольно). d (произвольно)	1600. (5 × 5 × 64)	1344. 1088	24	And, Xor, Rot, Not	мин (d / 2, 128). мин (d / 2, 256)	256. 512	7,08. 8,59	155,25. 155,50	2015

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

Реализации

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

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

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

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

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

Ethereum § Ether

См. также

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

Ссылки

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

Веб-сайт Keccak