# CSAW CTF 2018 Qualification Round - Collusion
Writeup by: Andrew He
## ChallengeCrypto, 500 pts, 32 solves
Written by Brendan McMillion & Krzysztof Kwiatkowski, Cloudflare
### Files
* bobs-key.json* carols-key.json* common.go* message.json* generate-challenge.go
## tl;dr
We're given an RSA-based identity-based encryption (IBE) scheme, and two users'private keys. Turns out those are enough to figure out the group manager'sprivate key, allowing us to decrypt arbitrary messages.
## Deciphering the crypto system
I jumped on this problem after [betaveros](https://beta.vero.site/) had alreadyread and simplified the code, so I got a bit of a condensed form of the problem:we're given a large semiprime `N=pq`, integers `a`, `b`, `c`, `inv(x+b) modphi(N)`, `inv(x+c) mod phi(N)`, `3^(r*(x+a)) mod N`, and the flag encrypted with`3^r mod N` as the key (here, `p`, `q`, `r`, and `x` are unknowns). I'll diveinto a little more detail where these came from, but feel free to jump to thenext section for the solution and exploit.
The go files contain an identity-based encryption scheme, which allows anyone toencrypt data using just the recipient's name (you can think of it as apublic-key distribution system that magically uses a common public/private keyowned by a trusted third-party).
In this scheme, the trusted group manager first generates an RSA semi-prime `N =p * q` using safe primes `p = 2p'+1` and `q = 2q'+1`, as well as a secret value`x` modulo `phi(N)`. They publish `N` and `H = 3^x` as public keys. Also,there's a public function `DecrypterId` maps the identity (name) of therecipient to a deterministic integer modulo `N`.
For any recipient with `DecrypterId(recipient) = id`, the group managerdistributes `N` and `d = inv(x + id) mod phi(N)` as their private decryptionkey (presumably after properly verifying their identity).
To encrypt for a recipient with `DecrypterId(recipient) = id`, we first pick ashared secret `K = 3^r mod N` for a random `r`, and then produce thekey-encapsulation message (KEM) `V = (3^id * H)^r mod N = 3^(r*(x + id)) mod N`.The secret secret is used to encrypt the message with an AES cipher and a randomnonce plugged into Go's AEAD black box, and we send the triple `(V, AEAD(...),nonce)`.
To decrypt, the recipient can recover the shared secret by taking
    V^d mod N = 3^(r*(x+id))^(inv(x+id) mod phi(N)) mod N = 3^r mod N
as in standard RSA.
In this problem, we're given Bob and Carols' secret keys, as well as anencrypted message for Alice containing the flag. From these, we can find:* `N` from the secret keys,* `a`, `b`, and `c`, the `DecrypterId`s of Alice, Bob, and Carol,* `inv(x+b) mod phi(N)` and `inv(x+c) mod phi(N)`, the secret keys of Bob and Carol,* `3^(r*(x+a)) mod N`, the KEM of the message* the message ciphertext and nonce itself
Interestingly, we weren't given the public encryption key, even though thechallenge program supposedly saves it. We didn't need it in the end, but just asmall oddity.
## Some number theory
The number theory part of this challenge was pretty short and sweet once we sawit.
In essence, we know `1/(x+b) mod phi(N)` and `1/(x+c) mod phi(N)` for given`b` and `c`, so we'd like to find some information about `x` or `phi(N)` orboth. We can't take modular inverses because `phi(N)` is unknown, so the nextbest thing is maybe working directly with the fractions.
A bit of experimentation led us to the identity
    1/(x+b) - 1/(x+c) = (c-b) / (x+b) / (x+c) mod phi(N)
Note that we can compute the left hand side and right hand side of thisequation, so subtracting gives us a multiple of `phi(N)`. If we let thismultiple be `myPhi`, we can do our modular arithmetic modulo `myPhi`, and itwill be correct mod `phi(N)`!
In particular, we can just compute `x+b = inv(inv(x+b) mod phi) mod myPhi`,which allows us to find `x`, `x+a`, and `inv(x+a) mod myPhi`. Then, we can justuse `inv(x+a) mod myPhi` as Alice's decryption key to decrypt the flag, as it'scongruent to `inv(x+a) mod phi(N)`.
One small note: it's possible that the numbers we work with aren't relativelyprime with `myPhi`, in which case we can't take modular inverses. However, weknow that `x+b` and `x+a` are both relatively prime with `phi(N)`, so the commonfactors with `myPhi` must be extraneous, so we can just divide them out of`myPhi`. Fortunately, this didn't occur in the actual challenge data, so wedidn't have to implement this.
## Exploit
The exploit can be found in `exploit.go` and can be built with `go buildexploit.go common.go`. One weird point was having to implement `Decrypt`ourselves: the given code implemented `Encrypt` but not the matching function.