Rating: 4.0

## Memory Corruption - Ace of Spades

What we have is a card game. Fooling around with it (under `valgrind` - why
not?) reveals the following:
* There is a shuffled deck of 52 cards.
* We can draw as many cards as we please (even all 52).
* We can discard drawn cards in FIFO manner.
* When we are happy with the hand, we can "play" it - this will compute the
score based on the following table:
* Jack: 300
* Queen: 600
* King: 900
* Ace: 1200
* Ace of Spades: x2
* Only some of the cards in the hand are taken into account.
* After the hand is played, all the cards are shuffled into the deck and we can
draw again.
* So the theoretical maximum of points we can achieve is `(1200 * 3 + 900) * 2 =
9000`. Memez FTW!
* Winning 1000 or more points results in a prize. We can keep it or we can
replace it with anything else.
* Stuff like drawing more than 52 cards and discarding from the empty hand seems
to be handled correctly. No easy way to crash the program.
* The only valgrind warning is:

```
==11086== Source and destination overlap in strcpy(0x10b260, 0x10b261)
==11086== at 0x4833537: strcpy (in vgpreload_memcheck-x86-linux.so)
==11086== by 0x108D92: ??? (in ace_of_spades)
==11086== by 0x109236: ??? (in ace_of_spades)
==11086== by 0x109354: main (in ace_of_spades)
```

Well, this is for sure a lousy non-portable coding practice, but on our
particular platform this seems to work fine. Moving on.

Reversing the code in IDA raises more eyebrows than I care to count. Spoiler:
most of them ended up being useless at the end:

* The function that calculates points explicitly handles multiple Aces of
Spades:

```
.text:00000DEB cmp al, 28h ; '('
.text:00000DED jnz short is_not_aos
.text:00000DEF is_aos:
.text:00000DEF add [ebp+aos_count], 1
.text:00000DF3 jmp short next_index

...

.text:00000E48 double_points:
.text:00000E48 shl [ebp+points], 1
.text:00000E4B add [ebp+index], 1
.text:00000E4F loop_end:
.text:00000E4F mov eax, [ebp+index]
.text:00000E52 cmp eax, [ebp+aos_count]
.text:00000E55 jb short double_points
```

A doorway into exceeding the maximum "fair" amount of points?

* The function that shows the hand does not honor the number of cards and
instead waits for the trailing `\0`:

```
.text:0000115E movzx eax, byte ptr [eax]
.text:00001161 test al, al
.text:00001163 jnz short loop_body
```

An opportunity for an arbitrary memory read?

* RNG seed is not discarded, but rather stored into a global variable, which
lies right after deck, hand and discard pile. Can we read it somehow?

```
.bss:00003220 deck db 35h dup(?)

...

.bss:00003260 hand db 35h dup(?)

...

.bss:000032A0 discard_pile db 35h dup(?)

...

.bss:000032E0 seed dd ?
```

* Prize selection does not handle 11000 points and more correctly. Winning 16000
points and keeping the prize allows us to read memory pointed to by `rbp`.
Replacing the prize allows us to write to said memory:

```
.text:00000FDE mov eax, [ebp+points]
.text:00000FE1 mov edx, 10624DD3h
.text:00000FE6 mul edx
.text:00000FE8 mov eax, edx
.text:00000FEA shr eax, 6
.text:00000FED mov [ebp+prize_index], eax
.text:00000FF0 mov eax, [ebp+prize_index]
.text:00000FF3 mov eax, [ebp+eax*4+prizes]
.text:00000FF7 sub esp, 8
.text:00000FFA push eax
.text:00000FFB lea eax, (aYourPrizeS - 2F98h)[ebx] ; "Your prize: %s\n"
.text:00001001 push eax ; format
.text:00001002 call _printf
```

But how do we win that much?!

* Winning regular prizes and changing them to `'x' * 0x20` allows us to
overwrite the trailing '\0' and see the next prize:

```
.text:00001087 change:
.text:00001087 mov eax, [ebp+prize_index]
.text:0000108A mov eax, [ebp+eax*4+prizes]
.text:0000108E sub esp, 4
.text:00001091 push 20h ; ' ' ; nbytes
.text:00001093 push eax ; buf
.text:00001094 push 0 ; fd
.text:00001096 call _read
```

Any possibility to read something useful here?

* Familiar `strcpy` issue:

```
.text:00000D7D lea eax, (hand+1 - 2F98h)[ebx]
.text:00000D83 sub esp, 8
.text:00000D86 push eax ; src
.text:00000D87 lea eax, (hand - 2F98h)[ebx]
.text:00000D8D push eax ; dest
.text:00000D8E call _strcpy
```

Uh huh. I would NACK that in a code review, but this is CTF.

* Only the first 5 cards count towards the score, even if we play an empty hand:

```
.text:00000E39 loop_header:
.text:00000E39 cmp [ebp+index], 4
.text:00000E3D jbe short process_card
```

Can we somehow put Aces of Spades into empty slots?

* Function that asks for a choice reads 4 characters and calls `atoi()` without
any checking - can we read something useful this way?

* When reading the seed from `/dev/urandom` the code doesn't check the return
value of `read()`: can we somehow overwhelm the system RNG and make `read()`
return just 1 byte, making the seed more predictable?

* Why are we given the `xinetd` file? Is the environment the server runs in
somehow useful?

Two pieces of the puzzle come together: duplicating Aces of Spades will make it
possible to exceed the maximum score and gain the ability to read and write to
the stack. The missing piece is: how to duplicate the cards?

All the issues related to predicting the RNG, even if they would somehow work,
are useless: we need to actively mess with the deck, not learn stuff about it.

After hours and hours of reading the assembly and experimenting with ideas
above, I come back to `strcpy` and wrote the following (by this time I've
developed a bunch of `pyexpect`-based helpers to drive the game):

```
def strcpy_problem(p):
for _ in range(52):
draw(p)
h = print_hand(p)
for _ in range(52):
discard(p)
h1 = print_hand(p)
if h[1:] != h1:
print('^^^ BUG ^^^')
h = h1
fold(p)
```

Ouch! When working with certain string lengths (29, 44, 45), `strcpy` with
overlapping buffers duplicates certain characters. So, let's do the following
in a loop:

* Draw 52 cards.
* See if some combination of 5 cards gives us the desired score.
* Discard until those 5 cards become the first ones and play the hand.
* If in rare cases when `strcpy` bug messes with that, tough luck - fold
and try again.
* See if `strcpy` bug lets us replace a worthless card with a `Jack` or
something better.
* Discard until the bug is triggered, fold.
* Fold.

Here are the scores that we want to achieve, in order:

* Some "legal" score in range 1000-10999 in order to change the prize to the
name of the file containing the flag - `/home/ace_of_spades/flag\0`. This
actually required some guesswork (`flag` vs `flag.txt` and `/` vs `.` vs
`$HOME`) - `xinetd` file allowed to learn the name of the home directory.

* 16000-16999 in order to print the prize, which is the stack contents.
`prize[4:8]` contains the return address, which is always `main+147` -
so long, ASLR!

* 16000-16999 again in order to change the prize and overwrite the stack.

Where can we return? We have a bunch of libc functions in PLT, but, alas, no
sweet `exec`. We have to `open` the flag anyway. Then we need to `read` it.

The first step is easy - overwrite the stack with:

* `0` (old `ebp`)
* `open` address
* `0` (`open` return address)
* address of path to `flag`
* `open` flags

and leave the game in order to pass control to `open`.

When `open` returns, the flag fd will be in `eax` and top of the stack is going
to be:

* address of path to `flag`
* flag length

Can we do anything useful with that? Turns out we can. Let's find all the `read`
calls. One of them is in the very beginning and is responsible for reading
`/dev/urandom`. Let's try jumping there:

* `0` (old `ebp`)
* `open` address
* `main + 0x46`:
```
.text:00001308 push eax ; fd
.text:00001309 call _read
```
* address of path to `flag`
* `64` which is a valid `open` flag and at the same time a reasonable flag
length

When we are at the `read` call site, the stack looks like this:

* flag fd
* address of path to `flag`
* `64`

The flag will be placed into the prize slot, which used to contain the path.
After that the game will be restarted, so we just play again, win the prize at
this slot and get the flag!