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

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

To encrypt a message xFx \in F, first generate a random matrix MF(n1)×nM \in F^{(n-1) \times n} and compute the vector v=tMv = t' \cdot M. Then, the ciphertext matrix CFn×nC \in F^{n \times n} consists of the n1n-1 rows of MM followed by the row Cn=1tn(xtv)C_n = \frac{1}{t_{n}} (x t - v).

To decrypt it, first compute w=tCw = t \cdot C. By construction, this is equal to xtx t, so the plaintext xx is equal to wi/tiw_i / t_i for any index ii.

ElGamal

The flag is encrypted as follows. We recognize ElGamal encryption in FF, 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)(G, H, Z) and the ciphertext (U,C)(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 αt\alpha t of the key vector is sufficient to decrypt messages (we compute αw\alpha w instead of ww and obtain x=αwi/αti)x = \alpha w_i / \alpha t_i). In particular, we consider τ=t/tn\tau = t / t_n (such that τn=1\tau_n = 1) and aim at recovering τ\tau.

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

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

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

However, we are given only 5 ciphertexts G,H,Z,U,CG, 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 FF. In particular, for any X=FHE(x)X = FHE(x), we know that Xp1=FHE(xp1)=FHE(1)X^{p-1} = FHE(x^{p-1}) = FHE(1) because the multiplicative group of FF has order p1p-1. This gives us the known plaintext-ciphertext pair that we need!

With the given values, it turns out that Gp1G^{p-1} does not work because the matrix is not inversible, but Zp1Z^{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)F = GF(p). This amounts to finding the secret exponent xx such that h=gxh = g^x (discrete logarithm problem). It turns out that the chosen prime pp (of 337 bits) is weak because p1p-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 pmax=695890117602047p_{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 pmax=26.3M\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 xx is recovered, we can decrypt the flag as m=cuxzm = 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.


Twitter | GitHub | RSS


You may also like

How secure is PDF encryption?
GoogleCTF 2017 - Rubik write-up
Lessons learned from stracing a password manager in Docker
Advent of Code in Rust: lessons learned
And 20 more posts on this blog!