0
$\begingroup$

Using and benefiting from hash functions on a daily basis, I keep wondering how hash functions actually work down in their core.

Most of the available resources I found, only explained hash functions on a very high level, usually referring to their awesome properties and some of them mentioning something like reducing inputs.

But HOW does functions like Sha actually work on a very concrete level?

How to they actually implement something like collision resistance?

$\endgroup$
  • 1
    $\begingroup$ Hmm, this is a very broad question. Most crypto textbooks go over this in an entire chapter (for example HAC Chapter 9). Even then it is only going over principles and some methods to achieve security properties. Is there something we can do to make the question more narrowly scoped? $\endgroup$ – mikeazo Aug 9 '16 at 15:50
  • $\begingroup$ Please clarify. Have you looked at the definition of e.g. SHA-1? Are you asking what the hash function does or why it does those things? $\endgroup$ – otus Aug 9 '16 at 15:52
  • $\begingroup$ If I want to implement one myself how would I start? What operations would be in it? $\endgroup$ – Daniel Hitzel Aug 9 '16 at 15:59
  • 1
    $\begingroup$ Try the simple substitution /permutation network type. Look up a Google Image of one, then try to code it with eight 8 bit S boxes. This will form a 256 bit wide hash block. You can make a S box with just an 8 bit random permutation. That forms a random substitution of bits as: out = Box[in]. Then distribute the bits between the S boxes as per a diagram. Do 3+ iterations and it'll work, but it's not very clever. Just remember to distribute on the bit level and not the byte level. It's relatively easy with just bit moving operations. It's a start... $\endgroup$ – Paul Uszak Aug 10 '16 at 13:14
5
$\begingroup$

There are a variety of ways to construct a hash function. The two you will probably hear about the most are the Merkle–Damgård construction and the sponge function. The former is an older construction(dated 1979), and suffers from length extension attacks. New hashes might opt for the sponge construction, as it is immune to that particular attack.

As for how they work, they both contain an internal state, and operate on that state using a function that is actually invertible.

The Merkle–Damgård construction

In the case of the Merkle–Damgård construction, the function used is usually a block cipher. Normally, the go-to example of a block cipher is AES, but because of a related key attack, you would not want to use it to make a hash with this particular construction.

Basically, in the Merkle–Damgård construction, successive blocks of the hash input are used along with the internal state as the inputs to a block cipher; This is also how the construction compresses large inputs into a finite state. This is another requirement of hash functions: the ability to operate on (effectively) arbitrary sized inputs, and produce a finite sized output.

As for collision resistance, the MD construction has a proof: "... that if the one-way compression function f is collision resistant, then so is the hash function constructed using it.".

However, according to wikipedia, the MD construction itself, has generic vulnerabilities that are not the result of an unsatisfactory compression function:

Unfortunately, this construction also has several undesirable properties:

  • Second preimage attacks against long messages are always much more efficient than brute force.
  • Multicollisions (many messages with the same hash) can be found with only a little more work than collisions.
  • "Herding attacks" (first committing to an output h, then mapping messages with arbitrary starting values to h) are possible for more work than finding a collision, but much less than would be expected to do this for a random oracle.
  • Length extension: Given the hash H(X) of an unknown input X, it is easy to find the value of H(pad(X) || Y), where pad is the padding function of the hash. That is, it is possible to find hashes of inputs related to X even though X remains unknown. Length extension attack was actually used to attack a number of commercial web message authentication schemes such as one used by Flickr.

It is possible to use the MD construction with a sort of capacity, similar to a sponge, by not outputting the entire state. This is where the ideas of SHA-224 and SHA-384 fit in, for example. They are simply truncated outputs of SHA-256 and SHA-512 (with other small modifications). By not revealing the entire state, length extension attacks may be foiled, depending again on the "capacity", or number of bytes dropped this way. However, usage of a capacity/truncating the state does come at the price of a reduced output rate.

The sponge construction

The sponge construction operates in a different manner. The sponge too, has an internal state, and it uses an invertible permutation to mix the state. Basically, the sponge "absorbs" a message block into it's internal state, then applies the mixing permutation, and repeats this until all message blocks have been consumed into the state. This is how the sponge compresses data. The absorption of data either happens by XOR'ing the message block into the state, or simply replacing a section of the state with the message block.

The sponge construction being uninvertible, resistant to length extension attacks, and preimage resistant is related to the use of a "capacity" section of the state. Basically, there is an imaginary line dividing the internal state into two sections, a "rate" section, and the capacity section. The output stage of the function only "squeezes" bytes from the rate section of the internal state. Since the capacity is never output directly, length extension attacks are resisted. The security of the sponge against attacks is related to the capacity size of the state, along with how well the mixing function resists things like differential cryptanalysis.

Padding

There is a little bit more to hashing then a confusing/diffusing primitive that compresses data. Since we require that it be infeasible to generate any preimage for a given output, and prevent anyone from finding collisions, things like padding of the input become very important, in order to prevent trivial collisions from being created. This is a contributor as to why the construction of a hash is more complicated and often times requires more applications (rounds) then simply encrypting some data.

Other compression functions

There is actually an entire wikipedia article about one way compression functions, and there a few constructions one could use:

Some methods to turn any normal block cipher into a one-way compression function are Davies–Meyer, Matyas–Meyer–Oseas, Miyaguchi–Preneel (single-block-length compression functions) and MDC-2, MDC-4, Hirose (double-block-length compressions functions)

$\endgroup$
  • $\begingroup$ I would not call bcrypt a cryptographic hash. That's a password hash, which is actually more a Password Based Key Derivation Function. PBKDF's have things like a work factor config and salt input which are generally not present for cryptgraphic hashes. Maybe mention Skein which is based on ThreeFish and uses MD construction. $\endgroup$ – Maarten Bodewes Aug 9 '16 at 22:15
  • $\begingroup$ I'm not sure about foiling length extension attacks using truncated output. SHA-224 only has 32 bits missing; that doesn't seem like a 112 bit decrease in length extension attack to me - an attacker could just bruteforce the missing 32 bits (if the protocol allows it, of course). $\endgroup$ – Maarten Bodewes Aug 9 '16 at 22:19
  • $\begingroup$ I think "However, the MD construction is old, and has generic vulnerabilities irrespective of the strength of the compression function. Nowadays, most new constructions will be of the sponge style." is too subjective. I'm not so sure, but I think most of the SHA-3 candidates were MD-style hashes, and some delivered XOF-like functionality as well. Same goes a bit for the last paragraph. Those are not that needed. The MD truncation could be made part of MD part and padding part is probably best seen as a separate part from the sponge construction (I'm trying to improve the answer here, sorry :P) $\endgroup$ – Maarten Bodewes Aug 9 '16 at 22:40
  • $\begingroup$ @MaartenBodewes Ok, I fixed most of those I think. The reason why I opted for Bcrypt was because there's a good and simple Q/A here about it. Is there a concise resource you are aware of that you can share that explains how skein functions? The wikipedia link about UBI chaining mode is non-existent, and the Skein paper is 100 pages with lots of unrelated material. $\endgroup$ – Ella Rose Aug 9 '16 at 23:18
  • $\begingroup$ feel free to edit directly if ever necessary $\endgroup$ – Ella Rose Aug 10 '16 at 0:04
0
$\begingroup$

Essentially collision resistance is required to stop "Daniel" generating the same hash as "Daniel0000" taking note of the extra zeros. That is done by automatically appending some extra bits of data such as the length of "Daniel" to the input string, or filling the extra spaces with some data to indicate where "Daniel" stops and "0" begins. Or a combination of these.

Other than that, they don't specifically implement collision resistance in a hash in any other way. It occurs naturally as a result of a full avalanche effect. Avalanche effect is where all bits of the hash output have a 50% probability of changing if you change any single bit of the hash input. If the 50% thing holds true in your hash and you do get a collision, it's just statistical bad luck.

$\endgroup$

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