0
$\begingroup$

Although this question is strongly related to my previous question, it's certainly not the same:

Suppose the input of SHA-512 is 512 bits of data (so exactly the same size as the output). If I would test every possible permutation (so $2^{512}$ calculations), then will the output also be exactly $2^{512}$ different hashes, or will collisions occur ?

If collisions occur, would the amount of collisions and the 'size' of the collisions (approximately) be the same as statistics would predict after randomly generating $2^{512}$ 512-bit strings ? (With 'size' i mean the amount of times a specific hash occurs)

$\endgroup$

1 Answer 1

2
$\begingroup$

Suppose the input of SHA-512 is 512 bits of data (so exactly the same size as the output). If I would test every possible combination (so $2^{512}$ calculations), then will the output also be exactly $2^{512}$ different hashes, or will collisions occur?

It would be astonishing if SHA-512 turned out to be a permutation on 512-bit inputs, so no, absent a publication-worthy breakthrough in SHA-512 analysis, the output would not be exactly $2^{512}$ distinct hashes.

If collisions occur, would the amount of collisions and the 'size' of the collisions (approximately) be the same as statistics would predict after randomly generating $2^{512}$ 512-bit strings? (With 'size' I mean the amount of times a specific hash occurs)

As far as we know, yes. The usual model is a uniform random function. Under each distinct input, the output is an independent uniform random bit string. This model is like writing down a giant book of outputs with $2^{512}$ pages, one page per input having the corresponding 512-bit output, where every output is chosen independently and uniformly at random—which is exactly what you just described.

If we examine the structure of SHA-512 under the hood—a block cipher, which we might call ‘SHACAL-512’ (related to SHACAL-2, which is the block cipher underlying SHA-256), in Davies–Meyer composition—for 512-bit message $m$, we have $H(m) = E_{\operatorname{pad}(m)}(h_0)$ where $h_0$ is the standard initialization vector. In the ideal cipher model, every distinct 1024-bit string $\operatorname{pad}(m)$ gives rise to an independent uniform random permutation $E_{\operatorname{pad}}(m)$, whose output on a fixed input string $h_0$ is then an independent uniform random 512-bit string. Absent cryptanalysis of ‘SHACAL-512’, there isn't a much better model for this either.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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