SHA-3 Algorithms¶
SHA-3 (Secure Hash Algorithm 3) is a set of cryptographic hash functions defined in FIPS 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions.
The SHA-3 family consists of six hash functions with digests (hash values) that are 128, 224, 256, 384 or 512 bits: SHA3-224, SHA3-256, SHA3-384, SHA3-512, SHAKE128, SHAKE256.
Currently, this library supports all of the algorithms mentioned above.
- SHA3-224
- SHA3-256
- SHA3-384
- SHA3-512
- SHAKE-128
- SHAKE-256
Implementation on FPGA¶
The internal structure of SHA-3 algorithms can be shown as the figures below:
As we can see from the figures, hash calculation in both SHA-3 and SHAKE is much different from SHA-1 and SHA-2. Since the internal state array is updated iteratively (by the input message) and used in the next permutation, it cannot be partitioned into block generation part and digest part.
Both the digest parts of SHA-3 and SHAKE pad or split the input message into fixed sized blocks (1600-bit for each), and XOR it to the state array of the last iteration.
The message word size is 64-bit for both SHA-3 and SHAKE, and each block has a different number of message words according to the specific suffix of the algorithm which is selected. The number can be defined as:
Loop-carried dependency is enforced by the algorithm, and thus the digest part cannot reach II=1.
Performance¶
SHA3-224¶
A single instance of SHA3-224 function processes input message at the rate of 144 byte / 1105 cycles at 303.58MHz.
The hardware resource utilizations of SHA3-224 is listed in tab1SHA3224 below:
| BRAM | DSP | FF | LUT | CLB | SRL | clock period(ns) |
| 0 | 0 | 36974 | 45821 | 7819 | 606 | 3.294 |
SHA3-256¶
A single instance of SHA3-256 function processes input message at the rate of 136 byte / 1104 cycles at 306.65MHz.
The hardware resource utilizations of SHA3-256 is listed in tab1SHA3256 below:
| BRAM | DSP | FF | LUT | CLB | SRL | clock period(ns) |
| 0 | 0 | 36787 | 44975 | 7203 | 606 | 3.261 |
SHA3-384¶
A single instance of SHA3-384 function processes input message at the rate of 104 byte / 1100 cycles at 310.75MHz.
The hardware resource utilizations of SHA3-384 is listed in tab1SHA3384 below:
| BRAM | DSP | FF | LUT | CLB | SRL | clock period(ns) |
| 0 | 0 | 33782 | 40511 | 7264 | 611 | 3.218 |
SHA3-512¶
A single instance of SHA3-512 function processes input message at the rate of 72 byte / 1096 cycles at 316.25MHz.
The hardware resource utilizations of SHA3-512 is listed in tab1SHA3512 below:
| BRAM | DSP | FF | LUT | CLB | SRL | clock period(ns) |
| 0 | 0 | 32994 | 39794 | 7264 | 611 | 3.162 |
SHAKE-128¶
A single instance of SHAKE-128 function processes input message at the rate of 168 byte / 1108 cycles at 306.37MHz.
The hardware resource utilizations of SHAKE-128 is listed in tab1SHAKE128 below:
| BRAM | DSP | FF | LUT | CLB | SRL | clock period(ns) |
| 0 | 0 | 37577 | 47898 | 8229 | 610 | 3.264 |
SHAKE-256¶
A single instance of SHAKE-256 function processes input message at the rate of 136 byte / 1104 cycles at 302.02MHz.
The hardware resource utilizations of SHAKE-256 is listed in tab1SHAKE256 below:
| BRAM | DSP | FF | LUT | CLB | SRL | clock period(ns) |
| 0 | 0 | 36789 | 44909 | 7889 | 606 | 3.311 |
Clustering¶
To boost the throughput of SHA-3 primitives, multiple instance can be organized into a cluster, and offer message level parallelism.
Аппаратное шифрование в процессорах
Оформление разрешительных документов для ввоза и вывоза ШКС:
В современном мире шифрование используется практически повсеместно, как для защиты особо важной информации в специальных областях (оборонный сектор, банковская сфера и т.д.), так и в составе бытовых устройств: компьютеров, смартфонов, телевизоров. Более того, с каждым годом расширяется сфера применения криптографии, и растет объем передаваемых (хранимых) зашифрованных данных.
В то же время, шифрование данных значительно увеличивает вычислительную нагрузку на реализующие его устройства, поэтому неудивительно, что все чаще криптографические операции переносятся на аппаратный уровень (часто в виде специальных криптографических ко-процессоров или плат расширения). В последние годы шифровальные инструкции стали также широко внедряться непосредственно в центральные процессоры крупнейших брендов для бытовых ПК и мобильных устройств.
Содержание
Использование шифрования
По мере проникновения электроники и автоматики во все сферы нашей жизни растет потребность в защите передаваемых данных и ограничении доступа к ключевым компонентам. Практически все современные компьютеры, планшеты и смартфоны, роутеры, «умные» бытовые приборы, автомобили и пр. активно используют шифрование. Так, например, криптографические алгоритмы используются:
- при подключении к большинству видов беспроводных сетей передачи данных (Wi-Fi, Bluetooth и пр.);
- в мобильной связи;
- мобильные ОС (iOS, Android) шифруют данные на устройствах для защиты от несанкционированного доступа;
- безопасное хранение паролей требует определенных криптографических функций (т.е. большинство устройств с возможностью задания пароля использует шифрование);
- банковские карты, банкоматы, терминалы оплаты всегда защищены криптографически;
- криптовалюты основаны на принципах шифрования.
Все больше организаций и людей осознают важность применения шифрования для защиты данных. Так, совместными усилиями многих компаний, в частности, Google, доля зашифрованного HTTP-трафика выросла с 30% в начале 2014 года до 70% на начало 2018 [1] .
В то же время, любое шифрование — математически сложное преобразование данных и требует дополнительных вычислительных ресурсов от аппаратуры. В зависимости от сценария работы с данными внедрение шифрования может снизить общую пропускную способность (объем обрабатываемых данных в единицу времени) в несколько раз [2] .
Алгоритмы шифрования
Существует большое количество криптографических алгоритмов [3] . Поддерживать их все было бы технически трудно осуществимо.
Некоторые алгоритмы, однако, используются значительно чаще, чем другие. Это связано с тем, что многие алгоритмы признаны устаревшими или недостаточно безопасными, другие оказываются излишне сложными вычислительно. Есть также и другие причины.
Среди блочных симметричных алгоритмов прежде всего следует выделить AES (Advanced Encryption Standard). Данный алгоритм был отобран в качестве национального стандарта США по результатам конкурса [4] . AES является основным симметричным алгоритмом шифрования во многих протоколах и технологиях (TLS, Wi-Fi, Bluetooth (с версии 4.0), GPG, IPsec, Bitlocker (шифрование файловой системы Windows), LUKS (шифрование файловой системы Linux), Miscrosoft Office, многие программы-архиваторы (WinZip, 7-zip) и пр.).
Также крайне широко используются алгоритмы криптографического хеширования. В связи с тем, что алгоритм MD5 был признан небезопасным, в настоящее время наиболее распространенными являются алгоритмы серии SHA, прежде всего, SHA-1 и SHA-2, также являющимися стандартами FIPS США. Им на смену со временем придет алгоритм SHA-3, ставший в 2012 году победителем соответствующего конкурса.
Среди алгоритмов с открытым ключом стоит отметить RSA, DSA и Diffe-Hellman.
В процессорах наиболее распространенной архитектуры x86-64 (производителей Intel и AMD) последних поколений реализованы специальные инструкции для ускорения вычислений по алгоритмам AES и SHA-1, SHA-2 (256 бит).
Инструкции Intel
Компанией Intel в 2008 г. были предложены новые команды для x86-64 архитектуры, которые добавили поддержку на аппаратном уровне симметричного алгоритма шифрования AES. На данный момент AES — один из самых популярных алгоритмов блочного шифрования. Поэтому аппаратная реализация должна привести к повышению производительности программ, использующих этот алгоритм шифрования.
Набор новых инструкции носит название AES-NI (AES New Instructions) и состоит из четырёх инструкций для шифрования AES:
- AESENC — выполнить один раунд шифрования AES,
- AESENCLAST — выполнить последний раунд шифрования AES и расшифровки,
- AESDEC — выполнить один раунд расшифрования AES,
- AESDECLAST — выполнить последний раунд расшифрования AES,
и ещё двух инструкции для работы с ключом AES:
- AESIMC — Inverse Mix Columns,
- AESKEYGENASSIST — поспособствовать в генерации раундового ключа AES.
Как и раньше, инструкции относятся к SIMD, то есть к типу «одна инструкция много данных» (Single Instruction Multiple Data). Поддерживаются все три ключа режима AES (с длинами ключей 128, 192 и 256 битов с 10, 12 и 14 проходами подстановки и перестановки).
Использование этих инструкций обеспечивает ускорение операций шифрования в несколько раз [5] .
В 2013 году Intel представила спецификацию нового набора инструкций для алгоритмов SHA-1 и SHA-256:
- SHA-1: SHA1RNDS4, SHA1NEXTE, SHA1MSG1, SHA1MSG2
- SHA-256: SHA256RNDS2, SHA256MSG1, SHA256MSG2
Данные инструкции должны вызываться на различных этапах вычисления подписи (хеша) сообщения для ускорения наиболее вычислительно сложных операций.
Первые процессоры с поддержкой данных инструкций были представлены в 2016 году (микроархитектура Goldmont).
Поддержка процессорами
Набор инструкций AES-NI поддерживается процессорами Intel на основе архитектур [6] :
- Westmere:
- Westmere-EP (Xeon 56xx)
- все настольные, кроме Pentium, Celeron, Core i3
- мобильные: только Core i7 и Core i5
- Bulldozer
- Piledriver
- Steamroller
- Excavator
- Jaguar
- Puma
- Zen
Инструкции SHA поддерживаются процессорами Intel, начиная с архитектуры Goldmont (2016 год), процессорами AMD — с архитектуры Zen (2017 год).
Другие процессоры
Процессоры общего назначения других архитектур и производителей также часто включают поддержку специальных криптографических инструкций.
Так, поддержка алгоритма AES реализована в процессорах:
- на основе архитектуры Qualcomm ARMv8 и выше [7] ;
- SPARC T4 и выше [8] ;
- VIA (C3, C7) [9] .
Архитектура ARM также имеет набор инструкций для алгоритмов SHA:
- SHA1C — SHA1 hash update accelerator, choose
- SHA1H — SHA1 fixed rotate
- SHA1M — SHA1 hash update accelerator, majority
- SHA1P — SHA1 hash update accelerator, parity
- SHA1SU0 — SHA1 schedule update accelerator, first part
- SHA1SU1 — SHA1 schedule update accelerator, second part
- SHA256H — SHA256 hash update accelerator
- SHA256H2 — SHA256 hash update accelerator, upper part
- SHA256SU0 — SHA256 schedule update accelerator, first part
- SHA256SU1 — SHA256 schedule update accelerator, second part
Примечания
- ↑Доля страниц, загружаемых браузером Firefox по HTTPS
- ↑Производительность сети Wi-Fi при использовании различных алгоритмов шифрования и аутентификации
- ↑Симметричные алгоритмы (неполный список)
- ↑Конкурс NIST
- ↑ Ускорение в 5 раз (Truecrypt), в
Ссылки
Если Вам требуются услуги по таможенному оформлению, получению разрешительных документов или у Вас есть вопросы, свяжитесь с нами — Контакты IFCG.
В частности, мы готовы оказать услуги по оформлению следующих разрешительных документов для ввоза и вывоза товаров с шифровальными функциями:
Алгоритм 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:
Алгоритм :
Для всех , таких, что
Пусть — массив длинны , заполненный нулями
Для массива в стороку длины
Алгоритм перестановок:
Перевод строки в массив
Перевод массива в строку длины
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 лет. Развитие в мире квантовых вычислений может сократить эти временные рамки, но пока что данный алгоритм все еще один из лучших алгоритмов хеширования, который человечество имеет на данный момент.
Алгоритмы хеширования — простое объяснение сложного
Одним из ключевых слов, которые новички слышат, когда узнают о блокчейне, являются понятия хэша и алгоритма хэширования, которые кажутся распространёнными для безопасности. Запуск децентрализованной сети и консенсуса, такой как биткойн или сеть эфириум с десятками тысяч узлов, соединенных через p2p, требует, как “надежности”, так и эффективности проверки. То есть, эти системы нуждаются в способах кодирования информации в компактном формате, позволяющем обеспечить безопасную и быструю проверку ее участниками
Основным примитивом, обрабатываемым как Биткойном, так и Эфириумом, является понятие блока, который представляет собой структуру данных, включающую транзакции, временную метку и другие важные метаданные. Критическая часть их безопасности включает в себя возможность сжимать большие куски информации о глобальном состоянии сети в короткий стандарт сообщений, который может быть эффективно проверен, если это необходимо, известный как хэш.
Криптографические хэши используются везде, от хранения паролей до систем проверки файлов. Основная идея состоит в том, чтобы использовать детерминированный алгоритм (алгоритмический процесс, который выдает уникальный и предопределенный результат для задачи входных данных), который принимает один вход и создает строку фиксированной длины каждый раз. То есть, использование одного и того же ввода всегда приводит к одному и тому же результату. Детерминизм важен не только для хэшей, но и для одного бита, который изменяется во входных данных, создавая совершенно другой хэш. Проблема с алгоритмами хэширования — неизбежность коллизий. То есть, тот факт, что хэши являются строкой фиксированной длины, означает, что для каждого ввода, который мы можем себе представить, есть другие возможные входы, которые приведут к тому же хэшу. Коллизия — это плохо. Это означает, что, если злоумышленник может создавать коллизии, он может передавать вредоносные файлы или данные, как имеющие правильный и неправильный хэш и скрываться под правильным хешем. Цель хорошей хэш-функции состоит в том, чтобы сделать чрезвычайно сложным для злоумышленников найти способы генерации входных данных, которые хешируются с одинаковым значением. Вычисление хэша не должно быть слишком простым, так как это облегчает злоумышленникам искусственное вычисление коллизий. Алгоритмы хэширования должны быть устойчивы к «атакам нахождения прообраза». То есть, получая хеш, было бы чрезвычайно сложно вычислить обратные детерминированные шаги, предпринятые для воспроизведения значения, которое создало хэш (т.е нахождение прообраза).
Напомним, что «хорошие» алгоритмы хэширования имеют следующие свойства:
- Изменение одного бита во входных данных должно создать эффект изменения всего хеша;
- Вычисления хеша не должно быть слишком простым, высокая сложность нахождения прообраза;
- Должен иметь очень низкую вероятность коллизии;
Одним из первых стандартов алгоритма хэширования был MD5 hash, который широко использовался для проверки целостности файлов (контрольных сумм) и хранения хэшированных паролей в базах данных веб-приложений. Его функциональность довольно проста, так как она выводит фиксированную 128-битную строку для каждого входа и использует тривиальные однонаправленные операции в нескольких раундах для вычисления детерминированного результата. Его короткая выходная длина и простота операций сделали MD5 очень легким для взлома и восприимчивым к атаке «дня рождения».
Вы когда-нибудь слышали о том, что если вы поместите 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, должен был быть трудно вычисляемым для аппаратного обеспечения.
Биткойн имеет интересный способ хэширования данных с помощью SHA256, поскольку он выполняет две итерации алгоритма в своем протоколе. Обратите внимание: это не контрмера для атак на день рождения, так как ясно, что если hash (x) = hash (y), то hash (hash (x)) = hash (hash (y)). Вместо этого двойной SHA256 используется для смягчения «Атаки удлинения сообщения — тип атаки на хэш-функцию, заключающейся в добавлении новой информации в конец исходного сообщения». Атака опасна тем, что можно поменять запрос, а соответственно выполнить то, за что этот запрос отвечает (например, перевод денег)
SHA3 не был единственным прорывом, который вышел из конкурса хеширования NIST в 2006 году. Несмотря на то, что SHA3 выиграл, алгоритм, известный как BLAKE, занял второе место. Для реализации шардинга Ethereum 2.0 использует более эффективное. Алгоритм хэширования BLAKE2b, который является высокоразвитой версией BLAKE от конкурентов, интенсивно изучается за его фантастическую эффективность по сравнению с KECCAK256 при сохранении высокой степени безопасности. Вычисление BLAKE2b фактически в 3 раза быстрее, чем KECCAK на современном процессоре.
Кажется, что независимо от того, что мы делаем, мы просто либо (1) увеличиваем сложность внутренних хеш-операций, либо (2) увеличиваем длину хеш-выхода, надеясь, что компьютеры атакующих не будут достаточно быстрыми, чтобы эффективно вычислять ее коллизию. Мы полагаемся на двусмысленность предварительных прообразов односторонних операций для обеспечения безопасности наших сетей. То есть цель безопасности алгоритма хеширования состоит в том, чтобы сделать как можно более сложным для любого, кто пытается найти два значения, которые хешируются на один и тот же вывод, несмотря на то, что существует бесконечное количество возможных столкновений. «Как насчет будущего квантовых компьютеров? Будут ли алгоритмы хэширования безопасными?» Короткий ответ и текущее понимание заключаются в том, что да, алгоритмы хэширования выдержат испытание временем против квантовых вычислений. То, что квантовые вычисления смогут сломать, — это те проблемы, которые имеют строгую математическую структуру, основанную на аккуратных трюках и теории, такой как шифрование RSA. С другой стороны, алгоритмы хэширования имеют менее формальную структуру во внутренних конструкциях. Квантовые компьютеры действительно дают повышенную скорость в вычислении неструктурированных проблем, таких как хэширование, но в конце концов, они все равно будут грубо атаковать так же, как компьютер сегодня попытается это сделать. Независимо от того, какие алгоритмы мы выбираем для наших протоколов, ясно, что мы движемся к вычислительно-эффективному будущему, и мы должны использовать наше лучшее суждение, чтобы выбрать правильные инструменты для работы и те, которые, мы надеемся, выдержат испытание временем.
Дмитриев Марк — Технический аналитик и управляющий криптоактивами инвестиционного фонда GT Blockchain Investments