PlaidCTF 2017 - FHE write-up | Blog

This post is a mirror of the original publication available here.

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
- Details
A custom encryption scheme
- Custom FHE scheme
- ElGamal
Solution
- Known-message attack against custom FHE
- Weak group for ElGamal

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 $p$ , the field $F = GF(p)$ and a dimension $n$ , the secret key consists of a random vector $t \in F^n$ . We denote by $t'$ the first $n-1$ elements of $t$ , i.e. $t' = (t_{1}, \ldots, t_{n-1})$ .

To encrypt a message $x \in F$ , first generate a random matrix $M \in F^{(n-1) \times n}$ and compute the vector $v = t' \cdot M$ . Then, the ciphertext matrix $C \in F^{n \times n}$ consists of the $n-1$ rows of $M$ followed by the row $C_n = \frac{1}{t_{n}} (x t - v)$ .

To decrypt it, first compute $w = t \cdot C$ . By construction, this is equal to $x t$ , so the plaintext $x$ is equal to $w_i / t_i$ for any index $i$ .

ElGamal

The flag is encrypted as follows. We recognize ElGamal encryption in $F$ , 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 $(G, H, Z)$ and the ciphertext $(U, C)$ .

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 $\alpha t$ of the key vector is sufficient to decrypt messages (we compute $\alpha w$ instead of $w$ and obtain $x = \alpha w_i / \alpha t_i)$ . In particular, we consider $\tau = t / t_n$ (such that $\tau_n = 1$ ) and aim at recovering $\tau$ .

We note that the last ciphertext row $C_n$ is equal to $x \tau - \tau' \cdot M$ . If we denote by $C_n'$ and $M'$ the first $n-1$ columns of respectively $C_n$ and $M$ , we obtain the following linear relation

C_n' = \tau' \cdot (x I_{n-1} - M')

If we know a plaintext-ciphertext pair such that $x I_{n-1} - M'$ is inversible (i.e. $x$ is not an eigenvalue of $M'$ ), then we can solve this equation and recover the key $\tau$ .

However, we are given only 5 ciphertexts $G, H, Z, U, C$ and do not know the corresponding plaintexts… But we know that the scheme is homomorphic, and that plaintexts are elements of the field $F$ . In particular, for any $X = FHE(x)$ , we know that $X^{p-1} = FHE(x^{p-1}) = FHE(1)$ because the multiplicative group of $F$ has order $p-1$ . This gives us the known plaintext-ciphertext pair that we need!

With the given values, it turns out that $G^{p-1}$ does not work because the matrix is not inversible, but $Z^{p-1}$ does the trick and we can recover the secret key $\tau$ . 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 $F = GF(p)$ . This amounts to finding the secret exponent $x$ such that $h = g^x$ (discrete logarithm problem). It turns out that the chosen prime $p$ (of 337 bits) is weak because $p-1$ 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 $p_{max} = 695890117602047$ , 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 $\sqrt{p_{max}} = 26.3M$ entries, each containing at least a group element of 337 bits (without taking into account the overhead of a hash table in Python).

Once $x$ is recovered, we can decrypt the flag as $m = c u^{-x} - z$ .

x = 131426230370998706684707180455307948782769587060042913899926112173267357048112721116886754336478065989
PCTF{eigen_see_a_valuable_flag_here}

Comments

To react to this blog post please check the Twitter thread.

RSS | Mastodon | GitHub | Reddit | Twitter