Как найти коллизию первых 56 бтс для MD5 (MD5 (x)) для входных данных с таким же префиксом?

Question

У меня есть код, чтобы найти столкновение первых 56 битов функции ha sh: md5 (md5 (x)) (используя алгоритм Флойда для поиска циклов). Скрипт возвращает две строки (заяц, черепаха), для которых происходит столкновение. Как изменить этот скрипт, чтобы он возвращал «заяц» и «черепаха» с одинаковым префиксом?

Например:

hare = 'myprefix11233 ...'

tortoise = 'myprefix37008 ...'

Пример:

MD5 (MD5 ('myprefix11233 ...')) = 0x66545ea223fe91a874 7a0 ...

MD5 (MD5 ('myprefix37008 ...')) = 0x66545ea223fe91a874 da5 ...

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