Simple attack on simple password authentication

Checking password byte by byte during authentication and denying access after encountering the first wrong byte is a perfect setup for a timing attack. We will show how to attack a program that operates in such a way.

We won’t use graphic analyzers provided in ChipWhisperer software. Instead, Jupyter notebooks will be in use from now on. The notebooks are much more flexible and convenient to use.

Jupyter comes with WinPython that was installed during ChipWhisperer bring up. In order to start using Jupyter you need to perform the following steps:

  1. Go to ChipWhisperer/WinPython* directory
  2. Run “WinPython PowerShell Prompt.exe”
  3. python -m pip install --upgrade pip
  4. python -m pip install jupyter tqdm
  5. (optional) If you don’t want to put every jupyter file in ChipWhisperer/WinPython*/notebooks, create a symlink. In PowerShell:
    • cd ../notebooks (assuming current directory was “ChipWhisperer/WinPython*/scripts”)
    • New-Item -Path [link name] -ItemType Junction -Value [dest path]
  6. Run “Jupyter Notebook.exe”

Jupyter should open in your default web browser. You can find the notebook for this attack and all the source files for the chip in our public git repo:

https://gitlab.com/myrelabs/devblog/tree/master/chipwhisperer/firmware/simple_password_timing

Let’s get started. We will attack the program provided by ChipWhisperer on XMEGA – simple_pass_timing.c. It waits for a password that is 8 characters long. The main thing that makes the program vulnerable to the attack is a loop that checks if bytes of the provided password are correct one by one.

while(1){
my_read(p, N);
trigger_high();
unsigned c = 1;
for(int i =0; i<N; i++){
if(p[i]!=q[i]) {
c = 0;
break;
}
}
trigger_low();
if(c) {
my_puts("Pass");
}
else {
my_puts("Fail");
}
}

The program is not time-invariant, which in this case means the time of execution depends linearly on the password length and that’s something we will use in our analysis. We can see it on power traces where the first four bytes of the provided password are correct:

Power trace for a partially correct password (4 bytes correct)
Power trace for an incorrect password

As we can see, both power traces stabilize after execution of all the instructions. Measurements after iteration ~600 in the first graph and after iteration ~430 are not dependent on the executed instructions. The loop in which characters are checked can be clearly seen in the first graph.

We will discover the first byte of the correct password using correlations between power traces. Firstly, we collect 256 power traces for passwords that start with a byte from 0 to 255 and zeros besides that. Below you can see a graph with correlations between the power trace with ‘0’ as the first byte of the password and traces with other first byte. Correlation drastically drops for only one byte: ’97’ representing character “a”. In this case it is enough to claim that it is the first byte of the password, because we can see a change in program’s behavior only for that byte.

Correlations of power traces

By looking at the graph with the correct first byte of the password we can suspect when the actual comparison of bytes takes place and where the ‘after loop’ part of the program executes. Thanks to that, we can take a pattern that we expect to occur in every execution of the program, regardless of the password input.

Orange rectangle – part of the program with byte comparison
Green rectangle – (more or less) part of the program that will occur at every execution

Now, if this pattern occurs later for one value of a byte on a particuler position then this value is the correct byte of the password. In other words, we can look for this pattern for each value and each byte position, note its offset and deduce the correct password byte from the offsets.

We will usethe code below to find the offset of our pattern. The pattern is taken from the captured trace for first byte value ‘0’, using trace points 250 through 449. The choice of the pattern is quite arbitrary, anything works as long as it’s after the compare iteration.

def find_offset(trace, pattern):
pattern_length = len(pattern)
correlations = []
for i in range (100, len(trace)-pattern_length):
correlations.append(np.corrcoef(trace[i:(i+pattern_length)], pattern)[0,1])
return np.argmax(correlations)+100

It is more than enough to start looking for the pattern starting from the 100th measurement in a trace. We simply test all possible offsets by computing correlation between all the fragments of the trace of the proper length and choose the offset with the highest correlation.

The final thing to do is to test all posible bytes one after another and look for the one which offset for the pattern is higher than for the others. In this manner we managed to recover the whole password.

num_of_letters_left = 7
while num_of_letters_left > 0:
    password_suffix = ''
    for i in range(num_of_letters_left-1):
        password_suffix += '\x00' 

    traces = []
    for i in range(256):
        traces.append(runone(password+chr(i)+password_suffix))

    offsets = []
    for i in range(256):
        offsets.append(find_offset(traces[i],pattern))

    password = password + chr(np.argmax(offsets))

num_of_letters_left -= 1

And the password is:

print(password)
aE!!23bY

Now, let’s apply some countermeasures – let’s implement time-invariant string comparison and run the attack again:

unsigned c = 0;
for(int i = 0; i<N; i++){  
    c |= p[i]^q[i];
}

Here we have power traces for correct and incorrect passwords:

Time-invariant version of the program on the correct password
Time-invariant version of the program on an incorrect password

And here we have a graph of correlations computed like before:

Correlations between power trace ‘0’ and other power traces. Red arrow points to a correlation with a power trace with the correct first character of the password.

As you can see, now we don’t leak any information that would indicate that ‘a’ is the correct value for first byte of the password – we secured the program against this timing attack.

Leave a Reply

Close Menu