Cryptopals Set 1

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

1. 热身

热身的练习相对比较简单,但为后续的练习提供了一些相对好用的代码模板。

1.3 Single-byte XOR cipher

这一个问题要求我们破译一个使用1字节异或加密的字符串。

1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736

需要注意题目中提到明文是一段英文句子,那么其理应:

  • 字母的分布符合英文字符的统计规律。
  • 不包含字母、数字、标点符号、空白字符之外的字符。

在实际解密中,感觉第二条更加重要一些,因为有可能解密解密出有一堆a或者e但其它全是乱码的句子。

维基百科提供了一个英文句子中字符出现的频率,我们只需要自己也统计一下解码之后的字符串各个字符出现的频率,然后做一个向量点乘,排除明显不符合的(包含非法字符的)答案之后即可。

这一题中,得分最高的句子不包含任何非法字符,但下一题就未必了。

cargo run --bin 1_3_single_byte_xor_cipher
    Finished dev [unoptimized + debuginfo] target(s) in 0.01s
     Running `target/debug/1_3_single_byte_xor_cipher`
Ok("Cooking MC's like a pound of bacon") (score 3.826559)

1.4 Detect single-character XOR

这题在第三题的基础上加强,给出了一堆字符串,其中一个是用异或加密过的。需要注意的是这一题给出的字符串过多,如果不过滤掉包含ASCII中,不是字母、数字等字符的字符串,会出现得分最高的句子是乱码的情况。

cargo run --bin 1_4_detect_single_byte_xor_cipher
   Compiling cryptopals v0.1.0 (/home/matsu/my_solutions/misc/cryptopals)
    Finished dev [unoptimized + debuginfo] target(s) in 0.19s
     Running `target/debug/1_4_detect_single_byte_xor_cipher`
#35 Ok("iu`'ern.&nZeM,MjT\u{b}:FD~i5+OyEmL") (score 2.2037334)
#149 Ok("K2\"YPe(JOG5\u{1c}]/o)_B\"FsXABnPgu&\u{1b}") (score 1.5408334)
#165 Ok("Hs>u1Y/orf:AP|m\[email protected]?v:9\n=9yNct<o") (score 1.9225669)
#170 Ok("Now that the party is jumping\n") (score 4.449133)
#195 Ok("Ae$JA}6LgEkB6Qi{GQ|a!w-Wr2=OUH") (score 1.8434335)
#225 Ok("U3YOh,\\0sUHXcQ.?3an$$\\[email protected]") (score 1.6776335)
#230 Ok("mjOia}tti:\\\"x7{N(0`H[ra]p$bo_^") (score 2.2667336)
#289 Ok("Ey0DGvdt|eg:XtgmB}{_7mh\u{12}tXNTeg") (score 2.5576)
#295 Ok("^!IwIl>mvAgs$0%[email protected];wNAi8V") (score 1.943767)

在这个基础上保留得分最高的字符串即是结果。

1.6 Break repeating-key XOR

本题要求我们解密一个用异或加密的字符串,而密钥是一个有一定长度的字符串。

题目里面提示我们:

  • 枚举可能的密钥长度,取密文的前若干块,计算这些块之间的编辑距离。编辑距离最小的可能就是答案。
  • 对于枚举出的密钥长度,按密文(也是明文)下标取模,依次暴力枚举密钥的每一位。

在做这一题的时候,最开始比较偷懒,只取了前两块来计算,但最后发现怎么解密都不对。这时候意识到是样本太小,统计规律不足以显示。于是修改代码比较五倍密钥长度的字符串。

为何可以通过这样的统计来得知密钥长度?

异或加密没有改变明文每一位的相对关系,由于我们知道明文是一段英文文本,那么其明文的每一位必定是在一段很小的区间內,即在明文二进制表示中有很多位都相同,而异或加密没有打破这一层统计学关系,因此可以被如此攻击。

在真实世界中,如果不带消息校验码(MAC)的话,ECB、CFB等加密模式也可以被这样攻击,因为其明文的第i位在加密后一定是在密文的第i位上,如果不校验消息则可能被探测到通信协议相关特征。

更新:上述表述并不正确,在AES加密过程中,明文有参与到扩散这一步骤当中。但需要注意的是,由于CBC加密IV的参与,对IV对应位的修改会反映到明文对应位上。

本题密钥长达29字节。

...
Key = [84, 101, 114, 109, 105, 110, 97, 116, 111, 114, 32, 88, 58, 32, 66, 114, 105, 110, 103, 32, 116, 104, 101, 32, 110, 111, 105, 115, 101]
Ok("I'm back and I'm ringin' the bell \nA rockin' on the mike while the fly girls yell 
...

1.8 Detect AES in ECB mode

这题延续上一题的思路,我们知道ECB模式只是简单地将明文异或一个字符串,同异或加密没有本质区别。

我们也是简单统计各块之间的相关性即可,需要注意也是要多统计几块,由于密文不长,我直接统计了两两之间的编辑距离。最后得出的编辑距离显著小于其它输入。

Possible ECB cipher #132: distance=239.8
d880619740a8a19b7840a8a31c810a3d
08649af70dc06f4fd5d2d69c744cd283
e2dd052f6b641dbf9d11b0348542bb57
08649af70dc06f4fd5d2d69c744cd283
9475c9dfdbc1d46597949d9c7e82bf5a
08649af70dc06f4fd5d2d69c744cd283
97a93eab8d6aecd566489154789a6b03
08649af70dc06f4fd5d2d69c744cd283
d403180c98c8f6db1f2a3f9c4040deb0
ab51b29933f2c123c58386b06fba186a

可以注意到肉眼可见的统计特征。