Why do we need to add a "sleep" method to make a constant time attack succeed?

Question

In this website: http://elijahcaine.me/remote-timing-attacks/ the author describes well what is a constant time attack and how to protect against this type of vulnerability.

But in the code that the author have done:

# secret.py
from time import sleep # Used to exaggerate time difference.
from sys import argv   # Used to read user input.

def is_equal(a,b):
    """Custom `==` operator"""
    # Fail if the strings aren't the right length
    if len(a) != len(b):
        return False

    for i in range(len(a)):
        # Short-circuit if the strings don't match
        if a[i] != b[i]:
            return False

        sleep(0.15) # This exaggerates it just enough for our purposes

    return True

# Hard-coded secret globals FOR DEMONSTRATIONS ONLY
secret = 'l33t'

# This is python for "If someone uses you as a script, do this"
if __name__ == '__main__':

    try:
        # The user got it right!
        if is_equal(str(argv[1]), secret):
            print('You got the secret!')

        # The user got it wrong
        else:
            print('Try again!')

    # The user forgot to enter a guess.
    except IndexError:
        print('Usage: python secret.py yourguess\n' \
             +'The secret may consist of characters in [a-z0-9] '\
             +'and is {} characters long.'.format(len(secret)))

I don't understand why we have to add this line to make the constant time attack succeed:

sleep(0.15) # This exaggerates it just enough for our purposes

In the website, the author says :

it exaggerates the time it takes to evaluate the is_equal function.

I've tried it, and we need a "sleep" method to make this attack succeed. Why we need to exaggerate the time?

Answer 1

There are two possible paths to take in the "match" loop:

for i in range(len(a)):
    # Short-circuit if the strings don't match
    if a[i] != b[i]:
        return False

    sleep(0.15) # This exaggerates it just enough for our purposes
    return True

1. if a[i] != b[i] evaluates as True - no match, exit from the function.
2. if a[i] != b[i] evaluates as False - match, continue to Sleep(0.15) before leaving function.

Sleep(0.15) if characters match adds significant time difference between these two paths. This in turn allows to simply use max of all attempts to identify correct character of the secret. Without this exaggeration you need to look for statistically significant differences in matching times.

Author mentioned this here:

Most important [for the author] we don't need to use StatisticsTM to figure the secret, evaluating each input multiple times and collecting/processing that timing data, it already takes about one magnitude longer to evaluate a matching letter than it does to evaluate a non-matching letter.

Use debug lines to see how times are different with and without sleep.

# Uncomment the following line for fun debug output
print('max {} min {}'.format(max(guess_times), min(guess_times)))

# Add this line to see full guess_times list    
print(['{:.2f}'.format(elem) for elem in guess_times])

Answer 2

Edit 1:

Why we need to exagerate the time ?

We need to exaggerate the time to showcase the time difference when two characters match and when they don't. So in this case, if the first character of a and b match, the method sleeps, then if the second characters don't match the function returns. This took 1 comparasion time + sleep(0.15) + 1 comparasion time. On the other hand, if the first characters don't match, the functions returns in 1 comparasion time, so the attacker can see, if they match any character or not. The example uses this sleep to demonstrate this time difference.

For this to not happen, the is_equal function should be implemented in a way, that the response time of the function is static.

Using the example you provided:

def is_equal(a,b):
    _is_equal = True

    if len(a) != len(b):
        return False

    for i in range(len(a)):
        if a[i] != b[i]:
            _is_equal = False

    return _is_equal

There is a built-in function in the secrets module which solves this problem. compare_digest()