Итак, привет всем кто решил уделить малую часть своего времени этой статье. Это мои первые попытки написания, так что попрошу не судить строго(есть куда расти:)).
Если вы понимаете о чём говорите, то должны суметь объяснить свои знания языком, доступным каждому.
Сегодня я попытаюсь вкратце или “на пальцах” объяснить как работают хеш функции, что определяет криптостойкость и почему вам понадобятся знания математики, если вы рассчитываете стать востребованным специалистом.
Для начала хотелось бы дать понять опытным и уже разбирающимся в этой теме читателям(если вдруг таковые чудным образом оказались тут): я далеко не специалист в криптографии и даже близко не претендую на подобные звания. Статья исключительно для начинающих или же совсем не разбирающихся людей, для вас я собрал немного интересных фактов с простор бескрайнего интернета.
Позволю себе заметить: если целью вашего обучения является не больше, чем “клепание” сайтов на фрилансе, то вам эти знания никогда и не понадобятся, уж поверьте мне, НО если вы хотите быть художником в мире такого искусства как криптография или чуть дальше "низкоуровневого программирование", то без понимая, как минимум, основ - вам не выжить. Итак, прошу:
Функция
Для начала поймем что такое функция. Если говорить на сложном и непонятном, для этой статьи, языке, то теория множеств даёт определение функции как ее графику, но я не собираюсь углубляться в дебри дискретной математики, так что обозначим функцию как обычное преобразование входных данных в шашлыки выходные. Работает точно так же как любый метод/функция на любом языке программирования.
Хеш функция
В принципе, тоже самое. Хеш-функция принимает, допустим, пароль как входные данные и выдаёт хеш как выходные.
А теперь представим: у вас имеется какой-либо сервис, аутентификация на котором проходит посредством ввода логина и пароля. Как, возможно, вы уже знаете на сервере хранятся не пароли, а хеши, которые генерируются посредством тех самых хеш-функций.
Давайте-ка зададим хеш-фукнцию для преобразования паролей на вашем сервиса так:
Теперь каждый раз при регистрации нового пользователя введеный им пароль будет находить остаток от деления на 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. Приведу пример инъективной и не инъективной функции:
Функция не инъективна(один хеш представляет два разных пароля):
Функция инъективна(каждый хеш представляет разный пароль):
Будет, опять же, бесмысленно приводить сейчас какие то сложные примеры, требующие какой либо математической подготовки, в статье "объяснение на пальцах", но если же кому то будет интересно об этом узнать, так же подготовлю отдельные части статьи по теории чисел и множеств.
Заключение
На этом в общем то статья подошла к концу и раз уж вы дочитали до этого момента, надеюсь она была для вас полезна. В случае появления заинтересовавшихся в продолжении, буду рад написать ещё несколько статей :)
Спасибо!
P.S.
P.S. Как говорит один из гениев дискретной математики: "Не дай господь кто-либо из вас в будущем решит заняться криптографией";
Комментарии (16)
Protos
09.02.2022 20:10+3В статье должен был быть вывод: на самом деле разрабу знать математику не надо, ибо попытка написать свою хеш-функцию ведет лишь к тому что ее взломают. А значит нужно использовать встроенные в язык программирования хеш-функции - для их встраивания знать математику не надо и они безопасны ровно настолько, насколько боги математики закладывали в них безопасность при разработке действительно стойких хеш-функций.
NTDLL
09.02.2022 20:34Во всех этих алгоритмах есть статистические параметры, причём нелинейные. И их сложно прикинуть в голове. Если разраб вообще знает об их существовании. А ведь статистические свойства криптоалгоритмов - их основа.
попытка написать свою хеш-функцию ведет лишь к тому что ее взломают
Не только к этому. Можем получить ни с чем не совместимую штуковину, использование которой весьма коварно
ReadOnlySadUser
10.02.2022 10:43А ведь статистические свойства криптоалгоритмов - их основа
И зачем рядовому программисту их знать? :) Да даже не рядовому, а человеку который занимается непосредственно реализацией криптографии? Куда важнее знать об ILP, об устройстве кэша, ключевых системах, умение грамотно пользоваться профилировщиком ну и да, иногда потребуется немножко понимать как работает арифметика в конечных полях, но это за вечер-другой можно разобраться.
MentalBlood
10.02.2022 10:28Уметь писать свою не обязательно, но иметь представление о том что это и какое бывает пригодится при выборе конкретной (или отказе от них вообще)
kahi4
09.02.2022 21:58+8Вообще подобные рассказы начинают с "а зачем это вообще нужно?".
Попробуем улучшить статью: зачем? Ну хранили бы пароль и хватит. Оказывается, что мы не хотим чтобы в случае утечки кто-то получил все пароли, отсюда нам нужно преобразовывать пароль каким-то образом в белиберду чтобы нельзя было преобразовать обратно. Функцию, которая преобразовывает одно множество в другое без возможности преобразования обратно и принято называть хеш-функцией. Самая простая: f(x) = 1. попробуй преобразовать обратно.
Но теперь у нас новая проблема: любой пароль даст ту же единицу и, соответственно, быстро подберется. Т.е. нам нужна функция, которая преобразует входную строку с минимум конфликтов, особенно для малых изменений (пароли, условно, находятся в пределах 20 символов и много похожих).
Допустим, мы нашли такую функцию (это очень сложно), которая на изменение каждого бита будет выдавать полностью непредсказуемую строку и обратно разобрать это нельзя.
Но нам и не нужно, если утекла база - нам не нужен оригинальный пароль, нам нужен любой, который даст такой же хеш. Как следствие - будет достаточно просто перебрать кучу вариантов и получить доступы.
Но, как мы заметили, если хотя бы немного изменить входное значение (пароль) - выход поменяется значительно. Таким образом мы можем дописывать какое-то значение, которое не хранится в базе данных, к каждому паролю, тогда пароли, которые дают конфликты с теми, что мы украли из базы данных, нам не помогут - если ему дописать такую же соль - результат будет уже значительно другой и пароль уже не подойдёт (это ещё одно требование к криптостойкой хеш функции - "абсорбция" не должна выполняться, т.е. F(A) = F(B), но F(A+C) !== F(B+C)). Вот такое не хранимое в бд значение и называется солью.
Осталось только выяснить что делать если соль утеряна или утекла...
Нужен ли матан чтобы написать такую хеш функцию? Естественно. Нужно ли самому придумывать такую функцию? Нет. Любое статистическое отклонение позволит значительно упростить перебор, и задача разработки такой функции требует огромный математический опыт и багаж.
Нужен ли матан чтобы использовать такую функцию? Вряд ли, ложное ощущение что вы понимаете что происходит и умнее чем интернет опаснее полного не понимания.
miksir
09.02.2022 23:05+8Вот такое не хранимое в бд значение и называется солью.
У понятия "соль" при хранении паролей есть вполне устоявшийся смысл, и это не совсем то, что вы написали. В статье как раз верно раскрыт смысл "соли" при хранении паролей. Это удлинитель паролей, цель которого - защита от брутфорса пачки хешей или использования радужных таблиц. Для этих целей важна уникальность соли для каждого хеша, а вот задачи прятать соль от хеша нет. По-этому соль хранят рядом с хешом.
kahi4
09.02.2022 23:11+2Посыпаю голову пеплом, мой недосмотр. Хах, наглядная иллюстрация что никогда не стоит изобретать велосипед, думаю что умнее всех.
davidnatro Автор
09.02.2022 23:33-3ложное ощущение что вы понимаете что происходит и умнее чем интернет опаснее полного не понимания.
Но разве в какой-либо части статьи я подразумевал, что я умнее интернета? Или же что имею полное понимание происходящего? Прошу обратить внимание на вступительную часть статьи:
Для начала хотелось бы дать понять опытным и уже разбирающимся в этой теме читателям(если вдруг таковые чудным образом оказались тут): я далеко не специалист в криптографии и даже близко не претендую на подобные звания. Статья исключительно для начинающих или же совсем не разбирающихся людей, для вас я собрал немного интересных фактов с простор бескрайнего интернета.
Статья была написано исключительно в целях приобретения некого опыта "журнализма" и объяснения элементарных вещей людям буквально ни разу не слышавших о криптографии.
saboteur_kiev
10.02.2022 02:55+2дать понять опытным и уже разбирающимся в этой теме читателям(если вдруг таковые чудным образом оказались тут)
Как бы Хабр как раз тот ресурс, где таких читателей совсем не чудом, а закономерностью тут должно быть достаточно. так что вы сразу не так начали.
YourgenAP
10.02.2022 17:21+3Как человек, изучавший дискретную математику, я понял, что пытался донести автор, хоть и в статье огромное множество ошибок, в том числе математических определений. Но если брать человека с околонулевыми знаниями, то статья - набор какой-то информации, которая даже никак особо не объяснена.
Как уже писали выше, не объяснен смысл хеш-функций, зачем они нужны и в чем смысл. Приведен пример хеша по модулю, хотя есть еще хеш по умножению (из простых). Коллизии: из текста следует, что коллизия при mod 5 возникнет только у чисел кратных 5, хотя коллизия возникнет и для чисел 6, 11, 26, 41, 251 или 33, 88, 218, 7898.
Почему отображение Р на Н (что и является функцией в ее математическом определении) не должно быть инъективным для хеш-функций не понятно. То есть автор напрямую пишет, что хеш-функция может содержать коллизии и это нормально, да и бороться с этим не должно. И да, инъективность - это свойство функции, что любое значение из области значений является отображением не более чем одного значения из области определения. А в статье дано нечто странное и среднее между суръективностью и инъективностью.
В общем и целом: статья не объясняет ни основы хеширования, ни его смысл, ни принцип работы и важные свойства хеш функций (например, что идеальная хеш функция - инъективна для любого количества значение в области определения) и для новичка не представляет никакой ценности.
dmitrysvd
11.02.2022 20:24-1Почему отображение Р на Н (что и является функцией в ее математическом определении) не должно быть инъективным для хеш-функций не понятно.
То есть автор напрямую пишет, что хеш-функция может содержать коллизии и это нормально, да и бороться с этим не должно.
Как можно бороться с коллизиями, и как она может быть инъективна, если по определению у хеш-функции область определения бесконечна, а область значений конечна?
gecube
Из статьи совершенно непонятно - что такое хэш функция. Почему мы не можем попросту построить функцию, которая будет брать исходный аргумент и, например, попросту его удваивать. Причем можно как строково или численно. Это будет хэш? На мой взгляд, нет.
1 -> 2, 2 -> 4, 3 -> 6 etc.
или "1" -> "11", "2" -> "22" и пр.
Тогда что такое хэш? Это, очевидно, необратимая функция. При этом мы еще и пытаемся эффективно (в бытовом плане) неограниченное множество исходных значений утрамбовать во вполне конечное множество выходных значений, нет?
Как-то про это все очень вскользь.
lihogub
Нам преподаватель по Computer Science на паре про хэш-функции показал картинку мясорубки и все всё поняли
sshikov
Ну, на самом деле в оригинале hash это не фарш. Это все-таки скорее котлета. То есть у нее есть некий фиксированный размер, что характерно.
sshikov
>При этом мы еще и пытаемся эффективно (в бытовом плане) неограниченное множество исходных значений утрамбовать во вполне конечное множество выходных значений, нет?
Да. Хотя неограниченность тут вроде не обязательна. Достаточно чтобы одно множество было «больше» другого.
Причем, чтобы все было понятно, было бы вполне достаточно не изобретать велосипед, а просто прочитать статью в википедии, где уже написано вполне внятно (и по сути — как у вас). Необратимость вытекает логически из того, что пространство значений исходных данных больше, чем пространство результата — поэтому часть значений потеряется, поэтому же и коллизии.