r1ngs's blog

HCTF-2018-crypto和一些思考

2018-11-12

又是一场产出为0的比赛

xor game

题解

题目代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.strxor import strxor
import base64
import random


def enc(data, key):
key = (key * (len(data) / len(key) + 1))[:len(data)]
return strxor(data, key)


poem = open('poem.txt', 'r').read()
flag = "hctf{xxxxxxxxxxx}"

with open('cipher.txt', 'w') as f:
f.write(base64.b64encode(enc(poem, flag[5:-1])))
f.close()

之前在DCTF上遇到过类似的题目,writeup

但是这道题至少可以依据前四个字节都是0和flag格式为DCTF{…}来有依据猜,但是这道题猜都不能猜

在google上搜索ctf xor repeate key ,我发现了这篇文章Repeated XOR - 70

文章揭露了可以使用频度分析的方式来达到攻击从而推测出明文的结果,博主还非常良心的贴出了完整的脚本

由于整篇poem比较长,一共有1398个字节,所以我试着跑了一下

可以看到,密钥长度为21的可能性比较大,调成21,再跑一下poem

可以看到虽然大部分是乱码,但是已经零零散散有一些单词了,可惜当时做到这里的时候就以为自己思路有问题,所以就没有继续往下面做了,如果接着往下面做,将密钥打印出来:

6o7i6_i+te7es1ing!@#

第3位是一个不可见字符,flag里面肯定不可能是不可见的字符,所以我们暂时令他为1

然后我们跑一下下面的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.strxor import strxor
import base64
from string import *


def enc(data, key):
key = (key * (len(data) / len(key) + 1))[:len(data)]
return strxor(data, key)

poem = open('cipher', 'r').read()
flag = '6o71i6_i+te7es1ing!@#'
for i in letters + digits +'_':
l = list(flag)
l[0] = i
print '+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++'
print i
print enc(base64.b64decode(poem), ''.join(l))
print '-----------------------------------------------------------------------'

可以看到,最后一行那个单词明显应该是autumn

那么对应的字母是x,然后我们再用这个密钥xo71i6_i+te7es1ing!@#,通过查看poem里面残缺了一个字母的单词,找到对应的位置,依此去跑就能得到flag

看了别人的wp,我发现有人用了xortool这个工具,github地址

这里我直接用xortool,将密文转为hex,指定空格为最常见字符: python xortool -x -c 20 c.txt

我实际测了一下,这个工具和那个作者的脚本效果差不多

原理

我觉得还是要研究一下原理,那个作者的文章是全英文的,不太容易看懂,我做一个补充

依据原文的两个加密的例子:

1
2
3
4
84, 72, 73, 83, 32, 73, 83, 32, 65, 32, 77, 69, 83, 83, 65, 71, 69
89, 79, 85, 89, 79, 85, 89, 79, 85, 89, 79, 85, 89, 79, 85, 89, 79
xor --------------------------------------------------------------
13, 7, 28, 10,111, 28, 10,111, 20,121, 2, 16, 10, 28, 20, 30, 10

首先之所以有28, 10,111的重复,是因为明文里面有一个is的重复,这两个重复间隔的位数是0(3的倍数)

1
2
3
4
84, 72, 73, 83, 32, 77, 69, 83, 83, 65, 71, 69, 32, 73, 83, 32, 78, 79, 84
89, 79, 85, 89, 79, 85, 89, 79, 85, 89, 79, 85, 89, 79, 85, 89, 79, 85, 89
xor ----------------------------------------------------------------------
13, 7, 28, 10,111, 24, 28, 28, 6, 24, 8, 16,121, 6, 6,121, 1, 26, 13

如果is隔了8个字符,不是3的倍数了,那么这个28, 10,111的重复也就不存在

也就是说,通过长度为3的key,使得明文进行了分组,而至少有些时候,重复的明文会因此而偏移(情况一),我们通过一个粗略的算法(代码里的shift函数), 使密文经过len(key)偏移一次,然后与之前的密文对比,有多少bytes相同,如果相同的次数比较多,就说明明文加密后很可能进行了这么长的偏移,而这么长的偏移就是key的长度造成的,所以可以大致推测出key的长度

一旦我们得到了key的长度,那么我们可以说,明文其实可以想象成分成了很多行进行加密,然后再将他们加密的结果拼接起来,那么对于每一列,都使用的是同一个key的某一位进行加密,那么对于加密的结果应该符合频率分布规律, 出现最高的频率应该是空格(这也就是为什么键盘的空格键在最下方中间而且那么长的原因了= =)被加密的密文,因此将密文和空格异或就能推测出这位key了。从0到len(key)列做重复的操作就能粗略的得到一个key,也就可以用来加密明文了


xor?rsa

首先我拿到这道题的时候以为这是出题人自己想出来的一种攻击手法,然后用出了自己学过的所有数论知识和异或的公式尝试去化简和推导,结果整整2天没有一点进展

当时我google和百度了好久,就是没有找到这种攻击方式,后来请教了别队的师傅,他说这个攻击手法在ctf-wiki上有,攻击手法叫Coppersmith’s short-pad attack

攻击条件

目前在大部分消息加密之前都会进行 padding,但是如果 padding 的长度过短,也有可能被很容易地攻击。

这里所谓 padding 过短,其实就是对应的多项式的根会过小。

在百度上找到了一个现成的轮子,github地址

这个轮子是sage代码,在命令行里面用sage ***.sage直接运行,也可以在线运行

直接抄过来跑的话会报错,Eur3kA队的wp是对CoppersmithShortPadAttack函数以及传入eps的值做了一点改动,不是很懂怎么改的(太菜了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def CoppersmithShortPadAttack(e,n,C1,C2,eps=1/30):
import binascii
P.<x,y> = PolynomialRing(ZZ)
ZmodN = Zmod(n)
g1 = x^e - C1
g2 = (x+y)^e - C2
res = g1.resultant(g2)
P.<y> = PolynomialRing(ZmodN)
rres = 0
for i in range(len(res.coefficients())):
rres += res.coefficients()[i]*(y^(res.exponents()[i][1]))

diff = rres.small_roots(epsilon=eps)
recoveredM1 = franklinReiter(n,e,diff[0],C1,C2)
print(diff)
print(recoveredM1)
print(recoveredM1 + diff[0])

总结

首先第一题,我觉得当时如果仔细看了明文,能够注意到已经还原了部分单词的话,就能坚持做下去的,虽然同队的师傅后来也做出了这道题,影响不是很大,但是对于自己来说,还是欠了一点坚持

对于第二题,这种不能用简单的数论解决的题目应该都是一种单独的攻击面,后续的学习可能要参照ctf-wiki了= =

参考文章

[1] HCTF 2018 Writeup — Whitzard

[2] HCTF2018 Writeup — Eur3kA

Tags: CTF

1000000