<p>Short answer: you will &quot;probably&quot; find a collision after <code>2^128</code> attempts.</p>
<p>The concept you are looking for is called the <a href="https://en.wikipedia.org/wiki/Birthday_problem" rel="nofollow noreferrer">birthday problem</a>, explained also very well in <a href="https://youtu.be/tLkHk__-M6Q?t=3176" rel="nofollow noreferrer">this video by Professor Christoph Parr</a>.</p>
<p>One of the approximations from The Birthday Problem is that given a random output space of size <code>n</code>, the probability of an input collision approaches 50% after approximately <code>√n</code> attempts. <code>(2^256)^1/2 = 2^128</code></p>

CC BY-SA 4.0
2020-11-23T13:18:03.353Z
2020-11-23T13:18:03.353Z
pinhead
<p>Will a recursive sha256 run over all 2^256 inputs before a collision?</p>
<p>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?</p>
<pre><code>import hashlib

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

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

print (&quot;first input:&quot; + input.hex())

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

    print (&quot;Hash: &quot; + hash.hex())

    # try again with the hash output as input
    input=hash
</code></pre>

<hash><sha256><key-collision>
Will a recursive sha256 run over all 2^256 inputs before a collision?
hodddl
# Will a recursive sha256 run over all 2^256 inputs before a collision?

(Asked by: username_0 on 2020-11-23)

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

**Tags:** hash, sha256, key-collision


---

## 1 answers

### Answer by username_1 on 2020-11-23. Score: 2 | Accepted answer

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

The concept you are looking for is called the [birthday problem](https://en.wikipedia.org/wiki/Birthday_problem), explained also very well in [this video by Professor Christoph Parr](https://youtu.be/tLkHk__-M6Q?t=3176).

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`


---

