# Pythia
**Category**: crypto \**Points**: 173 (65 solves)
Yet another oracle, but the queries are costly and limited so be frugal withthem.
```nc pythia.2021.ctfcompetition.com 1337```
Attachments: `server.py`
## Overview
The premise is pretty simple:
- The server picks 3 random passwords, but they are only 3 characters each  (which normally can be brute-forced).
- We can submit ciphertexts for the server to decrypt with AES GCM mode. We  also get to choose the nonce, and we pick which of the 3 passwords to use.
- If we find all 3 passwords, then the server sends us the flag.
- However, each decryption takes 10 seconds, and we are only allowed to use it  150 times.
## Solution
A naive bruteforce requires around `26^3 / 2` attempts per character, whichexceeds the limit. But if we can send specially crafted ciphertexts so thatdecryption is only successful for half the known keys, then we can use this asan oracle to binary search for the key.
Luckliy [this paper](https://eprint.iacr.org/2020/1491.pdf) has us covered, andeven provides a SageMath[implementation](https://github.com/julialen/key_multicollision)!
I just copied it and wrote a pwntools wrapper to solve this challenge (scriptin `solve.sage`). One issue is that generating a ciphertext to collide `26^3 /2` keys took way too long on my machine. Instead the largest partition size Ichose was 1024 keys, which worked well enough.
```$ sage solve.sage REMOTE[x] Opening connection to pythia.2021.ctfcompetition.com on port 1337[x] Opening connection to pythia.2021.ctfcompetition.com on port 1337: Trying 34.77.25.116[+] Opening connection to pythia.2021.ctfcompetition.com on port 1337: Done17576it [00:01, 13695.86it/s][+] Decryption successful 1024 7Making collisions for 128 keys ...DoneAll 128 keys decrypted the ciphertextMaking collisions for 128 keys ...DoneAll 128 keys decrypted the ciphertextMaking collisions for 64 keys ...DoneAll 64 keys decrypted the ciphertextMaking collisions for 64 keys ...Done...All 1 keys decrypted the ciphertext[+] Found password = b'kta'...All 1 keys decrypted the ciphertext[+] Found password = b'zod'All 1 keys decrypted the ciphertext[+] Found password = b'rqk'[+] passwords = [b'kta', b'zod', b'rqk'][*] Switching to interactive modeChecking...ACCESS GRANTED: CTF{gCm_1s_n0t_v3ry_r0bust_4nd_1_sh0uld_us3_s0m3th1ng_els3_h3r3}```