Tags: ibe rsa

Rating:

# CSAW CTF 2018 Qualification Round - Collusion

Writeup by: Andrew He

## Challenge
Crypto, 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's
private key, allowing us to decrypt arbitrary messages.

## Deciphering the crypto system

read 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) mod
phi(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 dive
into a little more detail where these came from, but feel free to jump to the
next section for the solution and exploit.

The go files contain an identity-based encryption scheme, which allows anyone to
encrypt data using just the recipient's name (you can think of it as a
public-key distribution system that magically uses a common public/private key
owned 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 the
recipient to a deterministic integer modulo N.

For any recipient with DecrypterId(recipient) = id, the group manager
distributes N and d = inv(x + id) mod phi(N) as their private decryption
key (presumably after properly verifying their identity).

To encrypt for a recipient with DecrypterId(recipient) = id, we first pick a
shared secret K = 3^r mod N for a random r, and then produce the
key-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 random
nonce 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 an
encrypted message for Alice containing the flag. From these, we can find:
* N from the secret keys,
* a, b, and c, the DecrypterIds 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 the
challenge program supposedly saves it. We didn't need it in the end, but just a
small oddity.

## Some number theory

The number theory part of this challenge was pretty short and sweet once we saw
it.

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) or
both. We can't take modular inverses because phi(N) is unknown, so the next
best 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 this
equation, so subtracting gives us a multiple of phi(N). If we let this
multiple be myPhi, we can do our modular arithmetic modulo myPhi, and it
will 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 just
use inv(x+a) mod myPhi as Alice's decryption key to decrypt the flag, as it's
congruent to inv(x+a) mod phi(N).

One small note: it's possible that the numbers we work with aren't relatively
prime with myPhi, in which case we can't take modular inverses. However, we
know that x+b and x+a are both relatively prime with phi(N), so the common
factors 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 we
didn't have to implement this.

## Exploit

The exploit can be found in exploit.go and can be built with go build
exploit.go common.go. One weird point was having to implement Decrypt
ourselves: the given code implemented Encrypt but not the matching function.

Original writeup (https://github.com/TechSecCTF/writeups/tree/master/CSAWQuals2018/collusion).