Thursday, June 19, 2008

Speaking at Last Hope

I'll be speaking at Last Hope in Manhattan next month. My abstract follows.

Introduction to MCU Firmware Analysis and Modification with MSP430static
The Texas Instruments MSP430 is a low-power, 16-bit microcontroller which is rapidly gaining in popularity in the embedded world. MSP430static is a tool for reverse engineering the MSP430's firmware. Following a quick tour under the hood of this tool, this lecture will demonstrate how to analyze, modify, and reflash a black-box firmware image.

The Last HOPE

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;
}

Sunday, June 15, 2008

Syringe Logic Probe, Revision 2


While my original probe is damned useful, it was a bit of a rushed job. Since then, I've found uncoated silver jewelry wire whose diameter is just a hair smaller than the inner diameter of the needle, allowing me to force it in for an electrical connection. More importantly, as I no longer solder to the outside of the needle, I can restore the safety cap and save my fingers from getting nicked.

--Travis Goodspeed
<travis at utk.edu>

Friday, June 13, 2008

Spring Cleaning

microbox contents
I just received Nick Chernyy's Microbox as part of The Great Internet Migratory Box of Electronic Junk project.

I took the 8051 board, the 2x16 LCD, and a MAX232 level-converter chip. I then removed a healthy number of packing peanuts, swapped one of the microcontroller cases for a smaller one, and added the following:
  • Two PICs.
  • Three MSP430F2012 DIPs.
  • A 4G iPod, sans hard disk
  • Two TI CC1100 radio boards.
  • A board of ZIF sockets for PIC programming.
As is tradition, I'll be sending the box to someone on the Box Requests page within the next week or so.

--Travis

Monday, June 2, 2008

CopyWench, a File Format for Publicly Discussing Undistributable Material

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

Suppose that an author has written a document describing the reverse engineering of ROM image, and he wishes to publish his work. Further, let us suppose that the author is an honest and law-abiding citizen of a nation with intellectual property laws that prevent him from distributing software copyrighted by another. He cannot distribute his work in its entirety, as his work will cite numerous lines of the original. In this short article, I will discuss a format for a utility which--much like diff--allows an author to distribute only his changes to a document. Unlike diff, my format will not include so much as a single line of the original.

First, suppose this to be our secret file. It is from Wikipedia's BASIC article. We'll call it secret.txt:
10 INPUT "What is your name: ", U$
20 PRINT "Hello "; U$
30 INPUT "How many stars do you want: ", N
40 S$ = ""
50 FOR I = 1 TO N
60 S$ = S$ + "*"
70 NEXT I
80 PRINT S$
90 INPUT "Do you want more stars? ", A$
100 IF LEN(A$) = 0 THEN 90
110 A$ = LEFT$(A$, 1)
120 IF A$ = "Y" OR A$ = "y" THEN 30
130 PRINT "Goodbye ";U$
140 END
Each line of secret.txt has a one-way MD5 hash, which is what will be published in lieu of the line itself. To someone who does not have the secret file, 12b9bdf57db1a1c9e4fb2fb1b35e9c41 means nothing. But to someone who does have the file, it's rather easy to find that the hash belongs to line 10 above.

Suppose this to be our private commentary:
Commentary of a BASIC program.
by John Doe.

10 INPUT "What is your name: ", U$
My name is John!
20 PRINT "Hello "; U$
Hello to you, too!
30 INPUT "How many stars do you want: ", N
Tons of stars!
40 S$ = ""
50 FOR I = 1 TO N
60 S$ = S$ + "*"
70 NEXT I
80 PRINT S$
90 INPUT "Do you want more stars? ", A$
Always.
100 IF LEN(A$) = 0 THEN 90
110 A$ = LEFT$(A$, 1)
120 IF A$ = "Y" OR A$ = "y" THEN 30
130 PRINT "Goodbye ";U$
Adieu.
140 END
By replacing every secret line--that is to say every line which is found in secret.txt--with a one-way hash of the original, we will arrive with something like the following, which is free of copyrighted material.
Commentary of a BASIC program.
by John Doe.

COPYWENCH 12b9bdf57db1a1c9e4fb2fb1b35e9c41
My name is John!
COPYWENCH 8a80ddc83dc0592951d29151d62487a4
Hello to you, too!
COPYWENCH cbbf650ae187427f3cd74a58a7b0edf4
Tons of stars!
COPYWENCH f842a481f76099503c63c611dc84784e
COPYWENCH 9376ab1f0bed02260134dc9d6b723433
COPYWENCH 5cbb0ef3dbb1b75c047b278b3480fa46
COPYWENCH 95cfeba9a3004c3e6b2db6ce3222341b
COPYWENCH 402c331f990b99054568e72315e5e01b
COPYWENCH f8ee49bfcd41e6a43266105e65964247
Always.
COPYWENCH 24407c853d6df83fecd3074dc44e5ef5
COPYWENCH cc67be8c43810e63859ae75abaf7b1c2
COPYWENCH 36c25fd5bf40b1a5a0ef8d68af1580c7
COPYWENCH 80a1d74d3d5b1321fe3805a6d6f6011c
Adieu.
COPYWENCH 811061ce8478b3e56543e103ccd52c67
The following algorithm will translate between public and private files:
  1. For each line of secret.txt:
    1. Place a hash of the line in an associative array.
  2. Then for each line of the input file,
    1. If the line begins with COPYWENCH, print the line matching the checksum of the second word.
    2. Else if the line exists in the associative array, print "COPYWENCH" followed by a space and the line's hash.
    3. Else print the input line.
I recommend this file format, which I've named the CopyWench format, because it is terribly easy to implement. A few minutes in any scripting language will result in a working implementation.

A sample implementation follows. As all implementations ought to be licensed so as to be distributable with the documents with which they are intended to be used, this one is in the public domain. Do with it as you will.

#!/usr/bin/perl

#CopyWench 0.1
#Authored for the Public Domain
#by Travis Goodspeed <travis at utk.edu>

#Either Digest::MD5 or Digest::Perl::MD5 is needed.
BEGIN {
eval {
require Digest::MD5;
import Digest::MD5 'md5_hex'
};
if ($@) { # no Digest::MD5
require Digest::Perl::MD5;
import Digest::Perl::MD5 'md5_hex'
}
}

if($#ARGV!=0){
print "Usage: $0 secret.txt <input.txt >output.txt
Where secret.txt is the secret being written about.\n"
;
exit;
}

my $secret=$ARGV[0];
my %lines;
my ($line,$hash);
open SECRET, "<$secret";

#Build an associative array of secret lines.
while(<SECRET>){
chomp($_);
$line=$_;
$hash=md5_hex($line);
#print "$hash $line\n";
$lines{$hash}=$line;
}
close SECRET;

while(<STDIN>){
chomp($_);
$line=$_;
$hash=md5_hex($line);
if($lines{$hash}){
print "COPYWENCH $hash\n";
}elsif($line=~m/\bCOPYWENCH ([0-9a-f]+)/){
print "$lines{$1}\n";
}else{
print "$line\n";
}
}