Monday, June 16, 2008

MSP430 BSL Passwords: Brute Force Estimates and Defenses

by Travis Goodspeed <travis at utk.edu>
at the Extreme Measurement Communications Center
of the Oak Ridge National Laboratory
regarding the work of
Alexander Becher, Zinaida Benenson, and Maximillian Dornseif
with minor additions and comments.

The MSP430 microcontroller uses its 256-bit interrupt vector table (IVT) as a password for its serial bootstrap loader (BSL), which can remain activated despite a blown JTAG fuse. As code confidentiality then depends upon the BSL password, this article will make some preliminary observations as to the difficulty of guessing the password. It doesn't attempt to be terribly thorough, precise, or academic. Rather, consider this to be a few `back of the napkin' notes on breaking the password. Further, the scope of this article is limited to the brute forcing of passwords. Alternatives to brute forcing will not be discussed here.

A good starting point would be [1] Tampering with Motes: Real World Physical Attacks on Wireless Sensor Networks. It's an excellent paper, but be sure to get the 15-page version; the 4-page variant is no substitute. This article will begin by recapping their estimate of the BSL password strength, and it will conclude with the source code of a Perl script mentioned--but not included--in that paper.

The issue at hand is that the MSP430 reuses its interrupt vector table (IVT) as a password. Thus, while the password is technically 256 bits in length, many of those bits are either fixed or predictable. Further, as the BSL allows for direct memory access to the device, it might be used to compromise keys where the firmware is known.

Becher et all attempted to determine the minimum keyspace, which is to say the number of bits out of 256 which are truly unpredictable in a rather small program. Beginning with 256 bits in an array of sixteen 16-bit interrupt handler function pointers, their reasoning follows: (1) As all MSP430 instructions must be even-aligned, every valid interrupt handler must have a least-significant bit of 0. Therefore, the space is reduced to 16*15=240 bits. (2) As the reset vector always points to the beginning of flash memory, the space is further reduced to 15*15=225 bits. (3) All unused interrupts point to the same address. As a worst case would have at least four distinct handlers, the keyspace will be reduced to no less than 4*15=60 bits by this observation. (4) As code is placed in a contiguous region of memory, a smaller program would have less are in which to place interrupt handlers. Supposing the program uses only 2^11=2kb of flash memory, the key domain is reduced to only 4*10=40 bits.

Note that as the intent is to come up with a reasonable minimum, claims (3) and (4) above refer only to a reasonable minimum of program security. An average, complicated ZigBee application might well have many more bits of randomness. They then measured that the speed of a brute forcing algorithm is 12 passwords/second at 9600 baud, 31p/s at 38,400 baud, and 83p/s at 38,400 baud with a modified client. They state a theoretical limit at 38,400 baud of 150p/s. Rounding off to 2^7=128 passwords per second, they conclude that brute forcing would be limited to 2^(40-7-1)=2^32 seconds, which is roughly equal to 128 years.

I'd like to briefly consider how brute forcing might be sped up beyond their estimates, even if such a speed-up is not of sufficient magnitude to make unassisted brute-forcing of the BSL feasible.

While the most recent revisions of the BSL require a password for changing the baud rate, V1.60 and V1.61 have no such requirement[2]. When using this command, the BSL client sends three bytes: D1, D2, and D3. D3 is what we would expect: 0x00 for 9600 baud, 0x01 for 19200 baud, and 0x02 for 38400 baud. D1 and D2, however, are much more interesting. They are written directly to the clock module control registers! (DCOCTL and BCSCTL1 on F1xx/F2xx; SCFI0/SCFI1 on F4xx.) These two registers control the frequency of the device, and they may be set to anything the device supports, which is in excess of the 4.2Mhz required for 38400 baud. Further, bytes are read by bit-banging, which is calibrated by the 0x80 synchronization character. By sending 0x80 too quickly and setting the microcontroller to 8 or 16mhz, it should be possible to brute force at a much faster rate. 2^9 passwords is a reasonable rough estimate; a bit more might be possible. 32 years is still too slow to be practical, but perhaps with possession of another revision of the target firmware image this speed-up might be valuable.

Suppose that you wish to maximize the security of the BSL password on your MSP430-based device, and you don't want to disable the BSL entirely. Becher's solution from [1] is a Perl script which replaces each interrupt pointer in the IVT with a pointer to another address, which contains a branch to the original address. At the cost of a few extra cycles on each interrupt, it can considerably increase the difficulty of brute-forcing a password. Most importantly, by separately randomizing the vectors of every device you ship, it is possible to defend against an attacker who has a copy of the firmware but does not have internally held keys of a device from reading those keys through the BSL.

In August at Black Hat USA 2008, I'll be presenting a timing attack which makes it possible to break some revisions of the BSL in short order.

[1] Tampering with Motes: Real World Physical Attacks on Wireless Sensor Networks
[2] SLAA089: Features of the MSP430 BSL


#!/usr/pkg/bin/perl
use warnings;
use strict;

# Use with Intel Hex files for Texas Instruments MSP430 microcontrollers.
# Replace ALL interrupt vectors with addresses generated randomly.
# Store jump instructions to the original interrupt handlers there.

# Written by Alexander Becher <alex@cyathus.de>, 2005.
# Use freely.

# $start and $end define the address range into which new vectors will point.

# The start address will be updated by the Ihex reading code below.
# It must be correctly aligned.
my $start = 0x4000;

# This is where the interrupt table starts. Addresses >= $end will not be used!
my $end = 0xffe0;

my $align = 2; # code addresses on MSP430 must be even

my %used; # will contain used memory regions

my @interrupts; # stores the original interrupt vector table

# Read an Intel hex file. With much help from BFD.
while (<>) {
my ($len, $addr, $data, $checksum)
= (/^:([[:xdigit:]]{2})([[:xdigit:]]{4})00([[:xdigit:]]*)([[:xdigit:]]{2})\cM?$/);

## Does not work? What did I do wrong??
# if (m/^: # colon
# ([[:xdigit:]]{2}) # data length
# ([[:xdigit:]]{4}) # address
# 00 # record type
# ([[:xdigit:]]*) # data
# ([[:xdigit:]]{2}) # checksum
# \cM?$/x # CRLF
# ) {

if (!defined $addr || ($addr ne "FFE0" && $addr ne "FFF0")) {
# update start of unused address region
# assume ascending order of addresses
# (i.e. it is not the case that there is a line in the hex file
# which contains code for address 0x4242 which is followed by a
# line which contains code for address 0x2323)

# assume all data first, then interrupts, then trailing stuff
if (defined $addr && defined $len) {
$start = align(hex($addr) + $len);
}

print;
next;
}

# If we reach this point, we are reading the first or the second
# line of the interrupt vector table.

# Attention: MSP430 is little endian!
while ($data =~ /([[:xdigit:]]{2})([[:xdigit:]]{2})/g) {
push @interrupts, hex "$2$1";
}

# If this is the second line, do The Real Work[tm].
if (@interrupts && $addr eq "FFF0") {
replace_interrupts(@interrupts);
}
}

#
# Why this program exists ;->
#
sub replace_interrupts {
my (@interrupts) = @_;

foreach my $addr (@interrupts) {
# Create a branch instruction to the original address of the handler
my $instr = br($addr);

# Get a new, unused address, using key material
my $new_addr = new_addr(length $instr);

# write a branch instruction there, mark appropriate addresses as used.
code($new_addr, $instr);

# point interrupt vector to new address (use Perl's loop aliasing)
$addr = $new_addr;
}

print ihex(0xFFE0, map { rep_16bit_le($_) } @interrupts);
}

#
# Returns a new random unused address suitable for putting code of
# $length bytes there. Return value will be aligned.
#
sub new_addr {
my ($length) = @_;

my ($addr, $diff);

$diff = ($end - $start) / $align;

# create a new random address until an unused region of the desired
# length is found
do {
my $n = int rand $diff;
$addr = $start + $n * $align;
} while (grep { $_ } map { isused($addr+$_) } (0..$length-1));
# Woohoo, Perl's list processing rocks. ;-> The above was a crude
# form of "Is any address in the region [$addr, $addr+$length) used?".

return $addr;
}

sub isused { $used{shift()} }

sub mark_used {
my ($addr, $len) = @_;

foreach ($addr .. $addr + $len) {
$used{$_} = 1;
}
}

#
# Place $code at $addr (which must be aligned). Outputs an ihex line
# which says just that, and marks the memory area as used.
#
sub code {
my ($addr, $code) = @_;

my $l = length $code;
mark_used($addr, $l);

print ihex($addr, $code);
}

# MSP 430 branch instruction
sub br { "\x30\x40" . rep_16bit_le(@_) }

# 16 bit little endian representation
sub rep_16bit_le { pack("v", @_) }

# ihex($addr, @data)
# write an ihex line, saying that $addr contains bytes @data
# @data should contain "\xXX" binary data
sub ihex {
my ($addr, @data) = @_;

@data = split //, join("", @data);

my $type = 0; # data

my $ret = "";

while (@data) {
my @bytes = @data >= 16 ? (splice @data, 0, 16) : (splice @data);

my $c = @bytes;

# XXX pack?
my $data = join("", map { sprintf "%02X", ord $_ } @bytes);

# checksum computation from GNU binutils bfd/ihex.c
my $checksum = $c + $addr + ($addr >> 8) + $type;
foreach (@bytes) {
$checksum += ord;
}
$checksum = (- $checksum) & 0xff;

$ret .= sprintf(":%02X%04X%02X%s%02X\cM\cJ",
$c, $addr, $type, $data, $checksum);

$addr += 16; # wrong for last iteration, but irrelevant then
}

return $ret;
}

# round up to the nearest multiple of $align
sub align {
my ($n) = @_;
if ($n % $align != 0) {
$n += $align - ($n % $align);
}
return $n;
}

3 comments:

Chris said...

Awesome article. I look forward to hearing your talk at BH USA 2008.

Croelan Grandez,Jr said...

Hi Travis, My name is Croelan from Lima - Peru. I've seen your blogger where a post stating that you can break the MSP430 BSL password. Now, I'd appreciate to send the steps to crack the password of an MSP430F2011 microcontroller, I have a FET-Texas Instruments MSP430 device with JTAG. I want to know how to use with devices that I have to break the password.
My email is croelanjr@cbs-corporation.com.pe

User said...

I don't understand the part where the key domain is reduced to 40 bits.
Why must the reset vector point to the beginning of the flash? I can
let it point anywhere in flash and start my processing there...
Why must unused interrupts point to the same address? Why can't I
scatter their entires anywhere in the address space - maybe even with
odd addresses (never tried that)?