[CSAW CTF 2021] bits
[CSAW CTF 2021] bits
tl;dr
The flag is encrypted with a password of \(a^d \pmod N\). Decrypt by solving the discrete logarithm problem to compute \(d\) from \(g^d\pmod N\) and an oracle that given a number \(g^x \pmod n\) will return the 883rd bit of \(x\). Do the discrete log problem by factorizing \(N\) with the oracle by getting the top bits with a binary search, the lower bits by interactively querying the oracle and doing some number theory to factorize and compute the discrete log.
Description
crypto/bits; 24 solves, 497 points
Challenge authors: Robin_Jadoul and jack
I wrote this oracle in rust so that it can’t sue companies over java stuff.
nc crypto.chal.csaw.io 5010
Solving the challenge
Interacting with the oracle gives:
+++++++++++++++++++++++++++++++++++++++++++++++
+ I hear there's a mythical oracle at Delphi. +
+++++++++++++++++++++++++++++++++++++++++++++++
N = 1264774171500162520522740123707654912813731191511600716918716574718457223687306654609462735310087859826053230623347849924104479609383350278302774436797213741150063894250655073009487778309401701437562813695437500274843520937515731255706515213415007999907839388181535469916350256765596422669114523648082369
G = 2
publ = 1212487202243646984386173446511282289931417044351458340480622092138117454231970360918091810951525920616364982248466162290051013120417592308811316654798136079145284397900865487961920243710196032048995386251362920330926430559242059799715206708168895458603215715146064914454925425870564649600485121538888979
alice = 1024640601443471247332323755059540128989623988611561774565028170938628815764407641381833150460508942917290472170138094077448704053365256467287344121743320435086310199233461822424914222345675720038545559040111784145778223966348376549176125773372309112010889362453693591886310086077964503934892770669706366
nbits = 1006
FLAG = c19eb80cb79e8e15e854db731190f514405670c9fd686775c235905a70293808b0506b42d62398aabe55bb949db56edd0c
We can look at the code (all in rust) to explain some of this output.
let mut rnd = RandState::new_custom(&mut sysrng);
let d = Integer::from(&*ORDER).random_below(&mut rnd);
let publ = Integer::from(&*G).pow_mod(&d, &*N).unwrap();
let nbits = ORDER.significant_bits();
let alice = Integer::from(&*G).pow_mod(&Integer::from(&*ORDER).random_below(&mut rnd), &*N).unwrap();
println!("N = {}\nG = {}\npubl = {}\nalice = {}\nnbits = {}",
*N,
*G,
publ,
alice,
nbits);
encrypt_flag(alice.pow_mod(&d, &N).unwrap());
Looking at encrypt_flag() we see:
fn encrypt_flag(shared: Integer) {
let mut hasher = Sha256::new();
hasher.update(shared.to_string());
let key = hasher.finalize();
let mut cipher = Aes256Ctr::from_block_cipher(
Aes256::new_from_slice(&key.as_slice()).unwrap(),
&GenericArray::clone_from_slice(&[0; 16])
);
let mut flag = FLAG.clone();
cipher.apply_keystream(&mut flag);
println!("FLAG = {}", flag.iter().map(|c| format!("{:02x}", c)).collect::<String>());
}
The code is a bit difficult to understand to someone who has never done any rust, but the gist of it is clear, the function takes in an integer, does some transformations, than encrypts the flag with it. If we knew the password we should be able to easily decrypt the function.
So it looks like FLAG is encrypted with alice.pow_mod(d, N), and we are given alice,
so it is enough to figure out what d is.
We are given publ = G.pow_mod(d, N) and G = 2, so we need to solve the discrete log problem
to recover d.
Normally this is very difficult without knowing the factorization of \(N\), but we also have access
to an oracle.
for line in std::io::stdin().lock().lines() {
let input = line.unwrap().parse::<Integer>().unwrap();
match dlog(input.clone()) {
None => println!("-1"),
Some(x) => {
assert!(G.clone().pow_mod(&x, &*N).unwrap() == input % &*N);
assert!(x < *ORDER);
assert!(x >= 0);
println!("{}", x.get_bit(nbits - 123) as i32)
}
}
}
Checking nbits=1006 we have that nbits-123 = 883.
So we have access to an oracle which given an integer \(m\), computes the discrete log base \(G\),
the value \(x\) which solves \(G^x \equiv m\pmod{N}\),
then returns the 883rd bit of \(x\).
So if we send to the oracle \(2^y\pmod N\), the oracle will spit out the 883rd bit of
\(y\pmod{\texttt{ORDER}}\) where ORDER is the order of \(2\) in \(P\).
If \(y< \texttt{ORDER}\) this just gives us the 883rd bit, but if we query larger numbers,
we get the 883rd bit of \(y-k\cdot \texttt{ORDER}\) for some \(k\).
Let’s denote \(m_k = k\cdot \texttt{ORDER}\).
Playing around with this, if the 883rd bit of \(m_k\) of \(1\), but that bit is \(0\) for \(m_i\) with \(0\le i < k\), than we can actually find the exact value of the leading bits if we send queries with \(y\) having the last 883 bit be all \(1\)s.
b = 883
# pad the last b bits with 1s
def pad(k):
return k*2**(b+1) | (2**(b+1)-1)
# do binary search for the most significant bits of
hi = 2**124
lo = 2**123
print("Binary searching for leading bits")
# Technically I didn't verify that function is 0/1 in this range
# (could have multiple flipping threshholds) but this works so ¯\_(ツ)_/¯
while lo+1 < hi:
mid = (lo + hi)//2
if query(pad(mid)) == b'1':
lo = mid
else:
hi = mid
assert(query(pad(lo))!=query(pad(hi)))
At this point we have the highest bits, we want to recover the lower bits Since now we have have a good estimate of \(m_k\) (call that \(y\)), we can get the next bit by querying for \(2y\), which we’ll get a response of the 883rd bit of \(2y-2m_k\), or equivalently the 882nd bit of \(m_k\). This way we can recover the lower bits of \(m_k\).
# At this point, leading bits is hi, we should search for next bits
hi = 2*hi+1
for i in range(b+1):
if query(pad(hi)) == b'0': # bit is 0
hi = 2*hi + 1
else:
hi = 2*hi
From here, we can guess that \(m_1 = \texttt{ORDER}\) is \(\phi(N)/2\), and use that to compute the factorization of \(N\) into \(p\) and \(q\).
# ok at this point, hi is k*phi/? where ? is 2 or 3, guess ? = 2
qs = 2
k = (hi+N//qs)//(N//qs)
# this should give approximately what we were looking for, round up because N > qs
assert(hi%k==0)
phi = (hi//k)*qs
# integer sqrt
def _sqrt(n):
lo = 0
hi = n
while lo+1<hi:
mid = (lo+hi)//2
if mid*mid <=n:
lo = mid
else:
hi = mid
return lo
# use solution from
# https://crypto.stackexchange.com/questions/5791/why-is-it-important-that-phin-is-kept-a-secret-in-rsa
pplusq = N - phi+1
pminq = _sqrt(pplusq*pplusq-4*N)
assert(pminq*pminq==pplusq*pplusq-4*N)
q = (pplusq + pminq)//2
p = pplusq - q
assert(p*q==N)
print(p, q)
This gives us the factorization! Now we can run the following sage code and use CRT to compute the discrete log of publ.
# Note now we have G, N = p*q
# We need to calculate x s.t. G^x == publ (mod N)
publ = 1212487202243646984386173446511282289931417044351458340480622092138117454231970360918091810951525920616364982248466162290051013120417592308811316654798136079145284397900865487961920243710196032048995386251362920330926430559242059799715206708168895458603215715146064914454925425870564649600485121538888979
p = 26713395582018967511973684657814004241261156269415358729692119332394978760010789226380713422950849602617267772456438810738143011486768190080495256375003
q = 47346065295850807479811692397225726348630781686943994678601678975909956314423885777086052944991365707991632035242429229693774362516043822438274496319123
# Calculate G^x_1 == publ (mod p)
x_1 = Mod(publ, p).log(2)
# Calculate G^x_2 == publ (mod q)
x_2 = Mod(publ, q).log(2)
# => x = x_1 (mod p-1), x = x_2 (mod q-1)
x = crt([x_1, x_2], [p-1, q-1])
print(x)
Now that we have d all we need to do is decrypt it in rust:
fn decrypt_flag(shared: Integer) {
let mut hasher = Sha256::new();
hasher.update(shared.to_string());
let key = hasher.finalize();
let mut cipher = Aes256Ctr::from_block_cipher(
Aes256::new_from_slice(&key.as_slice()).unwrap(),
&GenericArray::clone_from_slice(&[0; 16]),
);
let mut flag = b">\x0f\x13\x1c\x123\xe6\xbf\xccC\xf5*,bfs\x19}\xb5{\x1f\x05\xa7\xe3\xcaE\xedh\xef\x07\x99\xed@\xf1BL\xb1Y\xb7\xcaHg\xdc\xc2'\x93\xdf\xcc\x8a".clone();
cipher.apply_keystream(&mut flag);
println!(
"FLAG = {}",
flag.iter().map(|&c| c as char).collect::<String>()
);
}
And by calling decrypt_flag(alice.pow_mod(&d, &N).unwrap()); we get our flag!
FLAG = flag{https://www.youtube.com/watch?v=uhTCeZasCmc}