Хеш-функции. Часть 1: Основы

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

Что такое хеш-функция?

Хеш-функция — это функция, которая принимает на вход данные произвольной длины и выдаёт на выходе данные фиксированной длины (хеш или дайджест), обладающая 3 свойствами: 

1) Устойчивость к нахождению прообраза.

2) Устойчивость к нахождению второго прообраза.

3) Устойчивость к коллизиям.

Также на практике нам важно, что при малейшем изменении входных данных — выходные изменяются неузнаваемо.

Но если более подробно, то первое свойство означает, что практически невозможно восстановить входные данные из выходных.

Второе свойство означает, что на основе входных данных и их дайджеста практически невозможно найти другие входные данные, имеющие тот же дайджест.

Третье свойство схоже со вторым, но мы ищем уже два разных входа, которые дадут один выход. То есть ни один из входов не зафиксирован заранее.

Методы обеспечения безопасности хеш-функций

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

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

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

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

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

Однако, мы берём 256 бит, так как они дают 128 бит защиты от атаки на поиск коллизий. Но если вам нужно обеспечить лишь первые два свойства, то хватит 128 хеша, он как раз и даёт 2^128 операций.

Есть знаменитая задача о парадоксе дней рождения: «Сколько человек должны находится в одной комнате, чтобы с вероятностью 50% хотя бы у двух из них совпали дни рождения?». Так как всего 365 дней, то нам достаточно 23 выбранных наугад человека. 

Вычислить это можно так: берем любого первого человека, вероятность того, что у второго с ним не совпал день рождения равна  364/365, у третьего с первыми двумя 363/365 и так далее до 343/365. 

Но нам нужно вычислить обратную вероятность вычисляем произведение этих вероятностей и вычитаем из единицы. На выходе получаем, что среди 23 человек вероятность найти двух с одинаковым днем рождения равна приблизительно 50,7%

Если обобщить результат этой задачи, то выходит, что когда мы генерируем строки из пространства 2^N, можно с вероятностью 50% ожидать, что кто-то найдет коллизию после того, как сгенерирует примерно 2^(N/2) строк.

Таким образом, чтобы обеспечить устойчивость от коллизий со 128 битами защиты нам нужен дайджест 256 бит.

Именно из-за недостаточной устойчивости к коллизиям MD5 и SHA1 считаются небезопасными.

Хеш-функции на практике

Начну с того, что захешировать что-либо вы можете без проблем, используя библиотеку OpenSSL и ваш терминал.

echo -n "какие-то слова" | openssl dgst -sha256

Вместо sha256 можете использовать любую другую хеш-функцию. Или вместо строк можно аргументом передать файл.

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

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

Таким образом хеш-функция обеспечит сокрытие базового значения и связывание (не даст кому-то вместо первоначальных данных подсунуть другие).

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

Для проверки целостности подключаем стили и библиотеки таким образом:

<link rel="stylesheet" href="https://my-provider.com" integrity="sha256-ХЭШ_СТИЛЯ" crossorigin="anonymous">

<script src="https://my-provider.com" integrity="sha256-ХЭШ_СКРИПТА" crossorigin="anonymous"></script>

Ну, и самое распространённое использование хеш-функций  (вроде Argon2, bcrypt) заключается в хранении паролей в безопасном виде.

Храним только хеш, а при получении пароля от пользователя хешируем его и сверяем с настоящим хешем.

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

На этом первая часть этого поста закончилась. В следующий раз расскажу подробнее про внутреннее устройство SHA2, SHA3, их преимущества и недостатки. Расскажу про XOF функции и когда их нужно применять.