**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

I jumped on this problem after [betaveros](https://beta.vero.site/) had already

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 `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 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).