Алгоритм хеширования sha это
Индустрия инфраструктуры открытых ключей (ИОК, англ. PKI — Public Key Infrastructure) рекомендует, чтобы любой объект инфраструктуры, использующий SHA-1, был переведён на более безопасный SHA-2. В этой статье описано, почему и как стоит это сделать.
В 2016 году миграция на SHA-2 была хорошей подготовкой к всеобщему дедлайну, сейчас же этот переход обязателен для обеспечения безопасности. Многие устройства и приложения, использующие электронные сертификаты, уже сейчас выводят предупреждения или ошибки или отказываются работать, если сертификат использует алгоритмы хеширования SHA-1 или старше. Зачем эти принудительные изменения? Потому что в хеше SHA-1 обнаружены серьёзные криптографические уязвимости, и дни, когда его защита ещё надёжна, уже сочтены.
Вплоть до 2017 года SHA-1 был самым популярным хешем, используемым для криптографической подписи, и некоторые, в особенности старые, приложения и устройства не принимали или не понимали хеши или сертификаты, основанные на алгоритме SHA-2. Это было основной проблемой перехода на новый стандарт.
SHA-3 уже здесь, но стоит ли его использовать?
Хотя в SHA-2 не обнаружено существенных криптографических слабостей, он считается алгоритмически схожим с SHA-1. Большинство экспертов думают, что его время жизни будет схожим с SHA-1. В августе 2015 NIST утвердило новый алгоритм криптографического хеширования SHA-3. Он не обладает теми же математическими свойствами, что SHA-1 и SHA-2 и должен быть более устойчив к криптографическим атакам, чем его предшественники.
К сожалению, люди, откладывающие свой переход на SHA-2 в надежде сразу перейти на SHA-3, будут очень расстроены. Общемировое принятие стандарта SHA-3 может затянуться на долгие годы, а переход на SHA-2 следует сделать уже сейчас. Если вы перейдёте на SHA-3 сейчас, то большинство, если не все, ваших криптографически-зависимых приложений или устройств, скорее всего, сообщат об ошибке (не смогут распознать цифровой сертификат).
Итак, если вы ещё не перешли на SHA-2, то переходите сейчас. И когда SHA-2 начнёт ослабевать, мы все вместе перейдём на SHA-3.
SHA-2 (Secure Hash Algorithm), в семейство которого входит SHA-256, — это один самых известных и часто используемых алгоритмов хэширования. В тексте подробно покажем каждый шаг работы этого алгоритма на реальном примере. SHA-2 отличается безопасностью (его тяжелее взломать, чем SHA-1) и скоростью.
Шаг 1 — Предварительная работа
Преобразуем «Привет, мир» в двоичный код:
Дополните код нулями, пока данные не станут равны 512 бит, минус 64 бита (в результате 448 бит):
Теперь у нас есть ввод, который будет делиться на 512 без остатка.
Что такое хеш-функция?
Если вы хотите узнать больше о хеш-функциях, можете почитать Википедию. Но чтобы понять, о чём пойдёт речь, давайте вспомним три основные цели хеш-функции:
- обеспечить проверку целостности (неизменности) данных;
- принимать ввод любой длины и выводить результат фиксированной длины;
- необратимо изменить данные (ввод не может быть получен из вывода).
Шаг 6. Цикл сжатия
- Инициализируем переменные a, b, c, d, e, f, g, h и установим их равными текущим значениям хеша соответственно. h0, h1, h2, h3, h4, h5, h6, h7 .
- Запустим цикл сжатия, который будет изменять значения a…h . Цикл выглядит следующим образом:
- for i from 0 to 63
- S1 = (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
- ch = (e and f) xor ((not e) and g)
- temp1 = h + S1 + ch + k[i] + w[i]
- S0 = (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
- maj = (a and b) xor (a and c) xor (b and c)
- temp2 := S0 + maj
- h = g
- g = f
- f = e
- e = d + temp1
- d = c
- c = b
- b = a
- a = temp1 + temp2
Давайте пройдём первую итерацию. Сложение рассчитывается по модулю 2^32:
Все расчёты выполняются ещё 63 раза, изменяя переменные а … h . В итоге мы должны получить следующее:
Шаг 3 — Инициализация округленных констант (k)
Как и в предыдущем шаге, мы создадим еще несколько констант. На этот раз их будет 64. Каждое значение (0—63) представляет собой первые 32 бита дробных частей кубических корней первых 64 простых чисел (2—311).
Свойства
Криптографическая хеш-функция должна уметь противостоять всем известным типам криптоаналитических атак.
В теоретической криптографии уровень безопасности хеш-функции определяется с использованием следующих свойств:Pre-image resistance
Second pre-image resistance
Имея заданное входное значение , должно быть сложно найти другое входное значение такое, что
Collision resistance
Давайте чуть более подробно поговорим о каждом из перечисленных свойств.
Несмотря на то, что хеш-функций без коллизий не существует, некоторые из них достаточно надежны и считаются устойчивыми к коллизиям.
Second pre-image resistance. Это свойство называют сопротивлением второму прообразу. Для упрощения можно сказать, что это свойство находится где-то посередине между двумя предыдущими. Атака по нахождению второго прообраза происходит, когда злоумышленник находит определенный вход, который генерирует тот же хеш, что и другой вход, который ему уже известен. Другими словами, злоумышленник, зная, что пытается найти такое, что
Отсюда становится ясно, что атака по нахождению второго прообраза включает в себя поиск коллизии. Поэтому любая хеш-функция, устойчивая к коллизиям, также устойчива к атакам по поиску второго прообраза.
Неформально все эти свойства означают, что злоумышленник не сможет заменить или изменить входные данные, не меняя их хеша.
В частности, хеш-функция должна вести себя как можно более похоже на случайную функцию, оставаясь при этом детерминированной и эффективно вычислимой.
SHA-256 «Привет, мир»
Атаки на хеши
Общепринятые криптографические хеш-функции изначально считаются криптографически стойкими, но со временем злоумышленники находят математические уловки, ослабляющие их защиту.
Шаг 7 — Измените окончательные значения
После цикла сжатия, во время цикла фрагментов, мы изменяем хеш-значения, добавляя к ним соответствующие переменные a-h. Как и ранее, все сложение производится по модулю 2 ^ 32:
Что такое хеш?
Службы центра сертификации (ЦС) ИОК используют криптографические хеш-функции для подтверждения идентификационных данных и запросов цифровых сертификатов. Кроме этого, хеши используются для подтверждения цифровых сертификатов (например, цифровой подписью) и списка аннулированных сертификатов (CRL, certificate revocation list), которые выдают другие доверенные стороны. Доверенные стороны не смогут полагаться на достоверность цифровых сертификатов и другого контента, подписанного ЦС, если службы ИОК используют ненадёжный криптографический хеш. Стойкость криптографического хеша создаёт доверие ко всей системе ИОК.
В общем, криптографические хеши считаются более безопасными, чем контрольные суммы, хотя последние часто используются для некритических проверок целостности и подлинности.
Применение хеш-функций
Рассмотрим несколько достаточно простых примеров применения хеш-функций:
• Верификация пароля
Проверка пароля обычно использует криптографические хеши. Хранение всех паролей пользователей в виде открытого текста может привести к массовому нарушению безопасности, если файл паролей будет скомпрометирован. Одним из способов уменьшения этой опасности является хранение в базе данных не самих паролей, а их хешей. При выполнении хеширования исходные пароли не могут быть восстановлены из сохраненных хеш-значений, поэтому если вы забыли свой пароль вам предложат сбросить его и придумать новый.• Цифровая подпись
Подписываемые документы имеют различный объем, поэтому зачастую в схемах ЭП подпись ставится не на сам документ, а на его хеш. Вычисление хеша позволяет выявить малейшие изменения в документе при проверке подписи. Хеширование не входит в состав алгоритма ЭП, поэтому в схеме может быть применена любая надежная хеш-функция.Предлагаю также рассмотреть следующий бытовой пример:
Алиса ставит перед Бобом сложную математическую задачу и утверждает, что она ее решила. Боб хотел бы попробовать решить задачу сам, но все же хотел бы быть уверенным, что Алиса не блефует. Поэтому Алиса записывает свое решение, вычисляет его хеш и сообщает Бобу (сохраняя решение в секрете). Затем, когда Боб сам придумает решение, Алиса может доказать, что она получила решение раньше Боба. Для этого ей нужно попросить Боба хешировать его решение и проверить, соответствует ли оно хеш-значению, которое она предоставила ему раньше.
Теперь давайте поговорим о SHA-3.
Национальный институт стандартов и технологий (NIST) в течение 2007—2012 провёл конкурс на новую криптографическую хеш-функцию, предназначенную для замены SHA-1 и SHA-2.
Организаторами были опубликованы некоторые критерии, на которых основывался выбор финалистов:
Способность противостоять атакам злоумышленников
• Производительность и стоимость
Вычислительная эффективность алгоритма и требования к оперативной памяти для программных реализаций, а также количество элементов для аппаратных реализаций
• Гибкость и простота дизайна
Гибкость в эффективной работе на самых разных платформах, гибкость в использовании параллелизма или расширений ISA для достижения более высокой производительности
В финальный тур попали всего 5 алгоритмов:
Победителем и новым SHA-3 стал алгоритм Keccak.
Давайте рассмотрим Keccak более подробно.
Шаг 8. Получаем финальный хеш
И последний важный шаг — собираем всё вместе.
Готово! Мы выполнили каждый шаг SHA-2 (SHA-256) (без некоторых итераций).
План перехода ИОК с SHA-1 на SHA-2
Каждая компания с внутренним ИОК, не использующая SHA-2, должна будет создать ИОК SHA-2 или перевести существующую ИОК с SHA-1 на SHA-2. Для перехода нужно:
- Обучить вовлечённых членов команды тому, что такое SHA-2 и почему требуется его использование (эта статья будет хорошим началом).
- Провести инвентаризацию всех критических хешей или цифровых сертификатов, используемых в приложениях или устройствах.
- Определить, какие критически важные устройства или приложения могут использовать SHA-2, какой размер ключа может быть использован и какие операционные проблемы могут возникнуть (этот этап зачастую включает обращение к поставщику и тестирование).
- Определить, какие компоненты ИОК могут или должны быть перенесены в SHA-2.
- Составить план перехода для преобразования компонентов SHA-1 в SHA-2, включая потребителей и компоненты ИОК, плюс резервный план на случай сбоя.
- Провести PoC-тестирование.
- Принять управленческий риск и решение о переходе или отказе от него.
- Внедрить план перехода в производственную среду.
- Провести тестирование и получить обратную связь.
Подумайте о своей миссии, чтобы определить, какие важные части вашей инфраструктуры будут или не будут работать. Начните с попытки инвентаризации каждого уникального устройства, ОС и приложения, которые должны понимать SHA-2. Затем соберите команду людей, которые протестируют, работает ли SHA-2. Можно предварительно полагаться на информацию от поставщиков, но вы не будете знать наверняка пока не проверите самостоятельно.
Обновление приложений и устройств — задача не из лёгких, и потребует больше времени, чем кажется. Даже сейчас существует множество устройств и приложений, использующих старые версии OpenSSL, которые следовало бы обновить после атаки Heartbleed, но администраторы серверов этого так и не сделали.
Если у вас есть внутренняя ИОК, вам понадобится подготовить её к переходу на SHA-2. Иногда это означает обновление ваших центров сертификации, получение новых сертификатов или установку полностью новых ИОК. Последнее рекомендуется по множеству причин, в основном потому, что новая ИОК даст вам шанс начать сначала без груза старых ошибок.
Шаг 3. Инициализация округлённых констант (k)
Создадим ещё немного констант, на этот раз их 64. Каждое значение — это первые 32 бита дробных частей кубических корней первых 64 простых чисел (2–311).
SHA-256 «hello world». Шаг 1. Предварительная обработка
1. Преобразуем «hello world» в двоичный вид:
2. Добавим одну единицу:
3. Заполняем нулями до тех пор, пока данные не станут кратны 512 без последних 64 бит (в нашем случае 448 бит):
4. Добавим 64 бита в конец, где 64 бита — целое число с порядком байтов big-endian, обозначающее длину входных данных в двоичном виде. В нашем случае 88, в двоичном виде — «1011000».
Теперь у нас есть ввод, который всегда будет без остатка делиться на 512.
Обработка устаревших хэшей SHA-1
К сожалению, переход с SHA-1 на SHA-2 является односторонней операцией в большинстве сценариев сервера. Например, как только вы начнёте использовать цифровой сертификат SHA-2 вместо SHA-1, пользователи, не понимающие сертификаты SHA-2, начнут получать предупреждения и уведомления об ошибках, или даже отказы. Для пользователей приложений и устройств, не поддерживающих SHA-2, переход будет опасным скачком.
Алгоритм SHA-2 в виде псевдокода
Если вы хотите посмотреть на все шаги, которые мы только что сделали, в виде псевдокода, то вот пример:
Keccak
Хеш-функции семейства Keccak построены на основе конструкции криптографической губки, в которой данные сначала «впитываются» в губку, а затем результат Z «отжимается» из губки.
Любая губчатая функция Keccak использует одну из семи перестановок которая обозначается , где
перестановки представляют собой итерационные конструкции, состоящие из последовательности почти одинаковых раундов. Число раундов зависит от ширины перестановки и задаётся как где
В качестве стандарта SHA-3 была выбрана перестановка Keccak-f[1600], для неё количество раундов
Далее будем рассматривать
Давайте сразу введем понятие строки состояния, которая играет важную роль в алгоритме.
Строка состояния представляет собой строку длины 1600 бит, которая делится на и части, которые называются скоростью и ёмкостью состояния соотвественно.
Соотношение деления зависит от конкретного алгоритма семейства, например, для SHA3-256
В SHA-3 строка состояния S представлена в виде массива слов длины бит, всего бит. В Keccak также могут использоваться слова длины , равные меньшим степеням 2.
Алгоритм получения хеш-функции можно разделить на несколько этапов:
• Строка P делится на n блоков длины
• «Впитывание»: каждый блок дополняется нулями до строки длиной бит (b = r+c) и суммируется по модулю 2 со строкой состояния , далее результат суммирования подаётся в функцию перестановки и получается новая строка состояния , которая опять суммируется по модулю 2 с блоком и дальше опять подаётся в функцию перестановки . Перед началом работы криптографической губки все элементыравны 0.
• «Отжимание»: пока длина результата меньше чем , где - количество бит в выходном массиве хеш-функции, первых бит строки состояния добавляется к результату . После каждой такой операции к строке состояния применяется функция перестановок и данные продолжают «отжиматься» дальше, пока не будет достигнуто значение длины выходных данных .
Все сразу станет понятно, когда вы посмотрите на картинку ниже:
Функция дополнения
Шаг 2. Инициализация значений хеша (h)
Создадим 8 значений хеша. Это константы, представляющие первые 32 бита дробных частей квадратных корней первых 8 простых чисел: 2, 3, 5, 7, 11, 13, 17, 19.
Модели перехода ИОК
Ниже перечислены сценарии для внедрения SHA-2 в компоненты ИОК (для этих примеров используется двухуровневая ИОК — автономная корневая система, онлайн центры сертификации), каждый из которых может быть либо новым компонентом, либо перенесённым:
- Два ИОК дерева, один полностью SHA-1, другой полностью SHA-2.
Остальные сценарии предполагают одно дерево ИОК:
- Всё дерево ИОК, от корня до конечных точек, — SHA-1.
- Всё дерево ИОК, от корня до конечных точек, — SHA-2.
- Корень — SHA-1, выдающие ЦС — SHA-2, сертификаты конечных точек — SHA-2.
- Корень — SHA-1, выдающие ЦС — SHA-2, сертификаты конечных точек — SHA-1.
- Корень — SHA-1, выдающие ЦС — SHA-2 и SHA-1, сертификаты конечных точек — SHA-2 и SHA-1.
- Корень — SHA-2, выдающие ЦС — SHA-1, сертификаты конечных точек — SHA-1.
- Корень — SHA-2, выдающие ЦС — SHA-2, сертификаты конечных точек — SHA-1.
- Корень — SHA-2, выдающие ЦС — SHA-2 и SHA-1, сертификаты конечных точек — SHA-2 и SHA-1.
Также возможно существование выдающего центра сертификации, который переключается между SHA-1 и SHA-2 по необходимости, но это с большой вероятностью вызовет путаницу в службах ИОК (и не особо рекомендуется). Если возможно, для облегчения перехода можно запустить параллельные ИОК, один — с SHA-1, другой — с SHA-2, а потом переводить используемые устройства после того, как позволит тестирование.
Примечание: собственный сертификат ЦС корневого ЦС не нужно переносить на SHA-2, даже если он всё ещё использует SHA-1. Все программы проверки устаревших SHA-1 заботятся обо всём после собственного сертификата корневого ЦС (и будут заботиться, по крайней мере, в обозримом будущем). Тем не менее, имеет смысл переместить всё, включая собственный сертификат ЦС корневого ЦС на SHA-2, чтобы можно было сказать, что вся ИОК — SHA-2, и избежать дальнейших изменений, связанных с SHA-1, в обозримом будущем.
Публичные ЦС уже перешли с SHA-1 на SHA-2 для любых сертификатов со сроком жизни, заканчивающимся после 1 января 2017, поэтому вы должны сосредоточить свои усилия на серверах и приложениях с ещё не перешедшими на SHA-2 публичными цифровыми сертификатами. После решения этой проблемы можно начать смотреть на внутренние ИОК и доверенные стороны. Переход с SHA-1 на SHA-2 технически не сложен, но это массовое логистическое изменение с множеством последствий, которое требует продолжительного тестирования.
Вряд ли большинство поставщиков знают точную дату смерти SHA-1 (т. е. дату, когда его использование в приложении или устройстве будет приводить к «фатальным» ошибкам), но скорее всего это произойдёт раньше, чем вы ожидаете, так как всё больше пользователей переходит на SHA-2. Поэтому вам действительно стоит совершить переход уже сейчас.
Шаг 4. Основной цикл
Следующие шаги будут выполняться для каждого 512-битного «куска» входных данных. Наша тестовая фраза «hello world» довольно короткая, поэтому «кусок» всего один. На каждой итерации цикла мы будем изменять значения хеш-функций h0 – h7 , чтобы получить окончательный результат.
1. Копируем входные данные из шага 1 в новый массив, где каждая запись является 32-битным словом:
2. Добавляем ещё 48 слов, инициализированных нулями, чтобы получить массив w[0…63] :
3. Изменяем нулевые индексы в конце массива, используя следующий алгоритм:
- For i from w[16…63] :
- s0 = (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] righthift 3)
- s1 = (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor (w[i-2] righthift 10)
- w [i] = w[i-16] + s0 + w[i-7] + s1
Давайте посмотрим, как это работает для w[16] :
Семейство SHA-2
SHA-2 — стандарт криптографического хеширования, который программное и аппаратное обеспечение должны использовать по крайней мере ближайшие пару лет. SHA-2 очень часто называется семейством хеш-функций SHA-2, поскольку содержит много хешей разных размеров, включая 224-, 256-, 384- и 512-битные последовательности. Когда кто-то говорит, что использует SHA-2, длина его хеша неизвестна, но сейчас самый популярный — 256-битный. Хотя некоторые математические характеристики SHA-2 совпадают с SHA-1, и в нём обнаружены незначительные недостатки, в криптомире он по-прежнему считается «стойким». Без сомнения, он лучше, чем SHA-1 и чем любой критический сертификат, приложение или аппаратное устройство, использующие SHA-1. Всё, что использует SHA-1, лучше перевести на SHA-2.
Шаг 8 — Финальный хэш
Наконец, соединяем все вместе.
Мы прошли каждый шаг (за исключением нескольких итераций) SHA-256 в подробностях. Если хотите увидеть весь путь, что мы совершили, в форме псевдокода, заходите на WikiPedia.Сегодня я хотел бы рассказать о том, что из себя представляет хеш-функция, коснуться её основных свойств, привести примеры использования и в общих чертах разобрать современный алгоритм хеширования SHA-3, который был опубликован в качестве Федерального Стандарта Обработки Информации США в 2015 году.
Введение в семейство SHA
Алгоритм SHA-1 был разработан Агентством национальной безопасности США (АНБ) и опубликован Национальным институтом стандартов и технологий США (NIST) в качестве федерального стандарта в 1995 году. Выпущенные NIST криптографические стандарты пользуются доверием по всему миру и как правило требуются на всех компьютерах, используемых правительством или вооружёнными силами Соединённых Штатов. SHA-1 заменил предыдущие ослабевшие хеш-функции, например, MD5.
Со временем несколько непрерывных криптографических атак на SHA-1 уменьшили эффективность длины ключа. Из-за этого в 2002 году АНБ и NIST выбрали SHA-2 новым рекомендуемым стандартом хеширования. Это случилось задолго до того, как SHA-1 начали считать взломанным. В феврале 2017 года обнаружили успешную атаку на хеш с помощью коллизий, которая сделала SHA-1 бесполезным для защиты электронной подписи.
Отличное обсуждение взлома SHA-1 и пример документации можно найти здесь.
Шаг 7. Изменяем окончательные значения
После цикла сжатия, но ещё внутри основного цикла, мы модифицируем значения хеша, добавляя к ним соответствующие переменные a … h . Как обычно, всё сложение происходит по модулю 2^32.
Шаг 6 — Сжатие
Инициализируйте переменные a, b, c, d, e, f, g, h и установите их равными текущим значениям хэш-функции соответственно h0, h1, h2, h3, h4, h5, h6, h7.
Запустите цикл сжатия, который изменит значения a… h. Выглядит он следующим образом:
- S1 = (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
- ch = (e and f) xor ((not e) and g)
- temp1 = h + S1 + ch + k[i] + w[i]
- S0 = (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
- maj = (a and b) xor (a and c) xor (b and c)
- temp2 := S0 + maj
- h = g
- g = f
- e = d + temp1
- d = c
- c = b
- b = a
- a = temp1 + temp2
Все вычисления выполняются еще 63 раза, меняя переменные a-h. К счастью, мы не делаем это вручную. В итоге мы получили:Общие сведения
Криптографическая хеш-функция - это математический алгоритм, который отображает данные произвольного размера в битовый массив фиксированного размера.
Для идеальной хеш-функции выполняются следующие условия:
Давайте сразу рассмотрим пример воздействия хеш-функции SHA3-256.
Число 256 в названии алгоритма означает, что на выходе мы получим строку фиксированной длины 256 бит независимо от того, какие данные поступят на вход.
На рисунке ниже видно, что на выходе функции мы имеем 64 цифры шестнадцатеричной системы счисления. Переводя это в двоичную систему, получаем желанные 256 бит.
Любой заинтересованный читатель задаст себе вопрос: "А что будет, если на вход подать данные, бинарный код которых во много раз превосходит 256 бит?"
Ответ таков: на выходе получим все те же 256 бит!
Дело в том, что 256 бит - это соответствий, то есть различных входов имеют свой уникальный хеш.
Чтобы прикинуть, насколько велико это значение, запишем его следующим образом:Надеюсь, теперь нет сомнений в том, что это очень внушительное число!
Поэтому ничего не мешает нам сопоставлять длинному входному массиву данных массив фиксированной длины.
Что такое хэш-функция?
Три основных цели хэш-функций:
- Детерминировано шифровать данные (такой вид шифрования всегда создает одно и то же зашифрованное значение для одного и того же текстового значения);
- Принимать ввод любой длины, а выводить результат фиксированной длины;
- Изменять данные необратимо. Ввод нельзя получить из вывода.
Итоги
В данной статье я постарался объяснить, что такое хеш-функция и зачем она нужна
Также в общих чертах мной был разобран принцип работы алгоритма SHA-3 Keccak, который является последним стандартизированным алгоритмом семейства Secure Hash AlgorithmОдним из ключевых слов, которые новички слышат, когда узнают о блокчейне, являются понятия хэша и алгоритма хэширования, которые кажутся распространёнными для безопасности. Запуск децентрализованной сети и консенсуса, такой как биткойн или сеть эфириум с десятками тысяч узлов, соединенных через p2p, требует, как “надежности”, так и эффективности проверки. То есть, эти системы нуждаются в способах кодирования информации в компактном формате, позволяющем обеспечить безопасную и быструю проверку ее участниками
Криптографические хэши используются везде, от хранения паролей до систем проверки файлов. Основная идея состоит в том, чтобы использовать детерминированный алгоритм (алгоритмический процесс, который выдает уникальный и предопределенный результат для задачи входных данных), который принимает один вход и создает строку фиксированной длины каждый раз. То есть, использование одного и того же ввода всегда приводит к одному и тому же результату. Детерминизм важен не только для хэшей, но и для одного бита, который изменяется во входных данных, создавая совершенно другой хэш. Проблема с алгоритмами хэширования - неизбежность коллизий. То есть, тот факт, что хэши являются строкой фиксированной длины, означает, что для каждого ввода, который мы можем себе представить, есть другие возможные входы, которые приведут к тому же хэшу. Коллизия - это плохо. Это означает, что, если злоумышленник может создавать коллизии, он может передавать вредоносные файлы или данные, как имеющие правильный и неправильный хэш и скрываться под правильным хешем. Цель хорошей хэш-функции состоит в том, чтобы сделать чрезвычайно сложным для злоумышленников найти способы генерации входных данных, которые хешируются с одинаковым значением. Вычисление хэша не должно быть слишком простым, так как это облегчает злоумышленникам искусственное вычисление коллизий. Алгоритмы хэширования должны быть устойчивы к «атакам нахождения прообраза». То есть, получая хеш, было бы чрезвычайно сложно вычислить обратные детерминированные шаги, предпринятые для воспроизведения значения, которое создало хэш (т.е нахождение прообраза).
Напомним, что «хорошие» алгоритмы хэширования имеют следующие свойства:
- Изменение одного бита во входных данных должно создать эффект изменения всего хеша;
- Вычисления хеша не должно быть слишком простым, высокая сложность нахождения прообраза;
- Должен иметь очень низкую вероятность коллизии;
Вы когда-нибудь слышали о том, что если вы поместите 23 человека в комнату, есть 50% шанс, что у двух из них будет один и тот же день рождения? Доведение числа до 70 человек в комнате дает вам 99,9% шанс. Если голуби рассажены в коробки, причем число голубей больше числа коробок, то хотя бы в одной из клеток находится более одного голубя. То есть фиксированные ограничения на выход означают, что существует фиксированная степень перестановок, на которых можно найти коллизию.
На самом деле MD5 настолько слаб к сопротивлению к коллизиям, что простой бытовой Процессор Pentium 2,4 ГГц может вычислить искусственные хэш-коллизии в течение нескольких секунд. Кроме того, его широкое использование в более ранние дни текущей сети создало тонны утечек MD5 предварительных прообразов в интернете, которые можно найти с помощью простого поиска Google их хэша.
NSA (Агентство национальной безопасности) уже давно является пионером стандартов алгоритмов хэширования, с их первоначальным предложением алгоритма Secure Hashing Algorithm или SHA1, создающий 160-битные выходы фиксированной длины. К сожалению, SHA1 просто улучшил MD5, увеличив длину вывода, количество однонаправленных операций и сложность этих односторонних операций, но не дает каких-либо фундаментальных улучшений против более мощных машин, пытающихся использовать различные атаки. Так как мы можем сделать что-то лучше?
В 2006 году Национальный институт стандартов и технологий (NIST) запустил конкурс, чтобы найти альтернативу SHA2, которая будет принципиально отличаться в своей архитектуре, чтобы стать стандартом. Таким образом, SHA3 появился как часть большой схемы алгоритмов хэширования, известной как KECCAK (произносится Кетч-Ак). Несмотря на название, SHA3 сильно отличается своим внутренним механизмом, известным как «конструкция губки», которая использует случайные перестановки для «Впитывания» и «Выжимания» данных, работая в качестве источника случайности для будущих входов, которые входят в алгоритм хэширования.
Когда дело дошло до интеграции алгоритма хеширования в блокчейн протоколы, биткоин использовал SHA256, в то время как Ethereum использовал модифицированный SHA3 (KECCAK256) для своего PoW. Однако важным качеством выбора хэш-функции для блокчейна с использованием доказательства работы является эффективность вычислений указанного хэша. Алгоритм хеширования биткойна SHA256 может быть вычислен достаточно просто с помощью специализированного оборудования, известного как специализированные интегральные схемы (или ASIC). Много было написано об использовании ASIC в майнинг пуле и о том, как они делают протокол направленным на централизацию вычислений. То есть доказательство работы стимулирует группы вычислительно эффективных машин объединяться в пулы и увеличивать то, что мы обозначаем “хэш-мощностью”, или мерой количества хэшей, которые машина может вычислить за интервал времени. Ethereum, выбрал модифицированный SHA3 известный как KECCAK 256. Кроме того, алгоритм PoW в Ethereum - Dagger-Hashimoto, должен был быть трудно вычисляемым для аппаратного обеспечения.
SHA3 не был единственным прорывом, который вышел из конкурса хеширования NIST в 2006 году. Несмотря на то, что SHA3 выиграл, алгоритм, известный как BLAKE, занял второе место. Для реализации шардинга Ethereum 2.0 использует более эффективное. Алгоритм хэширования BLAKE2b, который является высокоразвитой версией BLAKE от конкурентов, интенсивно изучается за его фантастическую эффективность по сравнению с KECCAK256 при сохранении высокой степени безопасности. Вычисление BLAKE2b фактически в 3 раза быстрее, чем KECCAK на современном процессоре.
Кажется, что независимо от того, что мы делаем, мы просто либо (1) увеличиваем сложность внутренних хеш-операций, либо (2) увеличиваем длину хеш-выхода, надеясь, что компьютеры атакующих не будут достаточно быстрыми, чтобы эффективно вычислять ее коллизию. Мы полагаемся на двусмысленность предварительных прообразов односторонних операций для обеспечения безопасности наших сетей. То есть цель безопасности алгоритма хеширования состоит в том, чтобы сделать как можно более сложным для любого, кто пытается найти два значения, которые хешируются на один и тот же вывод, несмотря на то, что существует бесконечное количество возможных столкновений. «Как насчет будущего квантовых компьютеров? Будут ли алгоритмы хэширования безопасными?» Короткий ответ и текущее понимание заключаются в том, что да, алгоритмы хэширования выдержат испытание временем против квантовых вычислений. То, что квантовые вычисления смогут сломать, - это те проблемы, которые имеют строгую математическую структуру, основанную на аккуратных трюках и теории, такой как шифрование RSA. С другой стороны, алгоритмы хэширования имеют менее формальную структуру во внутренних конструкциях. Квантовые компьютеры действительно дают повышенную скорость в вычислении неструктурированных проблем, таких как хэширование, но в конце концов, они все равно будут грубо атаковать так же, как компьютер сегодня попытается это сделать. Независимо от того, какие алгоритмы мы выбираем для наших протоколов, ясно, что мы движемся к вычислительно-эффективному будущему, и мы должны использовать наше лучшее суждение, чтобы выбрать правильные инструменты для работы и те, которые, мы надеемся, выдержат испытание временем.
Дмитриев Марк - Технический аналитик и управляющий криптоактивами инвестиционного фонда GT Blockchain Investments
SHA-2 (Secure Hash Algorithm 2) — одно из самых популярных семейств алгоритмов хеширования. В этой статье мы разберём каждый шаг алгоритма SHA-256, принадлежащего к SHA-2, и покажем, как он работает на реальном примере.
Шаг 2 — Инициализируйте значения хэша (h)
Теперь мы создаем 8 хэш-значений. Это жестко запрограммированные константы, которые представляют собой первые 32 бита дробных частей квадратных корней из первых восьми простых чисел: 2, 3, 5, 7, 11, 13, 17, 19.
Шаг 4 — Цикл фрагментов
Следующие шаги будут выполняться для каждого 512-битного «фрагмента» из наших входных данных. Поскольку фаза «Привет, мир» короткая, у нас есть только один фрагмент. В каждой итерации цикла мы будем изменять хэш-значения h0-h7, что приведет нас к конечному результату.
Скопируйте входные данные из шага 1 в новый массив, где каждая запись представляет собой 32-битное слово:
Добавьте еще 48 слов, инициализированных нулем, чтобы у нас получился массив w [0… 63]
Измените обнуленные индексы в конце массива, используя следующий алгоритм:
Для i из w[16…63]:- s0 = (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)
- s1 = (w[i- 2] rightrotate 17) xor (w[i- 2] rightrotate 19) xor (w[i- 2] rightshift 10)
- w[i] = w[i-16] + s0 + w[i-7] + s1
Функция перестановок
Базовая функция перестановки состоит из раундов по пять шагов:
Тета, Ро, Пи, Хи, Йота
Далее будем использовать следующие обозначения:
Так как состояние имеет форму массива , то мы можем обозначить каждый бит состояния как
Обозначим результат преобразования состояния функцией перестановки
Также обозначим функцию, которая выполняет следующее соответствие:
- обычная функция трансляции, которая сопоставляет биту бит ,где - длина слова (64 бит в нашем случае)
Я хочу вкратце описать каждый шаг функции перестановок, не вдаваясь в математические свойства каждого.
Шаг
Эффект отображения можно описать следующим образом: оно добавляет к каждому биту побитовую сумму двух столбцов и
Схематическое представление функции:
Шаг
Отображение направлено на трансляции внутри слов (вдоль оси z).
Проще всего его описать псевдокодом и схематическим рисунком:
Шаг
Шаг представляется псевдокодом и схематическим рисунком:
Шаг
Шаг является единственный нелинейным преобразованием в
Псевдокод и схематическое представление:
Шаг
Отображение состоит из сложения с раундовыми константами и направлено на нарушение симметрии. Без него все раунды были бы эквивалентными, что делало бы его подверженным атакам, использующим симметрию. По мере увеличения раундовые константы добавляют все больше и больше асимметрии.
Ниже приведена таблица раундовых констант для бит
Все шаги можно объединить вместе и тогда мы получим следующее:
Где константы являются циклическими сдвигами и задаются таблицей:
SHA-2 и SHA-256
SHA-2 — это семейство алгоритмов с общей идеей хеширования данных. SHA-256 устанавливает дополнительные константы, которые определяют поведение алгоритма SHA-2. Одной из таких констант является размер вывода. «256» и «512» относятся к соответствующим размерам выходных данных в битах.
Мы рассмотрим пример работы SHA-256.
Читайте также: