# [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 oracleand doing some number theory to factorize and compute the discrete log.
## Description 
crypto/bits; 24 solves, 497 pointsChallenge 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 [main.rs](https://ctf.csaw.io/files/cae893c9c0f0d7b488b3eddb1b99219a/main.rs)
## Solving the challenge
Interacting with the oracle gives:```++++++++++++++++++++++++++++++++++++++++++++++++ I hear there's a mythical oracle at Delphi. ++++++++++++++++++++++++++++++++++++++++++++++++
N = 1264774171500162520522740123707654912813731191511600716918716574718457223687306654609462735310087859826053230623347849924104479609383350278302774436797213741150063894250655073009487778309401701437562813695437500274843520937515731255706515213415007999907839388181535469916350256765596422669114523648082369G = 2publ = 1212487202243646984386173446511282289931417044351458340480622092138117454231970360918091810951525920616364982248466162290051013120417592308811316654798136079145284397900865487961920243710196032048995386251362920330926430559242059799715206708168895458603215715146064914454925425870564649600485121538888979alice = 1024640601443471247332323755059540128989623988611561774565028170938628815764407641381833150460508942917290472170138094077448704053365256467287344121743320435086310199233461822424914222345675720038545559040111784145778223966348376549176125773372309112010889362453693591886310086077964503934892770669706366nbits = 1006FLAG = c19eb80cb79e8e15e854db731190f514405670c9fd686775c235905a70293808b0506b42d62398aabe55bb949db56edd0c```
We can look at the code (all in rust) to explain some of this output.```rust     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:```rustfn 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(&[;; 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, butthe 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 easilydecrypt 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 problemto recover `d`. Normally this is very difficult without knowing the factorization of $N$, but we also have accessto an oracle.
```rust    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.
```pythonb = 883# pad the last b bits with 1sdef pad(k):    return k*2**(b+1) | (2**(b+1)-1)
# do binary search for the most significant bits of hi = 2**124lo = 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 bitsSince 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 bitsof $m_k$.```python# At this point, leading bits is hi, we should search for next bits hi = 2*hi+1for 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$.```python# ok at this point, hi is k*phi/? where ? is 2 or 3, guess ? = 2qs = 2
k = (hi+N//qs)//(N//qs) # this should give approximately what we were looking for, round up because N > qsassert(hi%k==0) phi = (hi//k)*qs
# integer sqrtdef _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-rsapplusq = N - phi+1pminq = _sqrt(pplusq*pplusq-4*N)assert(pminq*pminq==pplusq*pplusq-4*N)q = (pplusq + pminq)//2p = pplusq - qassert(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`.```python# Note now we have G, N = p*q# We need to calculate x s.t. G^x == publ (mod N)
publ = 1212487202243646984386173446511282289931417044351458340480622092138117454231970360918091810951525920616364982248466162290051013120417592308811316654798136079145284397900865487961920243710196032048995386251362920330926430559242059799715206708168895458603215715146064914454925425870564649600485121538888979p = 26713395582018967511973684657814004241261156269415358729692119332394978760010789226380713422950849602617267772456438810738143011486768190080495256375003q = 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:```rustfn 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(&[;; 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}```