---
# System prepended metadata

title: Moriarty's challenge
tags: [CTF, Write-up]

---

## Quick recap
There is a set of secret key vectors of length $N$ generated: $\bar S = \{S_i\}, 0\leq i<k$ as well as set of masking public polynomials $\bar A$. The cyphertext then is $B=\sum{A_i*S_i} + \Delta*M + E$

## Solution
The algorithm itself seems to be secure enough, so it's quite pointless to try to find any vulnerabilities. But it's also quite obvious that it highly depends on the key generation algorithm. Looking at parameters $N=16$ and $k=8$ we should have 128 bits of entropy, which is infeasible to bruteforce.
Fortunately there was a hint in the example code and tests, that there exists some subset of keys with low hamming weight.
And indeed this key generation code is flawed:
```rust
pub fn toy_binary_randomness(N: usize,k:usize) -> Vec<u64>{
    let mut rng = rand::thread_rng();
    let mut secret_key = vec![0u64;N*k];
    for i in 0..=k-1{
        secret_key[rng.gen_range(i*N..=(i+1)*N-1)]+=1u64;
    }
    secret_key
}
```
As you can see it generates all of the keys as a single array, where each key corresponds to a bucket from $i*N$ bit up to $(i+1)*N-1$ bit. And all the algorithm does switching a single bit in every key.That could indeed happen quite rarely if you generate all the bits randomly, but this would be prevented by a suitable assertion to prevent weak keys in production.

All this clues makes us want to check what if the key that was used in this challenge was indeed a weak one, generated with `toy_binary_randomness`. That key would have just $16$ different combinations for a single key and $16^8 = 2^{32} = 4294967296$ combinations in total which is around $8*10^{28}$ times less than original key.

Using this knowledge we can create a crude bruteforcing script. Which checks every weak key
```rust
(0..N).into_par_iter().for_each(|i0| {
        for i1 in 0..N {
            for i2 in 0..N {
                for i3 in 0..N {
                    for i4 in 0..N {
                        for i5 in 0..N {
                            for i6 in 0..N {
                                for i7 in 0..N {
                                    let mut sk = vec![0u64; N * k];
                                    sk[i0] = 1;
                                    sk[1 * N + i1] = 1;
                                    sk[2 * N + i2] = 1;
                                    sk[3 * N + i3] = 1;
                                    sk[4 * N + i4] = 1;
                                    sk[5 * N + i5] = 1;
                                    sk[6 * N + i6] = 1;
                                    sk[7 * N + i7] = 1;
                                    let glwe_poly_list = PolynomialList::from_container(sk, polynomial_size);
                                    let flag = decrypt_tfhe_test(
                                        &ciphertext_poly_list,
                                        glwe_poly_list,
                                        modulus_p,
                                        modulus_q,
                                        N,
                                        k,
                                    );

                                    if check_your_flag(&flag) {
                                        println!("{:#?}", flag);
                                        break;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    });
```
This took just around a minute to break 
