SUCTF-Crypto部分总结

发表于 | 分类于 | | 热度: ℃
字数统计: 3,617 | 阅读时长 ≈ 16

0x00 几句废话

总体来说,suctf的crypto部分的难度没有想象中的那么高（所以难度就全部集中到misc和web中去了吧可能），结合su-team分享的出题思路以及网上各路大神的解题脚本，学习了许多新姿势。

0x01 题目概览

此次比赛共出了四道密码学相关题目.

  • 传统的DSA题目——重复使用r进行签名.
  • 传统的RSA题目——LSB-Oracle攻击.
  • 新型RSA题目——e == n情况下使用四个素数构造n的情况.
  • 随机数发生器——考察mt19937-32位可逆随机比特发生器的应用.

0x02 解题新姿势

pwntools用于C/S交互

简介

pwntools是一个研究者开发的用于pwn的CTF框架,这里主要讨论其在用户端/客户端交互过程中的使用,从而对解决服务器交互类型的Crypto问题起到作用.

安装

  • Linux虚拟机中安装pwntools只需要命令pip install pwntools.
  • Mac系统中使用brew install pwntools,该命令的安装效果要强于使用pip命令.安装好之后,进入python2所在的包路径,在其中放入*.pth文件,在该文件中写入pwntools所在路径即可完成安装.
  • 安装参考链接

交互功能

  • 导入方法: from pwn import *
  • 连接
    • 本地: sh = process("./level10")
    • 远程: sh = remote("127.0.0.1",10001)
    • 关闭连接: sh.close()
  • I/O模块
    • 发送数据: sh.send(data)
    • 发送一行数据,相当于在数据后面加”\n”(许多服务器交互题目必须模拟提交后的回车键,故需要在提交信息后加上”\n”): sh.sendline(data)
    • 接收数据,numb指定接收的字节,timeout指定超时: sh.recv(numb=2048, timeout=default
    • 接收一行数据,keepends为是否保留行尾的\n: sh.recvline(keepends=True)
    • 接收数据直到出现设置的标志(避免了使用正则表达式): sh.recvutil("Hello,World\n",drop=false)
    • 一直接收直到EOF: recvall()
    • 持续接收直到EOF或timeout: recvrepeat(timeout=default)
    • 直接进行交互,相当于回到shell的模式,在取得shell之后使用: sh.interactive()
  • pwntools常用函数

python-z3库

Z3约束求解器是针对Satisfiability modulo theories Problem 的一种通用求解器.所谓SMT问题,在 Z3环境下是指关于算术、位运算、数组等背景理论的一阶逻辑组合决定性问题.能够用约束求解器搞定的问题常见于密码题、二进制逆向、符号执行Fuzzing模糊测试等.

安装

  • python3可以直接使用pip3 install z3-solver来安装z3库.
  • python2可以使用pip2 install z3-solver来获得安装包,再使用上文提到的创建*.pth文件将该包加入到python2包路径里
  • 基础用法
    • 创建约束求解器: solver = Solver()
    • 添加约束条件: solver.add()
    • 判断解是否存在: solver.check(),当该函数返回sat时说明有解,返回unsat说明无解
    • 求解: solver.model()
    • 数据类型:
      • Int(): 有符号数.
      • BitVec(variable, bits_number): 其中bits_number表示该变量的最大比特位数.只有BitVec变量可以进行异或,故可以用来解决位运算问题.BitVecVal值之间不能进行>或<比较,只能转换成python认识的类型才可以比较.
      • as_long(): 该函数用于将BitVec()类型的数据转换成long类型数据从而输出.
  • z3详细介绍
  • z3在CTF中的应用-长亭技术专栏

0x03 题目分析

DSA

基本原理

签名方案:

  1. 选定公共参数p,q,g,其中$ g^q mod p = 1 $,即g的阶为p;
  2. 签名方随机生成私钥x,满足0 < x < q,计算并公开公钥y = g^x mod q;
  3. 针对消息m,计算其哈希值h = H(m),并生成随机数k,满足0 < k < q;
  4. 计算r = (g^k mod p)mod q(相当于时间戳,防止重放攻击);
  5. 计算s = k^(-1)(H(m)+x*r) mod q;
  6. 以为数字签名进行发布.

验证方案:

接收方在已知公共参数p,q,g和接收到消息m与签名的基础上,可以通过验证以下等式是否成立来验证签名的有效性: r = (g^(s^(-1)*H(m)) + y^(s^(-1)*r) mod p) mod q

其中$ s^{-1} $指s在模q时的乘法逆元.

利用方法

一旦发现两条消息m1,m2的数字签名和,若满足r1=r2=r,则说明它们在签名过程中使用了相同的随机数k.根据签名方案,我们有:

1
2
k*s1 = H(m1) + x*r mod q
k*s2 = H(m2) + x*r mod q

因此有x*r*(s2-s1) = H(m2)*s1 - H(m1)*s2 (mod q)，所以x = (r*(s2-s1))^(-1)*(H(m2)*s1 - H(m1)*s2) mod q 。求得私钥x后,自然可以根据DSA数字签名方案对任意消息进行签名.

解题过程

题目为典型的与服务器交互的类型.直接nc目标端口,发现给出了p,q,g以及明文m,明文压缩之后的哈希值H(m)以及签名对.最后要求给提供的明文进行签名,并且同时提供了该明文的哈希结果.仔细观察发现,签名对中存在不只一个r相同的情况,联想到DSA攻击的方法,选取任意的重复r进行签名即可.脚本如下: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import gmpy2 
# flag{Wh4t_a_Prety_Si3nature!}
r = repeated_r
h_flag = given_hash
p = given_p
q = given_q
g = given_g
y = given_y
h1 = 193111848988193367504523557345609960681
h2 = 88354320495763378663407085075664840900
s1 = 248140921416747064122972352259424645911583156504
s2 = 99292285215174831827792682628484078123790973232
ds = s2-s1
dh = h2-h1
k = gmpy2.mul(dh,gmpy2.invert(ds,q))
k = gmpy2.f_mod(k,q)
tmp = gmpy2.mul(k,s1)-h1
x = tmp*gmpy2.invert(r,q)
x = gmpy2.f_mod(x,q)
print(int(x))
s_flag = (gmpy2.invert(k,q)*(h_flag+x*r)) % q
print((r,s_flag))

(310344651614765735153054256874236002445047411858L, 684046261087521716196888684831381917051249892988L)

mt

基本原理

随机数发生器MT19937在从状态提取32bits随机数时进行了四步平移和异或运算,但该四步运算均为可逆运算,从而导致可从32bits随机数还原状态.随机数生成原始过程如下: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def extract_number(self):
        if self.index >= 624:
            self.twist()
        y = self.mt[self.index]
        # Right shift by 11 bits
        y = y ^ y >> 11
        # Shift y left by 7 and take the bitwise and of 2636928640d
        y = y ^ y << 7 & 2636928640
        # Shift y left by 15 and take the bitwise and of y and 4022730752
        y = y ^ y << 15 & 4022730752
        # Right shift by 18 bits
        y = y ^ y >> 18
        self.index = self.index + 1
        return _int32(y)

解题过程

这是一倒较为基础的逆向随机数生成器的题目,没有什么特殊的技巧.两个基础的思路是爆破和逆向算法.参考大佬们的解决方案:官方给出的wp实现了左移和右移异或的逆运算函数,然后调用两个函数对密文进行解密;de1ta战队则选择了爆破;还有师傅使用python-z3库实现了算法的逆向.

首先来看官方的解题过程: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from Crypto.Util import number

transformed_flag = '641460a9e3953b1aaa21f3a2'
c = transformed_flag.decode('hex')

def decrypt_left(cipher, blocksize, mask):
    plain = cipher
    t = cipher
    for i in range(32 / blocksize):
        tt = (t << blocksize) & mask
        plain = plain ^ tt
        t = tt
    return plain

def decrypt_right(cipher, blocksize, mask):
    plain = cipher
    t = cipher
    for i in range(32 / blocksize):
        tt = (t >> blocksize) & mask
        plain = plain ^ tt
        t = tt
    return plain

def invert(block):
    block = decrypt_right(block, 19, 0xffffffff)
    block = decrypt_left(block, 17, 2245263360)
    block = decrypt_left(block, 9, 2029229568)
    block = decrypt_right(block, 13, 0xffffffff)
    return block

def transform(message):
    assert len(message) % 4 == 0
    new_message = ''
    for i in range(len(message) / 4):
        block = message[i * 4 : i * 4 +4]
        block = number.bytes_to_long(block)
        block = invert(block)
        block = number.long_to_bytes(block)
        new_message += block
    return new_message

flag = transform(c)
print flag.encode('hex')

对于左移和右移异或,写出其逆运算函数.基于mt随机数发生器使用32bits为一轮,故进行32/blocksize次数的异或还原,而blocksize则为左移或右移的位数,还原循环中的函数与加密过程相同.先挖一个坑,具体原理等研究完mt19937后再来填.

使用z3-solver解决的过程中,实际上也是利用了爆破的原理,以题目给出的关系式convert(init) == cipher为约束条件进行处理.

采用直接爆破方法的关键代码为: 

1
2
3
4
5
6
7
8
9
10
def decode(c):
    x = c
    while True:
        xx = x
        # 重复多次加密,直到达到随机数生成的循环周期,从而找到加密之后为所给密文的明文
        x = transform(x.decode('hex')).encode('hex')
        if x == c:
            return xx
c4 = '641460a9e3953b1aaa21f3a2'
print(decode(c4)

经过实验,爆破脚本的解题效率极高,以后碰到的随机数生成问题建议首选爆破脚本.该爆破能够成功主要由于伪随机数生成器得到的数字具有周期性,经测试该伪随机数生成器的周期为61320.

Prime

基本原理

该题目使用了RSA加密中e == n这一特殊情况构造模数n.

对任意两个不同素数p,q和整数n=p*q,对任意整数m,0 < m < p且m < q,若c = m^n mod n,则c^(q') mod q = m,其中q’满足q1*p mod (q-1) = 1.予以证明如下:

根据费马小定理: $ m^{q-1} mod q = 1 $,所以$ m^{k’*(q-1)+1} mod q = m $.同理$ c^{q’} mod p = m $.

该题以此为原理,进行了扩展,将素数数量由2个扩大到了4个,并将m的范围扩大到0 < m < n.

解题过程

nc地址之后,首先进行通过爆破的方式验证哈希值,从而通过proof_of_work()函数.爆破代码如下: 

1
2
3
4
5
6
7
8
from random import choice
from string import hexdigits
while True:
	for i in range(1, len(hexdigits)):
		string = "".join([choice(hexdigits) for _ in range(i)]).lower()
		if (md5(string + salt).hexdigest()[0:5] == part_hash):
            break
    break

然后返回c0-c3,n0-n3共四对(n,s)对.对给出的n0,n1,n2,n3进行最大公因子分析,可分别得出他们的四个素因子.一般的,对于n = p1*p2*p3*p4和c = m^n mod n,有$ c^{p{i}^{‘}} (mod p_i) = m (mod p_i) $,其中$p{i}^{‘}$满足$p{i}^{‘}(n(p_i))mod (p_i-1) = 1 $,即$ p{i}^{‘} $是$ (n/p_i) $在$(p_i-1)$下的乘法逆元.然后可以利用中国剩余定理求解.官方解题脚本如下: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import numpy as np
import gmpy2 as gm
def crack(N, ns, cs):
    M = np.ones((N, N))
    M = M.tolist()
    for i in range(N):
        M[i][i] = 1
        for j in range(N):
            if i != j:
                M[i][j] = gm.gcd(ns[i], ns[j])
                M[i][i] *= M[i][j]
        M[i][i] = ns[i] / M[i][i]

    nsns = [1] * 4
    for i in range(N):
        for j in range(N):
            nsns[i] *= M[i][j]

    index = np.ones((N, N))
    index = index.tolist()

    for i in range(N):
        for j in range(N):
            index[i][j] = 1
            for k in range(N):
                if k != j:
                    index[i][j] *= gm.invert(M[i][k], M[i][j] - 1)

    cc = np.ones((N, N))
    cc = cc.tolist()
    for i in range(N):
        for j in range(N):
            cc[i][j] = pow(cs[i], index[i][j], M[i][j])

    mms = [0] * N
    for i in range(N):
        for j in range(N):
            fac = cc[i][j]
            for k in range(N):
                if k != j:
                    fac *= (M[i][k] * gm.invert(M[i][k], M[i][j]))
            mms[i] += fac % ns[i]
        mms[i] = mms[i] % ns[i]
    return mms

RSA

基本原理

通读server2.py发现大致的交互过程如下:随机生成1024bits的n及加密密钥并公布.在0-(1024bits-1)范围内生成明文.用户可以不断向服务器发送加密过后的明文,服务器返回解密后明文的奇偶性.用户利用RSA的parity oracle漏洞得到随机生成的明文并上传给服务器.重复上述过程三次,当用户三次全部猜测正确时返回flag.

解题过程

拿到脚本之后,根据返回odd和even,可以想到是利用了LSB oracle漏洞.该漏洞原理较为简单,但一般情况下最终还原出的明文和真实明文会存在一定偏差,这主要是因为max和min是整数类型,其表示的上界和下界不够精确.官方给出了精确还原m的脚本: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def crack(n, e, c):
    rounds = int(math.ceil(math.log(n, 2)))
    d = pow(2, e, n)
    cc = c
    eigenvalue = 0
    for i in range(rounds):
        if i % 256 == 0:
            print i
        cc = (cc * d) % n
        parity = getParity(cc) #parity oracle返回明文奇偶性
        eigenvalue = (eigenvalue << 1) + parity
    if eigenvalue == 0:
        return 0
    else:
        return n * eigenvalue / pow(2, rounds) + 1

解题脚本如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
from pwn import *
from hashlib import md5
import decimal
from random import choice
from string import hexdigits


a = 0
def oracle(num):
    p.recvuntil("Please input your option:")
    p.sendline("D")
    p.recvuntil("Your encrypted message:")
    p.sendline(str(num))
    p.recvuntil("The plain of your decrypted message is ")
    lsb = p.recv(3)
    return lsb == 'odd'

def crack(n, e, c):
    rounds = int(math.ceil(math.log(n, 2)))
    d = pow(2, e, n)
    cc = c
    eigenvalue = 0
    for i in range(rounds):
        if i % 256 == 0:
            print i
        cc = (cc * d) % n
        parity = getParity(cc) #parity oracle返回明文奇偶性
        eigenvalue = (eigenvalue << 1) + parity
    if eigenvalue == 0:
        return 0
    else:
        return n * eigenvalue / pow(2, rounds) + 1

p = remote("47.111.59.243","9421")
p.recvuntil("[*] Please find a string that md5(str + ")
salt = p.recv(4)
p.recvuntil("[0:5] == ")
part_hash = p.recv(5)
while True:
	for i in range(1, len(hexdigits)):
		string = "".join([choice(hexdigits) for _ in range(i)]).lower()
		if (md5(string + salt).hexdigest()[0:5] == part_hash):
            break
    break

p.recvuntil("> ")
p.sendline(string)
p.recvuntil("Guess the Secrets 3 times, Then you will get the flag!\n")
for i in range(3):
    R = p.recvline().strip()
    p.recvuntil("n = ")
    n = eval(p.recvline().strip())
    p.recvuntil("e = ")
    e = eval(p.recvline().strip())
    p.recvuntil("The Encypted secret:")
    p.recvuntil("c = ")
    c = eval(p.recvline().strip())
    c_of_2 = pow(2,e,n)
    m = crack(n, e, (c*c_of_2)%n)
    p.recvuntil("Please input your option:")
    p.sendline("G")
    p.recvuntil('The secret:')
    p.sendline(str(m))
    s = p.recvline().strip()
    print(s)
    log.success(s+' '+R+" success!")
p.interactive()

完成与服务器的多次交互并正确猜测三次后即可得到flag.

0x04 再说几句废话

本次题目的crypto部分还是可以学到很多东西的.与nc类题目以前经常使用socket编程进行,但匹配到需要的数据需要同时使用正则表达式和eval()函数,较为繁琐,解题速度慢,这次比赛学到了pwntools这一集成工具的使用,大大加快了解题速度.另外使用python-z3库可以更快更明确地完成爆破,只需要提供约束条件即可.

请作者吃个小鱼饼干吧
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多