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.
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
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 than1ms
that it's incorrect, because the first bit is incorrect. Remember it takes1ms
to verify each bit. - If I send you
0001 1001
, your reply will take about6ms
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()
fromcrypto/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.
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
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:
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 withv
,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 usingConstantTimeByteEq
.
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!
Top comments (1)
Have you tried ServBay.dev?
A much easier tool for PHP developer, which provides a much easier way, especially for beginners. It handles all versions of PHP, MariaDB, PostgreSQL, as well as Redis and Memcached. You can run multiple PHP instances simultaneously and switch between them effortlessly, without the need for any environment setup. This tool has simplified my PHP development and is definitely worth a try!