Two weeks ago, I participated in the KalmarCTF and spent most of my time understanding the knowledge related to this challenge, but I didn’t solve it in the end. After the game, I saw Genni’s team solved this challenge in the discord, so I asked him for advice and finally solved it. I’ll record it here.

DESCRIPTION:

Run laconic commands on the [QWW18](https://eprint.iacr.org/2018/409) server!

Note: lattices in pure sage are very inefficient. Patience is encouraged. As is local testing on smaller parameters.

Since the attachment is too large, I will not post the code here.

In commands.py , there are allowed_commands and cat flag.txt , which is unallowed. What’s more, pks was generated by allowed_commands(It is very similar to the polynomial construction with a predicate product of 0.)

main part: server.py(about the process of laconic), ab_lfe.py(about the encrypt/decrypt of the scheme).

The purpose is to decrypt the compressed ciphertext returned by the output server to obtain the flag.

SOLUTION:

In the solution, I will mainly describe the concepts related to the problem and the ideas of solving the problem. I will not describe about the detours I took (such as running Flatter with 40GB swap, trying to do Knapsack on such a large dimension, etc.)

First, let me introduce the gadget decomposition in FHE.

Gadget Decomposition

In FHE schemes, Gadget decomposition is a key technique for decomposing large coefficients in ciphertext into smaller components for efficient homomorphic operations. This decomposition method is particularly important for controlling noise growth and achieving efficient homomorphic multiplication.

Suppose we have a Gadget vector , where is a base number (usually 2 or some other small integer, in the challenge). Gadget decomposition operation decomposes an element into vectors , such that:

Suppose we choose and need to factorize an integer .

First, we determine the Gadget vector: . Represent 45 in binary: 45 = 101101₂. The factorization result is

Verification:

When performing homomorphic multiplication of two RLWE ciphertexts and : perform Gadget decomposition on the second ciphertext to obtain multiple small coefficient polynomials. Multiply the first ciphertext with each of the small coefficient polynomials after decomposition. Appropriately combine the results of these products.

The key advantage of this approach is that when is multiplied by a small coefficient polynomial, the noise growth is significantly limited because one side of the multiplication has a small coefficient.

---

Now, comeback to challenge. Only focus on content related to the core problem solving of the challenge. We can give any comments, but no more than 69 polynomials. We can know that this is a variant of QWW18 where LWE is replaced by RLWE.

# server.py
...
        # Chunk the comment up into ring elements
        comment_chunks = []
        for i in range(0, len(comment), N // 8):
            comment_chunks.append(encode_bytes(comment[i : i + (N // 8)]))
        if len(comment_chunks) > len(comment_inputs):
            conn.sendall(b"Comment too long\n")
            return

        # Encrypt the result of running the command
        result = result[:N//8]
        input_ctxts, t, msg_ctxt = predicate_pk.encrypt_msg([command_input] + comment_inputs[:len(comment_chunks)],
		[encode_bytes(cmd)] + comment_chunks,
		encode_bytes(result))
...

# ab_lfe.py
...
class public_key:
    # Encrypt a message that can only be decrypted when this public_key evaluates to 0.
    def encrypt_msg(self, input_pks: list, input_values: list, msg: list):
        assert len(input_pks) == len(input_values)

        t = uniform_sampler_Rx()

        rlwe_mat = block_matrix([[pk.mat - matrix(Rx, val * gadget) for pk, val in zip(input_pks, input_values)]])
        rlwe_mat = rlwe_mat.augment(self.mat * gadget_inv_elem(t))
        ctxt = rlwe_sample(rlwe_mat)

        input_ctxts = [ctxt[ell * i : ell * (i + 1)] for i in range(len(input_pks))]
        msg_ctxt = ctxt[-1] + Rx(msg) * (q // 2)

        # Because no homorphic operations are done on msg_ctxt, we can afford to add much more noise.
        msg_noise_sampler = PolySampler(Rx, N, UniformSampler(Zq, q, (-q//8, q//8 + 1)))
        msg_ctxt += msg_noise_sampler()

        return (input_ctxts, t, msg_ctxt)
...
def encode_bytes(s: bytes):
    assert 8 * len(s) <= N
    s_bits = [(c >> j) & 1 for c in s for j in range(8)]
    s_bits += [0] * (N - len(s_bits))
    return Rx(s_bits)

The following information can be obtained from the code:

• flag is encrypted as msg_ctxt;
• If you want to get the cipher texts of flag directly, are fixed;
• Base of gadget is 17;
• is a polynomial of your choice, but the coefficients can only be 0 or 1;

What’s more, you can get lots of RLWE ciphertexts (), is a small distribution, is a complete distribution.

From section 7 of author’s paper and chats of discord, we can know if someone know and he/she can construct ( is much greater than ), then he/she can easily get and :

Rounding to get , just inverse to get by in . If we get , it’s easy to compute , cuz we have . At last, we could easily capture the flag from msg_ctxt !!!

---

Construct Comments

So how to construct comments could make us get ? I think this is really hard and the most wonderful part of challenge, and I asked @Genni for help to know how to construct it.

Now the problem has been transformed into the following form:

We have the known polynomial , and above and . We want to use and to get . If , it’s really easy to construct , like the following:

If in this case, each only takes a value at position , then it can traverse from 0 to 69.

Then we have

Since the base is 2 and , we can directly use binary decomposition to decompose the coefficients of each position of the polynomial to get new binary polynomials .

Based on the above, we can find a solution when the base is 2, so what about the base 17?

The core idea is that for each of the 69 comments, we use it to represent a binary digit, and then add them all up.

For example, for the first comment we use it to represent it as , for the second , for the third , and so on untill . Then the same approach is used as when the base is 2.

Due to the Gadget decomposition, each is based on 17, and 17^17 is larger than q. By using base 17 to represent binary values, and the noise superposition will be much smaller. For instance, we can represent powers of 2 with small coefficients: 1=1,2=2,4=4,8=8,16=17-1,32=2*17-2… and so on. This makes it easy to obtain with small noise. Finally, we add them up to get what we want: . Now done.

---

In summary, the improper use of Gadget decomposition primitives in FHE schemes can lead to severe security vulnerabilities, allowing attackers to decrypt arbitrary ciphertexts with minimal noise overhead.