y011d4.log

CSAW'21 Writeup

Mon Sep 13 2021

9/11-12 で開催していた CSAW'21 にチーム WreckTheLine で参加しました。結果は 4th/1216 (得点のあるチームのみカウント) でした。 自分は Crypto 全部と Pwn, Misc の一部を解きました。全体的に guessing が必要な問題が多くて若干つらかったです… 解いた問題の中で、 Crypto の Bits は面白い問題に感じたので、この問題について Writeup を書いておきます。

Crypto

Bits

24 solves

main.rs
use std::io::BufRead;
use getrandom::getrandom;
use rug::{
    rand::{RandGen,RandState},
    Integer
};
use sha2::{Sha256,Digest};
use aes::{Aes256,Aes256Ctr,NewBlockCipher,cipher::{FromBlockCipher,StreamCipher}};
use generic_array::GenericArray;

// Secret sauce
// N = p*q; p ≡ q ≡ 3 (mod 4); p, q prime
use hardcore::{dlog, N, G, ORDER, FLAG};

struct SystemRandom;
impl RandGen for SystemRandom {
    fn gen(&mut self) -> u32 {
        let mut buf: [u8; 4] = [0; 4];
        let _ = getrandom(&mut buf).unwrap();
        ((buf[0] as u32) << 24) | ((buf[1] as u32) << 16) | ((buf[2] as u32) << 8) | (buf[3] as u32)
    }
}

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>());
}

fn main() {
    println!("+++++++++++++++++++++++++++++++++++++++++++++++\n\
              + I hear there's a mythical oracle at Delphi. +\n\
              +++++++++++++++++++++++++++++++++++++++++++++++\n");
    let mut sysrng = SystemRandom;
    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());
    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)
            }
        }
    }
}

FN\mathbb{F}_N (NN は合成数) 上の乗算についての群について、入力値に対して離散対数を計算し (dlog)、そのうちの833番目の1ビットだけ教えてくれるオラクルです。DH で共有された鍵を使ってフラグが暗号化されています。

y≡Gxmod  Ny \equiv G^x \mod N となる xx をこのオラクルを使って yy から求められる方法を確立すればこの問題は解けたも同然なので、以下では yy を既知として xx を解く問題と考えます。

このようなオラクルでは、 Ga×GbG^a \times G^b を入力することで a+ba + b が dlog で計算されるはずです。 y×GΔy \times G^{\Delta} を送ると x+Δx + \Delta が返ってきます。今 yy を送ったときの返り値 (すなわち xx の883番目のビット) を cc とします。Δ\Delta を 28832^{883} よりも小さい値としたとき、 Δ\Delta がある値よりも小さければ cc が返り、ある値よりも大きければ 1−c1-c が返ってくるようなしきい値が存在することが示せます。このしきい値は 28832^{883} から xx の883番目以下のビットを引いた値になっており、これから xx の LSB を求めることができます。

あとは xx の MSB を求める方法がわかればこの問題を解くことができます。しかし自分はいい方法が思いつきませんでした。ナイーブに思いつくのは、 RSA の LSB オラクルみたいにある値をかけたら ORDER が引かれることにより883番目のビットが反転するのを利用することですが、 ORDER の値がわからないとこれは使えません。

なので ORDER を求められないか考えました。ORDER について思いを馳せると、そもそもなんで dlog はここまで高速に計算できるのか、というところに気がかりになりました。おそらく pohlig-hellman algorighm が使える程度には小さい素数の積になっているのでは…？もしそうならば、 ORDER の素因数さえ求まれば手元でも pohlig-hellman を使うことで簡単に dlog を計算できます。

N−ORDERN - \mathrm{ORDER} は ϕ(N)=(p−1)(q−1)=N+1−p−q\phi(N) = (p - 1)(q - 1) = N + 1 - p - q の約数になるはずです (ϕ\phi はオイラーの totient function)。オラクルの話に戻ると、 GNG^N を入力すると N>ORDERN > \mathrm{ORDER} なため、 N−k×ORDERN - k\times \mathrm{ORDER} が dlog で計算されます (kk は整数)。 NN が1007ビットで ORDER が1006ビットなことから、k=1k = 1 が期待されます。また、 N−ORDER≤p+q−1N - \mathrm{ORDER} \le p + q - 1 なので、503-504ビットだとわかります。前述の方法を使うことで N−ORDERN - \mathrm{ORDER} の833番目のビット以下を知ることができますが、十分小さい値なので N−ORDERN - \mathrm{ORDER}、すなわち ORDER を exact に知ることになります。

leak_order.py
from pwn import remote

io = remote("crypto.chal.csaw.io", 5010)


def recvsuffix(prefix):
    io.recvuntil(prefix)
    return io.recvline().strip()


N = int(recvsuffix("N = "))
G = int(recvsuffix("G = "))
publ = int(recvsuffix("publ = "))
alice = int(recvsuffix("alice = "))
nbits = int(recvsuffix("nbits = "))
FLAG = recvsuffix("FLAG = ")

print(f"{publ = }")
print(f"{alice = }")
print(f"{FLAG = }")


def check(n: int) -> int:
    io.sendline(str(n))
    return int(io.recvline())


target_idx = 883

r = 2 ** target_idx
l = 0
order_current = check(pow(G, N, N) % N)
while True:
    c = (r + l) // 2
    print(c)
    ret = check(pow(G, c, N) * pow(G, N, N) % N)
    assert ret != -1
    if ret == order_current:
        l = c
    else:
        r = c
    if l == r or l + 1 == r:
        break
for i in range(2):
    ret = check(pow(G, l + i, N) * pow(G, N, N) % N)
    if ret != order_current:
        n_order_lsb = 2 ** target_idx - (l + i)
        break
else:
    raise RuntimeError

print(f"{n_order_lsb = }")
order = n - n_order_lsb
print(f"{order = }")
print(factor(order))

これで ORDER が 2^2 * 633462701 * 785685301^16 * 794309437^16 * 942797321 であることがわかりました。 以下のようにして離散対数を解きます。

dlog.py
d = int(pari(f"znlog({publ}, Mod(2, {N}), [{order}, [2, 2; 633462701, 1; 785685301, 16; 794309437, 16; 942797321, 1]])"))

ここまでくればあとは AES の計算をするだけなのですが、 python の PyCryptodome にある AES だとうまくいかず… 配布された main.rs と同様に rust で復号しました。

Cargo.toml
[package]
name = "dec_flag"
version = "0.1.0"
edition = "2018"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
sha2 = "0.9.8"
rug = "1.13.0"
aes = { version = "0.7.5", features = ["ctr"] }
generic-array = "0.14.4"
src/main.rs
use aes::{
    cipher::{FromBlockCipher, StreamCipher},
    Aes256, Aes256Ctr, NewBlockCipher,
};
use generic_array::GenericArray;
use rug::Integer;
use sha2::{Digest, Sha256};

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_enc = [
        153, 3, 149, 222, 18, 52, 98, 0, 90, 40, 48, 96, 62, 50, 195, 251, 236, 214, 24, 27, 167,
        48, 178, 227, 11, 227, 126, 144, 124, 255, 22, 241, 231, 18, 84, 103, 79, 193, 75, 164, 77,
        246, 98, 55, 158, 112, 24, 8, 158,
    ];
    cipher.apply_keystream(&mut flag_enc);
    println!(
        "FLAG = {}",
        flag_enc
            .iter()
            .map(|c| format!("{:02x}", c))
            .collect::<String>()
    );
}

fn main() {
    decrypt_flag(Integer::from_str_radix("1242028178647590704279378147312715879596640199474561100680566513369493640389472928310317935390037326947665146024226278842300527014342781912911906398699666106786779642003210233394246219665550707396372046062028796441890562369476047244369050148474596530992544644857727508417684318244753524268776353439295955", 10).unwrap());
}

flag{https://www.youtube.com/watch?v=uhTCeZasCmc}