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 で共有された鍵を使ってフラグが暗号化されています。

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

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

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

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

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

    これで ORDER2^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}