8
$\begingroup$

In reading about the Bitcoin protocol I noticed how much its proofs-of-work apparently depend on uniformity of the SHA-256 hash function. And so presumably do many other applications.

How do researchers go about proving uniformity of proposed hash functions? Is it just an empirical matter of running many inputs through the function and observing the distribution of outputs, or can one formally prove the property? Where could one (non-crypto-expert) learn about how such proofs are constructed and look one up e.g. for the case of SHA-256?

Improve this question
$\endgroup$
  • 2
    $\begingroup$ I'll leave it to someone else to write up a formal answer but I believe the short answer is that there is no proof. One can sort of offer mathematical arguments that SHA-256 is secure against such and such attack, or has such and such general property, but by and large it's just a matter of cryptographers around the world banging as hard as they can on it and seeing it if breaks. Symmetric cryptography is nothing like number-theoretic crypto which is much bigger on actual proofs (cf. factorization, DLP, DDH, ..) $\endgroup$ – Thomas Dec 21 '13 at 3:50
  • 2
    $\begingroup$ It relies on partial pre-image resistance, not uniformity. It's trivial to create hash functions with provably uniform output (such as the identity function) but that doesn't mean they're secure. $\endgroup$ – Antimony Dec 21 '13 at 8:25
10
$\begingroup$

Uniformity is a tricky one. SHA-256 (as well as SHA-3 for that matter) follows a heuristic approach. That is, the design is not based on a hardness assumption (for example, the factoring or discrete-log assumption) but on criteria that have only been verified empirically. As such, also the study of uniformity is an empirical study. The development of SHA-1/SHA-2 was not a public process (it was developed by the NSA and NIST) and no rationale as to design choices were given. What you usually do in this case is to run statistical tests and see if any of them indicate any weaknesses. For example, a simple test would check that every single output bit is set to 1 with probability 0.5. A suite of statistical tests that, I believe, was used in the evaluation of AES was published by NIST (http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html).

If you want to go into more detail I would have a look at the SHA-3 competetion. Here, every candidate had to provide an elaborate and convincing case for why this candidate is a good pseudorandom function. You can find the documents for Keccak (the new SHA-3) on http://keccak.noekeon.org/files.html. The Keccak reference has a whole section on the analysis of Keccak as a pseudorandom function.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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