writeup
cryptopals解密之旅 (二)
2020-06-03 10:56

前言

cryptopals解密之旅 (一)

本系列文章将带来cryptocals 这套密码学挑战的write-up.不同于通过上课或者看书的方式学习密码学,这些题目来自于现在生活中一些软件系统和密码构造中的缺陷。

本系列每一个题的wp基本是采用如下结构:题目解释、相关知识点讲解、代码实现及解释,运行测试。代码均采用python3实现,代码实现部分是参考国外大佬ricpacca的,结合自己的理解及成文需要进行部分修改。

第一套一共有八关。

0x05 第5关

cryptopals解密之旅1-2216.png

给出了明文和密钥,要求实现repeating-key XOR,比如密钥是ICE,则明文第一个字符与I异或,第二个字符与C异或,第三个字符与E异或,第四个字符与I异或,继续下去。。。

通过i来控制ICE中由哪一个字符进行异或,在i=len(key),也就是i在循环中达到3时,将其置0,继续从I开始异或,否则自增,按照I、C、E顺序异或

cryptopals解密之旅1-2386.png

完整代码及执行结果如下

cryptopals解密之旅1-2400.png

0x06 第6关

cryptopals解密之旅1-2414.png

给出了一个文件,该文件首先经过repeating-key XOR,然后base64编码得到

要求我们给出密钥和明文。

并且给出了提示:

1.     确定KEYSIZE,也就是密钥的长度,比如说可以尝试从2到40的值

2.     实现一个函数,该函数功能是计算两个字符串的汉明距

3.     每次尝试KEYSIZE时,分别计算两个长度为KEYSIZE的字节的串,计算其汉明距

4.     选取2-3个最小汉明距离的KEYSIZE(如果选取了正确的密钥长度,两两块之间的汉明距离的值应该趋于小),在确定时可以采用一些技巧,如选取4个块,两两组合计算汉明距,再除以组合数,再除以key_size,进行规格化。

5.     知道KEYSIZE大小后,将密文按照KEYSIZE大小分到每个块里面

6.     然后可以重新组合,将每个块的第一个字节取出来重新组成一个块,将每个块的第二个字节取出来重新组成第二个块。。

7.     对于新组成的块而言,此时解密就相当于是单字符的异或,我们之前已经学过怎么处理这种情况了

8.     将每个单字符异或的key组合起来就是我们要求的repeating-key XOR的key了,将明文拼接起来就是所求的完整明文了

代码实现

汉明距是一个概念,它表示两个(相同长度)字对应位不同的数量,我们以d(x,y)表示两个字x,y之间的汉明距离。对两个字符串进行异或运算,并统计结果为1的个数,那么这个数就是汉明距离比如011,110,其第一位和第三位不同,故汉明距为2;而在代码中我们是通过异或的方式计算汉明距:将其异或,然后看有多个位是1.还是上面的例子,011和110异或得到101,结果中有两个1,所以其汉明距为2

cryptopals解密之旅1-21092.png

暴力测试key_size,根据题目的建议,取出根据key_size大小划分的4组

然后使用迭代器itertools的combinations来组合。这个函数很简单,看个简单的例子就清楚了

111.jpg

在代码中计算任两组的汉明距,然后累加,这里一共是6组数据,所以将累加结果除以6,得到平均的汉明距,接着将其除以key_size进行规范化,得到normaliezd_distance,将其存到key_size对应的数组里,便于与后面的数据进行比较。

有最小normalized_distance的key_size,最有可能就是真正的key_size。但是仅是可能性大而已,我们选中最有可能的三个key_size(normalized_distance最小的三个所对应的key_size)

cryptopals解密之旅1-21560.png

然后分别进行测试,安装key_size大小将密文分块,然后将每个块的第一个字节组成新的第一个块,将每个块的第二个字节组成新的第二个块。。。然后按照单字节xor的方式来分别处理每一块,将得到的明文拼接起来。这样子,一共会有三个结果,然后根据之前实验,通过字符频率相加计算分数的方法,分数最大的则是最有可能是正确明文。

cryptopals解密之旅1-21720.png

在main函数中我们首先是测试了我们计算汉明距的函数是否能正确执行

接着就是读入密文文件,先进行base64解密,然后进行前面介绍的流程,最后返回结果

cryptopals解密之旅1-21798.png

完整代码及运行结果如下

cryptopals解密之旅1-21813.png

0x07 第7关

cryptopals解密之旅1-21824.png

给出了密文,该密文是由明文经AES-128 ECB模式加密后得到的内容再经过base64编码而成。题目给了密钥,并提示大小写敏感,密钥长度为16字节

要求我们解密出明文

这里涉及两个知识点,一个是AES;一个是ECB,AES属于分组密码,密码密码典型的操作模式包括ECB,CBC,CFB,OFB,CTR,下文会介绍ECB,其他的操作模式在后面的题目中碰到了再介绍。

AES是高级加密标准(Advanced Encryption Standard: AES),是用以取代des的,在美国国家标准技术研究所(National Institute of Standards and Technology: NIST)在全球进行征集的时候,AES得到了全世界很多密码工作者的响应,先后有很多人提交了自己设计的算法。最终有5个候选算法进入最后一轮:Rijndael,Serpent,Twofish,RC6和MARS。最终经过安全性分析、软硬件性能评估等严格的步骤,Rijndael算法获胜。

Rijndael是一个分组密码算法族,其分组长度包括128比特、160比特、192比特、224比特、256比特,密钥长度也包括这五种长度,但是最终AES只选取了分组长度为128比特,密钥长度为128比特、192比特和256比特的三个版本。本次涉及的是128比特的。

AES加密算法涉及4种操作:字节替代(SubBytes)、行移位(ShiftRows)、列混淆(MixColumns)和轮密钥加(AddRoundKey)

cryptopals解密之旅1-22480.png

AES加解密的流程,从图中可以看出:1)解密算法的每一步分别对应加密算法的逆操作,2)加解密所有操作的顺序正好是相反的。正是由于这几点(再加上加密算法与解密算法每步的操作互逆)保证了算法的正确性。加解密中每轮的密钥分别由种子密钥经过密钥扩展算法得到。算法中16字节的明文、密文和轮子密钥都以一个4x4的矩阵表示。

1)字节代替的主要功能是通过S盒完成一个字节到另外一个字节的映射。S盒用于提供密码算法的混淆性,S盒在分组密码算法中,是唯一的非线性结构,其S盒的指标的好坏直接决定了密码算法的好坏。

2)行移位:是一个4x4的矩阵内部字节之间的置换,用于提供算法的扩散性

3)列混淆:利用GF(28)域上算术特性的一个代替,同样用于提供算法的扩散性

4)轮密钥加:依据的原理是“任何数和自身的异或结果为0”。加密过程中,每轮的输入与轮子密钥异或一次;因此,解密时再异或上该轮的轮子密钥即可恢复

5)密钥扩展算法比较复杂,可以参考:http://www.cs.utsa.edu/~wagner/laws/AESkeys.html

ECB模式:

ECB是最简单的加密模式。需要加密的消息按照块密码的块大小被分为数个块,并对每个块进行独立加密。

cryptopals解密之旅1-23068.png

其缺点在于同样的明文块会被加密成相同的密文块;因此,它不能很好的隐藏数据模式。在某些场合,这种方法不能提供严格的数据保密性,因此并不推荐用于密码协议中

题目的代码实现:这里我们直接使用crypto库的函数

查阅相关文档可知其具体用法:https://pycryptodome.readthedocs.io/en/latest/src/cipher/classic.html#ecb-mode

cryptopals解密之旅1-23271.png

AES.new(key, AES.MODE_ECB)可以实例化一个新的AES-ECB密文对象,然后调用decrypt方法即可解密

cryptopals解密之旅1-23338.png

解释一下最后一句的注释:

我们可以直接返回解密的结果,如第三行的代码所示;但是为了通用性(因为在后面的解答中还会这种这里的代码),使用我们在第二套第9关编写的pkcs7_unpad方法去除填充

在main函数中就是读入密文,先将其base64解码,然后传到aes_ecb_decrypt函数进行解密

完整代码及执行结果如下

cryptopals解密之旅1-23502.png

0x08 第8关

cryptopals解密之旅1-23515.png

题目给了一个文件,是16进制编码的一些字符串,其中有一个字符串是AES-ECB加密过的,要求我们找出来。

解题最关键的一步就是要知道:由于ECB模式的特点,同样的明文块会被加密成相同的密文块。所以我们可以通过查找加密字符串中是否有相同的密文块,来判断是否为ECB模式。如果都有相同的密文块(一般是不会出现这种情况的,因为如果有这种模式,那是非常危险的,这也是为什么ECB非常不被推荐使用的原因),则相同密文块最多的那个字符串是ECB模式加密得到的。

计算重复块的次数

cryptopals解密之旅1-23754.png

计算每一串密文的重复块数, 返回有最多重复块的密文,这最可能是AES-ECB加密得到的

cryptopals解密之旅1-23800.png

完整代码及执行结果如下

cryptopals解密之旅1-23814.png

参考:

1.     https://cryptopals.com/sets/1

2.     https://github.com/ricpacca/cryptopals

上一篇:cryptopals解密之旅 (一)
下一篇:今天你pwn了吗(三)
版权所有 合天智汇信息技术有限公司 2013-2021 湘ICP备14001562号-6
Copyright © 2013-2020 Heetian Corporation, All rights reserved
4006-123-731