Forging an SHA-1 MAC Using a Length-Extension Attack in Python

SHA-1 (Secure Hash Algorithm 1) is broken. It has been since 2005. And yet, that hasn’t stopped its continued use. For example, until early 2017 most internet browsers still supported SHA-1. As though to confirm that SHA-1 was really, truly dead, researchers from CWI Amsterdam and Google announced at the end of February 2017 they had performed a successful collision attack against SHA-1.

In this article, we’ll learn how to break an SHA1-keyed message authentication code (MAC), part of the authentication message that confirms the message came from the stated sender. This is useful for impersonating someone else. But first, some background.

What Is SHA-1?

SHA-1 is a cryptographic hashing algorithm designed by the United States National Security Agency back in the early 1990s. It is used to create a message digest, which in cryptography is a one-way mathematical algorithm that takes data of any size and maps it to a bit string of a fixed size (a hash function). So, feed SHA-1 an arbitrary amount of data and it will produce a 20-character message digest. Whether you input “Synopsys,” “I love cryptography!”, or Act I from Shakespeare’s Hamlet, the result will always be exactly 20 bytes.

People have used (and still use) SHA-1 to produce MACs. We’re going to break an SHA-1 MAC that has been prefixed with a key. Namely:

message digest = SHA1(key || message)

Given the message digest and message, it shouldn’t be possible to modify the message and produce a new corresponding message digest. That is, unless, there is complete knowledge of the key. This isn’t actually the case.

In this example, we’ll take the message “user=mantej;” and generate an SHA-1 message digest under an unknown key. We’ll continue to reverse engineer the hash, and use the result to create a valid message digest for the message “user=mantej; … ;admin=true” without any knowledge of the key.

But before we do that, let’s find an SHA-1 implementation and make a couple modifications.

Modifying SHA-1

For our example, we’ll use a pure-Python implementation of SHA-1 from StackExchange, and compare its output to an online SHA-1 calculator to verify correctness.

Figure 1. SHA-1 magic numbers

Now, a 160-bit SHA-1 hash is actually just made up of five internal 32-bit registers. These registers usually start at magic numbers (Figure 1).

We’re going to modify the function definition so that we can pass in an SHA-1 message digest and ‘re-create’ its state. We accomplish this by breaking our message digest into five 32-bit values (Figure 2), and passing in those values as function parameters in order to override the default magic numbers (Figure 3). By setting our own register values, we’re able to ‘pick up where we left off’ and append an arbitrary amount of data to the original message.

Figure 2. Breaking SHA-1 digest into five 32-bit registers

Figure 3. Overriding default magic numbers

Additionally, we need to append the bit-length of our forged message (Figure 4). Specifically, we need to compute length(key || original message with padding || new message). We can’t immediately compute this value since, if you recall, the key is completely unknown to us. Not to worry. So, let’s just brute-force–that is, bombard it with possibilities–for key length (Figure 5).

Figure 4. Inject bit-length of our forged message for length-extension attacks

Figure 5. Brute-forcing for key length

Performing the Attack

Let’s use a validate function that takes the forged message and forged message digest as input, computes SHA-1(key || forged message), and compares it to the forged digest. If they are identical (i.e., mission success!), validate() returns true. It looks something like this:

Figure 6. Validates our forged message digest under the secret key

For the sake of completeness, here’s the forge_message function:

Figure 7. Forges a message utilizing technique discussed above

Lastly, we’ll write a program that takes the message “user=mantej;” and generates an SHA-1 hash under a randomly generated secret key between 1 and 32 bytes. Utilizing everything described above, I’m going to brute-force for key length, append “;admin=true” to the original message, and generate a valid MAC under the secret key–without any knowledge of the key itself.

And. Here. We. Go.

Figure 8. Performing the length extension attack

Moral of the story? Only use SHA1(key || message) as a MAC if security isn’t important.