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-string
与random-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);
}
|
永远不要加密自己不受控制的内容,哪怕只有一部分也不行。