Tag Info

New answers tagged

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 ...


3

If we use $H_1(X) = H_0(X) \oplus firstnbits(X)$, this would seem to be trivial. EDIT: As C├ędric Van Rompay pointed out, this is only a counterexample if $H_1$ winds up being preimage-resistant. This may not be a necessary consequence of $H_0$ being preimage-resistant, but I really only need one case where it is.


1

If it is for completely random data you could still make a program that uses the random looking input to make different choices. For instance, you could sign two .jar files in Java, using the SHA-256 hash over the file in the META-INF folder. Then you can use the different files a property to make one choice or the other. Basically you're replacing one of ...


0

This was pretty vexing, but for some reason I could only create the "big endian" results given by table 2 in this paper. I get the same result as you for the first message ($M.$N0) : 8da3a17b43e0e134bdc17557ffef15ff and a different value for the second message. The following code seems to work for a test vector given in table 2: <?php $M0='02dd31d1 ...



Top 50 recent answers are included