Subscribe
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 a 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 a 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 a 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 a 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 Stack Exchange, 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 a 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 a 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.
Continue Reading
