Есть ли фиксированная точка MD5, где md5 (x) == x?

Question

Есть ли фиксированная точка в преобразовании MD5, то есть существует ли x такой, что md5(x) == x?

Answer 1

Поскольку сумма MD5 составляет 128 битов, любая фиксированная точка также обязательно должна быть длиной 128 битов. Если предположить, что сумма MD5 любой строки равномерно распределена по всем возможным суммам, то вероятность того, что любая данная 128-битная строка является фиксированной точкой, равна ¹ / _{2 ¹²⁸} .

Таким образом, вероятность того, что 128-битная строка не является фиксированной точкой, равна (1 - ¹ / _{2 ¹²⁸} ) ^{2 128} , поэтому вероятность наличия фиксированной точки равна 1 - (1 - ¹ / _{2 ¹²⁸ * * 1030) ^{2 128} .}

Поскольку предел при n стремится к бесконечности (1 - ¹ / _n ) ⁿ равен ¹ / _e и 2 ¹²⁸ , безусловно, очень большое число, эта вероятность почти точно равна 1 - ¹ / _e ≈ 63,21%.

Конечно, в действительности нет никакой случайности, & ndash; либо есть фиксированная точка, либо ее нет. Но мы можем быть на 63,21% уверены, что есть фиксированная точка. (Также обратите внимание, что это число не зависит от размера пространства ключей - если бы суммы MD5 были 32 или 1024 битами, ответ был бы таким же, если он больше примерно 4 или 5 бит).

Answer 2

Моя попытка грубой силы нашла совпадение 12 префиксов и 12 суффиксов.

префикс 12: 54db1011d76dc70a0a9df3ff3e0b390f -> 54db1011d76d137956603122ad86d762

суффикс 12: df12c1434cec7850a7900ce027af4b78 -> b2f6053087022898fe920ce027af4b78

Сообщение в блоге: https://plus.google.com/103541237243849171137/posts/SRxXrTMdrFN

Answer 3

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

Для уточнения, в хеше MD5 есть 16 байтов. Это означает, что есть 2 ^ (16 * 8) = 3,4 * 10 ^ 38 комбинаций. Если для вычисления хэша на 16-байтовом значении понадобится 1 миллисекунда, потребуется 10790283070806014188970529154,99 лет для вычисления всех этих хешей.

Answer 4

Хотя у меня нет ответа «да / нет», я предполагаю «да», и, кроме того, возможно, есть 2 ^ 32 таких фиксированных точек (для интерпретации битовой строки, а не для интерпретации символьной строки). Я активно работаю над этим, потому что это кажется удивительной, лаконичной головоломкой, которая потребует большого творческого подхода (если вы не согласитесь на поиск методом перебора).

Мой подход следующий: относитесь к нему как к математической задаче. У нас есть 128 булевых переменных и 128 уравнений, описывающих выходные данные в терминах входных данных (которые должны совпадать). Подключая все константы из таблиц в алгоритме и биты заполнения, я надеюсь, что уравнения можно значительно упростить, чтобы получить алгоритм, оптимизированный для 128-битного входного случая. Эти упрощенные уравнения могут быть затем запрограммированы на каком-то хорошем языке для эффективного поиска или снова обработаны абстрактно, присваивая отдельные биты за раз, следя за противоречиями. Вам нужно только увидеть несколько битов выходных данных, чтобы понять, что они не совпадают с входными!

Answer 5

Существует две интерпретации, и если разрешить одну из них, вероятность нахождения фиксированной точки возрастает до 81,5%.

• Интерпретация 1: соответствует ли MD5 выхода MD5 в двоичном его входу?
• Интерпретация 2: соответствует ли MD5 выхода MD5 в hex его входу?

Answer 6

Строго говоря, поскольку вход MD5 имеет длину 512 бит, а выход 128 бит, я бы сказал, что это невозможно по определению.

Answer 7

Возможно, но обнаружение этого заняло бы больше времени, чем мы, или потребовало бы компрометации MD5.