Timing side-channel attack example

Question

I understand that timing side-channel attack is a measurement of time taken to execute cryptographic algorithms. I'd like to see a simple example that explains how timing attack takes a place on any cryptographic algorithm.

Thank you.

Answer 1

One tangible example is timing attack on string comparison. It works by measuring how much it takes for the application to compare 2 strings.

The default string comparison implementations in nearly all programming languages are optimized and they work by comparing 2 strings character by character and they alert a mismatch as soon as they see a difference between the 2 characters currently being compared.

So if we have this code in our application:

def string_compare(a, b) :
    if (a == b)
        return True
    else
        return False
1: string_compare('abcdefg', 'abctyf2')
2: string_compare('abcdefg', 'abcdefb')

What happens is that (1) and (2) are going to take different amount of time to run. (1) fails faster than (2) so if we change our input (second string) one character at a time by measuring the time it takes for the function to return, we can guess the first string.

To mitigate this timing attack we have to change our code so that it takes a fixed amount of time regardless of what the inputs are:

def safe_string_compare(a, b) :
    if (sha256(a) == sha256(b))
        return True
    else
        return False
OR

def safe_string_compare(a, b) :
    if len(a) != len(b):
        return False

    result = 0
    for x, y in zip(a, b) :
        result |= x ^ y
    return result == 0

I find this reference helpful: coding rules