WriteUp Spiky_Elf@38C3 CTF
By fxrh
At 38C3, a few of us played together with the FluxFingers team. This write-up is about spiky_elf, a crypto challenge:
So I recently¹ did some power analysis stuff² and found this RSA private key, except I think I got a few bits wrong?
¹not actually recent
²not actually power analysis
For this challenge, we are given an RSA public key, the flag encrypted with the RSA key, and the RSA private key – however, the private key contains 16 bit flips.
Output.txt:
n = 0x639d87bf6a02786607d67741ebde10aa39746dc8ed22b191ff2fefe9c210b3ee2ce68b185dc7f8069e78441bdec1d33e2b342c226b5cde8a49f567ac11a3bcb7ff88eeededdd0d50eb981635920d2380a6b878d327b261821355d65b2ef9f807035a70c77252d09787c2b3dfafdfa4f5c6b39a1c66c5b39fe9d1ee4b36d86d5
e = 0x10001
flag = 0x40208a7900b1575431a49690030e4eb8be6269edcd3c7b2d97ae94a6eb744e9c622d81b95ea45b23ee6e0d773e3dd48adc6bb2c7c6423d8fd52eddcc6c0710f607590d5fc57a45883a36ad0d851f84d4bee86ffaf65bc1773f97430080926550dce3666051befa87bacc01d44dd09baa6ae93a85cedde5933f7cbbe2cb56cdd
d = 0x1a54893799cd9805600cfaee1c8a408813525db268fbc29e7f2a81eb47b64d2dd20dc8be52b6332e375f92a120957042a92a4bd4f5e13ef14e9b398bec330602dc9dbbb63cf3dfe6d33bf95d08306a894b052e005a57cc41673fe866f4f8b2ffb0aa26fc4c51a8f5135e40df2107e0259ddf4c1d9c1eb41b1f702b135c941
vuln.sage:
#!/usr/bin/env sage
proof.all(False)
bits = 1024
errs = 8
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))
print(f'{d = :#x}')
locs = sorted(Subsets(range(bits), errs).random_element())
for loc in locs:
d ^^= 1 << loc
print(f'{d = :#x}')
So the challenge simulates that we recover the private RSA key by power analysis, but we end up having some bit flips. The simplest way would be to just try out all possible bit flips on all 1009 positions of the private key d and test whether it is a valid key. However, we have \(\binom{1009}{2} \approx 2^{115}\) possible ds to try, so this is clearly infeasable.
Therefore, we have to learn more information about the real value d, and this overview on recovering keys from partial information by Gabrielle De Micheli and Nadia Heninger was really helpful for this. Indeed, by using the fact that e is small, we can recover nearly the first half of d:
def dtilde(k):
return (k * (n + 1) // 6 + 1) // e
min_k, min_count = None, 1024
for k in range(1, e-1):
count = int((dtilde(k) ^^ d) >> 512).bit_count()
if count < min_count:
print(k, count)
min_k, min_count = k, count
msb_d = d >> 514
msb_dtilde = dtilde(min_k) >> 514
diff = msb_d ^^ msb_dtilde
print(bin(diff))
This gives us the diff between the real d and given d for round about the first half of bits of d, and indeed, we find nine bit flips, leaving seven bit flips for the less significant bits.
We continued to try to recover more information about d. There is a very interesting paper by Henecka, May and Meurer in which they correct errors in private keys by using redundant information in the full RSA private key, which also contains p, q, d mod (p-1) and d mod (q-1). We, however, only have d, and so it seems this technique is not applicable.
In the end, it turned out that the last 7 bit flips are brute-forceable with a Meet-in-the-Middle attack. Let d0 be the d-value given to us and d1 the d-value with only 7 bit flips left. We know that if we encrypt and then decrypt a message m with RSA, we get the original message, so
\[m^{ed} \mod n = m.\]Now, if we have d1 instead of d, we have to correct for the bit flips: Assume that d1 has only a bit flip at position i, and it is a bit flip from 1 to 0, then we can correct for this by multiplying a factor as follows:
\[m^{ed_1} m^{e2^i} \mod n = m.\]If it is a bitflip from 0 to 1, we would have to invert the factor, but for simplicity of presentation, I just assume that all bitflips are from 1 to 0. With our 7 bit flips, we get
\[m^{ed_1} m^{e2^{i_1}} m^{e2^{i_2}} m^{e2^{i_3}} m^{e2^{i_4}} m^{e2^{i_5}} m^{e2^{i_6}} m^{e2^{i_7}} \mod n = m,\]which is equivalent to
\[m^{ed_1} m^{e2^{i_1}} m^{e2^{i_2}} m^{e2^{i_3}} \mod n = m m^{-e2^i_4} m^{-e2^i_5} m^{-e2^i_6} m^{-e2^i_7} \mod n.\]We have now 3 correction factors on the left side, and 4 on the right one, which we can now use for the MITM-attack: we calculate the left side for all possible combinations of \(i\)s, put the left side of the equation into a hash map, and then go through all possibilities of \(i\)s on the right side, checking whether we have a hit. Making some small assumptions about the distributions of errors (i.e., there are no more than 4 bit flips in the last 150 bits), I wrote down a rust program which can find the correct bit flips in about 10 minutes on a laptop, using 4GB of RAM, giving us the remaining bit flips, which then can be used to recover the flag:
hxp{fr13nd5_d0nt_l3t_fr1ends_r34d_p0wer_trac35_by_h4nd}
Here is the rust program:
use num::bigint::*;
use itertools::Itertools;
use std::collections::HashMap;
use threadpool::ThreadPool;
use std::sync::Arc;
fn main() {
let n = BigUint::parse_bytes(b"639d87bf6a02786607d67741ebde10aa39746dc8ed22b191ff2fefe9c210b3ee2ce68b185dc7f8069e78441bdec1d33e2b342c226b5cde8a49f567ac11a3bcb7ff88eeededdd0d50eb981635920d2380a6b878d327b261821355d65b2ef9f807035a70c77252d09787c2b3dfafdfa4f5c6b39a1c66c5b39fe9d1ee4b36d86d5", 16).unwrap();
let e = BigUint::parse_bytes(b"10001", 16).unwrap();
let d0 = BigUint::parse_bytes(b"1a54893799cd9805600cfaee1c8a408813525db268fbc29e7f2a81eb47b64d2dd20dc8be52b6332e375f92a120957042a92a4bd4f5e13ef14e9b398bec330602dc9dbbb63cf3dfe6d33bf95d08306a894b052e005a57cc41673fe866f4f8b2ffb0aa26fc4c51a8f5135e40df2107e0259ddf4c1d9c1eb41b1f702b135c941", 16).unwrap();
let d_map = BigUint::parse_bytes(b"10000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000100000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000010000000000000000000001000000000000000000000000000000000000000000000000001000000000000000000000000", 2).unwrap() << 514;
let d1: BigUint = d0 ^ d_map;
let m = BigUint::parse_bytes(b"1111", 16).unwrap();
let ms: Vec<BigUint> = (0..515).map(|i| {
let exp = &e * (BigUint::from(1u32) << i);
if !d1.bit(i) {
m.modpow(&exp, &n).modinv(&n).unwrap()
} else {
m.modpow(&exp, &n)
}
}).collect();
let ms_inv: Vec<BigUint> = (0..515).map(|i| {
let exp = &e * (BigUint::from(1u32) << i);
if d1.bit(i) {
m.modpow(&exp, &n).modinv(&n).unwrap()
} else {
m.modpow(&exp, &n)
}
}).collect();
let mmtilde = (m.modinv(&n).unwrap() * m.modpow(&(e * d1), &n)) % &n;
let bigmap: HashMap<BigUint,(usize,usize,usize)> = HashMap::from_iter((0..350).cartesian_product(0..350)
.cartesian_product(0..350)
.filter(|((a,b), c)| a < b && b < c)
.map(|((a, b), c)| {
if b==a+1 && c == b+1 {println!("{}", a)};
(((&mmtilde * (&ms_inv[a] * &ms_inv[b] * &ms_inv[c])) % &n), (a,b,c))
}));
println!("Done with map");
let pool = ThreadPool::new(4);
let abigmap = Arc::new(bigmap);
let ams = Arc::new(ms);
for d in 150..515 {
let inner_d = d.clone();
let n = n.clone();
let ms = ams.clone();
let bigmap = abigmap.clone();
pool.execute(move || {
println!("d: {}", inner_d);
for e in (inner_d+1)..515 {
let part_one = (&ms[inner_d] * &ms[e]) % &n;
for f in (e+1)..515 {
let part_two = (&part_one * &ms[f]) % &n;
for g in (f+1)..515 {
let mis = (&part_two * &ms[g]) % &n;
if bigmap.contains_key(&mis) {
println!("!!!!!!!!");
let (a,b,c) = bigmap.get(&mis).unwrap();
println!("{} {} {} {} {} {} {}", a, b, c, inner_d, e, f, g);
}
}
}
}
})
}
pool.join();
}