The Weaknesses of MD5, SHA1 and SHA-256 — The Length Extension Attack

The foundation of trust in cybersecurity is layed by the simple concept of data hashing, and where we take data and create a fixed-length hash for the data. If we cannot trust our hashing methods, we are in trouble. When we creating the perfect message hash, we thus need to make sure we have:

• Collision resistance. This is where it is extremely difficult to find two messages which have the same hash. Thus we should not be able to find the has of two messages (M1, and M2) that are the same, within a reasonable time: H(M1)=H(M2).
• Pre-image resistance. If we already have a hash value (h), it should be extremely difficult to find a message which will give the same hash. Thus for a given hash (h), it is difficult to find a message (M1) for H(M1)=h.

The original hash methods were often based on the Merkle-Damgård (MD) construction. With this, we create a hash function using blocks of data. Based on the MD constuct, Ron Rivest created the MD5 hashing method, and it was widely adopted in the industry. It works by taking a static initialisation vector (IV) and then feeding this into a one-way function (f), along with a block of the message. We feed this output into the next stage, and so on until we get to a message pad at the end:

Figure 1: The MD construct

The one-way function (f) will generally compress the data and produce fewer bits out than are fed in. Unfortunately, the MD construct has many weaknesses, and one of the most serious is the length extension attack. With this an adversary (Eve) can take a hash for an unknown message, and then add additional data to produce a new valid hash.

So Bob could take a hash of a password that he and Alice know (“qwerty123”) and the append with a message (“hello”) to produce:

H(Password || Message)

an where “||” identifies the appending of one string onto another. Thus when Bob sends a message to Alice, she will prepend the message with the shared password, and generate the same hash. In this way, Bob has proven the message and…