MD5 разработан, чтобы быть криптографически необратимым . В этом случае наиболее важным свойством является то, что в вычислительном отношении невозможно найти обратную сторону хеша, но легко найти хеш любых данных. Например, давайте подумаем только о работе с числами (в конце концов, двоичные файлы можно интерпретировать как очень длинное число).
Допустим, у нас есть число "7", и мы хотим взять его хеш. Возможно, первое, что мы попробуем в качестве нашей хеш-функции, - это «умножить на два». Как мы увидим, это не очень хорошая хеш-функция, но мы попробуем ее, чтобы проиллюстрировать ситуацию. В этом случае хеш числа будет «14». Это было довольно легко рассчитать. Но теперь, если мы посмотрим на то, как трудно это изменить, мы обнаружим, что это так же просто! Учитывая любой хеш, мы можем просто разделить его на два, чтобы получить оригинальное число! Это не очень хороший хеш, потому что весь смысл хэша в том, что вычислить обратное гораздо сложнее, чем вычислить хеш (это самое важное свойство по крайней мере в некоторых контекстах) .
Теперь давайте попробуем еще один хеш. Для этого мне нужно будет представить идею арифметики часов. На часах не бывает бесконечного количества чисел. На самом деле, он просто идет от 0 до 11 (помните, 0 и 12 одинаковы на часах). Так что если вы добавите один к 11, вы просто получите ноль. Вы можете распространить идеи умножения, сложения и возведения в степень на часы. Например, 8 + 7 = 15, но 15 на часах - это действительно только 3! Так что на часах вы бы сказали 8 + 7 = 3! 6 * 6 = 36, но на часах 36 = 0! так 6 * 6 = 0! Теперь для концепции полномочий вы можете сделать то же самое. 2 ^ 4 = 16, но 16 - это просто 4. Так что 2 ^ 4 = 4! Теперь вот как это связано с хешированием. Как насчет того, чтобы мы попробовали хеш-функцию f (x) = 5 ^ x, но с арифметикой часов. Как вы увидите, это приводит к некоторым интересным результатам. Давайте попробуем взять хеш 7, как и раньше.
Мы видим, что 5 ^ 7 = 78125, но на часах, это всего лишь 5 (если вы сделаете математику, вы увидите, что мы завернули в часы 6510 раз). Итак, мы получаем f (7) = 5. Теперь возникает вопрос: если бы я сказал вам, что хэш моего номера равен 5, вы сможете выяснить, что мой номер равен 7? Ну, на самом деле очень сложно вычислить обратное значение этой функции в общем случае. Люди намного умнее меня доказали, что в некоторых случаях отменить эту функцию на 1013 * путь сложнее, чем рассчитать ее вперед. (РЕДАКТИРОВАТЬ: Немо указал, что это на самом деле не было "доказано"; фактически, единственная гарантия, которую вы получаете, - то, что многие умные люди долго пытались найти легкий способ сделать это, и ни один из них не удался.) Проблема обращения этой операции называется « Задача дискретного логарифма ». Ищите это для более глубокого охвата. Это как минимум начало хорошей хеш-функции.
В реальных хэш-функциях идея в основном та же: вы обнаружите некоторую функцию, которую трудно изменить. Люди, намного умнее меня, создали MD5 и другие хеши, чтобы их было трудно перевернуть.
Теперь, возможно, раньше вам пришла в голову мысль: «Было бы легко вычислить обратное! Я бы просто взял хеш каждого числа, пока не нашел бы тот, который соответствовал!»Теперь для случая, когда все числа меньше двенадцати, это было бы возможно.Но для аналога реальной хеш-функции представьте, что все задействованные числа огромны .Идея состоит в том, что все еще относительно легко вычислить хеш-функцию для этих больших чисел, но поиск по всем возможным входным данным становится намного сложнее и быстрее.Но то, на что вы наткнулись, - все еще очень важная идея: поиск в области ввода для ввода, который даст соответствующий результат.Радужные таблицы представляют собой более сложную вариацию идеи, в которой предварительно вычисленные таблицы пар ввода-вывода используются умными способами для обеспечения возможности быстрого поиска по большому количеству возможных входных данных.
Теперь давайте скажем, чтоВы используете хеш-функцию для хранения паролей на вашем компьютере.Идея такова: компьютер просто хранит хэш правильного пароля.Когда пользователь пытается войти в систему, вы сравниваете хэш входного пароля с хешем правильного пароля.Если они совпадают, вы предполагаете, что у пользователя правильный пароль.Это выгодно потому, что если кто-то украл ваш компьютер, у него все равно не будет доступа к вашему паролю, а только к его хешу.Поскольку умные люди разработали хэш-функцию так, чтобы с ней было трудно справиться, они не могут легко получить из нее ваш пароль.
Лучшая ставка злоумышленника - атака грубой силой, когда они пробуют несколько паролей.Точно так же, как вы можете использовать цифры меньше 12 в предыдущей задаче, злоумышленник может использовать все пароли, состоящие только из цифр и букв длиной менее 7 символов, или все слова, которые отображаются в словаре.Здесь важно то, что он не может попробовать всех возможных паролей, поскольку существует слишком много возможных 16-символьных паролей, например, для теста ever .Таким образом, дело в том, что злоумышленник должен ограничить возможные пароли, которые он проверяет, иначе он никогда даже не проверит небольшой процент из них.
Теперь, что касается соли, идея такова: что если два пользователябыл тот же пароль?У них будет такой же хэш.Если подумать, злоумышленнику не обязательно взламывать пароль каждого пользователя в отдельности.Он просто просматривает все возможные входные пароли и сравнивает хеш со всеми хешами.Если это соответствует одному из них, то он нашел новый пароль.Мы действительно хотели бы заставить его вычислить новый хеш для каждой комбинации пользователь + пароль, которую он хочет проверить.Идея заключается в том, что хэш-функция должна немного отличаться для каждого пользователя, поэтому он не может повторно использовать один набор предварительно вычисленных значений для всех пользователей.Самый простой способ сделать это - прикрепить некоторую случайную строку к паролю каждого пользователя перед тем, как вы возьмете хеш, где случайная строка различна для каждого пользователя.Так, например, если мой пароль «shittypassword», мой хэш может отображаться как MD5 («6n93nshittypassword»), а если ваш пароль «shittypassword», ваш хэш может отображаться как MD5 («fa9elshittypassword»).Этот маленький "fa9el" называется "солью", и он отличается для каждого пользователя.Например, моя соль "6n93n".Теперь эта небольшая часть, прикрепленная к вашему паролю, просто хранится на вашем компьютере.Когда вы пытаетесь войти с паролем X, компьютер может просто вычислить MD5 («fa9el» + X) и посмотреть, соответствует ли он сохраненному хешу.
Таким образом, базовая механика входа в систему остается неизменной, но для злоумышленника теперь стоит более сложная задача: вместо списка хэшей MD5, они сталкиваются со списком сумм и солей MD5.,По сути, у них есть два варианта:
Они могут игнорировать тот факт, что хэши засолены, и попытаться взломать пароли с помощью своей таблицы поиска, как есть. Однако шансы на то, что они действительно взломают пароль, значительно уменьшены. Например, даже если «shittypassword» находится в списке входных данных для проверки, скорее всего, «fa9elshittypassword» нет. Чтобы получить даже небольшой процент вероятности взлома пароля, который у них был раньше, им нужно будет протестировать на несколько порядков больше возможных паролей.
Они могут пересчитывать хэши для каждого пользователя. Таким образом, вместо того, чтобы вычислять MD5 (пароль-пароль), для каждого пользователя X они вычисляют MD5 (Salt_of_user_X + пароль-пароль). Это не только вынуждает их вычислять новый хеш для каждого пользователя, которого они хотят взломать, но и, что более важно, оно не позволяет им использовать предварительно вычисленные таблицы (например, радужную таблицу), потому что они не могут знать, что Salt_of_user_X перед игрой, поэтому они не могут пересчитать хэши для проверки.
Таким образом, в основном, если они пытаются использовать предварительно вычисленные таблицы, эффективное использование соли значительно увеличивает возможные входные данные, которые они должны проверить, чтобы взломать пароль, и даже если они не используют предварительно вычисленные значения. таблиц, он по-прежнему замедляет их в N раз, где N - это количество паролей, которые вы храните.
Надеюсь, это ответит на все ваши вопросы.