3
$\begingroup$

I'm trying to find a MD5 hash collision between 2 numbers such that one is prime and the other is composite (at most 1024-bit). I'm using fastcoll with random prefixes for each iteration.

For this I wrote this script:

import subprocess
from Crypto.Util.number import bytes_to_long, isPrime
import string
import random

won = False

N = 10

while not won:
    # Run the fastcoll executable to generate the two messages
    pfx = ''.join(random.choices(string.ascii_uppercase + string.digits, k=N))
    file = open("prefix", "w")
    file.write(pfx)
    file.close()

    subprocess.run(["./fastcoll_v1.0.0.5.exe", "-p", "prefix", "-o", "msg1.bin", "msg2.bin"])

    # Convert the messages to integers
    with open("msg1.bin", "rb") as f:
        msg1_int = bytes_to_long(f.read())
    if(msg1_int.bit_length() > 1024):
        continue
    with open("msg2.bin", "rb") as f:
        msg2_int = bytes_to_long(f.read())
    if(msg2_int.bit_length() > 1024):
        continue
    
    print(msg1_int)
    print(isPrime(msg1_int))
    print(msg2_int)
    print(isPrime(msg2_int))

    # Check if one message is prime and the other is composite
    if isPrime(msg1_int) and not isPrime(msg2_int):
        won = True
    elif isPrime(msg2_int) and not isPrime(msg1_int):
        won = True

However, I'm not sure this is the most efficient way so can someone suggest improvements? Any help would be appreciated.

Improve this question
$\endgroup$
5
  • $\begingroup$ Generating the collision and then checking if the result is prime seems the only way, so in that sense the algorithm should be good. Of course, normally you'd simply compile an executable yourself and run everything in memory, without calls to external applications. $\endgroup$
    – Maarten Bodewes ♦
    Mar 14 at 20:37
  • $\begingroup$ @MaartenBodewes is there a way of restricting fastcoll to 1024 bit pre-images for collisions? $\endgroup$
    – infinite-blank-
    Mar 14 at 20:40
  • 1
    $\begingroup$ @infinite-blank: no. fastcoll is not a pre-image attack. We don't know any practical one for MD5. The general method of generating collisions until one matches the prime/composite criteria seems workable: probability that an integer near $n$ is prime is about $1/\ln(n)$ and that's not overly small. The only speedup I can think of is to modify fastcoll to restrict to odd values. $\endgroup$
    – fgrieu ♦
    Mar 15 at 8:18
  • 1
    $\begingroup$ @fgrieu how do I restrict it to odd values? + I had another idea, we can use the fact that if md5(x) ==md5(y) then md5(x+z) == md5(y+z). So if we find a collision, we can append 1 bits to the pre images until one of them becomes prime. Is this feasible? $\endgroup$
    – infinite-blank-
    Mar 15 at 12:45
  • $\begingroup$ Yes, for all colliding messages $x$ and $y$ of identical length multiple of 64 bytes that we know how to build, and all suffixes $z$, $\operatorname{MD5}(x)=\operatorname{MD5}(y)\implies\operatorname{MD5}(x\mathbin\|z)=\operatorname{MD5}(y\mathbin\|z)$, and yes that leads to a massive speedup (though if you want others to replicate your results, I recommend to keep what's hashed byte-aligned, since bit-aware MD5 implementations are a rarity). Congratulations. I recommend that you make an answer out of that. $\endgroup$
    – fgrieu ♦
    Mar 15 at 13:18

1 Answer 1

Reset to default
3
$\begingroup$

Using the length extension attack of MD5 as I discussed in the comments, I was able to achieve this.

Here's the script I used:

from Crypto.Util.number import isPrime, bytes_to_long, long_to_bytes
import hashlib

x = "4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2"
y = "4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2"

print("x : ", bytes_to_long(bytes.fromhex(x)))

print("md5(x) : ", hashlib.md5(bytes.fromhex(x)).hexdigest())
print("md5(y) : ", hashlib.md5(bytes.fromhex(y)).hexdigest())

z = 1

xx = 0
yy = 0

while True:
    # append 1s till prime
    xx = bytes_to_long(bytes.fromhex(x) + long_to_bytes(z))
    yy = bytes_to_long(bytes.fromhex(y) + long_to_bytes(z))
    if isPrime(xx) and not isPrime(yy):
        break
    z += 2

print("x+z :", xx)
print("y+z :", yy)

print("md5(x+z) : ", hashlib.md5(long_to_bytes(xx)).hexdigest())
print("md5(y+z) : ", hashlib.md5(long_to_bytes(yy)).hexdigest())
Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Note: If we wanted 1023-bit primes for some reason, we can change the initial z to 3**322. For 1024-bit, the initial collision would need to be changed so that the initial byte is at least 0x80. $\endgroup$
    – fgrieu ♦
    Mar 15 at 17:57
  • 1
    $\begingroup$ A little correction from my side, I should have written at most 1024 bit prime in the original question, I've corrected it now. $\endgroup$
    – infinite-blank-
    Mar 15 at 18:22
  • 1
    $\begingroup$ If would be best if you accept your answer. I hope it's possible. You well deserve it. $\endgroup$
    – fgrieu ♦
    Mar 16 at 10:20
  • $\begingroup$ @fgrieu I think it has a time limit after which I can accept the answer. I also wanted to know how you calculated this : "For 1024-bit, the initial collision would need to be changed so that the initial byte is at least 0x80. " $\endgroup$
    – infinite-blank-
    Mar 16 at 15:44
  • 1
    $\begingroup$ x is a 128-char string, representing 64-byte bytestring $X$, and (per the big-endian convention used) a 511-bit integer $x$ (rather than 512) because the high-order bit of the first byte (0x4d) is 0, and the second high-order bit of that is 1. Most MD5 implementations (including the one at hand) support only bytes as input, thus we append bytes to $X$ so that we can still hash it. Appending $k$ bytes to $X$ makes a $64+k$-byte bytestring coding integer xx of bit size $511+8k$. That can't be $1024$. For this we need to change the first byte of $X$ so that it's high-order bit is 1. $\endgroup$
    – fgrieu ♦
    Mar 16 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.