Cpu sha3 что это такое

Алгоритм SHA-3

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

Преобразование, производимое хеш-функцией, называется хешированием. Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования (выходные данные) называется «хешем», «хеш-кодом», «хеш-суммой».

Иными словами, хеш-функция — это вычислительный метод, который может отображать неопределенный размер данных в фиксированный размер данных. Или, проще говоря, преобразование выводит числовое значение, которое характеризуется входными данными. Криптографическая хэш-функция использует необратимые (односторонние) математические функции, чтобы сгенерировать хеш-значение из входных данных. Одним из распространенных способов генерации криптографических хешей является использование блочных шифров.

К надежным с точки зрения криптографии хеш-функциям должны быть предъявлены следующие основные требования:

Хеш-функция должна представлять из себя одностороннюю функцию т.е. по образу (хешу) невозможно или почти невозможно найти исходный прообраз (сообщение).
Функция хеширования должна быть устойчива к коллизиям. Коллизия – это пара исходных сообщений, имеющая одинаковое выходное значение. Считается, что относительно быстрое нахождение коллизии в алгоритме хеширования делает подобный алгоритм ненадёжным с точки зрения криптоанализа.

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

Что из себя представляет SHA-3?

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

SHA-3 (Keccak) – алгоритм хеширования переменной разрядности, разработанный группой во главе с Йоаном Дайменом в 2012 году. 5 августа 2015 года алгоритм утверждён и опубликован в качестве стандарта FIPS 202. Keccak был выбран в качестве официального алгоритма для SHA-3 в 2012 году. [1] Keccak основан на конструкции Sponge (Губка), которая является новым способом проектирования хеш-функций, помимо стратегии итерационного метода Меркла — Дамгора, реализуемой в MD(x).

Алгоритмы MD(x) основаны на методе вычислений в цикле с использованием простых логических операций типа OR, XOR, AND, NOT. поэтому становится возможным построение коллизий с одинаковым, заранее выбранным префиксом. Однако, как показало время алгоритмы MD(x) перестали быть безопасными из-за программ, способных находить коллизии за сравнительно небольшое время.

Губка — это итеративная конструкция для создания функции с произвольной длиной на входе и произвольной длиной на выходе на основе преобразований перестановки.

Алгоритм получения выходного значения хеш-функции с помощью алгоритма SHA-3 можно разделить на несколько этапов:

1 этап: Дополнение

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

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

Для SHA-3 значение l принимается равным 6. Чем больше размер, тем выше безопасность, которую он обеспечивает. Теперь, основываясь на значении «», мы также решаем, сколько вычислительных раундов необходимо выполнить для каждой части дополненного сообщения.

Теперь мы знаем, что для SHA-3 размер состояния будет равен 1600 битам, а количество раундов вычислений — 24.

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

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

Первый и последний бит заполнения будут ‘1″, а все биты между ними «0». После заполнения они делятся на » » частей, где эквивалентно длине дополненного сообщения. Математически это можно представить в следующем виде:

2 этап: Размер состояния

Сумма значений ‘ ‘ и ‘ ‘ всегда будет равна 1600, что продемонстрировано в таблице.

Теперь понятно, что длина дополненного сообщения точно кратна «» в зависимости от нужной длины хеша.( делится на блоков длины : )

Размер части состояния, который записывается и считывается, называется «скоростью» (англ. rate) и обозначается , а размер части, которая нетронута вводом / выводом, называется «емкостью» (англ. capacity) и обозначается .

Далее алгоритм можно условно разделить на две условные части: “впитывание” и “отжимание”.

3 этап: Функция впитывания

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

Рассмотрим более подробно функции перестановок. Функция перестановок, используемая в SHA-3, включает в себя исключающее «ИЛИ» (XOR), побитовое «И» (AND) и побитовое отрицание (NOT). Функция определена для строк длины-степени 2. Состояние можно представить в виде трёхмерного массива размером .

Тогда элемент массива будет размером строки состояния

Внутри функции мы выполняем один и тот же набор из пяти операций в течение двадцати четырех раз.

На каждом шаге обозначим входной массив выходной массив :

Шаг :

Для всех и таких, что , положим

Для всех таких что :

Шаг :

Для всех , таких, что
Пусть в начале . Для от 0 до 23:

Для всех таких, что

Шаг :

Для всех , таких, что

Шаг :

Для всех , таких, что ,

Шаг :

Введем дополнительную функцию , где вход-целове число

Если , то возвращается 1
Пусть

Для от 1 до 255:

Алгоритм :

Для всех , таких, что
Пусть — массив длинны , заполненный нулями
Для от 0 до :
Для массива в стороку длины

Алгоритм перестановок:

Перевод строки в массив
Для от до
Перевод массива в строку длины

4 этап: Функция отжимания

Пока длина меньше ( — количество бит в результате хеш-функции), к длине добавляется первых бит состояния после каждого прибавления к применяется функция перестановок . Затем происходит обрезается до длины бит.

Строка длины бит возвращается в качестве результата

Криптоустойчивость SHA-3

Семейство хеш-функций Keccak было подвергнуто интенсивному криптоанализу с момента его представления на конкурс SHA-3 в 2008 [5]. В 2012 году Национальный институт стандартов и технологий США выбрал Keccak победителем конкурса SHA-3. Семейство SHA-3 состоит из четырех криптографических хэш-функций c фиксированным размером хеша и двух расширяемых выходных функций (XOFs) с именами SHAKE128 и SHAKE256, каждая из которых основана на экземпляре алгоритмов Keccak.

Подробно сосредоточимся на коллизиях семейства Keccak, то есть на поиске двух разных исходных сообщениях, дающих разное значение хеша. Лучшие предыдущие практические атаки столкновений на семейство Keccak-это Keccak -224 и KECCAK -256, уменьшенные до 4 раундов, найденных Dinur l.[3] в 2012 году и позже представлен в журнальной версии [4]. После этого теоретические результаты улучшились до 5-раундового KECCAK -256. Однако на практике количество раундов остается на уровне 4. Чтобы продвинуть криптоанализ Keccak, команда разработчиков алгоритма предложила уменьшить количество раундов в Keccak challenge [6] т.е рассматривать хеш с размером 160 для атаки с по поиску коллизий и хеш размером 80 для атаки прообраза с каждым из 4 размеров внутренних состояний (state size в 1 шаге дополнения) , уменьшенных до 12 раундов т.е. полагается равным 0 в 1 шаге дополнения. Идеальные уровни безопасности обоих алгоритмов установлены на уровне 2^80 единичных вычислений для коллизий и прообразов соответственно. Здесь количество вычислений значительно ниже, чем у основных 4 экземпляров SHA-3, однако это количество остается вне досягаемости текущего вычислительного ресурса. Теоретические результаты были найдены Dinur l. против KECCAK -256 со сложностями с использованием обобщенных внутренних дифференциалов. Насколько известно, это остается единственным результатом атаки коллизиями против SHA-3, уменьшенным до 5 раундов на сегодняшний день.

Теоретическая оценка результатов по поиску коллизий на сервере с 32 ядрами процессоров AMD. Таблица взята из источника [2]

Теперь перейдем к рассмотрению алгебраических методов для установки атак прообразов на несколько вариантов Keccak, основанных на свойствах χ шага и линейных перестановок . Атаки прообраза на SHA-3 одинаковы, за исключением того, что временная сложность может быть на больше из-за двух дополнительных битов заполнения. В общем случае здесь мы находим прообразы сообщения длиной бита, устанавливая -й бит входного состояния равным 1, так что дополненное сообщение

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

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

Однако последние биты не могут быть выбраны, так как не предусмотрено добавления битов сообщения, поэтому допускается выбирать только “переменные” линейных структуры из первых битов . Именно поэтому стоит использовать разные линейные структуры для различных примеров.

Основная идея атак состоит в том, чтобы установить и решить линейные уравнения. Сложность в этом разделе измеряется количеством решений для линейной системы уравнений.

Далее последует представление атак прообразов, в зависимости от выбора линейных структур и способы инвертирования Sbox с последующим анализом сложности. Основная идея подобных атак состоит в том, чтобы установить и решить соответствующие системы линейных уравнений.

SHAKE128 -это экземпляр стандарта SHA-3, определенного из Keccak , с неограниченной выходной длиной (SHA3-X в табл 1) Рассмотрим атаку прообраза на SHAKE128 , обозначаемой далее SHAKE128 для простоты.

Данные взяты из источника [7]

Устанавливаем с =0,2 и =0,1,2,3 в качестве переменных и накладываем некоторые условия на входные биты таким образом, чтобы все выходные биты после двух раундов были линейными, как показано на рис. 10. устанавливается на любую константу, такую что является исходным сообщением. Полосы серого и светло-серого цветов заданы только единицами и нулями. Чтобы убедиться, что все выходные биты после двух раундов являются линейными, потребуется:

Данные взяты из источника [7]

Все эти 6×64 линейных уравнения линейно независимы и, таким образом, имеют решений. Полагаем, что существует одно решение, соответствующее заданному 128-битному хеш-значению.

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

Заключение

В целом результаты по поиску коллизий и описанная атака прообраза показывают, что на сегодняшний день алгоритм SHA-3 / Keccak является одним из самых безопасных и эффективных алгоритмов хеширования. Некоторые утверждают, что он не будет взломан в ближайшие 20-30 лет. Развитие в мире квантовых вычислений может сократить эти временные рамки, но пока что данный алгоритм все еще один из лучших алгоритмов хеширования, который человечество имеет на данный момент.

SHA-3

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

SHA-3 представляет собой подмножество более широкой криптографической примитивного семейства Keccak ( / к ɛ tʃ æ к / или / K ɛ tʃ ɑː к / ), [7] [8] разработан Guido Bertoni , Joan Daemen , Майкл Петерс, и Жиль Ван Аше , основанный на RadioGatún . Авторы Кеккака предложили дополнительные варианты использования функции, которая (пока) не стандартизована NIST, в том числе потоковый шифр , аутентифицированная система шифрования , «древовидная» схема хеширования для более быстрого хеширования на определенных архитектурах [9] [10] и шифры AEAD. Кеяк и Кете. [11] [12]

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

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

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

Алгоритм Keccak работа Гвидо Бертони, Джоан Daemen (который также совместно спроектировал Rijndael шифра с Винсентом Rijmen ), Майкл Питерс, и Жиль Ван Аше . Он основан на ранее хэш — функции конструкции ПАНАМА и RadioGatún . ПАНАМА был разработан Daemen и Крейг Клапп в 1998 году RadioGatún, преемник ПАНАМА, был разработан Daemen, Петерс и Ван Аше, и был представлен на NIST Hash семинара в 2006 году [15] эталонная реализация исходный код был посвящен в общественное достояние через отказ от CC0 . [16]

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

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

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

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

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

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

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

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

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

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

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

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

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

Позже он отказался от своего более раннего заявления, сказав:

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

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

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

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

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

заполните вход N с помощью функции заполнения, в результате чего получится заполненная битовая строка P с длиной, кратной р (такой, что п знак равно len ( п ) / р > (P) / r> целое число)
разбить P на n последовательных r -битных частей P₀ , . P_{n −1}
инициализировать состояние S строкой из b нулевых битов

поглощают ввод в состояние: для каждого блока P_i :

расширить P_i в конце строкой из c нулевых битов, получив в результате один длиной b
XOR, что с S
применить к результату блочную перестановку f , получив новое состояние S

добавить первые r битов S к Z
если длина Z все еще меньше d битов, примените f к S , получив новое состояние S

Тот факт, что внутреннее состояние 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 бит) могут использоваться в практических, легких приложениях. [11] [12]

Для экземпляров 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 . [5] : 5.1 В этом случае к сообщению добавляется еще один блок, содержащий 1 бит, за которым следует блок из r — 2 нулевых бита и еще 1 бит. Это необходимо для того, чтобы сообщение с длиной, кратной r, заканчивающейся чем-то похожим на заполнение, не создавало такой же хэш, как сообщение с удаленными битами.

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

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

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

Блочное преобразование f , которое представляет собой Keccak-f [1600] для SHA-3, представляет собой перестановку, которая использует операции XOR , AND и NOT , и предназначена для простой реализации как в программном, так и в аппаратном обеспечении.

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

Состояние можно рассматривать как массив бит 5 × 5 × w . Пусть a [ i ] [ j ] [ k ] будет битом (5 i + j ) × w + k ввода, используя соглашение о нумерации битов с прямым порядком байтов и индексирование по старшим строкам . Т.е. я выбирает строку, 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] , где ( я j ) знак равно ( 3 2 1 0 ) т ( 0 1 ) i \\ j \ end > = <\ begin 3 & 2 \\ 1 & 0 \ end > ^ <\ begin 0 \\ 1 \ end >> . π (пи) Переставьте 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 бит [1], что примерно соответствует SHA3-256:

57,4 ц / бит на IA-32, Intel Pentium 3 [37]
41 cpb на IA-32 + MMX, Intel Pentium 3
20 cpb на IA-32 + SSE, Intel Core 2 Duo или AMD Athlon 64
12,6 cpb на типичной машине на базе x86-64
6–7 cpb на IA-64 [38]

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

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

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

Экземпляры

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

Пример	Выходной размер d	Скорость r = размер блока	Емкость c	Определение	Сильные стороны безопасности в битах
Пример	Выходной размер 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 ) [5] : 20
Keccak-f [1600] = Keccak-p [1600, 24] [5] : 17
c — емкость
r — ставка = 1600 — c
N — входная битовая строка

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

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

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

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

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

В декабре 2016 года NIST опубликовал новый документ, NIST SP.800-185, [44], описывающий дополнительные производные от 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 2040 .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Общий результат ( алгоритм Гровера) заключается в том, что квантовые компьютеры могут выполнять атаку структурированного прообраза в 2 d знак равно 2 d / 2 >> = 2 ^ > , в то время как классическая атака полным перебором требует 2 d . Атака структурированного прообраза подразумевает атаку второго прообраза [27] и, следовательно, атаку столкновения . Квантовый компьютер также может выполнять атаку в честь дня рождения , тем самым нарушая сопротивление столкновениям 2 d 3 знак равно 2 d / 3 ] >> = 2 ^ > [52] (хотя это оспаривается [53] ). Отмечая, что максимальная сила может быть c / 2 , это дает следующие верхние [54] границы квантовой безопасности 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, разрушается и, как следствие, устойчива к квантовым столкновениям [55], но для конструкции губки, используемой в SHA-3, авторы предоставляют доказательства только для случай, когда блочная функция f не является эффективно обратимой; Keccak-f [1600], однако, эффективно обратим, и поэтому их доказательство неприменимо. [56]

Примеры вариантов 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

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

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

Реализации

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

Русте SHA-3
Ботан
Надувной Замок
Крипто ++
Libgcrypt
Крапива
OpenSSL
wolfSSL
MIRACL Cryptographic SDK
Golang’s x / crypto / sha3
libkeccak

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

Шестиядерные процессорные ядра SoC Apple A13 ARMv8 поддерживают [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] Также процессоры POWER8 реализуют 2×64-битное вращение вектора, определенное в PowerISA 2.07, что может каким-то образом ускорить реализацию SHA-3. [73] Большинство реализаций для ARM не используют неоновые векторные команды , как это происходит медленнее , чем скалярный код , однако он может быть ускорены с помощью СВА и SVE2 инструкции вектора (например , на Fujitsu A64FX CPU). [74]

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

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

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

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

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

^ a b Обзор реализации Keccak Версия 3.2 , раздел 3.1
^ Моравецкий, Павел; Пиепшик, Йозеф; Сребрный, Мариан (2013). Мориаи, С. (ред.). «Вращательный криптоанализ округлённо сокращенного Keccak» (PDF) . Конспект лекций по быстрому программному шифрованию в компьютерных науках . Конспект лекций по информатике. 8424 : 241–262. DOI : 10.1007 / 978-3-662-43933-3_13 . ISBN 978-3-662-43932-6 . Архивировано 8 января 2013 года (PDF) . Проверено 8 февраля 2019 года .
^
Бертони, Гвидо; Дэмен, Джоан; Петерс, Микаэль; ван Аше, Джайлс (14 января 2011 г.). «Представление Keccak SHA-3» (PDF) . keccak.noekeon.org . Архивировано 19 августа 2011 года (PDF) . Проверено 9 февраля 2014 года .
^ а б
«Хеш-функции» . NIST . 22 июня 2020 . Проверено 17 февраля 2021 года .
^ Б с д е е г ч I
NIST (август 2015 г.). «Стандарт SHA-3: хеширование на основе перестановок и функции расширяемого вывода» (PDF) . DOI : 10,6028 / NIST.FIPS.202 . Проверено 29 февраля 2020 года . Цитировать журнал требует |journal= ( помощь )
^
Дворкин, Моррис Дж. (4 августа 2015 г.). «Стандарт SHA-3: хеширование на основе перестановок и функции расширяемого вывода» . Федеральный Инф. Процесс. STDS. (NIST FIPS) — 202 .
^ а б
«NIST выбирает победителя конкурса алгоритмов безопасного хеширования (SHA-3)» . NIST . 2 октября 2012 . Проверено 2 октября 2012 года .
^
Круз, Хосе Р.С. (7 мая 2013 г.). «Keccak: новый стандарт шифрования SHA-3» . Доктор Доббс .
^
Гвидо Бертони; Джоан Дэмен; Михаэль Петерс; Жиль Ван Аше. «Семейство функций губки Keccak: Обзор технических характеристик» . Проверено 11 мая 2011 года .
^
Чанг, Шу-джен; Перлнер, Рэй; Берр, Уильям Э .; Сонмез Туран, Мельтем; Келси, Джон М .; Пол, Сурадьюти; Бэшем, Лоуренс Э. (ноябрь 2012 г.). «Отчет третьего раунда конкурса алгоритмов хеширования SHA-3» (PDF) . DOI : 10,6028 / NIST.IR.7896 . Проверено 29 февраля 2020 года . Цитировать журнал требует |journal= ( помощь ) Разделы 5.1.2.1 (упоминание «древовидного режима»), 6.2 («другие функции», упоминание аутентифицированного шифрования) и 7 (упоминание «дополнительных функций» может быть стандартизировано в будущем).
^ а б
Бертони, Гвидо; Дэмен, Джоан; Петерс, Микаэль; Ван Аше, Жиль; Ван Кир, Ронни (13 марта 2014 г.). «Представление CAESAR: Ketje v1» (PDF) . Проверено 29 февраля 2020 года .
^ а б
Бертони, Гвидо; Дэмен, Джоан; Петерс, Микаэль; Ван Аше, Жиль; Ван Кир, Ронни (13 марта 2014 г.). «Представление CAESAR: Keyak v1» (PDF) . Проверено 29 февраля 2020 года .
^ а б
Гвидо Бертони, Джоан Дэмен, Микаэль Петерс и Жиль Ван Аше. «Функции губки» . Ecrypt Hash Workshop 2007. CS1 maint: использует параметр авторов ( ссылка )
^
«Объявление запроса о выдвижении кандидатур алгоритмов для нового семейства криптографических алгоритмов хеширования (SHA-3) [Федеральный регистр США, том 72 № 212]]» (PDF) . 2 ноября 2007 г. Архивировано 31 марта 2011 г. (PDF) из оригинала . Проверено 18 июля 2017 года .
^
Бертони, Гвидо; Дэмен, Джоан; Петерс, Микаэль; Ван Аше, Жиль. «Дорога из Панамы в Кеччак через RadioGatún» (PDF) . Проверено 29 февраля 2020 года .
^ KeccakReferenceAndOptimized-3.2.zip mainReference.c «Функция губки Keccak, разработанная Гвидо Бертони, Джоан Дэемен, Микаэль Петерс и Жиль Ван Аше. Для получения дополнительной информации, отзывов или вопросов посетите наш веб-сайт: http: // keccak. noekeon.org/Implementation [ постоянная мертвая ссылка ] , разработанная дизайнерами, далее обозначается как «исполнитель». В той степени, в которой это возможно в соответствии с законом, исполнитель отказался от всех авторских и смежных или смежных прав на исходный код в этом файле. https: //creativecommons.org/publicdomain/zero/1.0/ «
^
Стивенс, Марк; Бурштейн, Эли; Карпман, Пьер; Альбертини, Анж; Марков, Ярик. «Первая коллизия для полного SHA-1» (PDF) . Проверено 23 февраля 2017 года .
^
Леурент, Гаэтан; Пейрин, Томас. «SHA-1 — это бойня» . Проверено 8 января 2020 года .
^
«Отдел компьютерной безопасности NIST — Конкурс криптографических хеш-алгоритмов SHA-3, ноябрь 2007 г. — октябрь 2012 г.» . 4 января 2017 г.
^
«Параметр Keccak изменяется для 2 раунда» . Команда Keccak . 22 сентября 2009 года. Архивировано 13 ноября 2017 года . Проверено 29 февраля 2020 года .
^
«Упрощение правила заполнения Keccak для раунда 3» . Команда Keccak . 17 января 2011 . Проверено 29 февраля 2020 года .
^
«Стандартизация SHA-3» . NIST . Проверено 16 апреля 2015 года .
^
Национальный институт стандартов и технологий (5 августа 2015 г.). «Федеральные стандарты обработки информации: хеширование на основе перестановок, функции расширяемого вывода и т . Д.» . Проверено 5 августа 2015 года .
^
«Объявление об утверждении Федерального стандарта обработки информации (FIPS) 202, стандарта SHA-3: хеширование на основе перестановок и функции расширяемого вывода, а также пересмотр пункта о применимости FIPS 180-4, стандарта безопасного хеширования» . 5 августа 2015 года.
^
Джон Келси. «SHA3, где мы были, куда мы идем» (PDF) . Конференция RSA 2013.
^
Джон Келси. «SHA3, прошлое, настоящее и будущее» . ЧЕС 2013.
^ а б
«Аннотация» (PDF) . cr.yp.to .
^
«Список рассылки хэш-форума NIST» . 4 января 2017 г.
^
«Представление Keccak SHA-3» (PDF) . 14 января 2011 . Проверено 8 февраля 2014 года .
^
«О 128-битной безопасности» .
^
«Конкретное предложение» . 2 октября 2013 г.
^ а б
«Шнайер о безопасности: будет ли Keccak = SHA-3?» .
^
«LShift: Почему я поддерживаю правительство США, ослабляющее стандарты криптографии» .
^
«Да, это Кечак!» .
^
«Движение вперед с SHA-3» (PDF) .
^
Отдел компьютерной безопасности NIST (CSD). «Стандарт SHA-3: хеширование на основе перестановок и функции расширяемого вывода» (PDF) . NIST.
^ «примерно 41 цикл / байт [. ] представляет 40% ускорение по сравнению с реализацией, использующей только 32-битные инструкции». По формуле 1 Икс × 1,40 знак равно 1 41 год > \ times 1.40 = >> мы получаем Икс знак равно 57,4
^
Бертони, Гвидо (29 мая 2012 г.). Обзор реализации Keccak (PDF) . п. 25 . Проверено 3 ноября 2018 года .
^
Бернштейн, Дэниел Дж. (4 января 2012 г.). «Ошибки оптимизации в программном обеспечении SHA-3» (PDF) . cr.yp.to . Проверено 29 февраля 2020 года .
^ а б
«Кечак Тим» . keccak.noekeon.org .
^
Го, Сюй; Хуанг, Синан; Нажандали, Лейла; Патрик Шаумонт (август 2010 г.), «Справедливая и всесторонняя оценка производительности 14 реализаций ASIC SHA-3 второго раунда» (PDF) , NIST 2nd SHA-3 Candidate Conference : 12 , получено 18 февраля 2011 г. Кечак уступает только Луффе, который не прошел в финальный раунд.
^ Корпорация ARM, справочное руководство по архитектуре ARM ARMv8, для профиля архитектуры ARMv8-A, документ ARM DDI 0487C.a (ID121917), https://www.arm.com
^ а б
«Сакура: гибкое кодирование для хеширования деревьев» (PDF) . Команда Keccak . 2014 . Проверено 29 февраля 2020 года .
^ Производные функции SHA-3: cSHAKE, KMAC, TupleHash и ParallelHash Эта статья включает текст из этого источника, который находится в общественном достоянии .
^
«Показатели производительности программного обеспечения» .
^ а б
«Команда Keccak: KangarooTwelve» . Команда Keccak.
^ а б
«KangarooTwelve: быстрое хеширование на основе Keccak-p» (PDF) . Международная ассоциация криптологических исследований . 2016 г.
^
«Кенгуру — двенадцать слайдов, представленных на ACNS 2018» (PDF) . Команда Keccak.
^
«draft-irtf-cfrg-kangarootwelve-00 — KangarooTwelve» . datatracker.ietf.org . IETF . Проверено 17 января 2020 года .
^
Гвидо Бертони, Джоан Дэмен, Сет Хофферт, Микаэль Петерс, Жиль Ван Аше, Ронни Ван Кир (29 декабря 2016 г.). «Фарфалле: криптография на основе параллельных перестановок» . CS1 maint: использует параметр авторов ( ссылка )
^
Гвидо Бертони, Джоан Дэмен, Сет Хофферт, Микаэль Петерс, Жиль Ван Аше, Ронни Ван Кир (12 октября 2018 г.). «Аутентифицированные схемы шифрования Kravatte-SANE и Kravatte-SANSE» . CS1 maint: использует параметр авторов ( ссылка )
^
Брассар, Жиль; Хойер, Питер; Тэпп, Ален (1998). «Квантовый криптоанализ хеш-функций и функций без когтей». Аннотация . Конспект лекций по информатике. 1380 . С. 163–169. arXiv : квант-ph / 9705002 . DOI : 10.1007 / BFb0054319 . ISBN 978-3-540-64275-6 . S2CID 118940551 .
^
«Анализ затрат» (PDF) . cr.yp.to .
^
«Проблема столкновения» (PDF) . scottaaronson.com .
^
«Бумага» (PDF) . eprint.iacr.org . 2016 г.
^
«Аннотация» (PDF) . eprint.iacr.org . 2017 г.
^
«NIST.gov — Отдел компьютерной безопасности — Ресурсный центр по компьютерной безопасности» . 29 декабря 2016 г.
^
«Таблица измерений» . bench.cr.yp.to .
^
Тао, Се; Лю, Фаньбао; Фэн, Дэнго (2013). Fast Collision Attack на MD5 (PDF) . Cryptology ePrint Archive (Технический отчет). МАКР .
^
Стивенс, Марк ; Бурштейн, Эли ; Карпман, Пьер; Альбертини, Анж; Марков, Ярик. Первая коллизия для полного SHA-1 (PDF) (Технический отчет). Google Research . Краткое содержание — Блог по безопасности Google (23 февраля 2017 г.).
^ Без усечения известно полное внутреннее состояние хеш-функции, независимо от сопротивления столкновениям. Если вывод усечен, удаленная часть состояния должна быть отыскана и найдена до того, как хеш-функция может быть возобновлена, что позволит продолжить атаку.
^
«Семейство функциональных губок Keccak» . Проверено 27 января, 2016 .
^
«openssl / openssl- kecak1600-avx512vl.pl» . GitHub . Проверено 25 июня 2020 года .
^
«openssl / openssl — keccak1600-avx2.pl» . GitHub .
^
«openssl / openssl — keccak1600-x86_64.pl» . GitHub . Проверено 25 июня 2020 года .
^
«openssl / openssl — keccak1600-armv8.pl» . GitHub .
^
«openssl / openssl — keccak1600-ppc64.pl» . GitHub . Проверено 25 июня 2020 года .
^
«openssl / openssl — kccak1600-mmx.pl» . GitHub . Проверено 25 июня 2020 года .
^
«llvm / llvm-project — AArch64.td» . GitHub . Проверено 24 июня 2020 года .
^
«ARMv8 — ARM — WikiChip» . en.wikichip.org . Проверено 24 июня 2020 года .
^
«weidai11 / cryptopp» . GitHub . Проверено 25 июня 2020 года .
^
«openssl / openssl» . GitHub . Проверено 25 июня 2020 года .
^
«openssl / openssl» . GitHub .
^
«Apple / llvm-project — lib / Target / AArch64 / AArch64SVEInstrInfo.td» . GitHub . Проверено 25 июня 2020 года .

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

Веб-сайт Keccak

Keccak, новый стандарт хеширования данных

Доброго времени суток, уважаемые читатели.
Многие из вас наверняка знают о том, что на протяжении нескольких лет NIST проводил конкурс среди хеш-функций с целью принятия нового стандарта SHA-3. И в этом году награда нашла своего героя. Новый стандарт был благополучно принят.
Ну а раз стандарт уже принят, самое время посмотреть что же он из себя представляет.
И тихим, субботним вечером, я ~~обложившись мануалами~~ открыв в браузере google.com начал свое небольшое исследование.

Прелюдия

В качестве нового стандарта была выбрана хеш-функция Keccak с переменной длиной выхода 224,256,384 и 512 бит. В основе Keccak лежит конструкция под названием Sponge(губка, та самая с верхней картинки).
Данную конструкцию можно представить следующим образом:

Как видно из рисунка схема состоит из двух этапов:

Absorbing(впитывание). Исходное сообщение M подвергается многораундовым перестановкам f.
Squeezing(отжатие). Вывод получившегося в результате перестановок значения Z.

Внимательный читатель наверняка заметил на рисунке буквы r и с. Не будем раньше времени раскрывать интригу, скажем только что варьируя значение этих переменных мы получим абсолютно разные хеш-функции. Так для SHA-512, в качестве этих значений нужно выбрать r=576, c=1024.

А поподробнее?

Взять исходное сообщение M и дополнить его до длины кратной r. Правила дополнения пленяют своей простотой. В виде формулы их можно изобразить следующим образом: M=M||0x01||0x00||..||0x00||0x80. Или говоря по-русски, к сообщению дописывается единичный байт, необходимое количество нулей и весь этот ансамбль завершает байт со значением 0x80.
UPD:Все вышесказанное справедливо только для случаев, когда добавляется более одного байта. Однако в случае, если необходимо дополнить всего один байт, то достаточно добавить лишь 0x81. Ошибка вскрылась благодаря бдительности уважаемого OverQuantum. А еще раньше об этом же говорил хабраюзер fdsc, чей пост в песочнице был незамечен, но теперь справедливость восторжествовала. Таким образом код необходимо переписать с учетом этого замечания!
Затем для каждого блока M_i длиной r бит выполняем:
Сложение по модулю 2 с первыми r-битами набора начальных состояний S. Перед началом работы функции все элементы S будут равны нулю.
N раз применяем к полученным в результате данным функцию f. Набором начальных состояний S для блока M_i+1 будет результат последнего раунда блока M_i.
После того как все блоки M_i закончатся взять итоговый результат и вернуть его в качестве хеш-значения.

Все равно ничего не понятно!

Ну а теперь вся подноготная алгоритма с ~~блекждеком и шлюхами~~ кодом и пояснениями.
Но сперва сорвем таки покровы с тайны и расскажем для чего нужны параметры r и c.
Для этого нужно сказать, что хеш-функция Keccak реализована таким образом, что функцию перестановки f, применяемую для каждого блока M_i, пользователь может выбирать самостоятельно из набора предопределенных функции b=.
Для того чтобы в вашей реализации использовалась, скажем, функция f-800, необходимо выбрать такие r и c, чтобы выполнялось равенство r+c=800.
Кроме того, изменяя значения r и c, вы тем самым изменяете количество раундов вашей хеш-функции. Т.к. количество оных вычисляется по формуле n=12+2l, где 2 l =(b/25). Так для b=1600, Количество раундов равно 24.
Однако хотя пользователь в праве выбирать для своей реализации любую из предложенных авторами функций, следует отметить что в качестве стандарта SHA-3 принята только функция Keccak-1600 и авторы всячески рекомендуют пользоваться только ею. Так в качестве основных значений для хешей разной длины авторы выбрали следующие параметры:

SHA-224: r=1156, c=448 (вернуть первые 28 байт результат)
SHA-256: r=1088, c=512 (вернуть первые 32 байт результат)
SHA-384: r=832, c=768 (вернуть первые 48 байт результат)
SHA-512: r=576, c=1024 (вернуть первые 64 байт результат)

А код-то где?

И после всех этих разъяснений можно уже перейти непосредственно к псевдокоду алгоритма.
Этап absorbing можно представить в виде следующей функции:

Keccak-f[b](A)

Здесь b это значение выбранной функции(по умолчанию 1600). А функция Round()-псевдослучайная перестановка, применяемая на каждом раунде. Количество раундов nr вычисляется из значений r и c.

Операции выполняемые на каждом раунде представляют из себя следующую функцию:

Round[b](A,RC)

Она состоит из 4 шагов на каждом из которых над входящими данными производится ряд логических операций.
Здесь функция rot(X,n) обозначает циклический сдвиг элемента X на n позиций.
Массив r[] представляет собой предопределенный набор значений, в котором указывается на сколько необходимо сдвигать байты на каждом раунде. Значение всех элементов данного массива продемонстированы на таблице ниже:

Массив RC это набор констант, которые тоже являются предопределенными:

Сама же функция Keccak представляет из себя следующее:

Keccak[r,c](M) < Initialization and padding for(int x=0; xwhile output is requested return Z; >

На этапе Absorbig производится вычисление хеш значения.
А на этапе Squeezing вывод результатов до тех пор пока не будет достигнута требуемая длина хеша.

Под спойлером небольшой класс, написанный на C#, реализующий все эти действия

 public class Keccack < //константы рандов, всего их 24 //применяются на шаге ι private ulong[] RC =; //матрица смещений, применяется при каждом раунде на шаге θ private int[,] r = , , , , >; private int w, l, n; //в конструкторе устанавливаем параметры функции b=1600 public Keccack(int b) < w = b / 25; l = (Convert.ToInt32(Math.Log(w, 2))); n = 12 + 2 * l; >//циклический сдвиг переменной x на n бит private ulong rot(ulong x, int n) < n = n % w; return (((x > (w - n)))); > private ulong[,] roundB(ulong[,] A, ulong RC) < ulong[] C = new ulong[5]; ulong[] D = new ulong[5]; ulong[,] B = new ulong[5, 5]; //шаг θ for (int i = 0; i < 5; i++) C[i] = A[i, 0] ^ A[i, 1] ^ A[i, 2] ^ A[i, 3] ^ A[i, 4]; for (int i = 0; i < 5; i++) D[i] = C[(i + 4) % 5] ^ rot(C[(i + 1) % 5], 1); for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) A[i, j] = A[i, j] ^ D[i]; //шаги ρ и π for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) B[j, (2 * i + 3 * j) % 5] = rot(A[i, j], r[i, j]); //шаг χ for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) A[i, j] = B[i, j] ^ ((~B[(i + 1) % 5, j]) & B[(i + 2) % 5, j]); //шаг ι A[0, 0] = A[0, 0] ^ RC; return A; >private ulong[,] Keccackf(ulong[,] A) < for (int i = 0; i < n; i++) A = roundB(A, RC[i]); return A; >//функция дополняет 16-чную строку до размер r-байт и преобразует ее в матрицу 64-битных слов private ulong[][] padding(string M, int r) < int size = 0; //дополняем сообщение до длины кратной r M = M + "01"; while (((M.Length / 2) * 8 % r) != ((r - 8))) < M = M + "00"; >; M = M + "80"; //получаем из скольки блоков длиной b-бит состоит сообщение size = (((M.Length / 2) * 8) / r); //инициальзируем массив массивов 64-битных слов ulong[][] arrayM = new ulong[size][]; arrayM[0] = new ulong[1600 / w]; string temp = ""; int count = 0; int j = 0; int i = 0; //конвертируем строковое представление в массив 64-битных слов foreach (char ch in M) < if (j >(r/w-1)) < j = 0; i++; arrayM[i] = new ulong[1600 / w]; >count++; if ((count * 4 % w) == 0) < arrayM[i][j] = Convert.ToUInt64(M.Substring((count - w / 4), w / 4), 16); temp = ToReverseHexString(arrayM[i][j]); arrayM[i][j] = Convert.ToUInt64(temp, 16); j++; >> return arrayM; > private string ToReverseHexString(ulong S) < string temp = BitConverter.ToString(BitConverter.GetBytes(S).ToArray()).Replace("-", ""); return temp; >private string ToHexString(ulong S) < string temp = BitConverter.ToString(BitConverter.GetBytes(S).Reverse().ToArray()).Replace("-", ""); return temp; >// public string GetHash(string M, int r, int c, int d) < //Забиваем начальное значение матрицы S=0 ulong[,] S = new ulong[5, 5]; for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) S[i, j] = 0; ulong[][] P = padding(M, r); //Сообщение P представляет собой массив элементов Pi, //каждый из которых в свою очередь является массивом 64-битных элементов foreach (ulong[] Pi in P) < for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) if((i + j * 5)<(r/w)) S[i, j] = S[i, j] ^ Pi[i + j * 5]; Keccackf(S); >string Z = ""; //добавляем к возвращаемой строке значения, пока не достигнем нужной длины do < for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) if ((5*i + j) < (r / w)) Z = Z + ToReverseHexString(S[j, i]); Keccackf(S); >while (Z.Length < d*2); return Z.Substring(0, d * 2); >>

P.S. все материалы и иллюстрации для этой статьи были найдены на официальном сайте хеш-функции Keccak.

UPD: fshp любезно поделился ссылкой на русскоязычное описание основных возможностей нового стандарта.

UPD2: после опубликовая статьи ко мне на почту обратился читатель с ником Admiral. Он предложил более оптимизированный код, в котором не используется работа со строками.

Реализация читателя Admiral

using System; using System.Linq; using System.Collections.Generic; class Program < /*const */ static private Byte InstanceNumber = 6; /*const */ static private UInt16[] b_array = < 25, 50, 100, 200, 400, 800, 1600 >; //permutation_width /*const */ static private Byte matrixSize = 5 * 5; /*const */ static private Byte[] w_array = < 1, 2, 4, 8, 16, 32, 64 >; //b / 25; /*const */ static private Byte[] l_array = < 0, 1, 2, 3, 4, 5, 6 >; //log(static_cast(m_w)) / log(2.0F) /*const */ static private Byte[] n_array = < 12, 14, 16, 18, 20, 22, 24 >; //12 + 2 * l -> number_of_permutation /*const */ static private Byte[,] r = < , , , , >; /*const */ static private UInt64[] RC = ; static private UInt64[,] B = new UInt64[5, 5]; static private UInt64[] C = new UInt64[5]; static private UInt64[] D = new UInt64[5]; /*const*/ static public UInt16[] rate_array = < 576, 832, 1024, 1088, 1152, 1216, 1280, 1344, 1408 >; /*const*/ static public UInt16[] capacity_array = < 1024, 768, 576, 512, 448, 384, 320, 256, 192 >; public enum SHA3 < SHA512 = 0, SHA384, SHA256 = 3, SHA224 >; static private UInt64[,] Keccak_f(UInt64[,] A) < for(Byte i = 0; i < n_array[InstanceNumber]; i++) A = Round(A, RC[i]); return A; >static private UInt64[,] Round(UInt64[,] A, UInt64 RC_i) < Byte i, j; //theta step for (i = 0; i < 5; i++) C[i] = A[i,0] ^ A[i,1] ^ A[i,2] ^ A[i,3] ^ A[i,4]; for (i = 0; i < 5; i++) D[i] = C[(i + 4) % 5] ^ ROT(C[(i + 1) % 5], 1, w_array[InstanceNumber]); for (i = 0; i < 5; i++) for (j = 0; j < 5; j++) A[i,j] = A[i,j] ^ D[i]; //rho and pi steps for (i = 0; i < 5; i++) for (j = 0; j < 5; j++) B[j,(2 * i + 3 * j) % 5] = ROT(A[i,j], r[i,j], w_array[InstanceNumber]); //chi step for (i = 0; i < 5; i++) for (j = 0; j < 5; j++) A[i,j] = B[i,j] ^ ((~B[(i + 1) % 5,j]) & B[(i + 2) % 5,j]); //iota step A[0,0] = A[0,0] ^ RC_i; return A; >static private UInt64 ROT(UInt64 x, Byte n, Byte w) < return ((x > (w - (n % w)))); > static private Byte[] Keccak(UInt16 rate, UInt16 capacity, List Message) < //Padding Message.Add(0x01); UInt16 min = (UInt16)((rate - 8) / 8); UInt16 n = (UInt16)Math.Truncate((Double)(Message.Count / min)); UInt32 messageFullCount = 0; if (n < 2) < messageFullCount = min; >else < messageFullCount = (UInt32)(n * min + (n - 1)); >UInt32 delta = (UInt32)(messageFullCount - Message.Count); if ((Message.Count + delta) > UInt16.MaxValue - 1) throw (new Exception("Message might be too large")); /*Byte[] byteArrayToAdd = new Byte[delta]; Message.AddRange(byteArrayToAdd);*/ while (delta > 0) < Message.Add(0x00); delta--; >if ((Message.Count * 8 % rate) != (rate - 8)) throw (new Exception("Length was incorect calculated")); Message.Add(0x80); /*const*/ Int32 size = (Message.Count * 8) / rate; UInt64[] P = new UInt64[size * matrixSize]; Int32 xF = 0, count = 0; Byte i = 0, j = 0; for(xF = 0; xF < Message.Count; xF++) < if (j >(rate / w_array[InstanceNumber] - 1)) < j = 0; i++; >count++; if ((count * 8 % w_array[InstanceNumber]) == 0) < P[size * i + j] = ReverseEightBytesAndToUInt64( Message.GetRange(count - w_array[InstanceNumber] / 8, 8).ToArray() ); j++; >> //Initialization UInt64 [,]S = new UInt64[5,5]; for(i = 0; i < 5; i++) for(j = 0; j < 5; j++) S[i,j] = 0; //Absorting phase for(xF = 0; xF < size; xF++) < for(i = 0; i < 5; i++) for(j = 0; j < 5; j++) if ((i + j * 5) < (rate / w_array[InstanceNumber])) < S[i, j] = S[i, j] ^ P[size * xF + i + j * 5]; >Keccak_f(S); > //Squeezing phaze Byte a = 0; Byte d_max = (Byte)(capacity / (2 * 8)); List retHash = new List(d_max); for( ; ; ) < for(i = 0; i < 5; i++) for(j = 0; j < 5; j++) if((5 * i + j) < (rate / w_array[InstanceNumber])) < if(a >= d_max) i = j = 5; else < retHash.AddRange(FromUInt64ToReverseEightBytes(S[j, i])); a = (Byte)retHash.Count; >> if(a >= d_max) break; Keccak_f(S); > return retHash.GetRange(0, d_max).ToArray(); > static private UInt64 ReverseEightBytesAndToUInt64(Byte[] bVal) < UInt64 ulVal = 0L; for (Byte i = 8, j = 0; i >0; i--) < ulVal += (UInt64)((bVal[i - 1] & 0xF0) >> 4) * (UInt64)Math.Pow(16.0F, 15 - (j++)); ulVal += (UInt64)(bVal[i - 1] & 0x0F) * (UInt64)Math.Pow(16.0F, 15 - (j++)); > return ulVal; > static private Byte[] FromUInt64ToReverseEightBytes(UInt64 ulVal) < Byte[] bVal = new Byte[8]; Byte a = 0; do < bVal[a] = (Byte)((ulVal % 16) * 1); ulVal = ulVal / 16; bVal[a] += (Byte)((ulVal % 16) * 16); a++; >while (15 < (ulVal = ulVal / 16)); while (a < 8) < bVal[a++] = (Byte)ulVal; ulVal = 0; >return bVal; > static void Main(String[] args) < if (args.Length < 1) return; ListMessageB; String message = string.Copy(args[0]); MessageB = strToByteList(message); String hash_224 = ByteArrayToString(Keccak(rate_array[(Byte)SHA3.SHA224], capacity_array[(Byte)SHA3.SHA224], MessageB)); MessageB = strToByteList(message); String hash_256 = ByteArrayToString(Keccak(rate_array[(Byte)SHA3.SHA256], capacity_array[(Byte)SHA3.SHA256], MessageB)); MessageB = strToByteList(message); String hash_384 = ByteArrayToString(Keccak(rate_array[(Byte)SHA3.SHA384], capacity_array[(Byte)SHA3.SHA384], MessageB)); MessageB = strToByteList(message); String hash_512 = ByteArrayToString(Keccak(rate_array[(Byte)SHA3.SHA512], capacity_array[(Byte)SHA3.SHA512], MessageB)); Console.WriteLine("Message: " + message + "\r\n" + "Hash_224: " + hash_224 + "\r\n" + "Hash_256: " + hash_256 + "\r\n" + "Hash_384: " + hash_384 + "\r\n" + "Hash_512: " + hash_512 + "\r\n"); > static List strToByteList(String str) < Listret = new List(str.Length); foreach(char ch in str) < ret.Add((Byte)ch); >return ret; > static public String ByteArrayToString(Byte[] b) < System.Text.StringBuilder sb = new System.Text.StringBuilder(16); for (Int32 i = 0; i < Math.Min(b.Length, Int32.MaxValue - 1); i++) sb.Append(String.Format("", b[i])); return sb.ToString(); > >

Информационная безопасность
Криптография
Алгоритмы

[GLN] Galleon | SHA-3

Зарегистрируйте новую учётную запись в нашем сообществе. Это очень просто!

Cpu sha3 что это такое

Алгоритм SHA-3

Что из себя представляет SHA-3?

1 этап: Дополнение

2 этап: Размер состояния

3 этап: Функция впитывания

Шаг :

Шаг :

Шаг :

Шаг :

Шаг :

Алгоритм :

Алгоритм перестановок:

Криптоустойчивость SHA-3

Заключение

SHA-3

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

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

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

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

Keccak, новый стандарт хеширования данных

Прелюдия

А поподробнее?

Все равно ничего не понятно!

А код-то где?

[GLN] Galleon | SHA-3

Войти

Последние посетители 0 пользователей онлайн

Similar Topics

lawtoken.finance — Аирдроп 20 токенов LAW (~$20) + (~$4) за реферала от глобальной юридической платформы GLN

[ANN][gln][POOL] gln.pool.mn 0% комиссия! Не пропустите запуск Galleon(gln) !

Добавить комментарий Отменить ответ