This is the thirteenth in a series. You might want to read the previous post before reading this.
This post is based on the Jakarta level on microcorruption.com. Like last time, we’re trying to find an input to open a lock without knowing the correct password, using knowledge of assembly language.
First steps
You’ve seen a lot of assembly by now, and this level is quite similar to the previous one, so I’m going to give less detailed commentary on the code. Try to follow the instructions for yourself and work out what’s going on.
Let’s dive in to the login function. Here’s the first and last few instructions of it.
4560: 0b12 push r11
4562: 3150 deff add #0xffde, sp
...
...
462e: 3150 2200 add #0x22, sp
4632: 3b41 pop r11
4634: 3041 ret
So there’s 0x22 = 34 bytes allocated on the stack.
4566: 3f40 8244 mov #0x4482 "Authentication requires a username and password.", r15
456a: b012 c846 call #0x46c8 <puts>
456e: 3f40 b344 mov #0x44b3 "Your username and password together may be no more than 32 characters.", r15
4572: b012 c846 call #0x46c8 <puts>
4576: 3f40 fa44 mov #0x44fa "Please enter your username:", r15
457a: b012 c846 call #0x46c8 <puts>
Output some stuff.
457e: 3e40 ff00 mov #0xff, r14
4582: 3f40 0224 mov #0x2402, r15
4586: b012 b846 call #0x46b8 <getsn>
458a: 3f40 0224 mov #0x2402, r15
458e: b012 c846 call #0x46c8 <puts>
Get 255 bytes of username, store it at 0x2402, and then write it out.
4592: 3f40 0124 mov #0x2401, r15
4596: 1f53 inc r15
4598: cf93 0000 tst.b 0x0(r15)
459c: fc23 jnz #0x4596 <login+0x36>
Increment r15 until it points to the null byte at the end of the username.
459e: 0b4f mov r15, r11
45a0: 3b80 0224 sub #0x2402, r11
Calculate the length of the username in bytes, in r11.
45a4: 3e40 0224 mov #0x2402, r14
45a8: 0f41 mov sp, r15
45aa: b012 f446 call #0x46f4 <strcpy>
Copy the username onto the stack.
45ae: 7b90 2100 cmp.b #0x21, r11
45b2: 0628 jnc #0x45c0 <login+0x60>
45b4: 1f42 0024 mov &0x2400, r15
45b8: b012 c846 call #0x46c8 <puts>
45bc: 3040 4244 br #0x4442 <__stop_progExec__>
Compare the length with 0x21 = 33. If the length is greater than 33, print something out and end the program.
45c0: 3f40 1645 mov #0x4516 "Please enter your password:", r15
45c4: b012 c846 call #0x46c8 <puts>
Write out some text.
45c8: 3e40 1f00 mov #0x1f, r14
45cc: 0e8b sub r11, r14
Work out 0x1f (=31) minus the length of the username, in r14
45ce: 3ef0 ff01 and #0x1ff, r14
Ensure that r14 only has its bottom 9 bits set. That means its value will be no bigger than 511.
45d2: 3f40 0224 mov #0x2402, r15
45d6: b012 b846 call #0x46b8 <getsn>
45da: 3f40 0224 mov #0x2402, r15
45de: b012 c846 call #0x46c8 <puts>
45e2: 3e40 0224 mov #0x2402, r14
45e6: 0f41 mov sp, r15
45e8: 0f5b add r11, r15
45ea: b012 f446 call #0x46f4 <strcpy>
Get a password of that length, print it out, then copy it onto the stack, right after the password.
45ee: 3f40 0124 mov #0x2401, r15
45f2: 1f53 inc r15
45f4: cf93 0000 tst.b 0x0(r15)
45f8: fc23 jnz #0x45f2 <login+0x92>
45fa: 3f80 0224 sub #0x2402, r15
Get the length of the password entered, stored in r15.
45fe: 0f5b add r11, r15
4600: 7f90 2100 cmp.b #0x21, r15
4604: 0628 jnc #0x4612 <login+0xb2>
4606: 1f42 0024 mov &0x2400, r15
460a: b012 c846 call #0x46c8 <puts>
460e: 3040 4244 br #0x4442 <__stop_progExec__>
If more than 33 characters were entered for the username and password together, it prints something out then ends the program.
4612: 0f41 mov sp, r15
4614: b012 5844 call #0x4458 <test_username_and_password_valid>
4618: 0f93 tst r15
461a: 0524 jz #0x4626 <login+0xc6>
461c: b012 4c44 call #0x444c <unlock_door>
4620: 3f40 3245 mov #0x4532 "Access granted.", r15
4624: 023c jmp #0x462a <login+0xca>
4626: 3f40 4245 mov #0x4542 "That password is not correct.", r15
462a: b012 c846 call #0x46c8 <puts>
Test the username and password for correctness. If they’re right, unlock the door. Otherwise, tell the user that the password is wrong.
An idea
There are a few similar numbers in this code - maybe some of them are slightly wrong. There are 34 bytes on the stack, we’re told our username and password must be at most 32 bytes in length. The username is then tested for being at most 33 bytes long. The password must be below (31 - username) bytes long. Then we check that the username and password together are less than 33 bytes long.
Let’s talk about overflow and underflow
A single byte can only hold values between 0 and 255. So how does a CPU processor cope when you tell it to do 255 + 1 and store the result in a single byte? Simple! It resets back to 0. So 255 + 5 = 4 (in a single byte).
You can imagine that the CPU adds the numbers together then ignores the bits that it doesn’t have space to hold. E.g. in binary, 255 + 5 looks like this: 0b11111111 + 0b00000101. That comes to 0b100000100. But the CPU can only store the bottom 8 bits! So we get 0b00000100 which is 4.
The same happens with subtractions, except here it’s called underflow. 0 - 1 will be computed as 0b00000000 - 0b00000001 which, in the same way as above, will come to 0b11111111.
Why would you ever want this? Well sometimes it’s useful! For example in this code, when we want to have 34 more bytes on the stack, we do add #0xffde, sp. In a 2-byte register, this sum will overflow. The amount it will overflow can be found by 0x10000 - 0xffde = 0x22 which is 34 bytes.
You can always check whether the previous sum has overflowed, as the carry bit will be set in the status register. The instructions jc and jnc will let you jump based on whether an operation has overflowed or not.
Using overflows and underflows
What would happen if our username was 32 bytes long here? Its length would be less than 33 bytes, so that test would pass. The password would have to be 31 - 32 bytes, which will underflow to 0xffff. The next line ensures it has a max of 511, so that’s the limit of the password that we can enter.
When the length of the password is added to the length of the username, it needs to be less than 33 in the lowest byte. If the username is 32 bytes, and the password is 256 bytes, then the sum will be 0x120. The code only looks in the lowest byte, which holds 0x20 which is indeed less than 0x21.
To hack this lock, the username needs to be 32 characters (e.g. ‘A’ 32 times). The password needs 4 character of anything, to fill up the allocated stack space, and the 2 bytes for the stored copy of r11. The next 2 bytes will overwrite the return address for the function (I’m using 4c44, so that the function returns into unlock_door), followed by 250 bytes of ‘A’ so that the total is 256.)
The door springs open
This is a complicated problem. Hacking this lock requires a good understanding of how overflow and underflow work, in order to spot ways to exploit them. The key here was noticing that a few similar numbers were coming up in the code: 32, 33, 34. That suggested that the person writing the code had made a small error somewhere - and they had. Allowing the username to be up to 33 characters, and letting the password be 31 characters minus the username’s length was the key to hacking the lock.