Cryptopals Set 2 Challenge 14 & 16

Cryptopals 是一套现代密码学相关的 Codelab,这一系列文章用于自己存档,如果你还没有做过这个Lab,也强烈建议访问 https://cryptopals.com/ 来亲自体验。

2.14 Byte-at-a-time ECB decryption (Harder)

这一题要求我们破解一个密文。加密的实现是:

AES-128-ECB(random-string || your-string || unknown-string, random-key)

这里unknown-string由题目以base64的形式给出(用于避免剧透),random-stringrandom-key则是需要由代码随机生成。在破解的过程中,不需要访问到这个key,到最后也不会访问(获得)到这个随机的密钥。

这一题是上一题的加强版本,但只要知道了ECB模式的原理,解决本题不算困难。

首先我们依然先实现辅助加密的函数:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
let unknown_prefix = random_bytes(rand::random::<u8>().into());
let unknown_key = random_bytes(16);

let do_encrypt_inner = |buf: &[u8]| -> Vec<u8> {
    return aes_128_ecb_encrypt(&unknown_key, &buf);
};
let do_encrypt = |prefix: &[u8]| -> Vec<u8> {
    return do_encrypt_inner(
        &[unknown_prefix.as_slice(), prefix, unknown_string.as_slice()].concat(),
    );
};

我们意识到,在这一问当中,主要问题在于如何知道未知前缀的长度。而考虑到ECB模式的特点,考虑构造两个完全一样的block——

| --- Block 0 --- | --- Block 1 --- | --- Block 2 --- | --- ...
| ? ? ? ? ? ? ? A | A A A A A A A A | A A A A A A A ? | ? ? ...
| unknown ---->|   <Your String> |   <Your String> |<-- Unknown 

注意到我们会得到两个加密后相同的块(在概率意义下)当且仅当我们的内容恰好使用了两个完整的块,因此我们可以构造形如

$$\\underbrace{\\texttt{AA}\\ldots\texttt{A}}\_{x\\ \\textrm{\\texttt{A}s}}\\underbrace{\\texttt{BB}\\ldots\texttt{B}}\_{2\\ \\textrm{blocks of \\texttt{B}s}}$$

通过枚举x,同时观察密文,我们可以知道unknown-prefix的长度,进而通过我们攻击的文本,将其填充到块大小的整数倍。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
let mut our_block = 0;
let mut prefix_in_block = 0;

for i in 1..block_size {
    let new_buffer = do_encrypt(&vec!['A' as u8; i]);
    let new_random = random_bytes(block_size);
    let new_buffer2 =
        do_encrypt(&[&vec!['A' as u8; i], &new_random[..], &new_random[..]].concat());
    let mut solved = false;

    for j in 0..cipher_size / block_size {
        if cipher[0..(j + 1) * block_size] != new_buffer[0..(j + 1) * block_size] {
            our_block = j;
            break;
        }
    }

    for j in 1..cipher_size / block_size {
        if new_buffer2[(j - 1) * block_size..j * block_size]
            == new_buffer2[j * block_size..(j + 1) * block_size]
        {
            solved = true;
            break;
        }
    }

    if solved {
        prefix_in_block = block_size - i;
        break;
    }
}

random_prefix_len = our_block * block_size + prefix_in_block;

之后的问题就十分简单了,只需要简单套用上一题的代码即可。

2.16 CBC bitflipping attacks

这一题是要求实现两个函数——

AES-128-CBC-ENC(prefix-string || escape(your-string) || suffix-string, random-key)
CONTAINS(AES-128-CBC-DEC(some-buffer, random-key), ";admin-true;")

来模拟一个鉴权的实现。我们注意到题目中的提示——

You’re relying on the fact that in CBC mode, a 1-bit error in a ciphertext block:

  • Completely scrambles the block the error occurs in
  • Produces the identical 1-bit error(/edit) in the next ciphertext block.

即,当CBC模式中的某一块的某一位被翻转时——

  • 它所在的块会被破坏
  • 在它的下一块的相同位置也会产生翻转

基于此,我们只需要随便往其中填入足够长的内容,定位到我们的明文对应的密文,将其部分位翻转,使得我们解密之后的文本包含我们设想的内容。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
fn main() {
    let unknown_key = &random_bytes(16);

    let encrypt = |x: &[u8]| -> Vec<u8> {
        return aes_128_cbc_encrypt(unknown_key, x, &random_bytes(16));
    };
    let decrypt = |x: &[u8]| -> Vec<u8> {
        return aes_128_cbc_decrypt(unknown_key, &x[16..], &x[..16]).unwrap();
    };
    let check = |x: &[u8]| -> bool {
        return twoway::find_bytes(&decrypt(x), ";admin=true;".as_bytes()).is_some();
    };

    let do_encrypt = |x: &str| -> Vec<u8> {
        return encrypt(
            &[
                "comment1=cooking%20MCs;userdata=".as_bytes(),
                x.as_bytes(),
                ";comment2=%20like%20a%20pound%20of%20bacon".as_bytes(),
            ]
            .concat(),
        );
    };

    // comment1=cooking%20MCs;userdata=00000000000000000admin0true;comment2=%20like%20a%20pound%20of%20bacon
    // ........--------........--------........--------........--------........--------........-----

    let mut val = do_encrypt("00000000000000000admin0true");
    val[16 + 8 * 2] ^= ('0' as u8) ^ (';' as u8);
    val[16 + 8 * 2 + 6] ^= ('0' as u8) ^ ('=' as u8);

    assert_eq!(check(&val), true);
}

永远不要加密自己不受控制的内容,哪怕只有一部分也不行。