Есть ли фиксированная точка MD5, где md5(x) == x?
Есть ли фиксированная точка в преобразовании MD5, т.е. существует ли x такой, что md5(x) == x?
7 ответов
Поскольку сумма MD5 составляет 128 битов, любая фиксированная точка также обязательно должна быть длиной 128 битов. Предполагая, что сумма MD5 любой строки равномерно распределена по всем возможным суммам, тогда вероятность того, что любая данная 128-битная строка является фиксированной точкой, составляет 1/2 128.
Таким образом, вероятность того, что 128-битная строка не является фиксированной точкой, составляет (1 - 1/2 128) 2 128, поэтому вероятность того, что фиксированная точка существует, составляет 1 - (1 - 1/2 128) 2 128.
Поскольку предельное значение n при переходе в бесконечность (1 - 1 / n) n равно 1 / e, а 2 128, безусловно, очень большое число, эта вероятность почти точно равна 1 - 1 / e ≈ 63,21%.
Конечно, в действительности нет никакой случайности - либо есть фиксированная точка, либо ее нет. Но мы можем быть на 63,21% уверены, что есть фиксированная точка. (Также обратите внимание, что это число не зависит от размера пространства ключей - если суммы MD5 были 32 или 1024 битами, ответ будет таким же, если он больше, чем примерно 4 или 5 бит).
Моя попытка грубой силы нашла совпадение 12 префиксов и 12 суффиксов.
префикс 12: 54db1011d76dc70a0a9df3ff3e0b390f -> 54db1011d76d137956603122ad86d762
суффикс 12: df12c1434cec7850a7900ce027af4b78 -> b2f6053087022898fe920ce027af4b78
Сообщение в блоге: https://plus.google.com/103541237243849171137/posts/SRxXrTMdrFN
Поскольку хеш необратим, это будет очень трудно понять. Единственный способ решить эту проблему - вычислить хеш на каждом возможном выводе хеша и посмотреть, есть ли совпадение.
Чтобы уточнить, в хеше MD5 есть 16 байтов. Это означает, что есть 2^(16*8) = 3,4 * 10 ^ 38 комбинаций. Если для вычисления хэша на 16-байтовом значении потребуется 1 миллисекунда, потребуется 10790283070806014188970529154,99 лет, чтобы вычислить все эти хэши.
Хотя у меня нет ответа "да / нет", я предполагаю "да", и, кроме того, возможно, есть 2^32 таких фиксированных точек (для интерпретации битовой строки, а не для интерпретации символьной строки). Я активно работаю над этим, потому что это кажется удивительной, лаконичной головоломкой, которая потребует большого творческого подхода (если вы не согласитесь на поиск методом перебора).
Мой подход заключается в следующем: рассматривать это как математическую задачу. У нас есть 128 булевых переменных и 128 уравнений, описывающих выходные данные в терминах входных данных (которые должны совпадать). Я надеюсь, что, подключив все константы из таблиц в алгоритме и биты заполнения, можно значительно упростить уравнения, чтобы получить алгоритм, оптимизированный для 128-битного входного случая. Эти упрощенные уравнения могут быть затем запрограммированы на каком-то хорошем языке для эффективного поиска или снова обработаны абстрактно, присваивая отдельные биты за раз, следя за противоречиями. Вам нужно только увидеть несколько битов вывода, чтобы знать, что он не соответствует входу!
Возможно, но нахождение этого заняло бы больше времени, чем у нас, или потребовало бы компрометации MD5.
Существует две интерпретации, и если один из них разрешает выбирать, вероятность нахождения фиксированной точки возрастает до 81,5%.
- Интерпретация 1: соответствует ли MD5 выхода MD5 в двоичном формате его входу?
- Interpretation 2: does the MD5 of a MD5 output in hex match its input?
Строго говоря, поскольку вход MD5 имеет длину 512 бит, а выход 128 бит, я бы сказал, что это невозможно по определению.