A check made of three small steps
A simple arithmetic check puts the number you type through a few steps, such as add, xor and subtract. It then compares the answer with a fixed value.
That is easy to undo, because every step has an inverse. Seeing how it is done shows a defender why such a check is no real protection. You will work on a practice program, not on the lab's own.
By the end of this lesson
Note
I can undo a small add, xor and subtract check.
Key words
| Word | What it means | Example |
|---|---|---|
| Immediate | a number written inside an instruction | 0xfa |
| Hexadecimal | numbers written in base 16, with the prefix 0x | 0xfa |
| XOR | a step that flips the bits where the other number has a 1 | |
| Inverse | the step that undoes another step | |
| Target | the fixed value the check compares with | |
| Unsigned | a number that is never negative, and wraps round instead |
The cells students fill in are left blank in this preview.
The check in the practice program
static int check(unsigned n) {
unsigned x = n;
x = x ^ 6000;
x = x + 250;
x = x - 17;
return x == 4321;
}
Every step has an undo
The check runs three steps on n and compares the answer with 4321. To find the n that passes, run the steps backwards.
Start at the target. Undo the last step first, then the one before it. The inverse of add is subtract, the inverse of subtract is add, and xor with a number undoes itself.
Worked example: from 4321 back to n
| Step undone | Calculation | Value now |
|---|---|---|
| Start at the target | 4321 | |
| Undo subtract 17 | 4321 + 17 | 4338 |
| Undo add 250 | 4338 - 250 | 4088 |
| Undo xor 6000 | 4088 xor 6000 | 6280 |
The cells students fill in are left blank in this preview.
The same steps in Python
# The check does: xor 6000, then add 250, then subtract 17, then compares with 4321.
# Work backwards: start at the target and undo the last step first.
value = 4321
value = value + 17
value = value - 250
value = value ^ 6000
print(value)
# Change 4321 to 5000 and run again. Which number does the badge check want now?
Reading the steps from the program
With no source, you read the steps from the disassembly. Each step is one line with a number written in it. The numbers come in hexadecimal, base 16, so 0xfa is 250.
The four Runs below build the practice program, read its steps, convert the numbers and try the answer. Note that an optimiser can merge steps, so read what is really there.
Write the practice program
printf '#include <stdio.h>\n#include <stdlib.h>\nstatic int check(unsigned n) {\n unsigned x = n;\n x = x ^ 6000;\n x = x + 250;\n x = x - 17;\n return x == 4321;\n}\nint main(int argc, char **argv) {\n if (argc != 2) { puts("usage: badge NUMBER"); return 2; }\n if (check((unsigned)strtoul(argv[1], 0, 10))) { puts("Badge accepted."); return 0; }\n puts("Badge refused.");\n return 1;\n}\n' > badge.cShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Compile it
gcc -O0 -no-pie -fno-stack-protector -o badge badge.cShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Read the four steps of check
objdump -d badge --disassemble=check -M intel | grep -E "[[:space:]](xor|add|sub|cmp)[[:space:]]"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Turn the hexadecimal into decimal
echo $((0x1770)) $((0xfa)) $((0x11)) $((0x10e1))Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Undo the steps in the shell
echo $(( ((4321 + 17) - 250) ^ 6000 ))Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Try the number on the badge
./badge 6280Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think the only way to beat a check like this is to try numbers until one works. You do not have to guess. Each step has an inverse, so start at the target and undo the last step first, then the one before it.