Introduction to the

The Merkle-Damgard structure, known as the MD structure for short, is used to defend against collision attacks in hash algorithms. This structure is the basis for some excellent hash algorithms, such as MD5,SHA-1, and SHA-2. I’m going to talk to you about this MD structure and the length extension attack on it.

MD structure

The MD structure was described by Ralph Merkle in his doctoral thesis in 1979. Since Ralph Merkle and Ivan Damgard respectively justified this structure, it is called the Merkle-Damgard structure.

Next, let’s look at how the MD structure works.

The MD structure first populates the input message as an integer multiple of a fixed length (such as 512 or 1024). This is because compression algorithms cannot process messages of any length, so they must be populated before processing.

Typically, we use constant data, such as 0, to populate the entire message block.

For example, if our message is “HashInput” and the compressed block size is 8 bytes (64 bits), then our message will be divided into two blocks, the last block will be filled with 0, and we will get “HashInpu t0000000”.

But this is often not enough, because often the compression function will remove the extra 0 at the end, resulting in the same hash value computed if the function is filled or not filled.

To avoid this, you must change the first digit of the populated constant data. Since constant fill usually consists of zeros, the first fill bit is forced to change to “1”.

HashInpu t1000000.

We can also further enhance the padding, such as using an additional block to fill the length of the message.

While using an extra block is often a bit of a waste, a more space-saving approach would be to put the length of the message in the last block if there is enough space to fill the zero.

After the block is filled, the message can be compressed. Let’s look at the MD flowchart:

The message is divided into many blocks. The initial initialization vector performs f operation with the first block, and then performs f operation with the second block, and so on. Finally, the final result is obtained.

Length spread attack

In cryptography, the attacker can know the value of the hash(message1 ‖message2) by using the known hash(message1) and message1 length. Where ‖ indicates the connection. And offensive and need to know what Message1 really is.

The MD structure we mentioned in the last section is to divide the message into blocks. The value calculated by the previous block will be evaluated again with the next block. This structure can be very convenient for the attack of length stretching. The premise is that we need to know the length of the original message.

For example, suppose we have the following request:

Original Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo
Original Signature: 6d5f807e23db210bc254a28be2d6759a0f5f5d99

The example above is to send an egg-filled waffle to user number 1, with a message signature attached to ensure that the message is correct. The MAC algorithm used here to sign the message.

Suppose a malicious attacker wants to change the value of waffle from EGgo to liege.

So the new data will look like this:

The count = 10 & lat = 37.351 & user_id = 1 & long = 119.827 & waffle = eggo&waffle = liege

In order to sign the new message, typically, the attacker needs to know the key used by the message signature and generate a new signature by generating a new MAC. However, with a length extension attack, you can take the hash (the signature given above) as input and continue the hash output where the original request has broken off, as long as you know the length of the original request.

If we consider the padding, we need to restore the padding of the original message, and then add our attack code after the padding is restored:

New Data: The count = 10 & lat = 37.351 & user_id = 1 & long = 119.827 & waffle = eggo \ x80 \ x00 \ x00 \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00 \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00 \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00 \x00\x00\x02\x28&waffle=liege

So we can get the new MAC value:

New Signature: 0e41270260895979317fff3898ab85668953aaa2

Wide pipe

In order to avoid the length-extending attack, we can make some deformation to the MD structure.

First look at the Wide Pipe structure:

The process of wide Pipe and MD is basically the same, except that the generated interim encrypted message is twice the length of the final generated message.

And that’s why we have two initial vectors IV1 and IV2 in the figure above. If the length of the final result is n, then the length of the result generated in the middle is 2n. We need to reduce 2n length data to n length data in the final step.

Sha-512/224 and SHA-512/256 simply discard half the data.

Fast wide pipe

There’s also a faster algorithm than wide Pipe called Fast Wide Pipe:

Unlike the Wide Pipe, the main idea is to forward half of the previous link value to XOR, which is then XOR with the output of the compression function.

This article has been included in http://www.flydean.com/md-length-extension/

The most popular interpretation, the most profound dry goods, the most concise tutorial, many you do not know the small skills waiting for you to find!

Welcome to follow my public number: “procedures those things”, understand technology, more understand you!