Виды хэш функций

• Наиболее распространенный вид хэш функции
• Стандарты хеширования: популярные варианты

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

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

Использование одного и того же ввода всегда приводит к одному и тому же результату. Если хоть малая часть входных данных изменяется, то и на выходе будет другой хэш.

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

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

Алгоритмы хеширования также должны быть устойчивы к «атакам нахождения прообраза». 

Наиболее распространенный вид хэш функции

Хэш-функцией называется всякая функция h:X -> Y, легко вычислимая и такая, что для любого сообщения M значение h(M) = H (свертка) имеет фиксированную битовую длину. X — множество всех сообщений, Y — множество двоичных векторов фиксированной длины.

Как правило хэш-функции строят на основе так называемых одношаговых сжимающих функций y = f(x1, x2) двух переменных, где x1, x2 и y — двоичные векторы длины m, n и n соответственно, причем n — длина свертки, а m — длина блока сообщения. 

Для получения значения h(M) сообщение сначала разбивается на блоки длины m (при этом, если длина сообщения не кратна m то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам M1, M2,.., MN применяют следующую последовательную процедуру вычисления свертки:

Ho = v,

Hi = f(Mi,Hi-1), i = 1,.., N,

h(M) = HN

Здесь v — некоторая константа, часто ее называют инициализирующим вектором. 

Она выбирается из разных соображений и может представлять собой секретную константу или набор случайных данных (выборку даты и времени, например).

При таком подходе свойства хэш-функции полностью определяются свойствами одношаговой сжимающей функции.

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

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

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

Стандарты хеширования: популярные варианты