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本身而言,计算每次得到的明文的数值就是用的统计学的方法,根据频率将明文的每个字母加入运算得到最终的数值。
所以本题的代码没有特别的地方,我们直接看全部代码及测试结果: