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

Ответ 1

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

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

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

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

Ответ 2

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

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

суффикс 12: df12c1434cec7850a7900ce027af4b78 → b2f6053087022898fe920ce027af4b78

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

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

для х = 0е215962017

md5 (x) == x => true в php. Как это свободный компаратор.

Ответ 6

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

Ответ 7

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

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

Ответ 8

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