Алгоритмы хеширования и их будущее

0

Хеш и алгоритмы хеширования — это ключевые понятия, с которыми знакомятся новички в сфере блокчейна и которые которые всегда идут об руку с безопасностью. Для поддержания децентрализованных сетей и консенсусных механизмов, среди которых Биткойн или 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 и имеет схожее с предыдущими алгоритмами название, он сильно отличается по своей внутренней структуре механизмом криптографической губки. Этот механизм осуществляет случайные перестановки для поглощения и создания данных, служа источником случайности для входящих данных, которые будут попадать в алгоритм хеширования в будущем.

Обработка входящих данных с помощью криптографической губки KECCAK256

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 требовал от аппаратного обеспечения слишком много памяти для вычислений.

Оставьте ответ

Ваш электронный адрес не будет опубликован.