对于具有相同前缀的输入数据，如何找到 MD5(MD5(x)) 的前 56 btis 的冲突？

Question

我有一个代码可以找到散列函数前56位的碰撞：md5(md5(x))（使用Floyd算法寻找循环）。脚本 returns 两个字符串 (hare, tortoise) 发生冲突。如何将此脚本修改为 return 'hare' 和 'turtle' 具有相同的前缀？

例如：

野兔='myprefix11233...'

乌龟='myprefix37008...'

示例：

MD5(MD5('myprefix11233...')) = 0x66545ea223fe91a8747a0...

MD5(MD5('myprefix37008...')) = 0x66545ea223fe91a874da5...

import hashlib

def hash(plain):
    temp = hashlib.md5(plain).hexdigest()
    bytes = []
    temp = ''.join(temp.split(" "))
    temp
    for i in range(0, len(temp), 2):
        bytes.append(chr(int(temp[i:i+2], 16)))
    first_hash = ''.join(bytes)


    return hashlib.md5(first_hash).hexdigest()[:14]


def floyd(hash, x0):
    tortoise = hash(x0)
    hare = hash(hash(x0))

    counter = 0
    final = ""
    print("first while")

    while (tortoise != hare):
        tortoise = hash(tortoise)
        hare = hash(hash(hare))

        counter += 1
        if(counter % 10000000 == 0):
            print(counter)

    tortoise = x0

    print("second while")
    counter = 0

    while (tortoise != hare):
        tortoise = hash(tortoise)
        hare = hash(hare)

        counter += 1
        if(counter % 10000000 == 0):
            print(counter)

        if (tortoise != hare):
            temp_tortoise = tortoise
            temp_hare = hare
            pass

        if (hash(tortoise) == hash(hare)):
            print("found hashes")
            print("tortoise", temp_tortoise)
            print("hare", temp_hare)
            final = 'tortoise: ' + temp_tortoise + "\n" + "hare: " + temp_hare
            with open('hashes.log', 'w') as file_:
                file_.write(final)
            break

    print("checking calculations...")
    print("tortoise", temp_tortoise, ">", hash(temp_tortoise))
    print("hare", temp_hare, ">", hash(temp_hare))

floyd(hash, 'init_data')

Answer 1

我在python2中解决了这个问题： https://github.com/jaroslaw-wieczorek/python2_collision_detection_by_floyd

和python3中的解决方案： https://github.com/jaroslaw-wieczorek/python3_collision_detection_by_floyd

对于具有相同前缀的输入数据，如何找到 MD5(MD5(x)) 的前 56 btis 的冲突？

How to find a collision of first 56 btis for MD5(MD5(x)) for input data with the same prefix?

python

md5

hash-collision

floyd-warshall

floyd-cycle-finding