Tag Info

New answers tagged

3

Your math is wrong — not the numerical calculation, but your interpretation of it. There are $256^{17}$ possible inputs and $256^{16}$ possible outputs. On average, there are $256$ inputs for each output. But there are no guarantees that this is the case for all outputs: it's in fact overwhelmingly likely that some outputs have more and others have fewer. ...


0

The wikipedia page for the Birthday problem gives the details, including the exact formula. As an approximation you can use: $$p \approx 1-\exp(-\frac{\tfrac{1}{2}n(n-1)}{2^{256}}) \approx 1-\exp\left(-\frac{n^2}{2 \cdot 2^{256}}\right) \approx 1-\exp\left(-\tfrac{1}{2} \left(\frac{n}{2^{128}}\right)^2\right)$$ If $n \ll 2^{256/2}$ and thus $p \ll 1$ you ...


0

If you want to get back to a specific starting point $v$ then it will take on average $2^{256}$ iterations. If you simply want to find a cycle, it will take about $2^{128}$ iterations, because of the birthday paradox.


5

$\text{SHA256}$ is designed to behave as a random function. Under that assumption, it is expected that for most 256-bit $v$, there is no positive integer $n$ with $\text{SHA256}^n(v)$ equal to $v$. Otherwise said, most $v$ do not belong to a cycle. To illustrate this visually, in the following picture showing iteration of a 7-bit hash, I drew the points ...


2

If a hash is modelled as a random function $H$ from input strings of length 256 to that same length output, then the probability that $H$ is in fact a permutation (which is equivalent to saying that all of the inputs have unique outputs) is negligible. So the chances are close to 0 that this is the case. For random functions some results on the cycle lenght ...



Top 50 recent answers are included