Можно ли восстановить пароль из (частичного) хеша MD5?

Question

Предположим, у меня есть только первые 16 символов хеша MD5. Если я использую таблицы "грубой силы" или "радуги" или любой другой метод для получения исходного пароля, сколько совместимых кандидатов я должен ожидать? 1? (Не думаю) 10, 100, 1000, 10^12? Приветствуется даже грубый ответ (для числа, но, пожалуйста, будьте последовательны с теорией и методологией хеширования).

Answer 1

Вывод MD5 составляет 16 байтов (128 бит). Я предполагаю, что вы говорите о шестнадцатеричном представлении, следовательно, как 32 символа. Таким образом, "16 символов" означает "64 бита". Вы рассматриваете MD5 с его выводом, усеченным до 64 бит.

MD5 принимает входные данные длиной до 2⁶⁴ бит; Предполагая, что MD5 ведет себя как случайная функция, это означает, что 2^{18446744073709551616} возможных входных строк будут отображаться более или менее равномерно среди 2⁶⁴ выходов, поэтому среднее число кандидатов для данного выхода составляет около 2^{18446744073709551552}, что близко к 10^{5553023288523357112.95}.

Однако, если вы считаете, что можете найти хотя бы одного кандидата, это означает, что пространство возможных паролей, которые вы считаете, значительно сокращено. Радужная таблица - это специальный вид предварительно вычисленной таблицы, которая принимает компактное представление (за счет относительно дорогой процедуры поиска), но если она охватывает N паролей, то это означает, что в какой-то момент кто-то может применить хэш-функцию N раз. На практике это сильно ограничивает размер N. Предполагая, что N = 2⁶⁰ (что означает, что у разработчика таблиц было около ста графических процессоров NVidia GTX 580 и он мог запускать их в течение шести месяцев; кроме того, таблица будет использовать довольно много жестких дисков), тогда, в среднем, только 1/16-й из 64-битных выходов имеет соответствующий пароль в таблице. Для тех паролей, которые есть в таблице, есть вероятность 93,75%, что в таблице нет другого пароля, который приводит к тому же выводу; если вы предпочитаете, если вы найдете соответствующий пароль, то вы найдете, в среднем, 0,0625 других кандидатов (т.е. большую часть времени, никаких других кандидатов).

Вкратце, ответ на ваш вопрос зависит от размера N пространства возможных паролей, которые вы рассматриваете (те, которые были рассмотрены при создании радужного стола); но на практике при использовании технологии на основе Земли, если вы можете найти один совпадающий пароль для 64-битного вывода, есть вероятность, что вы не сможете найти другой (хотя их действительно много).

Answer 2

Вы никогда не сможете получить пароль из частичного хэша.