cryptopals解密之旅3-1
0x00前言
本系列文章将带来cryptocals 这套密码学挑战的write-up.不同于通过上课或者看书的方式学习密码学，这些题目来自于现在生活中一些软件系统和密码构造中的缺陷。
本系列每一个题的wp基本是采用如下结构：题目解释、相关知识点讲解、代码实现及解释，运行测试。代码均采用python3实现,代码实现部分是参考国外大佬ricpacca的，结合自己的理解及成文需要进行部分修改。
第三套一共有八关。
这8个题目是关于分组密码学的，难度中等，包括针对CBC模式的典型攻击，针对RNG的cloning攻击等等。
接下来一一解决。
0x01
17题
这是针对分组密码学最著名的攻击手段
要求实现两个功能，一个功能从给出的10个字符串中随机选择一个，随机生成AES**，并进行填充，使用CBC模式进行加密。在需要时可以提供密文和IV
第二个功能则是解密密文，检查明文的填充是否有效，并以此返回true或者false
我们的目标是能够解密密文，这里解密依靠的是侧信道泄露，泄露的信息是判断解密后的明文的填充是否有效。
关于Padding Oracle Attack的介绍文章实在太多了，国内打CTF几年前就玩烂了，为了保持本系列的完整性，这里还是稍微展开介绍。如果有不清楚的地方，可以参考这篇文章，国内外很多文章都是参考它的:https://blog.gdssecurity.com/labs/2010/9/14/automated-padding-oracle-attacks-with-padbuster.html
关于这种攻击手段，有两块前置知识。一块是关于分组密码的填充，填充标准常用有的pkcs#5,pkcs#7，这在之前的文章中我们已经介绍过了。要注意的一点就是，在本次的攻击手段中就是通过判断得到的明文的填充是否符合标准，从而判断其是否有可能为正确的明文。
另一块就是CBC的加解密模式，我们之前也提过，不过这次的关注点不同。这里再次给出下图
这里注意到，以解密过程为例。
密文cipher不是解密后立刻得到明文的。
而是密文首先进行一系列处理，如图中的Block Cipher Decryption，我们将处理后的值称为intermediary value中间值，然后中间值与我们输入的iv进行异或操作，得到的即为明文。在解密下一分组时，第一个分组的密文则作为下一分组解密时的IV来使用，在第二个分组处理得到中间值后，与其异或得到第二个分组的明文，以此类推。
接下来我们举个例子。
假设已经知道中间值：0x39 0x73 0x23 0x22 0x07 0x6a 0x26 0x3d
原始的IV:0x6d 0x36 0x70 0x76 0x03 0x6e 0x22 0x39
两者异或后就可以得到明文：T E S T 0x04 0x04 0x04 0x04
但对于攻击者而言，攻击者只有正确的IV，但不知道中间值和正确解密得到的明文的。攻击者要做的就是，对IV进行暴力测试，与未知的中间值异或后，得到明文，如果明文的是按照标准填充的，则说明这一轮测试的Iv是有效的。
攻击者接下来会暴力测试IV：
从最后一位开始
第一轮的IV:0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
与中间值异或得到明文
0x39 0x73 0x23 0x22 0x07 0x6a 0x26 0x3d
可是最后一位Padding的字节是0x3d，明显说明这是不合法的padding，继续推理，可知这一轮的IV是不合法的，于是继续测试，直到某一轮：
IV:0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x3c
与中间值异或得到明文:
0x39 0x73 0x23 0x22 0x07 0x6a 0x26 0x01
程序校验最后一位，发现是0x01，即可通过校验.
有公式：
Middle[8]^暴力测试的iv[8] = 0x01
所以middle[8]=暴力测试的iv[8] ^0x01
又因为Middle[8]^原始的iv[8] = 真正的plain[8]
所以真正的plain[8]=暴力测试的iv[8] 0x01原始的iv[8]
在我们的例子中，真正的plain[8]=0x010x3c0x39=0x04（和我们正常解密得到的明文分组第8字节相符)）
还可以得到middle[8]=原始的iv[8] 真正的plain[8]=0x390x04=0x3d,这个值在下一轮会用到
接下来我们继续暴力测试IV,以期得到plain[7]
此时暴力测试iv时，需要注意，我们这次希望解密得到的明文末尾两字节是0x02
先看第8个字节
由于：iv[8]^middle[8]=0x02
所以iv[8]=middle[8]0x02=0x3d0x02=0x3f
然后固定iv[8]，去暴力测试Iv[7]，直到得到的明文分组的最后两字节是0x02 0x02即可
暴力测试到这时：
Iv：0x00 0x00 0x00 0x00 0x00 0x00 0x24 0x3f
Middle：
0x39 0x73 0x23 0x22 0x07 0x6a 0x26 0x3d
明文：0x39 0x73 0x23 0x22 0x07 0x6a 0x02 0x02
于是可以得到plain[7]=暴力测试的iv[7] 0x02原始的iv[7]=0x020x220x24=0x04(和我们正常解密得到的明文分组第7字节相符)
依次类推，即可解得明文
有了思路，代码就不难写了
先是按照题目要求，定义两个函数，分别用于加密和解密以及校验padding是否合法，这些功能在以前的题目题目中代码实现过，可以直接饮用
暴力测试IV,使得得到的IV能够有效解密密文，得到的明文符合填充标准
通过上面函数生成的IV，不断循环测试，一个个分组分别解密，得到明文
完整代码及测试结果如下
打印的结果是随机选择的密文解密后的明文
0x02
18题
要求我们实现CTR模式。并针对给出的例子进行测试。
CTR模式是常见分组密码工作模式中的一种，其全称是CounTeR模式（计数器模式）。CTR模式是一种将逐次累加的计数器进行加密来生成**流的流密码
CTR模式中，每个分组对应一个逐次累加的计数器，并通过对计数器进行加密来生成**流。也就是说，最终的密文分组是通过将计数器加密得到的比特序列，与明文分组进行xor而得到的。
加密图示如下
解密图示如下
从解密图示中我们可以看到，解密时只需要生成相同的**流，再异或就可以得到明文了。所以我们在写代码时，写一个函数就可以了
这里需要注意计数器的生成方法
每次加密时都会生成一个不同的值（nonce）来作为计数器的初始值
以分组长度为16字节为例，计数器的初值可能为：
前8个字节为nonce，这个值每次加密时都不同。后8字节为分组序号，这个部分会逐次累加。加密过程中，计数器的值可能会如下变化
这样就可以保证计数器的值每次都是不同的，因为对其加密得到的**流也是不同的。我们就是用分组密码来模拟生成的比特序列。
代码实现很简单，关键的函数就一个，用于实现AES-CTR模式加解密
完整代码及测试如下
在main中首先是对给出的密文进行解密。然后又任意给了一个例子，对其加密、解密进行测试。
从结果可以看到，成功实现了AES-CTR模式。
0x03
第19题
题目要求我们先对给出的40行经过base64编码的明文进行AES-CTR加密。这是为了模拟在某些情况下，在对大量的密文进行加密时，nonce并不会每次都是随机变化的，可能在加密时使用的是相同的**流。
而攻击者在解密时，会假设大量的密文都是使用相同的**流与明文异或得到。这样，我们就可以将可能的**流的每个字节分别通过循环，与密文异或，通过计算得到的明文，根据其分值，得到最可能的**流。然后在根据得到的**流进行解密即可。
这种方法可以得到大部分正确的明文，不过还是有些明文会解密错误。原因后续在分析代码时再解释。
总之通过这道题目我们可以学会：在大量的密文使用相同的nonce加密时，如何对其攻击得到明文。
写一个通过计算明文中的字母频率累加值来得到**流的函数
以及攻击的函数
红色框起来的部分，就是我之前提到为什么会有少部分明文解密失败的原因。
这里在调用获取**流的函数get_keystream_byte时，传入的column作为data参数，而column是从每行密文中综合得到的，而每行密文长度不一，所以在计算时column作为data参数并不十分精确。
这一点我们待会儿测试时可以验证。
在main中打印使用这种攻击手段**的明文和原明文
全部代码及测试如下
上一行是攻击得到的明文，下一行是原始明文，如我们分析的一样，两者是有些差别的，不过差别不大，基本可以辨认。
0x04
第20题
题目给出一个文件，文件里还是base64编码过的明文，要求我们对其进行AES-CTR加密，之后对其模拟攻击，进行解密。这里所谓的”statistically”，指的是利用统计学的方法，其实我们在上一题中就是用这种办法攻击的。”统计学的方法“体现在两个方面，一方面是在取密文传入get_keystream_byte时，所有的密文都参与了；一方面是在get_keystream_byte本身而言，计算每次得到的明文的数值就是用的统计学的方法，根据频率将明文的每个字母加入运算得到最终的数值。
所以本题的代码没有特别的地方，我们直接看全部代码及测试结果：