Skip to main content
Information Security

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

10
  • 4
    The range is 2^256 and the size of the input space is infinite If the input space is infinite there is an infinite number of collisions. ∞/2²⁵⁶ = ∞... Commented Aug 12, 2020 at 8:18
  • 7
    @d-b yes, but technically there need not be an infinite (or even more than one) collision for each output value; it could be the case that a subset of output values have only one possible input values or none at all. I suspect it is not possible to prove whether there is an infinite number of collisions for each output value for SHA-256 though I suspect it is the case. Commented Aug 12, 2020 at 10:32
  • 4
    The size of the input space is not quite infinite, it is 2^(2^64) since the size of the input is appended before taking the hash. Not that you are likely to ever have a bigger input than that. Commented Aug 12, 2020 at 12:42
  • 2
    @CaptainMan That is because 2^256 ≈ the number of atoms in the visible universe. Commented Aug 12, 2020 at 17:46
  • 19
    "it's not an invertible function because the size of the domain is greater than the size of the range" - You're talking about the mathematical definition of one way functions, but that's not what's relevant here. The cryptographic definition is "a function which is computationally infeasible to invert". The fact that the inverse is a multivalued function irrelevant. Commented Aug 12, 2020 at 20:24