Может ли анализ радужной таблицы извлечь простые текстовые пароли из значения md5?

Question

Я знаю, что хеш-значение (например, значение md5) может иметь связь с несколькими значениями, такими как '^ & #%we242eweqweqweqwedfdfdfee2', '%$#%3423efffe435%%^#'

Но так как большинство пользователей на самом деле используют очень простой пароль, могут ли эти значения md5 иметь связь только с ограниченными простыми паролями открытого текста?

Я имею в виду, что если у 'cfcd208495d565ef66e7dff9f98764da' просто есть соединение с 30 простыми значениями, такими как '0','tom123','goodcar', то хакер, получивший данные md5 из базы данных, легко выяснит связь между именем пользователя и его паролем открытого текста, а затем может использовать эту пару значений для взлома той же учетной записи на других сайтах.

Итак, является ли любое указанное значение md5 ответственным только за ограниченные простые значения?

PS: я знаю, что могу добавить соль или использовать лучший метод, как sha512, sha3, но мне очень любопытен вопрос выше.

Answer 1

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

Но поскольку вы говорили о "простых значениях", я предполагаю, что вы исключаете такие искусственно созданные сообщения, и тогда мы все равно можем рассматривать md5 как случайное отображение.

Для такого случайного отображения вероятность столкновения зависит только от размера входной области. Например, если вы просматриваете все 6-символьные пароли из кодировки {az, AZ, 0-9}, вы можете быть уверены, что столкновения не будет (и вы даже можете попробовать это сами, как указал Крис). Но если вы увеличите этот размер до 25 символов из одной и той же кодировки, то гарантированно произойдет коллизия, поскольку теперь существует больше возможных паролей, чем доступных значений хеш-функции.

Оценка вероятности столкновения называется проблемой дня рождения. Как просто оценить, если у вас есть k возможные выходные значения вы можете ожидать столкновения, когда вы достигнете sqrt(k) входные значения. Так что для md5 с k=2^128 вы ожидаете столкновения, если ваш входной набор значений приближается к размеру 2^64,