# Spikey Elf @ HXP 38C3 CTF

> Source: https://rot256.dev/post/spiky-elf/
> Author: Mathias Hall-Andersen
> Date: 2025-01-02
> License: CC BY 4.0 — reuse permitted with attribution to Mathias Hall-Andersen (rot256.dev).

Math macros in scope (KaTeX, `\name = expansion`):

```text
\Div = \mathrm{Div}
\FF = \mathbb{F}
\GG = \mathbb{G}
\NN = \mathbb{N}
\Norm = \mathrm{N}
\PRF = \mathsf{PRF}
\RR = \mathbb{R}
\Tr = \mathrm{Tr}
\ZZ = \mathbb{Z}
\adv = \mathscr{A}
\bin = \{0, 1\}
\coloneqq = \mathrel{\mathop:}=
\defeq = \coloneqq
\deg = \text{deg}
\divides =  \ | \ 
\gcd = \text{gcd}
\hash = \mathsf{H}
\img = \text{img}
\ker = \text{ker}
\language = \mathcal{L}
\lc = \mathrm{lc}
\lcm = \text{lcm}
\msg = \mathsf{msg}
\negl = \text{negl}(\lambda)
\pk = \mathsf{pk}
\prob = \mathbb{P}
\sample = \overset{\$}{\gets}
\secpar = \lambda
\sig = \sigma
\sign = \mathsf{Sign}
\sk = \mathsf{sk}
\support = \mathrm{Supp}
\tensor = \otimes
\verify = \mathsf{Verify}
```


Happy new year!

Here is a writeup for the challenge `Spikey Elf` from the 38C3 CTF by HXP.

# The Challenge

We are given the following code:

```sage
#!/usr/bin/env sage
proof.all(False)

bits = 1024
errs = 16

p = random_prime(2^(bits//2))
q = random_prime(2^(bits//2))
n = p * q
e = 0x10001
print(f'{n = :#x}')
print(f'{e = :#x}')

flag = pow(int.from_bytes(open('flag.txt','rb').read().strip()), e, n)
print(f'{flag = :#x}')

d = inverse_mod(e, lcm(p-1, q-1))
locs = sorted(Subsets(range(bits), errs).random_element())
for loc in locs:
    d ^^= 1 << loc
print(f'{d = :#x}')
```

And the output:

```txt
n = 0x639d87bf6a02786607d67741ebde10aa39746dc8ed22b191ff2
    fefe9c210b3ee2ce68b185dc7f8069e78441bdec1d33e2b342c22
    6b5cde8a49f567ac11a3bcb7ff88eeededdd0d50eb981635920d2
    380a6b878d327b261821355d65b2ef9f807035a70c77252d09787
    c2b3dfafdfa4f5c6b39a1c66c5b39fe9d1ee4b36d86d5
e = 0x10001
flag = 0x40208a7900b1575431a49690030e4eb8be6269edcd3c7b2d
    97ae94a6eb744e9c622d81b95ea45b23ee6e0d773e3dd48adc6bb
    2c7c6423d8fd52eddcc6c0710f607590d5fc57a45883a36ad0d85
    1f84d4bee86ffaf65bc1773f97430080926550dce3666051befa8
    7bacc01d44dd09baa6ae93a85cedde5933f7cbbe2cb56cdd
d = 0x1a54893799cd9805600cfaee1c8a408813525db268fbc29e7f2
    a81eb47b64d2dd20dc8be52b6332e375f92a120957042a92a4bd4
    f5e13ef14e9b398bec330602dc9dbbb63cf3dfe6d33bf95d08306
    a894b052e005a57cc41673fe866f4f8b2ffb0aa26fc4c51a8f513
    5e40df2107e0259ddf4c1d9c1eb41b1f702b135c941
```

In other words:

- The RSA public key (`n`, `e`)
- The encrypted flag (`flag`)
- The private key `d` with *16 random bits flipped*

## Solution

The first observation is that since `e` is small (we can enumerate `1..e`) we can easily recover the *high* bits of `d`.

To see this, observe:

$$
\begin{aligned}
e \cdot d &\equiv 1 \mod (p - 1) \cdot (q - 1) \\
e \cdot d &= 1 + k \cdot (p - 1) \cdot (q - 1) \\
e \cdot d &= 1 + k \cdot (p q - p - q + 1) \\
e \cdot d &= 1 + k \cdot (n - p - q + 1) \\
d &= \frac{k \cdot n - k (p+q - 1) - 1}{e}
\end{aligned}
$$

So if we simply guess $ k $ we can recover the high bits of $ d $
since $ n $ is roughly twice the length of the unknown $ p + q $.
This immediately lets us eliminate a bunch of the bit flips in $ d $.

After applying this trick we are left with the following partly corrected $ d $:

```txt
d = 0x1a548937b9cd9805600cface1c8a408813525db268fbc29e7f2
    a81ea47b6cd2dd205c8be52b6332e375f92a120957040a92acbd4
    f7e13ef14e9b39cbec330602dc9dbbb63cf3dfe6d33bf95d08306
    a894b052e005a57cc41673fe866f4f8b2ffb0aa26fc4c51a8f513
    5e40df2107e0259ddf4c1d9c1eb41b1f702b135c941
```

This leaves us with 7 errors in the low bits of $ d $ to correct.
Since the low bits of $ d $ are 512 bits long, and we have 7 errors, a naive bruteforce enumerating all options would take:

$$
\binom{512}{7} \approx 2^{51}
$$

Which is doable, but a bit much...

The better solution is a meet-in-the-middle attack:

- Pick a known plaintext $ m $ (e.g. $ 2 $ )
- Compute the ciphertext $ c = m^e \bmod n $.
- Partition the low bits of $ d $ into two random sets $ \text{lhs\_bits} \subseteq [512] $ and $ \text{rhs\_bits} \subseteq [512] $:
  - $ \text{lhs\_bits} $ containing 3 error positions.
  - $ \text{rhs\_bits} $ containing 4 error positions.

  Of course, we won't know that these partitions contain the correct number of errors,
  but we guess that they do. \
  It happens with probability roughly $ 27\% $.

Next observe that for the correct `d` we have:
$$
\begin{aligned}
(m^e)^d &\equiv m \bmod n \\
(m^e)^d \cdot m^{-1} &\equiv 1 \bmod n \\
\end{aligned}
$$
If we split `d` into:
$$
d = \mathsf{HIGH} + \sum_{i \in \text{lhs\_bits}} 2^i \cdot d_i + \sum_{i \in \text{rhs\_bits}} 2^i \cdot d_i
$$
For a constant $ \mathsf{HIGH} $ representing the upper bits of $ d $ -- which we have successfully recovered.

This formulation allows us to write:
$$
1 \equiv m^{-1} \cdot c^{\mathsf{HIGH} + \sum_{i \in \text{lhs\_bits}} 2^i \cdot d_i} \cdot c^{\sum_{i \in \text{rhs\_bits}} 2^i \cdot d_i} \bmod n
$$
If we divide both sides by $ m^{-1} \cdot c^{\mathsf{HIGH} + \sum_{i \in \text{lhs\_bits}} 2^i \cdot d_i} $ we get:
$$
m \cdot c^{- \mathsf{HIGH} - \sum_{i \in \text{lhs\_bits}} 2^i \cdot d_i} \equiv c^{\sum_{i \in \text{rhs\_bits}} 2^i \cdot d_i} \bmod n
$$
This enables us to search through the possibilities on the left and right hand side of the equation, looking for a match.
Meaning that we can *individually* guess which bits in $ \text{lhs\_bits} $ (3) and $ \text{rhs\_bits} $ (4) are flipped.
Once we have found a match, we can reconstruct $ d $ by flipping the bits in the correct positions.

In Rust, the attack looks like this:

```rust
use std::{collections::HashMap, sync::Mutex};

use rand::random;
use rayon::iter::{IntoParallelIterator, ParallelIterator};
use rug::{integer::Order, Complete, Integer};

const LOW_BITS: usize = 512;

const TOTAL_BITS: usize = 1024;

const IS_TEST: bool = false;

fn unhex(s: &str) -> Integer {
    Integer::parse_radix(s, 16).unwrap().complete()
}

fn main() {
    let e = unhex("10001");
    let n;
    let d; // partly faulty d
    if IS_TEST {
        n = unhex("100a4ee7a760d592fd30bcff5e45d790782c176a957193c8943d6bb4f9a9d3d202af512aeea585da574b3789c22
                   e3dbca5aff1423d5959efda1120f8b37f81b6a7c86bb15a4a448aa4aabb4ec3f5897333f75185c29b9a36924f0a
                   20e807308404269c1fc74914f0dc09aca0e9db293b1462cf84bc9d3472d90874c0c8de46af");
        d = unhex("263bec095378069ef0d6942b4253c8999d59bc175b51f7aa4d707aa44fd8f807c84e8d7380971c906f33e396833
                   e25fade169d45ff665472dda1a6ae2b6eeb897d3cab0f2e742fea35a7abfcd7bd0982c2c8665ab8fd0db99d7105
                   e544ea6406345df27a7dbd86639a6f9ce59bbeb7e773301400b8b2a02241b96bf51d50189");
    } else {
        n = unhex("639d87bf6a02786607d67741ebde10aa39746dc8ed22b191ff2fefe9c210b3ee2ce68b185dc7f8069e78441bdec
                   1d33e2b342c226b5cde8a49f567ac11a3bcb7ff88eeededdd0d50eb981635920d2380a6b878d327b261821355d6
                   5b2ef9f807035a70c77252d09787c2b3dfafdfa4f5c6b39a1c66c5b39fe9d1ee4b36d86d5");
        d = unhex("1a548937b9cd9805600cface1c8a408813525db268fbc29e7f2a81ea47b6cd2dd205c8be52b6332e375f92a1209
                   57040a92acbd4f7e13ef14e9b39cbec330602dc9dbbb63cf3dfe6d33bf95d08306a894b052e005a57cc41673fe8
                   66f4f8b2ffb0aa26fc4c51a8f5135e40df2107e0259ddf4c1d9c1eb41b1f702b135c941");
    }

    let pt = Integer::parse("2").unwrap().complete();
    let ct = pt.clone().pow_mod(&e, &n).unwrap();

    // compute ct^{2^i} for i in 0..MAX_BITS
    let mut powers: Vec<Integer> = vec![ct];
    for _i in 0..TOTAL_BITS {
        let last = powers.last().unwrap().clone();
        powers.push((last.clone() * last).modulo(&n));
    }

    // invert every power mod n
    let inv_powers: Vec<Integer> = powers
        .iter()
        .map(|x| x.clone().invert(&n).unwrap())
        .collect();

    // decompose d into bits
    let d_bits: Vec<bool> = d.to_digits(Order::Lsf);

    // bits to flip
    let sol: Mutex<Option<Vec<usize>>> = Mutex::new(None);
    while sol.lock().unwrap().is_none() {
        // randomly split the bits
        let mut lhs_bits: Vec<bool> = vec![false; LOW_BITS];
        let mut rhs_bits: Vec<bool> = vec![false; LOW_BITS];
        for i in 0..LOW_BITS {
            if random() {
                lhs_bits[i] = true;
            } else {
                rhs_bits[i] = true;
            }
        }

        // split the low bits
        // m = (m^e)^d = (m^e)^d_high * (m^e)^d_lo
        // (m^e)^-d_high * m = (m^e)^d_lo
        let mut pt_lhs = pt.clone();
        let mut pt_rhs = Integer::from(1);
        for (i, bit) in d_bits.iter().enumerate() {
            if !bit {
                continue;
            } else if i >= LOW_BITS {
                pt_lhs *= &inv_powers[i];
                pt_lhs %= &n;
            } else if lhs_bits[i] {
                pt_lhs *= &inv_powers[i];
                pt_lhs %= &n;
            } else if rhs_bits[i] {
                pt_rhs *= &powers[i];
                pt_rhs %= &n;
            }
        }

        fn flip(
            bits: &[bool],
            d_0_to_1: &[Integer], // group deltas taking "1"s to "0"s
            d_1_to_0: &[Integer], // group deltas taking "0"s to "1"s
            val: &Integer,
            n: &Integer,
            i: usize,
        ) -> Integer {
            let delta = if bits[i] {
                d_1_to_0[i].clone()
            } else {
                d_0_to_1[i].clone()
            };
            (val * delta) % n
        }

        //
        let mut table: HashMap<Integer, (usize, usize, usize)> = HashMap::new();

        // forward (low errors 3)
        println!("Building table");
        let lhs = pt_lhs.clone();
        for i1 in 0..LOW_BITS {
            if !lhs_bits[i1] {
                continue;
            }
            let lhs = flip(&d_bits, &inv_powers, &powers, &lhs, &n, i1);
            for i2 in i1..LOW_BITS {
                if !lhs_bits[i2] {
                    continue;
                }
                let lhs = flip(&d_bits, &inv_powers, &powers, &lhs, &n, i2);
                for i3 in i2..LOW_BITS {
                    if !lhs_bits[i3] {
                        continue;
                    }
                    let lhs = flip(&d_bits, &inv_powers, &powers, &lhs, &n, i3);
                    table.insert(lhs, (i1, i2, i3));
                }
            }
        }

        // matching time
        println!("Matching time");
        (0..LOW_BITS).into_par_iter().for_each(|i1| {
            let rhs = pt_rhs.clone();
            if !rhs_bits[i1] {
                return;
            }
            let rhs = flip(&d_bits, &powers, &inv_powers, &rhs, &n, i1);
            for i2 in i1..LOW_BITS {
                if !rhs_bits[i2] {
                    continue;
                }
                let rhs = flip(&d_bits, &powers, &inv_powers, &rhs, &n, i2);
                for i3 in i2..LOW_BITS {
                    if !rhs_bits[i3] {
                        continue;
                    }
                    let rhs = flip(&d_bits, &powers, &inv_powers, &rhs, &n, i3);
                    for i4 in i3..LOW_BITS {
                        if !rhs_bits[i4] {
                            continue;
                        }
                        let rhs = flip(&d_bits, &powers, &inv_powers, &rhs, &n, i4);
                        match table.get(&rhs) {
                            Some((j1, j2, j3)) => {
                                *sol.lock().unwrap() = Some(vec![i1, i2, i3, i4, *j1, *j2, *j3]);
                            }
                            None => {}
                        }
                    }
                }
            }
        });
    }

    // flip the bits
    let sol = sol.lock().unwrap().clone().unwrap();
    let mut d_bits: Vec<bool> = d.to_digits(Order::Lsf);
    for i in sol.iter() {
        d_bits[*i] = !d_bits[*i];
    }

    // reconstruct d
    let d = Integer::from_digits(&d_bits, Order::Lsf);

    // decrypt the flag
    let flag = unhex(
        "40208a7900b1575431a49690030e4eb8be6269edcd3c7b2d
         97ae94a6eb744e9c622d81b95ea45b23ee6e0d773e3dd48adc6bb
         2c7c6423d8fd52eddcc6c0710f607590d5fc57a45883a36ad0d85
         1f84d4bee86ffaf65bc1773f97430080926550dce3666051befa8
         7bacc01d44dd09baa6ae93a85cedde5933f7cbbe2cb56cdd",
    );
    let flag = flag.pow_mod(&d, &n).unwrap();
    let flag = flag.to_string_radix(16);

    // hex decode
    let flag = hex::decode(flag).unwrap();
    println!("{}", String::from_utf8_lossy(&flag));
}
```

Running the code we recover the flag:

```txt
rot256@digit ~/s/rsarac (master)> cargo run --release
   Compiling rsarac v0.1.0 (/Users/rot256/src/rsarac)
    Finished `release` profile [optimized] target(s) in 0.51s
     Running `target/release/rsarac`
Building table
Matching time
hxp{fr13nd5_d0nt_l3t_fr1ends_r34d_p0wer_trac35_by_h4nd}
```