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

Не решение Python, но ...

Я столкнулся с этой проблемой со сценарием, работающим под CentOS (Linux), и то, что работало в моей ситуации, было просто запуском «read -t» Bash "в подпроцессе. Жестокий отвратительный хак, я знаю, но я чувствую себя достаточно виноватым в том, насколько хорошо он работал, и я хотел поделиться им со всеми здесь.

import subprocess
subprocess.call('read -t 30', shell=True)

Все, что мне нужно, было то, что ожидало 30 секунд, если только ENTER нажата клавиша. Это отлично работает.

21
задан Scott Arciszewski 28 May 2019 в 20:49
поделиться

4 ответа

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

1114 Допустим, у нас есть число «7», и мы хотим взять его хеш. Возможно, первое, что мы попробуем в качестве нашей хеш-функции, - это «умножить на два». Как мы увидим, это не очень хорошая хеш-функция, но мы попробуем ее, чтобы проиллюстрировать ситуацию. В этом случае хеш числа будет «14». Это было довольно легко рассчитать. Но теперь, если мы посмотрим на то, как трудно это изменить, мы обнаружим, что это так же просто! Учитывая любой хеш, мы можем просто разделить его на два, чтобы получить оригинальное число! Это не очень хороший хеш, потому что весь смысл хэша в том, что вычислить обратное гораздо сложнее, чем вычислить хеш (это самое важное свойство по крайней мере в некоторых контекстах) .

1115 Теперь давайте попробуем еще один хеш. Для этого мне нужно будет представить идею арифметики часов. На часах не бывает бесконечного количества чисел. На самом деле, он просто идет от 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 и другие хеши, чтобы их было трудно перевернуть.

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

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

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

Теперь, что касается соли, идея такова: что, если бы два пользователя имели один и тот же пароль? У них будет такой же хэш. Если подумать, злоумышленнику не обязательно взламывать пароль каждого пользователя в отдельности. Он просто просматривает все возможные входные пароли и сравнивает хеш со всеми хешами. Если это соответствует одному из них, то он нашел новый пароль. Что мы действительно хотели бы заставить его сделать, так это вычислить новый хеш для каждой комбинации пользователь + пароль, которую он хочет проверить. Идея заключается в том, что хэш-функция должна немного отличаться для каждого пользователя, поэтому он не может повторно использовать один набор предварительно вычисленных значений для всех пользователей. Самый простой способ сделать это - прикрепить некоторую случайную строку к паролю каждого пользователя перед тем, как вы возьмете хеш, где случайная строка различна для каждого пользователя. Так, например, если мой пароль «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 - количество паролей, которые вы храните.

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

45
ответ дан feetwet 28 May 2019 в 20:49
поделиться

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

1
ответ дан Steve 28 May 2019 в 20:49
поделиться

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
ответ дан Karoly Horvath 28 May 2019 в 20:49
поделиться

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

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

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

20
ответ дан Paul Dixon 28 May 2019 в 20:49
поделиться
Другие вопросы по тегам:

Похожие вопросы: