Почему невозможно изменить криптографический хеш? - PullRequest
21 голосов
/ 07 июля 2011

Почему вы не можете просто повернуть алгоритм, как если бы вы могли повернуть математическую функцию?Как можно создать алгоритм, который не является обратимым?

И если вы используете радужный стол, что делает использование соли невозможным для ее взлома?Если вы создаете радужную таблицу с грубой силой для ее генерации, то она изобретает каждое возможное значение открытого текста (до длины), что в конечном итоге будет включать соль для каждого возможного пароля и каждую возможную соль (соль и пароль / текстпросто соберись как один кусок текста).

Ответы [ 5 ]

45 голосов
/ 07 июля 2011

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.,По сути, у них есть два варианта:

  1. Они могут игнорировать тот факт, что хэши засолены, и попытаться взломать пароли с помощью своей таблицы поиска, как есть. Однако шансы на то, что они действительно взломают пароль, значительно уменьшены. Например, даже если «shittypassword» находится в списке входных данных для проверки, скорее всего, «fa9elshittypassword» нет. Чтобы получить даже небольшой процент вероятности взлома пароля, который у них был раньше, им нужно будет протестировать на несколько порядков больше возможных паролей.

  2. Они могут пересчитывать хэши для каждого пользователя. Таким образом, вместо того, чтобы вычислять MD5 (пароль-пароль), для каждого пользователя X они вычисляют MD5 (Salt_of_user_X + пароль-пароль). Это не только вынуждает их вычислять новый хеш для каждого пользователя, которого они хотят взломать, но и, что более важно, оно не позволяет им использовать предварительно вычисленные таблицы (например, радужную таблицу), потому что они не могут знать, что Salt_of_user_X перед игрой, поэтому они не могут пересчитать хэши для проверки.

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

Надеюсь, это ответит на все ваши вопросы.

20 голосов
/ 07 июля 2011

Подумайте о 2 числах от 1 до 9999. Добавьте их.Теперь скажите мне последнюю цифру.

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

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

3 голосов
/ 07 июля 2011

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

Рассмотрим простой пример функции: «ИЛИ». Если вы примените это к своим входным данным 1 и 0, это даст 1. Но теперь, если вы знаете, что ответ «1», как вы отмените исходные данные? Ты не можешь. Это могло быть 1,1 или 0,1, а может 1,0.

Что касается соленых и радужных столов. Да, теоретически, у вас может быть радужная таблица, которая будет охватывать все возможные соли и пароли, но практически она слишком велика. Если вы попробовали все возможные комбинации строчных букв, прописных букв, цифр и двенадцати знаков препинания длиной до 50 символов, это (26 + 26 + 10 + 12) ^ 50 = 2,9 x 10 ^ 93 различных возможностей. Это больше, чем количество атомов в видимой вселенной.

Идея, лежащая в основе радужных таблиц, заключается в том, чтобы заранее рассчитать хэш для нескольких возможных паролей, а пароли намного короче 50 символов, поэтому это можно сделать. Вот почему вы хотите добавить соль впереди: если вы добавите '57sjflk43380h4ljs9flj4ay' в начале пароля. В то время как кто-то, возможно, уже вычислил хеш для «pa55w0rd», никто еще не вычислил хеш для «57sjflk43380h4ljs9flj4aypa55w0rd».

1 голос
/ 07 июля 2011

md5 - это 128 бит, то есть 3,4 * 10 ^ 38 комбинаций.

общее количество паролей длиной восемь символов:

  • только строчные буквы и цифры: 36 ^ 8 = 2,8* 10 ^ 12
  • в нижнем и верхнем регистре и цифры: 62 ^ 8 = 2,18 * 10 ^ 14

Вы должны хранить 8 байтов для пароля, 16 для значения md5, это 24Всего байтов на запись.

Таким образом, вам нужно около 67000G или 5200000G памяти для вашего радужного стола.Единственная причина, по которой на самом деле можно определить пароли, заключается в том, что люди используют очевидные.

1 голос
/ 07 июля 2011

Я не думаю, что md5 дает вам полный результат - поэтому вы не можете работать в обратном направлении, чтобы найти оригинальные вещи, которые были md5-ed

...