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

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

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

В качестве примера можно привести алгоритм MD5, часто используемый в P2P-загрузчиках и имеющий длину 128 бит. Пользователи могут сравнить хэш-значение загруженного файла с хэшем, предоставленным источником; совпадение указывает на вероятную целостность файла.

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

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

Поиск 'SHA256 Generator' показывает, что разные сайты, использующие один и тот же алгоритм, постоянно генерируют одинаковые хэш-значения для похожих входных текстов.

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

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

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

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

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

Если взять в качестве примера упомянутый MD5, возможно ли, чтобы разные файлы генерировали одно и то же хэш-значение? Ответ - да, но вероятность этого крайне мала. Это явление известно как криптографическая коллизия хэша, которая может произойти как случайно, так и в результате преднамеренной атаки. Стандартная вероятность столкновения для алгоритма MD5 составляет около 1/2¹²⁸, что делает случайное возникновение очень маловероятным. Однако MD5 считается уязвимым для атак с преднамеренным столкновением, поскольку получить одинаковое хэш-значение для двух разных открытых текстов довольно просто. Поэтому, хотя алгоритм MD5 все еще можно использовать для задач, не связанных с безопасностью, он больше не подходит для задач аутентификации безопасности (таких как аутентификация ключей или цифровые подписи).

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

Ethereum использует криптографическую хэш-функцию KECCAK-256, которую многие ошибочно идентифицируют как SHA-3 (в том числе в докторской диссертации основателя Celestia), потому что эта функция изначально была записана как 'sha3' в Solidity. Из-за путаницы он был впоследствии переименован в Keccak256.

В своих операциях MetaMask использует различные криптографические хэш-функции:

• Набор из 12 слов из случайной комбинации 2048 слов предложения BIP39 образует вспомогательные слова.
• Каждое слово соответствует значению, в совокупности образуя целые семена.
• MetaMask применяет функцию SHA-256 к начальному целому числу, генерируя закрытый ключ для импорта существующих кошельков. Иногда именно это требуется ввести при импорте существующего кошелька на новое устройство.
• Алгоритм ECDSA обрабатывает закрытый ключ для получения открытого ключа.
• MetaMask генерирует хэш открытого ключа с помощью функции Keccak-256, беря последние 20 байт хэша (переведенные в шестнадцатеричную систему, т.е. длиной в 40 букв или цифр) и префиксируя их 0x, который становится ETH-адресом.

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

Биткойн использует криптографическую хэш-функцию SHA-256. Здесь мы расскажем о том, как майнеры Bitcoin взаимодействуют с криптографическими хэш-функциями во время майнинга.

При добыче Биткойна майнеры объединяют данные о транзакциях с заголовком блока, содержащим детали транзакций, а также метаданные, такие как временные метки и случайные числа. Майнеры стремятся получить определенный хэш SHA-256, итеративно изменяя случайные числа (называемые "nonce") в заголовке блока, чтобы они соответствовали определенным критериям, обычно начинающимся с заданного количества ведущих нулей. Учитывая характер хэш-функции SHA-256, единственным способом обнаружения совместимого хэша является постоянное экспериментирование с различными случайными числами.

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

Помимо майнинга, криптографические хэш-функции играют ключевую роль в установлении связей между блоками и отслеживании изменений транзакций в системах блокчейн. Хеш-указатели служат в качестве структур данных, облегчающих индексацию, поиск и проверку изменений данных. Каждая транзакция в блокчейне проходит процедуру хэширования перед тем, как быть организованной в блоки. Затем хэш-указатель соединяет каждый блок с предыдущим, сохраняя хэш данных предыдущего блока. Взаимосвязанная природа блоков обеспечивает неизменность блокчейна; любое изменение транзакции приводит к появлению отдельного хэш-значения, что, соответственно, изменяет хэши всех последующих блоков. Например, рассмотрим блокчейн, состоящий из двух блоков:

• Блок 1: содержит хэши транзакций T1, T2 и T3.

• Блок 2: содержит хэши транзакций T4, T5 и T6, а также хэш Блока 1.

Если кто-то попытается подделать транзакцию T1 в Блоке 1, ему нужно будет перекалибровать хэш-значение Блока 1 и обновить новое значение в Блоке 2. Однако из-за однонаправленности и устойчивости криптографических хэш-функций к предызображениям изменить транзакцию T1 в Блоке 1 на основе хэш-значения Блока 2 довольно сложно.

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

В сфере блокчейна криптографическая хэш-функция выполняет несколько важных функций:

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

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

• Механизм консенсуса: В рамках механизма консенсуса Proof of Work (PoW) майнеры должны определить значение nonce, отвечающее требованиям сложности, выполняя хэш-функции.

Будущее криптографических хэш-функций

2 сентября 2022 года Виталик опубликовал в Твиттере вопрос (X), в котором спрашивал, какая криптографическая хэш-функция останется безопасной, если будет изобретен квантовый компьютер, использующий алгоритм Шора.

Источник: Твиттер Виталика

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

Заключение

Насколько надежны криптографические хэш-функции, такие как SHA-256? Число "256" в SHA-256 представляет собой 2, возведенное в степень 256 - цифра настолько огромная, что ее трудно понять конкретно.

Источник: 3Blue1Brown

Тем не менее, 3Blue1Brown привел яркую аналогию, которая поможет понять безопасность криптографических хэш-функций: представьте себе сценарий, в котором 4 миллиарда человек на Земле обладают компьютером с исключительными вычислительными возможностями, эквивалентными в 1 000 раз вычислительной мощности Google во всем мире. Одновременно представьте себе космос с 4 миллиардами планет и 4 миллиардами галактик, похожих на Млечный Путь! Даже при таких экстремальных условиях потребуется более 500 миллиардов лет, прежде чем появится шанс 1 к 4 миллиардам точно угадать "конкретные входные данные, необходимые для генерации выходного хэш-значения SHA-256".