How to test distribution of a hash function?

Question

From what I've found, it is generally accepted a cryptographic hash function like SHA-2 has an evenly, randomly distributed output. Is there a way to test this without running through the entire 2^512 keyspace? Generate a large number of high-quality 512 bit random numbers? What about random 64 character "keyboard ascii" strings?

Answer 1

Well, for one, SHA-2 (either SHA-256 or SHA-512) doesn't have a 'keyspace'; that's because it doesn't have a key. SHA-2 takes an arbitrary bitstring is input, and generates an output; while there are limits on how long the bitstring can be, those limits are so huge ($2^{64}-1$ bits for SHA-256, $2^{128}-1$ bits for SHA-512), those limits can in practice be ignored.

With that nit aside, your question is 'given arbitrary inputs (that is, inputs that are not specifically selected with the SHA-2 hash in mind), does the SHA-2 hash functions really generate outputs that are evenly distributed?

To test that, you can use any input distribution that strikes your fancy (as long as inputs aren't repeated; that would bias the statistics, and as long as you're not selecting inputs specifically because of what their SHA-2 hashes are). You can certainly consider random 512 bit (or whatever size) bit strings, or random 64 character strings. I would personally advise you to look at "related inputs", that is, inputs that are similar (for example, a 512 bit counter that increments for every hash) -- similar inputs are more likely to stress the SHA-2 function.

Now, one final comment: while you can verify a weakness in SHA-2 with this procedure (although it's extremely unlikely you'll find anything); you cannot verify that SHA-2 is actually well-distributed. Just because the tests you run cannot find anything doesn't mean that a different set of tests wouldn't.