How To Safely Verify MACs With Go And PHP Examples
Tags: go, php, cryptography, security
Published: 2023-02-23 23:06:51


I wanted to write this short article to explain the recent learning I had while reading on Message Authentication Codes (MACs).

First, let's briefly explain what MACs are and how they can be useful to us.

MACs (Message Authentication Code) are cryptographic algorithms that use a hash function and a secret key (they are also called symmetric cryptographic algorithms) to generate what's called an `authentication tag`  or just `tag`, which is used to verify the integrity (the message wasn't changed) & authenticity (the sender's identity) of the message given knowledge of the secret key.

The most widely used MAC in the wild is what's called an HMAC: Hash-based MAC. Like its name suggests, it's a way to use hash function with a secret key. HMACs can be used with SHA128, SHA256, SHA512... etc. The result of an HMAC function is called hmac or tag. I'll use the lowercase hmac from here on in this article.

In other words, if you and I agree on a secret key and a hash algorithm to use we can effectively share messages, that only we can verify the authenticity & integrity of. No one can tamper with our messages in transit.

Let's start off by creating an example Go program that creates an HMAC of some data, and then verifies it, using SHA256 hashing algorithm and a strong, randomly generated secret key.

```go
package main

import (
	"crypto/hmac"
	"crypto/sha256"
	"encoding/hex"
	"fmt"
	"strconv"
)

var secretKey = "randomly generated, secure secret key"
var data = "This is private information"

func hmac(data, secretKey string) string {
	hash := hmac.New(sha256.New, []byte(secretKey))
	hash.Write([]byte(data))

	return hex.EncodeToString(hash.Sum(nil))
}

func verify(data, hmac, secretKey string) bool {
	// Recompute the signature
	correctHmac := sign(data, secretKey)

	// Check if they are equal
	return correctHmac == hmac
}

func main() {
	hmac := hmac(data, secretKey)
	fmt.Printf("Data: %s\nHMAC: %s", data, hmac)

	fmt.Println()

	correct := verify(data, hmac, secretKey)
	fmt.Printf("\nIs HMAC %s correct ? %s", hmac, strconv.FormatBool(correct))
}
```

And here's a PHP example of the same functionality:

```php
<?php

const secretKey = "randomly generated, secure secret key";
const data = "This is private information";

function hmac(string $data, string $secretKey): string {
    return hash_hmac(algo: 'sha256', data: $data, key: $secretKey);
}

function verify(string $data, string $hmac, string $secretKey): bool {
    $correctHmac = sign($data, $secretKey);

    return $correctHmac === $hmac;
}

function run() {
    $hmac = hmac(data, secretKey);
    print sprintf("Data: %s\nHMAC: %s", data, $hmac);
    
    print "\n";
    
    $correct = verify(data, $hmac, secretKey);
    print sprintf("Is HMAC %s correct ? %s", $hmac, $correct ? "true" : "false");
}

run();
```

Both programs output are:
```
Data: This is private information
HMAC: cf824e1bfbc628aca8709483622f9c2aaf7ac9e57d50623d225cc76d8ad578fc
Is HMAC cf824e1bfbc628aca8709483622f9c2aaf7ac9e57d50623d225cc76d8ad578fc correct ? true
```

## The Problem with our code
Using `==` to compare hashes makes us vulnerable to a type of attack called Timing Attack. Because the == comparison returns as soon as it detects that the two hmacs differ, it's not suitable for this use case.

Because, an attacker can recreate the valid hmac by measuring how long it takes for the comparison to finish.

To put this into better perspective, let's make an example. Say we have 8 bit hmacs and each bit takes exactly `1ms` to compare it to the other hmac bit. The valid signature looks like this: `0001 1010`

- If I send you the correct hmac, then it should take exactly `8ms` for you to verify that it is in fact valid.
- If I now send you `1000 0000`, you'll reply in less than `1ms` that it's incorrect, because the first bit is incorrect. Remember it takes `1ms` to verify each bit.
- If I send you `0001 1001`, your reply will take about `6ms` because the first 6 bits are correct, but not the last 2.
- ... etc. and I keep doing this until you reply with `8ms` which then I know that it's the valid hmac.

And like that, I was able to re-create the valid hmac by updating my forged hmac and measuring how long it took you (the secret key owner) to verify it. Of course this is an overly simplified example, authentication tags produced by MACs should be at least `128 bit` to be strong enough and to avoid collisions.

The takeaway though is that **MAC tags comparison/verification should ALWAYS be done in constant time.** In our simplified example, whether the hmacs were equal or not it should always take the same `8ms` to return with the result.

*Note that this also applies to Digital Signatures (the asymmetric brother to MAC). Signatures also need to be verified in constant time to avoid timing attacks.*

## The Solution
I purposefully used the == operator in both languages to illustrate this problem but we should always use good and well known libraries when it comes to cryptographic operations and algorithms.
- In Go, we can verify hmacs in constant-time using `hmac.Equal()` from `crypto/hmac` package.
- In PHP, we can compare hmacs and hashes using `hash_equals()` function.

Let's rewrite our Go & PHP examples using the correct way. I'll just rewrite the `verify` function as it's all we need.
```go
func verify(data, signature, secretKey string) bool {
	// Recompute the signature
	correctSignature := sign(data, secretKey)

	// Check if they are equal
	return hmac.Equal([]byte(correctSignature), []byte(signature))
}
```

and the PHP example will look like this
```php
function verify(string $data, string $signature, string $secretKey): bool {
    $correctSignature = sign($data, $secretKey);

    return hash_equals($correctSignature, $signature);
}
```

### How to do constant-time comparison
Let's dive a bit deep and see how `hmac.Equals()` is implemented. The source code reveals that it actually uses a function from the `crypto/subtle` package called `ConstantTimeCompare`, which is implemented like this:

```go
func ConstantTimeCompare(x, y []byte) int {
	if len(x) != len(y) {
		return 0
	}

	var v byte
	for i := 0; i < len(x); i++ {
		v |= x[i] ^ y[i]
	}

	return ConstantTimeByteEq(v, 0)
}
```

- We return early if the two slices are not of equal length, because in that case we know that entirely different hashing algorithms were used.
- Next, create a byte variable `v` which will hold our result.
- Then we iterate over the slices and we XOR each slice element and the result is ORed with the variable `v`. That is, if the two bytes we're comparing are different the XOR will be 1, ORed with `v`, `v` will be equal to 1, and will stay 1 for the entirety of the loop. `v` will only be 0 if all bytes from the two slices are the same.
- Then, taking another precaution, and we also compare the two bytes `v` and 0 in a time constant manner using `ConstantTimeByteEq`.

Whether the two slices were equal or not, the function takes the exact same time to return, which makes it timing-attack safe.

And that's it! Thanks for reading and until the next episode, have a great day!