Micro Corruption: Halifax

Table of Contents

Introduction

Micro Corruption is a self-paced Capture The Flag competition, where the aim is to unlock the fictional lock holding the door of a fictional Cy Yombinator warehouse, and steal the fictional bearer bonds worth “billions comma billions of dollars.” Halifax is the 25th challenge in the series, and the final challenge of the new challenge set, which begins with 20, Vancouver.

This challenge is simple: Interrupt 0x7f, which opens the lock, has been disabled using a new mechanism, and a random key is stored in a secure SRAM only accessible to their hardware authenticator, ostensibly accessed through Interrupt 0x41. More on that later. The program prints the sha256 hash of the entire internal SRAM before accepting a debug payload. A sample payload is provided, similar to earlier challenges in the new series.

The Sample Payload

The manual includes a sample payload, 8000023041, which, when run, makes the debug payload structure fairly obvious.

This program is loaded into location 0x8000, is 2 bytes long, and contains an instruction 3041, the MSP430 ret instruction. The payload can be broken down as such:

loadaddr  size  instructions...
8000      02    3041

Reconnaissance

In my initial dive into the code, I noted that, though it was stated to unlock the lock, INT 0x41 was already used in a function named sha256_internal, which, as seen at location 0x449e, takes 3 arguments:

Location 449e

449e:  0d41           mov	sp, r13
44a0:  3e40 0010      mov	#0x1000, r14
44a4:  0f43           clr	r15
44a6:  b012 b645      call	#0x45b6 <sha256_internal>

The parameters are, roughly,

void sha256_internal(char* sram_addr, size_t length, char* out_buffer)

The implementation of sha256_internal is as follows:

45b6:  0d12           push	r13
45b8:  0e12           push	r14
45ba:  0f12           push	r15
45bc:  3012 4100      push	#0x41
45c0:  b012 5045      call	#0x4550 <INT>
45c4:  3152           add	#0x8, sp
45c6:  3041           ret

It's just a wrapper around INT (0x41, sram_addr, length, out_buffer). INT 0x41, then, takes 3 arguments.

Exfiltration

How do you read the contents of a buffer when you can only grab a sha256 hash? Trivial: You ask it for the hash of each byte individually.

Unfortunately, that would mean printing 32 bytes of hash (64 nibbles) for every single byte of the internal SRAM — which, according to Location 449e is 0x1000 bytes in length. That's 0x40000 bytes. Doable, but there's got to be a better way.

Thankfully, we can exploit sha256's confusion to do the work for us. A single bit change in input should produce a change across the entire output, right? There should be a way to uniquely identify a single byte using the first n bytes of output. We can find n by computing the hashes of the numbers 00-ff, and counting how many unique sequences there are when truncating those hashes to a certain length. If there are 0x100 unique sequences, you can uniquely identify bytes by their sha256 hash. Is it the most optimal approach? Probably not, but it gets the job done.

Spoiler alert: the answer is 5 nibbles. My payload prints 6, because splitting a byte is infeasible.

The Dumping Stage

const: ; We start by defining a series of constants
.define msize  0x1    ; length of each hash in bytes
.define hsize  0x3    ; bytes kept per hash (only needs to be 3 to determine 1 byte of sram)
.define sr_len 0x140  ; number of bytes in sram to dump
.define haddr  0x7000 ; address of the big hash array

get_sram_hashes:
clr   r11            ; loop variable in r11
mov   #msize, r14    ; r14 = 1
mov   #haddr, r13    ; set destination to 0x8000
sr_loop:
mov   r11, r15       ; mov addr r15
call  sha256_internal; sha256_internal (0x8000 + hsize * index, 0x1, index)
add   #hsize, r13    ; keep 3 bytes of the output
inc   r11            ; inc r11
cmp   #sr_len, r11        ; do that 0x1000 times
jnc   sr_loop

The start of my payload, which defines some constants, then saves 3 bytes of the hash of each byte in the internal SRAM, for later printing.

As you can see, it's fairly simple to reuse their sha256_internal function, and repeatedly save 3 bytes of each sha256 hash, overwriting the tail with the next location's hash.

But why dump 0x140 bytes?

After dumping the SRAM, I noticed that the vast majority of it is 0. In fact, more often than not, it was 0 from 0x40 to 0x1000. So, again, why dump 0x140 bytes?

A screenshot of the python script which accompanies my payload, having dumped mostly 0-bytes.

A screenshot of the same script, the same payload, but with 0x140 bytes dumped.

As it turns out, the length of the SRAM contents is non-deterministic, but always exactly 0x40 or 0x140 bytes. Worse, I would later discover that the offset of the key within this window is also different between the two lengths. That didn't turn out to matter in the end, however.

We have the key, now what?

As mentioned before, the software interrupt we're told to use, 0x41, is used by sha256_internal to hash the internal SRAM. Me and two other competitors fought endlessly with this interrupt, providing every conceivable sequence of 16 bytes in the output buffer, using the length as a pointer... We exhausted our supply of ideas, and eventually concluded that the challenge must be broken. Nothing was working, and it didn't seem to even attempt to use our keys. So, we contacted the challenge authors. No response.

check_all_passwords:
;for i in 0..sr_len:
clr   r9
pw_loop:
; memcpy(kaddr, iaddr + i, len)
mov   #10, r13
mov   #iaddr, r14
add   r9, r14
mov   #kaddr, r15
call  memcpy
; INT (0x41, key)
push  #kaddr
push  #41
call  INT
add   #4, sp
; INT(7f)
unlock7f:
push  #0
push  #0
push  #7f
call  INT
add   #6, sp
inc   r9
cmp   #sr_len, r9
jl    pw_loop

A subroutine which checks each possible 16-byte sequence within the dumped SRAM data

Over the course of the next 6 months, the three of us worked collaboratively to figure out what went wrong. I discovered a string formatting error in my python script that caused it to print /[0-9]/ when it meant /0[0-9]/, but still, no dice. But, eventually, a member of the ReSwitched Discord who happens to have access to the project informed us that there was a typo in both the directions and the program itself.

The Typo

In a cruel twist of fate, our efforts were almost thwarted by this insidious typographical error. The program and the instructions never once mention the true software interrupt. The software answer to life, the universe, and everything.

Interrupt 0x42.

The only reason I didn't find this sooner is because of the formatting error. When I was poking around with alternate interrupt numbers, I did check if interrupt 0x42 did anything... But it didn't seem to. There are no side effects to calling INT 0x42. It doesn't return anything in any registers, it doesn't touch the stack, or even take more than one cycle to execute.

All it seems to do is signal the emulator to check whether the buffer pointed to by the top of the stack is identical to a region in SRAM.

This behavior is surprisingly hard to identify. Most other interrupts, if I remember right, cost something to run—are implemented somewhere within the MSP430 emulator's firmware. Yet this one isn't. It's just bizarre.

Once I found out about interrupt 0x42, it was mere minutes before I got that beautiful end screen.

; INT (0x42, key) ; unlock the unlocker
push  #kaddr
push  #42 ; A single-character change. Wild!
call  INT
add   #4, sp
; INT(7f) ; use the unlocker to unlock the lock
unlock7f:
push  #0
push  #0
push  #7f
call  INT
add   #6, sp

Door Unlocked Our operatives are entering the building. Go back to the world map to see what new warehouses they find. The CPU completed in 173262 cycles.

What a relief! I'd been sitting on this working payload for months, held back by a single typo in my Python script and a single typo in the challenge instructions. Bravo to the challenge authors for this one, I learned a lot of valuable skills from this challenge.

Lessons Learned or Reinforced

#microcorruption #halifax #reverseengineering #hacking #ctf #writeup