0

Will a recursive sha256 run over all 2^256 inputs before a collision?

Here'a a python program showing my question - will this loop for 2^256 times - given endless memory or will it terminate before - if so when?

import hashlib

# start with 0
input = (0).to_bytes(32, byteorder="little", signed=False)

# dictionary to detect hash collisions - yes, this will eat up ALL memory
hit = {}

print ("first input:" + input.hex())

while (1):
    hash = hashlib.sha256(input).digest()
    
    # do we have a collision?
    assert (hash not in hit), "Collision!"
    
    # store current hash
    hit[hash]=1

    print ("Hash: " + hash.hex())

    # try again with the hash output as input
    input=hash
2

Short answer: you will "probably" find a collision after 2^128 attempts.

The concept you are looking for is called the birthday problem, explained also very well in this video by Professor Christoph Parr.

One of the approximations from The Birthday Problem is that given a random output space of size n, the probability of an input collision approaches 50% after approximately √n attempts. (2^256)^1/2 = 2^128

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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