Криптостойкость хеш функций «на пальцах» или зачем нужна математика программисту

Итак, привет всем кто решил уделить малую часть своего времени этой статье. Это мои первые попытки написания, так что попрошу не судить строго(есть куда расти:)). 

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

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

Позволю себе заметить: если целью вашего обучения является не больше, чем “клепание” сайтов на фрилансе, то вам эти знания никогда и не понадобятся, уж поверьте мне, НО если вы хотите быть художником в мире такого искусства как криптография или чуть дальше "низкоуровневого программирование", то без понимая, как минимум, основ - вам не выжить. Итак, прошу:

Функция

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

Хеш функция

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

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

Давайте-ка зададим хеш-фукнцию для преобразования паролей на вашем сервиса так:

Теперь каждый раз при регистрации нового пользователя введеный им пароль будет находить остаток от деления на 5 и сохранять его в базе данных, это и будет хешем. Если же вы не знакомы с математикой от слова совсем, но знакомы на каком либо уровне с программирование то привожу пример на языке C#:

private int GetHash(int _password) => _password % 5;

Коллизия

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

Наша же хеш функция образует коллизию на каждом пароле кратном 5.

Console.WriteLine($"Хеш: {GetHash(5)}"); // Хеш: 0
Console.WriteLine($"Хеш: {GetHash(10)}"); // Хеш: 0
Console.WriteLine($"Хеш: {GetHash(555)}"); // Хеш: 0

"Ломануть" её можно люб...да тут и слов не надо, я думаю.

Криптостойкость

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

Система является безопасной ровно до того момента, пока её взлом стоит дороже хранимой в ней информации.

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

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

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

Соли

"Соли", кстати, применяются в UNIX системах для хранения паролей.

Соль является некоторой последовательностью символов. К примеру, пользователь вводит пароль, который объединяется с солью в одну строку и из которой уже и получается хеш.

НО соль не усложняет атаку на какой-либо пароль в отдельности. Соль повышает сложность при построеннии коллизий типа f(x) = f(y) к группе паролей, но не к каждому по отдельности!

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

Математика

Как и обещал, объясняю пользу математики, а точнее действительно ли важно её понимание.

Теория Множеств. Инъективность.

Допустим у нас есть 2 множества. Пусть множество P - пароли и множество H - хеши.

Отображения нашего множества не должны быть инъективными

Инъективность - это хотя бы один элемент из множества H является отображением более одного элемента из множества P. Приведу пример инъективной и не инъективной функции:

Функция не инъективна(один хеш представляет два разных пароля):

Функция инъективна(каждый хеш представляет разный пароль):

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

Заключение

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

Спасибо!