SHA-3 - SHA-3

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

SHA-3
(Кечак)

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

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

SHA-3 - это подмножество более широкого семейства криптографических примитивов. Кечак (/ˈkɛtʃæk/ или же /ˈkɛtʃɑːk/),^[6][7] разработано Гвидо Бертони, Джоан Дэмен, Микаэль Петерс и Жиль Ван Аше, опираясь на RadioGatún. Авторы Кеккака предложили дополнительные варианты использования функции, не стандартизированные (пока) в NIST, включая потоковый шифр, аутентифицированное шифрование система, "древовидная" схема хеширования для более быстрого хеширования на определенных архитектурах,^[8][9] и AEAD шифры Keyak и Ketje.^[10][11]

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

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

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

История

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

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

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

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

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

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

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

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

Дизайн

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

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

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

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

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

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

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

Прокладка

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

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

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

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

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

Блок перестановки

Преобразование блока ж, который является Keccak-f [1600] для SHA-3, представляет собой перестановку, которая использует XOR, И и НЕТ операций и разработан для простой реализации как в программном, так и в аппаратном обеспечении.

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

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

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

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

θ (тета)

Вычислить паритет каждого из 5ш (320, когда ш = 64) 5-битные столбцы и исключающее-ИЛИ на два соседних столбца в обычном шаблоне. Точнее, а[я][ j][k] ← а[я][ j][k] ⊕ четность (a [0 ... 4] [ j−1][k]) ⊕ четность (a [0 ... 4] [ j+1][k−1])

ρ (ро)

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

π (число Пи)

Переставьте 25 слов в фиксированном порядке. а[3я+2j][я] ← а[ я][j].

χ (чи)

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

ι (йота)

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

Скорость

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

• 57.4 cpb на IA-32, Intel Pentium 3^[25]
• 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^[26]

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

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

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

Экземпляры

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

Пример	Выход размер d	Ставка р = размер блока	Емкость 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)	мин (d/2,128)	≥мин (d,128)	мин (d,128)
SHAKE256 (M, d)	d	1088	512	Кечак [512] (M || 1111, d)	мин (d/2,256)	≥мин (d,256)	мин (d,256)

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

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

Обратите внимание, что добавленные постфиксы записываются как битовые строки, а не шестнадцатеричные цифры.

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

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

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

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

С 10^*1 заполнение всегда добавляет как минимум два бита, в библиотеках с байтовым выравниванием всегда есть шесть неиспользуемых нулевых битов. Следовательно, эти добавленные дополнительные биты никогда не увеличивают длину дополненного сообщения.^{[нужна цитата ]}

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

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

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

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

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

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

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

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

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

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

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

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

Общий
Дизайнеров	Гвидо Бертони, Джоан Дэмен, Микаэль Петерс, Жиль Ван Аше, Ронни Ван Кир, Бенуа Вигье
Впервые опубликовано	10 августа 2016 г.; 4 года назад (2016-08-10)
Происходит от	Кечак
Деталь
Размеры дайджеста	произвольный
Структура	конструкция из губки и перемешивание деревьев с прыжками кенгуру
Раундов	12
Скорость	0.51 cpb на SkylakeX с AVX-512[33]
Лучшая публика криптоанализ
То же, что и у Кечака

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Посмотреть
• разговаривать
• редактировать

Алгоритм и вариант		Размер вывода (биты)	Размер внутреннего состояния (биты)	Размер блока (биты)	Раундов	Операции	Безопасность (в биты) против столкновения атак	Емкость против атаки удлинения длины	Производительность на Skylake (медиана cpb )[58]		Впервые опубликовано
									длинные сообщения	8 байт
MD5 (как ссылки)		128	128 (4 × 32)	512	64	И, Xor, Rot, Добавить (мод 2^32), Или же	≤18 (обнаружены коллизии)[59]	0	4.99	55.00	1992
SHA-0		160	160 (5 × 32)	512	80	И, Xor, Rot, Добавить (мод 2^32), Или же	<34 (обнаружены коллизии)	0	≈ SHA-1	≈ SHA-1	1993
SHA-1							<63 (обнаружены коллизии)[60]		3.47	52.00	1995
SHA-2	SHA-224 SHA-256	224 256	256 (8 × 32)	512	64	И, Xor, Rot, Добавить (мод 2^32), Или, 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	И, Xor, Rot, Добавить (мод 2^64), Или, Shr	192 256	128 (≤ 384) 0[61]	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[62]	И, 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
	Встряхивание128 Встряхивание256	d (произвольный) d (произвольный)		1344 1088			мин (d/2, 128) мин (d/2, 256)	256 512	7.08 8.59	155.25 155.50

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

Реализации

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

• Ржавчины sha3
• Ботан
• Надувной Замок
• Крипто ++
• Libgcrypt
• Крапива
• OpenSSL
• LibreSSL
• wolfSSL
• MIRACL Cryptographic SDK
• Голанга х / крипто / sha3

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

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

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

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

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

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

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

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

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

внешняя ссылка

• Веб-сайт Keccak