Are there md5 collisions for integers in range(1,1000000000)

user_4411799 0
Viewed 743

I want to generate a uuid in python using the md5 hash of a preexisting unique identifier ranged between 1 and 999999999

It seems obvious that on numbers so small there couldn't be any worry... but it made me think, do we know the smallest two integers that have the same md5 hash ?

md5 hash guid uuid python
3 Answers

I tested, and the answer is no.

counting with set() will trigger MemoryError on my 64GB memory box, so I write hexlify hash to disk:

import hashlib
from multiprocessing import Pool
import os

def f(args):
    s, e = args
    l = []
    for i in xrange(s, e):
        h = hashlib.md5(str(i)).hexdigest()
        l.append(h)
    l.sort()
    fn = '/data/tmp/%s_%s' % (s, e)
    with open(fn, 'w') as f:
        for h in l:
            f.write('%s\n' % (h,))

def main():
    def gen():
        end = 1000000000
        step = 5000000
        s = 0
        while s < end:
            yield s, s+step
            s += step

    pool = Pool(processes=16)
    res = pool.imap_unordered(f, gen())
    list(res)

then counting with sort(1):

sort -mu /data/tmp/* | wc -l

yields:

1000000000

note that I encoded integer into ASCII string.

user_42018100

You could test it:

provided you have ample memory, and/or an OS that manages excess memory usage with disk access, but then it will be rather slow - thanks to @EricDuminil & @vsenko in the comments

import hashlib

h = hashlib.new('md5', buffer=64)
md5hashes = set()

N = 1000000000

for _ in range(N):
    if _ % 10000000 == 0:
        print(".", flush = True)
    h.update(str(_).encode())
    hsh = h.hexdigest()
    if hsh in md5hashes:
        print(_, hsh)
    md5hashes.add(hsh)


print(f"has collisions: {len(md5hashes) != N})
user_28755630

You could test it using MongoDb as data store:

import hashlib
import sys
import pymongo

def int_to_bytes(x):
    return x.to_bytes((x.bit_length() + 7) // 8, byteorder=sys.byteorder)

CLIENT = pymongo.MongoClient('mongodb://localhost:27017/')
DB = CLIENT['md5test']
COLLECTION = DB['vals']

COLLECTION.create_index('value', unique=True)

for x in range(1000000000):
    if x % 1000000 == 0:
        print(x)
    m = hashlib.md5()
    m.update(int_to_bytes(x))
    value = m.digest()
    COLLECTION.insert_one({
        'value': value
    })

print('done!')

It will throw in case of a duplicate. But it will take time to process your range.

Also it matters how you encode integers, see int_to_bytes().

user_52640410
Related