# Understanding one-way hash functions construction

I understand the needs that lead to the development of cryptography and I am quite familiar with the uses we make of the cryptographic tools.

But, as a programmer, I am conditioned to see them as "black boxes" with specific properties. To me, SHA-X (with X being 1, 2 or 3) is some dark magic, even though I understand why I need it and use it.

That said, I am eager to find some literature to light this up.
From what I have read so far, I have seen that the common mathematical demonstrations consist of games and the evaluation of the winning advantage of an enlightened attacker over a player that would just randomly take decisions. This is exactly the kind of things I am looking for : what mathematical background lead to this construction for this hash function. Learning through an example can be worthy, but the more global this maths background is, the better.

To say it in other words, how does a cryptographer prove the essential properties of his design ? In the case of cryptographic hash functions, these properties are one-wayness, collision resistance and preimage resistances.

What are the logical steps, starting from the required properties, that lead to the specification of a hash function ? How are these properties translated into mathematical definitions ?

Note : I think I needed to ask that last question because for a cryptographic hash function, I feel there is the need to define some thresholds somewhere.

• I'm having a hard time telling exactly what you are looking for. The title leads me to believe you are looking for a reference to a paper/video/lecture notes/etc that will better describe one-way hash functions. If so, please note that reference requests are considered off topic here. The body of the question seems to be more looking for reasons why hash functions are analyzed using mathematical games. – mikeazo Apr 4 '13 at 14:16
• Are you looking for references on ciphers, or on hash functions? They are very different beasts. I suggest you pick one and edit the question appropriately. – D.W. Apr 5 '13 at 1:32
• @mikeazo, actually it's a bit related to the second hypothesis you were formulating. I edited the question – Rerito Apr 5 '13 at 8:13
• @D.W. I am aware that they are very different although they can be linked together and the fact is ... I am interested in both ! But for the sake of simplicity, I will prioritize hash functions this time – Rerito Apr 5 '13 at 8:15
• You have to tone down your hopes: AFAIK, there is no method around to construct practical hash functions that demonstrably pass "game tests", unless we start from something (like a block cipher) assumed to pass similar "game tests". Classic constructions are the Merkle–Damgård construction and variants; see the HAC. A more modern one is the sponge construction. – fgrieu Apr 5 '13 at 9:50

First, it's important to understand that no one knows how to build a practical hash function that is provably secure.

The stuff you've read about games and advantage are part of a theory for proving schemes secure, but that theory doesn't help you build a provably secure hash function all that much. Rather, it starts from the assumption that a particular hash function is secure (or a block cipher or stream cipher is secure), and then builds more complicated stuff out of those basic building blocks. So, that theory doesn't help us design the basic building blocks, like hash functions, in the first place. (Sometimes the theory is used to help guide the design of the structure of a hash function, where designers build a hash function out of a building block like a compression function. The designers might use the theoretical analysis to demonstrate that if the compression function is good, then the hash function will be good -- but it doesn't help you with the question of how to design a good compression function.)

For more details on how we know that a hash function is secure, see my answer to a similar question (on the IT Security Stack Exchange site).

Generally speaking, to learn how to build a secure hash function, you start by learning about all of the various attacks on hash functions. Then, you try to design a hash function that will resist all of those attacks (as well as all others you can imagine). Therefore, a good starting place for you would be to read about attacks on hash functions.

You could start by reading Chapter 9 of the Handbook of Applied Cryptography. Also check out Wikipedia's articles on cryptographic hash functions and the Merkle–Damgård construction. Then, you could read all of the submissions to the NIST hash algorithm competition; most of the submissions should provide a design rationale and security analysis, which should give you a chance to read about some of the attacks on hash functions and design strategies. They should also cite related papers in the research literature, so next you could read papers in the research literature on hash function cryptanalysis -- you might start by reading the papers cited in the Wikipedia links mentioned above, then proceed to reading papers that are cited in submissions to the NIST competition or that you find through others means. For instance, it's worth reading about parallel collision search, multicollision attacks, indifferentiability, and the sponge construction.

After several years of study, you'll be well on your way to becoming an expert in hash function cryptanalysis, and then you might be ready to start thinking about designing your own hash function.

• I don't claim to design my own hash function ! I just wanted to understand how the designers of such tools make their choices (I mean in a global scale). By the way, excellent guidance that I will follow right away – Rerito Apr 8 '13 at 7:42