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 \(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}