Почему невозможно реверсировать криптографический хэш?


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

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

5   16   2011-07-07 02:33:40

5 ответов:

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? Ну, на самом делеочень трудно вычислить обратную сторону этой функции в общем случае. Люди гораздо умнее меня доказали, что в некоторых случаях обращение этой функции в обратную сторону намного сложнее, чем ее вычисление вперед. (правка: Немо указал на самом деле, единственная гарантия, которую вы получаете, заключается в том, что многие умные люди долгое время пытались найти простой способ сделать это, и ни один из них не преуспел.) задача обращения этой операции называется "дискретной логарифмической задачей ". Посмотрите его для более глубокого охвата. Это, по крайней мере, начало хорошей хэш-функции .

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

Теперь, возможно, раньше вам пришла в голову мысль: "было бы легко вычислить обратное! Я просто возьму хэш каждого числа, пока не найду то, которое соответствует!- Так вот, для случая, когда все числа меньше двенадцати, это вполне осуществимо. Но для аналога реальной хэш-функции представьте себе все вовлеченные числа являютсяогромными . Идея заключается в том, что вычислить хэш-функцию для этих больших чисел все еще относительно легко, но поиск по всем возможным входным данным становится сложнее намного быстрее. Но то, на что вы наткнулись, все еще очень важная идея: поиск во входном пространстве для входа, который даст соответствующий выход. Радужные таблицы-это более сложная вариация идеи, которая использует предварительно вычисленные таблицы пар "вход-выход" умными способами, чтобы сделать ее возможен быстрый поиск по большому количеству возможных входов. Теперь предположим, что вы используете хэш-функцию для хранения паролей на вашем компьютере. Идея заключается в следующем: компьютер просто хранит хэш правильного пароля. Когда пользователь пытается войти в систему, вы сравниваете хэш входного пароля с хэшем правильного пароля. Если они совпадают, вы предполагаете, что у пользователя есть правильный пароль. Причина, по которой это выгодно, заключается в том, что если кто-то украдет ваш компьютер, они по-прежнему не имею доступа к вашему паролю, только хэш его. Поскольку хэш-функция была разработана умными людьми, чтобы быть трудно принять обратную сторону, они не могут легко получить ваш пароль от него.

Лучшая ставка злоумышленника-это атака bruteforce, где он пытается использовать кучу паролей. Так же, как вы могли бы попробовать цифры меньше 12 в предыдущей задаче, злоумышленник может попробовать все пароли, состоящие только из цифр и букв длиной менее 7 символов, или все слова которые появляются в словаре. Здесь важно то, что он не может попробовать все возможные пароли, потому что существует слишком много возможных 16-символьных паролей, например, чтобы когда-либо проверить. Таким образом, суть в том, что злоумышленник должен ограничить возможные пароли, которые он проверяет, иначе он никогда не проверит даже небольшой процент из них.

Теперь, что касается соли, идея заключается в следующем: что, если у двух пользователей был один и тот же пароль? У них будет тот же самый гашиш. Если ты подумайте об этом, злоумышленник на самом деле не должен взломать каждый пароль пользователя по отдельности. Он просто перебирает все возможные входные пароли и сравнивает хэш со всеми хэшами. Если он соответствует одному из них, то он нашел новый пароль. Что мы действительно хотели бы заставить его сделать, так это вычислить новый хэш для каждой комбинации user+password, которую он хочет проверить. Вот в чем суть соли: вы делаете хэш-функцию немного другой для каждого пользователя, так что он не может повторное использование одного набора предварительно вычисленных значений для всех пользователей. Самый простой способ сделать это-прикрепить некоторую случайную строку к паролю каждого пользователя, прежде чем вы возьмете хэш, где случайная строка отличается для каждого пользователя. Так, например, если мой пароль "shittypassword", мой хэш может отображаться как MD5("6n93nshittypassword"), а если ваш пароль "shittypassword", ваш хэш может отображаться как MD5("fa9elshittypassword"). Этот маленький кусочек "fa9el" называется "соль", и это разные для каждого пользователя. Например, моя соль - "6n93n". Теперь этот маленький кусочек, который прикреплен к вашему паролю, просто хранится на вашем компьютере. Когда вы пытаетесь войти с паролем X, компьютер может просто вычислить MD5 ("fa9el" +X) и посмотреть, соответствует ли он сохраненному хэшу.

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

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

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

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

Подумайте о 2 числах от 1 до 9999. Сложить их. А теперь назови мне последнюю цифру.

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

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

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

Рассмотрим простой пример функции: 'OR'. Если применить это к входным данным 1 и 0, то получится 1. Но теперь, если вы знаете ответ "1", Как вы возвращаете исходные данные? Вы не можете. Это может быть 1,1 или, может быть, 0,1, или, может быть, 1,0.

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

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

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

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

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

  • только строчные символы и цифры: 36^8 = 2.8*10^12
  • нижний и верхний регистры и числа: 62^8 = 2.18*10^14

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

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