Cryptopals Set 2 Challenge 12

2022-07-10

cryptopals / 加密 / 解题报告

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

2.12 Byte-at-a-time ECB decryption (Simple)

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

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

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

题目已经给出一个相对完整的步骤，我们只需要实现它即可。

在最开始，题目要求我们做两步准备工作，以假装我们不知道这个加密的内幕。再此，为了后续的实现方便，我将上述加密过程包装成了一个单独的函数。

1
2
3
4
5
6
7
8


let unknown_string = base64_to_bytes(String::from_utf8_lossy(&buf).to_string());
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(&[prefix, unknown_string.as_slice()].concat());
};

将your-string设置成若干长度一样的字符，观察密文长度，用以推断出加密的块大小。
使用2-11中的代码。判断加密过程使用的是ECB模式。

再之后，构造一个比块大小恰好小1的字符串，喂给do_encrypt。

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

上述代码以块大小为8字节为例。注意到your-string的长度恰为块大小减1的时候，未知字符串的第一个字符放进了第一个block，由于使用ECB模式加密的特性，我们只需要枚举不多于256个字符串即可知道原文第一个字符。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


let probe_first_block_enc = do_encrypt(&last_block[i..]);

for ch in 0..256 {
    let probe_block = do_encrypt(&[&vec!['A' as u8; block_size - 1], &[ch as u8]].concat());

    if probe_block[0..block_size]
        == probe_first_block_enc[0..block_size]
    {
        println!(
            "First Byte: {}",
            char::from_u32(ch as u32).unwrap()
        );
        break;
    }
}

这样我们就可以知道未知字符串的第一个字符。在此基础上，如果我们的your-string的长度比块大小小2的话，我们可以得到：

| --- Block 0 --- | --- Block 1 --- | --- ...
| A A A A A A ! ? | ? ? ? ? ? ? ? ? | ? ? ? ...
| <your  str>|<------ Unknown String ----------

考虑到明文的第一个字符已知，我们仍然只需要再枚举一个字符即可。重复这个操作，就可以得到明文的第一块的内容。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


let mut block = Vec::new();

for i in 1..=block_size {
    let probe_first_block_enc = do_encrypt(&vec!['A' as u8; block_size - i]);

    for ch in 0..128 {
        let probe_block = do_encrypt(&vec!['A' as u8; block_size - i], &block, &[ch as u8]].concat());

        if probe_block[0..block_size]
            == probe_first_block_enc[0..block_size]
        {
            println!(
                "Byte {}: {}",
                i,
                char::from_u32(ch as u32).unwrap()
            );
            block.push(ch as u8);
            break;
        }
    }
}

题目给出的提示到此为止，但给出的文本显然不止一块大小，那么如何获得整个文本呢？不妨假设我们想知道第二块的内容，那么加入我们将your-string设成我们已知的第一块的内容最后若干字节的话……

| --- Block 0 --- | --- Block 1 --- | --- Block 2 --- | ...
| ! ! ! ! ! ! ! # | @ @ @ @ @ @ @ ? | ? ? ? ? ? ? ? ? | ...
|  Your Stirng |? |Cracked String|<----- Unknown Sting ----

此时如果我们再次枚举#处的字符，即可得到unknown-string当中第二块的第一个字符，以此类推，我们可以得到unknown-string第二块的所有内容……以及第三块、第四块……的内容，至此，我们已经解出了整个unknown-string的内容。

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

2.12 Byte-at-a-time ECB decryption (Simple)

Contents