We are given a transcript of many RAWR exchanges. Looking at the source, RAWR is basically ML-KEM with dinosaur branding:
#define NR_OF_MESSAGES 1000
#define NR_OF_SEEDS 100
for (uint64_t i = 0; i < NR_OF_SEEDS; ++i) {
csprng.generate(seed_ds[i]);
csprng.generate(seed_zs[i]);
csprng.generate(seed_ms[i]);
}
for (uint64_t i = 0; i < NR_OF_MESSAGES; ++i) {
seed_idx = seed_dist(csprng);
if (i == cosmic_ray_idx) {
// same as else branch, but oh no! A cosmic ray hit us during communication!
// Probably nothing went wrong, I'll just continue.
// (No cosmic rays are distributed with this program, make your own...)
continue;
}
else {
rawr_1024::keygen(seed_ds[seed_idx], seed_zs[seed_idx], ek, dk);
assert(rawr_1024::encapsulate(seed_ms[seed_idx], ek, ct, shared_secret_sender));
}
std::string in = "RAWR*" + std::to_string(i) + "! " + flag;
assert(aes_gcm_encrypt(in, &out, (const uint8_t *) &shared_secret_sender));
}
There are only 100 seed triplets, but 1000 messages. So most public keys appear multiple times in the transcript. One exchange is hit by a cosmic ray though, meaning one computation was faulty.
We can find it by counting the public keys in the transcript. There are 101 unique public keys: 100 normal ones and one key that appears exactly once. That one-time key is the faulty exchange.
The ML-KEM public key has the form:
ek = ByteEncode_12(t_hat) || rho
The last 32 bytes are
cosmic rho: ...68396001...
normal rho: ...683d6001...
xor: ...00040000...
So the cosmic ray flipped one bit in
For the normal key we have:
t = A * s + e
For the faulty key we have:
t' = A' * s + e
Subtracting these cancels the error:
t' - t = (A' - A) * s
So instead of solving noisy LWE, we just have to solve a linear system modulo
The solver parses the normal and faulty public keys, regenerates both matrices from
for (size_t p = 0; p < N / 2; p++) {
size_t idx0 = 2 * p;
size_t idx1 = 2 * p + 1;
rawr_field::zq_t zeta = rawr_ntt::POLY_MUL_ZETA_EXP[p];
uint32_t mat[8][9] = {};
for (size_t row = 0; row < K; row++) {
for (size_t col = 0; col < K; col++) {
size_t a_offset = (row * K + col) * N;
rawr_field::zq_t dA0 = delta_A[a_offset + idx0];
rawr_field::zq_t dA1 = delta_A[a_offset + idx1];
mat[2 * row][2 * col] =
(mat[2 * row][2 * col] + dA0.raw()) % Q;
mat[2 * row][2 * col + 1] =
(mat[2 * row][2 * col + 1] + (dA1 * zeta).raw()) % Q;
mat[2 * row + 1][2 * col + 1] =
(mat[2 * row + 1][2 * col + 1] + dA0.raw()) % Q;
mat[2 * row + 1][2 * col] =
(mat[2 * row + 1][2 * col] + dA1.raw()) % Q;
}
mat[2 * row][8] = delta_t[row * N + idx0].raw();
mat[2 * row + 1][8] = delta_t[row * N + idx1].raw();
}
uint32_t solution[8];
gauss_solve(mat, solution);
}
As a quick sanity check, we can compute
Now we do not need to implement full decapsulation. We can directly decrypt the K-PKE ciphertext with the recovered
// K-PKE decrypt:
// ct = (Compress(u, 11), Compress(v, 5))
// m = Compress_1(v - s^T * NTT(u))
rawr_utils::poly_vec_ntt<K>(u);
std::array<rawr_field::zq_t, N> stu{};
rawr_utils::matrix_multiply<1, K, K, 1>(s_ntt, u, stu);
rawr_utils::poly_vec_intt<1>(stu);
rawr_utils::poly_vec_sub_from<1>(stu, v);
rawr_utils::poly_compress<1>(v);
std::array<uint8_t, 32> m{};
rawr_utils::encode<1>(v, m);
The shared secret is then:
SHA3-512(m || SHA3-256(ek))[:32]
Finally, the
nonce || ciphertext || tag
So we use the recovered shared secret as an AES-256-GCM key and decrypt the message.
Running the solver gives:
Secret key recovered successfully! Error vector has small coefficients.
Recovered m: 6151fd297873d25abe74ba215f18b50ab10abf89caaff60dcc5a0ccd22f919c3
Shared secret: f92068b17ea895dbdb8e63693fe75b10fd476b52a5b23360de84b692443f5424
Decrypted: RAWR*88! dach2026{m4yb3_If_7h3_qu4nt0s4ur1_W0uldn't_h4v3_l00k3d_th3_b1t_W0uldn't_h4v3_fl1pp3d_2c6215227012}
So the flag is:
dach2026{m4yb3_If_7h3_qu4nt0s4ur1_W0uldn't_h4v3_l00k3d_th3_b1t_W0uldn't_h4v3_fl1pp3d_2c6215227012}