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,到最后也不会访问(获得)到这个随机的密钥。
题目已经给出一个相对完整的步骤,我们只需要实现它即可。
在最开始,题目要求我们做两步准备工作,以假装我们不知道这个加密的内幕。再此,为了后续的实现方便,我将上述加密过程包装成了一个单独的函数。
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个字符串即可知道原文第一个字符。
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 ----------
考虑到明文的第一个字符已知,我们仍然只需要再枚举一个字符即可。重复这个操作,就可以得到明文的第一块的内容。
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
的内容。
答案剧透
Decrypted text:
Rollin' in my 5.0
With my rag-top down so my hair can blow
The girlies on standby waving just to say hi
Did you stop? No, I just drove by
永远不要加密自己不受控制的内容,哪怕只有一部分也不行。