Cryptopals Set 2 Challenge 12

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());
};
  1. your-string设置成若干长度一样的字符,观察密文长度,用以推断出加密的块大小。

  2. 使用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的内容。

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