# PlaidCTF 2017 - FHE

*The flag is encrypted with ElGamal and an additional layer of custom fully-homomorphic encryption.
We can recover the FHE key under known-message attack by solving a linear system.
The group used for ElGamal is weak (its order has small prime factors), so we can compute a discrete logarithm to recover the secret exponent and decrypt the flag.*

### Description

If you didn’t get the memo, homomorphic encryption is the future. But we might have to work out a few bugs first.

### Details

Points: 275

Category: Crypto

Validations: 14

### A custom encryption scheme

We were given a Sage script describing the custom encryption scheme, along with a public key and ciphertext. Let’s first understand the encryption scheme.

#### Custom FHE scheme

The custom FHE scheme works as follows. Given a prime , the field and a dimension , the secret key consists of a random vector . We denote by the first elements of , i.e. .

To encrypt a message , first generate a random matrix and compute the vector . Then, the ciphertext matrix consists of the rows of followed by the row .

To decrypt it, first compute . By construction, this is equal to , so the plaintext is equal to for any index .

#### ElGamal

The flag is encrypted as follows. We recognize ElGamal encryption in , with all values encoded with the FHE scheme.

```
# Generate key
x = F.random_element()
g = F.multiplicative_generator()
G = fhe.encrypt(g)
H = G^x
z = F.random_element()
Z = fhe.encrypt(z)
# Public key
pubkey = (G, H, Z)
# Encrypt flag
m = int(FLAG.encode('hex'), 16)
M = fhe.encrypt(m)
y = F.random_element()
U = G^y
S = H^y
# Ciphertext
enc = (U, (M + Z) * S)
```

We are given two files containing the public key and the ciphertext .

### Solution

We first break the FHE scheme and then ElGamal.

#### Known-message attack against custom FHE

We first note that knowing any non-zero multiple of the key vector is sufficient to decrypt messages (we compute instead of and obtain . In particular, we consider (such that ) and aim at recovering .

We note that the last ciphertext row is equal to . If we denote by and the first columns of respectively and , we obtain the following linear relation

If we know a plaintext-ciphertext pair such that is inversible (i.e. is not an eigenvalue of ), then we can solve this equation and recover the key .

However, we are given only 5 ciphertexts and do not know the corresponding plaintexts… But we know that the scheme is homomorphic, and that plaintexts are elements of the field . In particular, for any , we know that because the multiplicative group of has order . This gives us the known plaintext-ciphertext pair that we need!

With the given values, it turns out that does not work because the matrix is not inversible, but does the trick and we can recover the secret key . This Sage script recovers the key and decrypts the ciphertexts.

```
g = 19
h = 52774084559796279986932845454574924346254819718383580319471373405857169799126978135712589651459738007
z = 74806619223436318057488019757923349388331709109526109048262015729998830471407099824963764117455225281
u = 161202540669710418030574172350388444507933259401173773637054984225018825685147997081838166382338594386
c = 99581767808000746292621272224666290248510197049015601126446298319169184317601777135057806610999909987
```

#### Weak group for ElGamal

The challenge now consists of solving the ElGamal problem over the field . This amounts to finding the secret exponent such that (discrete logarithm problem). It turns out that the chosen prime (of 337 bits) is weak because has small factors:

```
sage: factor(P - 1)
2^8 * 3 * 5^2 * 7^3 * 13^3 * 17 * 23 * 41 * 191 * 727 * 2389 * 2617 * 4451 * 8678318629 * 108546579551 * 126366136639 * 134180934337 * 17434239546719 * 695890117602047
```

In particular, we can use the Pohlig-Hellman algorithm to compute the discrete log.
Sage has a built-in `discrete_log`

function but it used more than 4GB of RAM before we aborted.
We wrote our own implementation of Pohlig-Hellman in the following script.

For the biggest prime factor , we split the look-up table of the baby-step giant-step algorithm into two passes, each fitting into 4GB of RAM. Indeed, this last prime requires a look-up table of entries, each containing at least a group element of 337 bits (without taking into account the overhead of a hash table in Python).

Once is recovered, we can decrypt the flag as .

```
x = 131426230370998706684707180455307948782769587060042913899926112173267357048112721116886754336478065989
PCTF{eigen_see_a_valuable_flag_here}
```