Last week, we saw why SHA256 is 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 IWTokenIWToken = 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 roughly equal to S2 = SHA256(SecretKey || M1 || M2) (more on that later) where M2 is malicious data appended to M1, without knowing SecretKey, only it's size.

In our example, we will 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 can create an IWToken like 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 (please don't forget to star the repo 🙏).

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 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
c) Append the size of the message in bits as a big endian uint64: (32 + 19) * 8 = 408 = 0x00000198

After all these steps, the initial 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

Why does it matters?

In order to create a forged signature, we will need to generate some padding so that our malicious data &something=true&role=admin is appended after this padding. Remember, 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 signature (hash): 5b0b4b2472778fea87faac08a72a47d24538bff9d7f19a3a85d069893e2b08ab.

Go does not expose SHA256's internal state, so we need to copy the files sha256.go and sha256block.go 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:

1. We generated a malicious message MaliciousMessage = LegitimateData || padding(SecretKeyLength, LegitimateDataLength) || MaliciousData
2. Loaded the legitimate signature's state SHA256(SecretKey || LegitimateData) and appended our MaliciousData
3. Which allowed us to generate a MaliciousSignature that will return true for MaliciousSignature(LegitimateSignature, MaliciousData) == SHA256(SecretKey, MaliciousMessage).

You can run the code:

$ go run ./
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 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 such as 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 like in the Signal Protocol or in JSON Web Tokens.

As always, you can find the code on GitHub: github.com/skerkour/kerkour.com (please don't forget to star the repo 🙏).

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).