MSP430 Side-Channel Timing Attacks, Part 1

by Travis Goodspeed <travis at utk.edu>
at the Extreme Measurement Communications Center
of the Oak Ridge National Laboratory

regarding ongoing work performed in collaboration with
David Carne <davidcarne at gmail.com>

What follows is a brief introduction to microcontroller side-channel timing attacks, as one might find them on the MSP430 microcontroller. This sort of attack is most commonly used against cryptography, but my present discussion will focus on attacking password-comparison routines. Be sure to check your own code--as well as that of your library vendors--for this issue.

Suppose that a password protection routine accepts a password through the serial port from an untrusted source, compares the password, and raises the privilege level if the password is correct. We will consider the following attempts at implementing such protection.

strcmp

Using strcmp() is clearly not a secure option, because it leaks information. Let us consider the implementation from the strcmp article at Wikipedia.

int strcmp (const char * s1, const char * s2){
   while ( *s1 == *s2 && *s1 != '\0' ) {
        s1++;
        s2++;
   }
   return *s1 - *s2;
}

This function--when used to compare passwords--runs in linear time, which is to say that every correct letter of the password adds a constant amount of time to the function's execution. By measuring the time that it takes to return, an attacker can guess the password one byte at a time. So an attacker could guess a 32-byte password in at most 32*256=8192 attempts, instead of the 2^^(8*32) attempts that might naively be assumed.

Another Attempt

Aversion to the C string comparison function is often enough to prompt authors to come up with creative comparison methods. One vendor uses a scheme similar to the following:

• An access control variable is set to 1.
• For each input byte:
  • The input byte is compared to the matching byte of the password.
  • If the two differ, the access control variable is cleared.
• Access is granted if the access control register is still set.

The center of this loop, if isolated to be a function, looks something like this:

void check(char a, char b){
  if(a!=b)
    access=0;
}

When compiled to assembly language with GCC, the result is the following:

    c040:       4d 4f           mov.b   r15,    r13     ;
    c042:       4d 9e           cmp.b   r14,    r13     ;
    c044:       02 24           jz      $+6             ;abs 0xc04a
    c046:       82 43 22 02     mov     #0,     &0x0222 ;r3 As==00
    c04a:       30 41           ret

Which has the following flow diagram:

Even though the password comparison is now independent of length, there is a still a variance in timing. Every incorrect byte of the password will add four cycles of execution time to the comparison! To fix this, it's necessary to make an else{} clause which balances the timing.

In practice, it's often only possible to determine whether a guess regarding timing is correct or incorrect. This is done by "gambling a clock edge", using non-standard timing in a serial protocol such that an edge is detected under one timing but not detected in another. Using this technique, the worst-case time for guessing is the same as the strcpy() example.

The possibility remains, however, that still more information may be leaked. In such a case, because all bytes are compared, it might be possible to break the password in significantly fewer attempts. The fastest cracking case would be one in which each byte's correctness could be individually determined, in which case the password could be guessed in 256 attempts.

Balanced Timing

A proper password comparison ought to look like the following, which takes the same amount of time to execute, regardless of the password's correctness.

Proper support for automated timing analysis isn't yet available in msp430static, but its insflow() sub--which was used to generate the diagrams above--does a lot of the work. To reproduce these diagrams, dump the flow graph to disk then annotate timing to match the Instruction Timing section of the mspgcc manual or the Instruction Cycles and Lengths subsection of the Instruction Set section of an MSP430 family guide. The Single Line MSP430 Assembler is also handy.

I'll be writing more on this topic in the near future, perhaps citing some examples of this vulnerability that I've located in the wild.