Какая трансформация md5? Математический (от любой строки до 128 бит) или от любой строки до 32-символьной шестнадцатеричной строки (практический)? Не очевидно, что ответы для них обоих одинаковые ...
Рафал Даугирд
4
Что ж, это один и тот же ответ, правда? Мы знаем, что не существует x, длина которого не превышает 128 бит, для которого md5(x) == x, поскольку он md5(x)имеет длину 128 бит. Следовательно, в md5 есть фиксированная точка для ввода произвольного размера тогда и только тогда, когда есть фиксированная точка в md5 в 128-битной области.
Павел
1
Я не думаю, что это один и тот же ответ, поскольку для практической шестнадцатеричной строки из 32 символов это произвольный выбор, представляете ли вы шестнадцатеричные цифры в верхнем регистре [AF] или в нижнем регистре [af]. Оба представления соответствуют одному и тому же 128-битному числу, но они дадут разные хэши, если они будут входить в MD5. Таким образом, вероятность того, что в любом из представлений есть фиксированная точка, действительно есть1-(1/e)*(1/e) ≈ 86.47%
Душан
Ответы:
138
Поскольку сумма 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 бит).
Можете ли вы действительно сделать предположение, что сумма MD5 любой строки равномерно распределена по всем возможным суммам?
Ori Pessach
13
Да. Большие числа и модульность образуют примерно случайное распределение. Если бы они этого не сделали, у вас были бы постоянные столкновения. Природа md5 заставляет его вывод распределяться случайным образом.
Извините ... Я не сохранил сообщение в блоге, и у меня не работает резервное копирование Google +. Но вот мой проект на github: github.com/thomasegense/MD5FixPointSearch
Thomas Egense
Вы уверены в этом: префикс 12: 54db1011d76dc70a0a9df3ff3e0b390f -> 54db1011d76d137956603122ad86d762 Я использовал md5sumкоманду linux, у меня другой результат
ThunderPhoenix
Не уверен, что вы правильно используете md5sum. Вы также можете подтвердить это онлайн здесь: onlinemd5.com
Thomas Egense,
11
Поскольку хеш-код необратим, это очень сложно понять. Единственный способ решить эту проблему - это вычислить хэш для каждого возможного вывода хэша и посмотреть, нашли ли вы совпадение.
Чтобы уточнить, в хэше MD5 есть 16 байтов. Это означает, что есть 2 ^ (16 * 8) = 3,4 * 10 ^ 38 комбинаций. Если на вычисление хэша для 16-байтового значения ушла 1 миллисекунда, то на вычисление всех этих хэшей потребуется 10790283070806014188970529154,99 лет.
Верно, если бы надо было все перепробовать . Но вам нужно только попробовать все возможные входные данные, чтобы убедиться, что нет фиксированной точки. Если есть фиксированная точка (а ответ Адама Розенфилда предполагает, что она может быть), то все, что нужно, - это одна удачная догадка.
Naaff
Функция необратима в том смысле, что у нее нет математического обратного, однако это означает только то, что для данного выхода может быть более одного входа. В общем, пространство входов для данного выхода было бы бесконечным, но если вы знаете, что он начинался как 128-битное значение, вы можете сузить возможности. Есть шанс «работать в обратном направлении», если вы не относитесь к функции как к черному ящику, а вместо этого читаете спецификацию и применяете математическое мышление.
rndmcnlly
2
@Naaff: «нужно только попробовать все возможные входные данные» - а это проще, чем попробовать каждый хеш, как? Как раз наоборот, поскольку несколько возможных входов могут быть хешированы в один и тот же выход.
Писквор покинул здание 03.06.2009
1
@Piskvor: Вы неправильно поняли, что имел в виду Наафф (у меня это тоже заняло минуту). Более ясный способ сказать, что это будет: «Только если нет фиксированной точки, вы должны попробовать все возможные вводы (из пробела 2 ^ 128)». Другими словами, вам нужно только попробовать все возможности, если ни одна из них не сработает. Итак, 1.08e28 года, или одна удачная догадка!
P Daddy
«Если на вычисление хеша ушла 1 миллисекунда». Современные графические процессоры могут вычислять миллиарды хэшей в секунду, намного быстрее, чем это. Но все равно это займет очень много времени.
markasoftware
0
Хотя у меня нет ответа «да / нет», я предполагаю «да» и, кроме того, таких фиксированных точек может быть 2 ^ 32 (для интерпретации битовой строки, а не для интерпретации символьной строки). Я активно работаю над этим, потому что это похоже на потрясающую лаконичную головоломку, которая потребует большого творчества (если вы сразу не согласитесь на поиск грубой силы).
Мой подход следующий: относитесь к этому как к математической задаче. У нас есть 128 логических переменных и 128 уравнений, описывающих выходы в терминах входов (которые должны совпадать). Я надеюсь, что, подключив все константы из таблиц в алгоритме и биты заполнения, уравнения можно значительно упростить, чтобы получить алгоритм, оптимизированный для случая 128-битного ввода. Эти упрощенные уравнения затем могут быть запрограммированы на каком-нибудь приятном языке для эффективного поиска или снова рассматриваться абстрактно, назначая отдельные биты за раз и обращая внимание на противоречия. Вам нужно только увидеть несколько битов вывода, чтобы знать, что они не совпадают с вводом!
Он не был сломан. Все, что они смогли сделать, это за разумное время создать 2 строки, которые соответствуют одному и тому же хешу. По-прежнему очень сложно создать строку, которая будет соответствовать определенному хешу.
Кибби,
9
не уверен, как найти один из них может скомпрометировать md5, как и алгоритм, если я скажу вам MD5 («Быстрая коричневая лиса перепрыгивает через ленивую собаку») = 9e107d9d372bb6826bd81d3542a419d6
Кип
5
Фиксированная точка, вероятно, дала бы некоторое влияние на математику, которая могла бы привести к более полному нарушению MD5. Я не уверен, что Гломек действительно может оправдать «вероятно»; Я бы принял слово «возможно» без двусмысленности.
Джонатан Леффлер,
-9
Есть две интерпретации, и если можно выбрать любую из них, вероятность нахождения фиксированной точки возрастает до 81,5%.
Интерпретация 1: делает ли MD5 вывода MD5 двоичным его входу?
Интерпретация 2: совпадает ли MD5 вывода MD5 в шестнадцатеричном формате с его вводом?
В алгоритме MD5 нет ничего, что подразумевает шестнадцатеричный код - он работает с байтами и производит байты, поэтому я считаю, что последняя интерпретация неверна.
Ник Джонсон,
Независимо от того, существует ли фиксированная точка при интерпретации 1, она все еще может быть (или не быть) при интерпретации 2. Однако, если вы заинтересованы в изучении проблемы, интерпретация 1 кажется гораздо лучшим местом для начала, потому что вы выиграли Не нужно принимать всевозможные произвольные решения относительно регистра и кодировки символов. Кроме того, в двоичном регистре меньше битов!
rndmcnlly
4
Вы неверно истолковываете, что такое гексагон. Вы можете представить двоичный файл в шестнадцатеричном формате, точно так же, как вы можете представить его в десятичном, восьмеричном или базовом 3. Это число, которое имеет разные представления. Итак, интерпретация 1 и 2 - это одно и то же. То, о чем вы думаете, - это представление строки символов, которое вообще не является тем же шестнадцатеричным, а представляет собой совершенно другое двоичное значение. Фактически у вас может быть много разных шестнадцатеричных строк в разных наборах символов. 128-битное хеш-значение может быть представлено как "шестнадцатеричная" строка, но оно не равно строке. Строка - это не те же двоичные данные.
определяет
Дастин, интерпретация 2 действительно означает MD5 отображаемой строки.
Джошуа
4
Однако есть огромная проблема с этой идеей, поскольку она напрямую зависит от кодировки ваших символов. Разная схема кодирования приведет к совершенно другим наборам результатов. Есть даже целый проект и статья, разоблачающая его, основанная на непонимании того, как работает MD5 acodingfool.typepad.com/blog/2009/05/the-kembler-identity.html
определяет
-23
Строго говоря, поскольку входной сигнал MD5 имеет длину 512 бит, а выход - 128 бит, я бы сказал, что это невозможно по определению.
Вход может быть любого размера. Если входной файл меньше 512 байт, он дополняется, но небольшие входные данные по-прежнему приемлемы. Из Википедии: «MD5 преобразует сообщение переменной длины в выходной файл фиксированной длины, равный 128 битам. Входное сообщение разбивается на блоки по 512 бит (шестнадцать 32-битных целых чисел с прямым порядком байтов); сообщение дополняется таким образом, чтобы его длина делится на 512. "
Naaff
Итак, вы предполагаете, что, скажем, 0000000001 = 1? Я бы сказал, что вопрос в лучшем случае сформулирован плохо.
Ori Pessach
11
Ввод в MD5 может быть 128 бит. Если MD5 хочет дополнить этот ввод, то, честно говоря, это дело MD5. Вход по-прежнему четко определен. Точно так же вывод - это четко определенные 128 бит. Если (четко определенный) вход и (четко определенный) выход одинаковы, тогда MD5 (x) = x.
Naaff
2
@Joshua даже существует MD5 пустой строки (то есть 0 байт)
md5(x) == x, поскольку онmd5(x)имеет длину 128 бит. Следовательно, в md5 есть фиксированная точка для ввода произвольного размера тогда и только тогда, когда есть фиксированная точка в md5 в 128-битной области.1-(1/e)*(1/e) ≈ 86.47%Ответы:
Поскольку сумма 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
источник
md5sumкоманду linux, у меня другой результатПоскольку хеш-код необратим, это очень сложно понять. Единственный способ решить эту проблему - это вычислить хэш для каждого возможного вывода хэша и посмотреть, нашли ли вы совпадение.
Чтобы уточнить, в хэше MD5 есть 16 байтов. Это означает, что есть 2 ^ (16 * 8) = 3,4 * 10 ^ 38 комбинаций. Если на вычисление хэша для 16-байтового значения ушла 1 миллисекунда, то на вычисление всех этих хэшей потребуется 10790283070806014188970529154,99 лет.
источник
Хотя у меня нет ответа «да / нет», я предполагаю «да» и, кроме того, таких фиксированных точек может быть 2 ^ 32 (для интерпретации битовой строки, а не для интерпретации символьной строки). Я активно работаю над этим, потому что это похоже на потрясающую лаконичную головоломку, которая потребует большого творчества (если вы сразу не согласитесь на поиск грубой силы).
Мой подход следующий: относитесь к этому как к математической задаче. У нас есть 128 логических переменных и 128 уравнений, описывающих выходы в терминах входов (которые должны совпадать). Я надеюсь, что, подключив все константы из таблиц в алгоритме и биты заполнения, уравнения можно значительно упростить, чтобы получить алгоритм, оптимизированный для случая 128-битного ввода. Эти упрощенные уравнения затем могут быть запрограммированы на каком-нибудь приятном языке для эффективного поиска или снова рассматриваться абстрактно, назначая отдельные биты за раз и обращая внимание на противоречия. Вам нужно только увидеть несколько битов вывода, чтобы знать, что они не совпадают с вводом!
источник
Возможно, но на его поиск потребуется больше времени, чем у нас, или потребуется взломать MD5.
источник
Есть две интерпретации, и если можно выбрать любую из них, вероятность нахождения фиксированной точки возрастает до 81,5%.
источник
Строго говоря, поскольку входной сигнал MD5 имеет длину 512 бит, а выход - 128 бит, я бы сказал, что это невозможно по определению.
источник