Хеш и алгоритмы хеширования — это ключевые понятия, с которыми знакомятся новички в сфере блокчейна и которые которые всегда идут об руку с безопасностью.
Для поддержания децентрализованных сетей и консенсусных механизмов, среди которых Биткоин или Ethereum с тысячью узлов, соединённых с помощью p2p, необходимо «отсутствие доверия» и эффективная система подтверждения. Этим сетям нужны компактные способы шифрования информации, которые позволяли бы участникам проводить быструю и безопасную проверку.
Блок — одна из основных составляющих Биткоина и Ethereum. Блок содержит информацию о транзакциях, временных метках и прочие существенные метаданные. Огромную роль в обеспечении безопасности играет возможность сжимать большие объёмы информации о глобальном состоянии сети в короткие стандартные сообщения, которые при необходимости можно легко проверить. Эти сообщения и есть хеш.
Если изменить хотя бы один символ входящего значения, получится совершенно другой хеш!
Криптографические хеши используются везде, начиная с хранения паролей и заканчивая системами проверки. Их суть заключается в использовании детерминированного алгоритма, который берёт входные данные и создаёт строку с фиксированной длиной. Таким образом, одни и те же входные данные всегда будут преобразованы в одинаковые выходные данные.
Детерминизм важен не только для хешей, ведь даже если изменить один бит входных данных, получится совершенно другой хеш.
Проблема алгоритмов хеширования заключается в неизбежности коллизий. Так как длина строки такого хеша фиксированна, то могут существовать и другие входные данные, образующие тот же хеш. Коллизии — это плохо. Это значит, что злоумышленник может создавать коллизии по запросу, может передавать вредоносные файлы или данные с корректным хешем и выдавать эти данные за правильные. Хорошая функция хеширования должна максимально усложнять для злоумышленников процесс поиска путей создания входных данных с тем же значением хеша.
Процесс расчёта хеша не должен быть слишком эффективным, так как в этом случае злоумышленники легко могут вычислить коллизии. Алгоритмы хеширования должны быть устойчивыми к атакам нахождения прообраза. Необходимо максимально усложнять процесс расчёта шагов для нахождения исходного значения, из которого был создан хеш (например, прообраза).
Необходимо, чтобы способ вычисления x для s= hash(x) был практически невозможным.
Итак, «достойные» алгоритмы хеширования должны иметь три свойства:
- Если изменить один бит входящих данных, должен образоваться лавинный эффект и получиться совершенно другой хеш;
- Небольшая вероятность коллизий;
- Эффективность, которая не жертвует коллизионной устойчивостью.
Навигация по материалу:
Взлом хешей
Один из первых стандартов алгоритмов хеширования — хеш MD5. Этот алгоритм пользовался популярностью для проверки целостности файлов (контрольные суммы) и хранения хешированных паролей в базах данных веб-приложений.
Его функционал достаточно прост — он выдаёт строку с фиксированной длиной в 128 бит для каждого входного значения и использует стандартные односторонние операции в нескольких циклах для вычисления детерминированного выходящего значения. Из-за короткой длины выходного значения и простоты операций хеш MD5 очень легко поддаётся взлому, в частности атаке «дней рождения».
Атака «дней рождения»
Существует известное утверждение о том, что если в комнате находятся 23 человека, то шанс того, что у двое из них родились в один день, равняется 50%. Если в комнате находятся 70 человек, то эта вероятность увеличивается до 99,9%. Это происходит согласно принципу Дирихле, который утверждает, что если поместить 100 голубей в 99 коробок, то в одной из коробок окажется два голубя. Ограничение фиксированной длины выходящего значения означает, что существует фиксированный уровень комбинаций для коллизий.
Хеш MD5 настолько уязвим к коллизиям, что даже на простом процессоре Pentium с частотой 2,4 ГГц можно вычислить коллизии хеша всего за несколько секунд. Более того, широкое применение этого хеша на заре существования сети создало миллионы прообразов MD5, которые можно было найти с помощью обычного поиска Google по их хешу.
Разнообразие и эволюция алгоритмов хеширования
Начало: SHA1 и SHA2
АНБ (да-да, АНБ) уже в течение долгого времени является пионером по созданию стандартов алгоритмов хеширования. Именно АНБ предложило алгоритм Secure Hashing Algorithm или SHA1 с фиксированной длиной выходящего значения в 160 бит.
К сожалению, SHA1 ненамного превосходил MD5 благодаря увеличению значения, количества односторонних операций и их сложности, но этот хеш не предлагал основательных улучшений защиты от более мощных машин, создающих разные векторы атаки.
Как же улучшить алгоритм хеширования?
SHA3
В 2006 году Национальный институт стандартов и технологий США (NIST — National Institute of Standards and Technology) объявил конкурс на создание альтернативы алгоритму SHA2, которая должна была фундаментально отличаться по своему дизайну и стать новым стандартом. Из схемы алгоритмов хеширования под названием KECCAK (произносится как «кечак») появился алгоритм SHA3.
Хотя SHA3 и имеет схожее с предыдущими алгоритмами название, он сильно отличается по своей внутренней структуре механизмом криптографической губки. Этот механизм осуществляет случайные перестановки для поглощения и создания данных, служа источником случайности для входящих данных, которые будут попадать в алгоритм хеширования в будущем.
SHA3 сохраняет изначальное состояние с большим количеством битов информации, чем в выходящем значении, и тем самым превосходит ограничения прежних алгоритмов. Этот алгоритм стал стандартом NIST в 2015 году.
Хеширование и доказательство выполненной работы
В рамках внедрения алгоритма хеширования в протокол блокчейна для алгоритма доказательства выполненной работы Bitcoin использовал SHA256, а появившийся позже Ethereum — модифицированную версию SHA3 (KECCAK256). При выборе хеш-функции для блокчейна с доказательством выполненной работы очень важна эффективность вычисления хеша.
SHA256 Биткоина может быть крайне эффективно вычислен с помощью специального аппаратного обеспечения — специализированных интегральных микросхем (ASIC — Application Specific Integrated Circuits). Об использовании ASIC в майнинговых пулах и о том, как они приводят к централизации вычисления, написано очень много. Доказательство выполненной работы провоцирует создание пулов из групп эффективных в вычислительном отношении машин, благодаря чему увеличивается так называемая «хеш-мощность» или количество хешей, которые может вычислять машина за определённый период времени.
[прим.ред.: Майнинг в пуле против соло-майнинга никак не увеличивает хэш-мощность участвующего. скорость нахождения хэшей при фиксированной хэш-мощности оборудования участника не меняется, если сравнивать с соло-майнингом. Однако, собранная от разных участников хэш-мощность всех участников пула, позволяет находить блоки чаще, чем у каждого из единичных участников пула. Соответственно, пул находит блоки чаще и выплачивает вознаграждение за блок всем участникам пула в единицу времени пропорционально хэш-мощности, участвующей в пуле — за вычетом комиссии пула. Например, участник с 1Ghash/s при майнинге Биткоина соло мог бы ожидать событие «нахождение блока» — и получение за него награды в размере 12,5 BTC — когда-нибудь в течение пяти лет (например!). Участие же в пуле той же мощностью 1Ghash/s (при условии не изменения сложности на интервале пяти лет!) позволяет тому же майнеру получать 12,5 BTC частями, равномерно в течение тех же пяти лет. Это решает проблему майнера с выплатами фиата в реале на поддержание фермы].
В Ethereum внедрён модифицированный алгоритм SHA3 — KECCAK256. Алгоритм доказательства выполненной работы Ethereum под названием Dagger-Hashimoto требовал от аппаратного обеспечения слишком много памяти для вычислений.
Биткоин и двойной SHA256
Биткоин хеширует данные с помощью SHA256 необычным способом: он запускает в протоколе два вида алгоритма. Нужно понимать, что это НЕ мера против атак «дней рождения», потому что если hash(x) = hash(y), то hash(hash(x)) = hash(hash(y)). Двойной алгоритм SHA256 используется для борьбы с атакой удлинением сообщения.
Если злоумышленники знают длину входных данных хеша, то могут заставить хеш-функцию взять определённую часть внутреннего состояния, добавив секретную строку к значению хеша. Из-за этого недостатка алгоритма SHA256 из семейства алгоритмов SHA2 Биткоин вычисляет хеш дважды.
Ethereum 2.0 и BLAKE
SHA3 — не единственное изобретение, появившееся в результате конкурса NIST в 2006 году. Второе место занял алгоритм BLAKE. Для сегментирования Ethereum 2.0 более эффективное хеширование — это практически обязательное требование, которое серьёзно исследуется командами разработчиков. Тщательному анализу подвергается алгоритм хеширования BLAKE2b — сильно усовершенствованная версия BLAKE — из-за своей фантастической эффективности по сравнению с KECCAK256 и высокого уровня безопасности.
На современном процессоре вычисление с помощью BLAKE2b производится в три раза быстрее, чем с помощью KECCAK.
Перспектива: будущее алгоритмов хеширования
Похоже, что будущее алгоритмов хеширования сводится либо к (1) увеличению сложности внутренних операций хеширования, либо к (2) увеличению длины выходящего значения хеша в надежде на то, что компьютеры злоумышленников не успеют вычислить коллизии.
Для обеспечения безопасности сетей разработчики полагаются на неоднозначность прообразов односторонних операций. Таким образом, в целях безопасности алгоритма хеширования необходимо как можно сильнее усложнить процесс поиска двух значений хеша с одинаковыми выходными данными, несмотря на наличие бесконечного количества возможных коллизий.
Что насчёт квантовых вычислений будущего? Устоят ли алгоритмы хеширования против них?
Если коротко, то исходя из текущей ситуации, можно ответить, что да, алгоритмы хеширования пройдут проверку временем и устоят против квантовых вычислений. Квантовые вычисления могут создать проблемы касательно строгих базовых математических структур с использованием ловких трюков и таких теорий, как шифрование по методу RSA. Однако, алгоритмы хеширования имеют более формальную внутреннюю структуру.
Квантовые компьютеры действительно ускоряют процесс вычисления таких неструктурированных задач, как хеширование, но они всё равно будут использовать атаку «грубой силой», как это делают обычные компьютеры сегодня.
Независимо от того, какие алгоритмы используются в протоколах, ясно одно — нас ждёт эффективное в отношении вычислений будущее и мы должны разумно подходить к выбору правильных инструментов для этого дела, и тогда алгоритмы выдержат проверку временем.