2016 HITCON Crypto -- PAKE(++)

前几天的HITCON是我最近参加过质量最高的CTF了, 里面的题目够我研究几周了, 而且大部分都有源码, 本地也是很容易复现

Reference: writeup

PAKE(Crypto 250)

pake1

[源码]https://github.com/Hcamael/CTF_repo/blob/master/HITCON/PAKE(250)/pake1.rb_c077fdcc6ed6488b53504bc8ad0069e8281ad21a

原题复现

源码已经有了, 还缺两个文件, passwordsflag1.txt, 本地搭环境这两个自己随便设置就好了

我的如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# passwords
8
15
9
15
7
7
13
11
10
15
4
# flag1.txt
hitcon{73n_w34k_p455w0rd5_c0mb1n3d_4r3_571ll_wE4k_QQ}

这样可以在本地复现环境了

1
2
$ chmod +x pake1.rb
$ socat TCP4-LISTEN:10001,fork EXEC:./pake1.rb

分析源码

第一部分先是跑proof:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
x = SecureRandom.random_bytes(6)
puts 'Robot test'
puts "prefix: #{[x].pack('m0')}"
r = gets.strip.unpack('m0')[0]
r = Digest::SHA1.digest(x + r)
# We want the digest to begin with 23 bits of zero.
# [0..15]
unless r.start_with?("\0\0")
puts 'FAIL! GO AWAY!'
exit
end
c = r[2].ord
r, s = c / 2, c % 2
# r: [16..22], s: [23]
unless r == 0
puts 'FAIL! GO AWAY!'
exit
end
print 'Good job! '

很简单的证明, 为了减小跑这部分脚本的时间, 把倒数2-5行注释了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
x = SecureRandom.random_bytes(6)
puts 'Robot test'
puts "prefix: #{[x].pack('m0')}"
r = gets.strip.unpack('m0')[0]
r = Digest::SHA1.digest(x + r)
# We want the digest to begin with 23 bits of zero.
# [0..15]
unless r.start_with?("\0\0")
puts 'FAIL! GO AWAY!'
exit
end
c = r[2].ord
r, s = c / 2, c % 2
# r: [16..22], s: [23]
# unless r == 0
# puts 'FAIL! GO AWAY!'
# exit
# end
print 'Good job! '

写了个proof.py脚本

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
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import hashlib
import itertools
import base64
import sys
import threading
import time
from multiprocessing import Pool

fuzzing = "abcdefghijklmnopqrstuvwxyz0123456789QWERTYUIOPASDFGHJKLZXCVBNM"
for x in xrange(255):
fuzzing += chr(x)

def md5_proof(fuzz, prefix, verify):
y = len(verify)
while True:
try:
padd = "".join(fuzz.next())
except StopIteration:
break
r = hashlib.md5(prefix + padd).hexdigest()
if r[:y] == verify:
return padd


def sha1_proof(fuzz, prefix, verify):
y = len(verify)
while True:
try:
padd = "".join(fuzz.next())
except StopIteration:
break
r = hashlib.sha1(prefix + padd).hexdigest()
if r[:y] == verify:
return padd


def proof(s, verify="0000", method="sha1"):
'''
目前只提供md5与sha1
'''

fuzz = itertools.permutations(fuzzing, 5)
if method == 'md5':
result = md5_proof(fuzz, s, verify)
else:
result = sha1_proof(fuzz, s, verify)

assert result != ""
return result

if __name__ == '__main__':
t1 = time.time()
p = Pool(2)
p.map(proof, ["3f4sd4y5ydfgs","ertwd4t32354ffcd"])
print time.time() - t1
#md5_proof(s, verify)

接下来就是正文了

本题的逻辑不难懂, 仔细读读源码应该就能看懂了, 就不在这多说了.

本题的重点在于passwords, 如果能知道其值, 则该题就很容易就出来了, 每轮输入$sha512(password[i])^2\ mod\ q$, 然后$flag = enc\_flag\ xor\ sha512(bb)$

比赛期间我能想到的只有爆破, 虽然passwords的值很小, 但是也要遍历最多$16^{11}$次, 不现实.

这题就像是题目名一样, 涉及到了PAKE原理:

已知:
$$
x^a\ mod\ q = A\\
x^b\ mod\ q = B
$$
则:
$$
A^b\ mod\ q = B^a\ mod\ q
$$

这个逻辑应该很容易理解, 也不难推导.

当初我也想过, 可以建立两个连接, 两个连接每一轮都有一个相同password[i], 和q, 每轮返回的值我们按照源码里称为bb
每轮:

$$
password[i]^{2 * b_1}\ mod\ q = bb_1\\
password[i]^{2 * b_2}\ mod\ q = bb_2
$$
如果我们把连接1的$bb_1$ 发送给连接2, $bb_2$发送给连接1
则在源码中每轮和flag进行xor的k相等

$$
k_1 = bb_2^{b_1}\ mod\ p\\
k_2 = bb_1^{b_2}\ mod\ p\\
k_1 == k_2
$$

虽然得出了这个结论, 但好像对解出flag并没有帮助, 当时我就是卡在这里了.

之后看了wp才明白, 这一步的作用可以用来爆破password, 不需要要像最开始想的那样需要爆破$16^{11}$次, 现在最多只需要16*11

根据上述结论, 我们可以很容易的得到, 如果建立两个连接, 11轮都互相交换$bb_i$, 则最后得到enc_flag是相等的.

1
enc_flag = flag xor sha512(ki)

根据PAKE原理, 每轮的k都相等, flag相等, 所以最后得到的enc_flag也相等

现在, 我们假设password[0] = 1

然后我们第一轮, 两个链接都传入$sha512(1)^2\ mod\ q$, 然后之后的所有轮都通过PAKE原理让k相等,

我们可以推导出来, 两个连接最后输出的enc_flag, 肯定不想等, 但是分别xor自己那个连接的第一轮的sha512(k)后, 值就相等了.

见下图:
PS: 在理解逻辑的情况下sha512暂时省去

pake2

那么两个连接的第一轮的k怎么得到? 就比如在上面这种情况下, $k_1 = bb_1$, 但是如果我们传入的不是$sha512(1)^2\ mod\ q$, 则$k_1 \neq bb_1$

所以说, 在我们猜中password的情况下, 我们可以预知到k, 能预知到k, 我们可以和enc_flag进行异或后使其值相等, 如果猜错password的值, 则我们预知的k值是错误的, xor后的结果不相等

这样, 每个password最多只要跑16次, 有11轮, 每个password之间互不干扰, 所以最多只要爆破$16*11$次, 就可以得到所有的password

payload:

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
# pake1_payload.py
#! /usr/bin/env python
# -*- coding: utf-8 -*-

from multiprocessing import Pool as ThreadPool
from Crypto.Util.number import long_to_bytes, bytes_to_long
from proof import proof
import hashlib
from pwn import *

context.log_level = "CRITICAL"
pool = ThreadPool(2)
pp = 285370232948523998980902649176998223002378361587332218493775786752826166161423082436982297888443231240619463576886971476889906175870272573060319231258784649665194518832695848032181036303102119334432612172767710672560390596241136280678425624046988433310588364872005613290545811367950034187020564546262381876467

def guess_password(password):
for x in xrange(len(password)):
if password[x] != None:
continue
for gn in xrange(1, 17):
g_num = pow(bytes_to_long(hashlib.sha512(str(gn)).digest()), 2, pp)
p1 = remote("127.0.0.1", 10001)
p2 = remote("127.0.0.1", 10001)
p1.readuntil("prefix: ")
p2.readuntil("prefix: ")
prefix1 = p1.readline().decode('base64')
prefix2 = p2.readline().decode('base64')
solve1, solve2 = pool.map(proof, [prefix1, prefix2])
p1.sendline(solve1.encode('base64').strip())
p2.sendline(solve2.encode('base64').strip())

diff_num1 = 0
diff_num2 = 0
for y in xrange(len(password)):
p1.readuntil("Server send ")
p2.readuntil("Server send ")
tmp_num1 = p1.readline().strip()
tmp_num2 = p2.readline().strip()
if y == x:
p1.sendline(str(g_num))
p2.sendline(str(g_num))
diff_num1 = bytes_to_long(hashlib.sha512(tmp_num1).digest())
diff_num2 = bytes_to_long(hashlib.sha512(tmp_num2).digest())
else:
p1.sendline(tmp_num2)
p2.sendline(tmp_num1)
p1.readuntil("Flag is (of course after encryption :D): ")
p2.readuntil("Flag is (of course after encryption :D): ")

enc_flag1 = int(p1.readline().strip())
enc_flag2 = int(p2.readline().strip())
p1.close()
p2.close()
if (enc_flag1^diff_num1) == (enc_flag2^diff_num2):
password[x] = gn
print "find! %s" %gn
print password
break
return password

def getflag(password):
p = remote("127.0.0.1", 10001)
p.readuntil("prefix: ")
prefix = p.readline().decode('base64')
solve = proof(prefix)
p.sendline(solve.encode('base64').strip())
tmp_num = []
for x in password:
send_num = pow(bytes_to_long(hashlib.sha512(str(x)).digest()), 2, pp)
p.readuntil("Server send ")
tmp_num.append(p.readline().strip())
p.sendline(str(send_num))

p.readuntil("Flag is (of course after encryption :D): ")
enc_flag = int(p.readline().strip())
flag = enc_flag
for x in tmp_num:
flag ^= bytes_to_long(hashlib.sha512(x).digest())
print long_to_bytes(flag)

if __name__ == '__main__':
password = [None] * 11
# password = [8, 15, 9, 15, 7, 7, 13, 11, 10, 15, 4]
password = guess_password(password)
getflag(password)

pake3

PAKE++(Crypto 150)

pake4

[源码]https://github.com/Hcamael/CTF_repo/blob/master/HITCON/PAKE%2B%2B(150)/pake2.rb_3a9fcc07faff2d8ff6f48c5636c52209fa2f8e51

本地环境搭建同上, 同样注释那4行, 减少我们跑脚本的时间

同样需要两个文件

1
2
3
4
# password2
7ygvnht567ujmkihgfdR
# flag2.txt
hitcon{m17m_f0r_pr0f1t_bu7_S71ll_d035n7_kn0w_p455w0rd}

和上题不同, 分值降低了, 难度应该也降低了, 循环变2轮了, 但是q变多了, 每轮从8个q中随机选取一个

跟上题相比, 这回的password是固定的值, 如果能得到, 那就能做出来了, 但是这回password根据代码可以知道

1
fail unless password =~ /\A[a-zA-Z0-9]{20}\z/

如果爆破的话, 需要$62^{20}$次, 明显不现实

所以上题先求password的方法在这题不可行了, 但是我们能借鉴下上题的思路

这回我们引入第三个连接:
$$
enc\_flag1 = flag \bigotimes k1_1 \bigotimes k1_2\\
enc\_flag2 = flag \bigotimes k2_1 \bigotimes k2_2\\
enc\_flag3 = flag \bigotimes k3_1 \bigotimes k3_2
$$

按照前面PAKE的思路, 使得
$$
k1_1 = k2_1\\
k3_1 = k1_2\\
k2_2 = k3_2
$$

然后再把三个enc_flag进行异或运算, 最后得到就是flag

不过这有个小问题, 根据PAKE的原理, 要求p要相等, 但是这题的p是从8个中随机出一个

这个问题不大, 毕竟只有8个, 完全可进行爆破, 在q相等的情况下进行

payload:

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#! /usr/bin/env python
# -*- coding: utf-8 -*-

from pwn import *
from proof import proof
import hashlib
from multiprocessing import Pool as ThreadPool
from Crypto.Util.number import long_to_bytes

# context.log_level = "debug"
pool = ThreadPool(2)

p1 = remote("127.0.0.1", 10001)
p2 = remote("127.0.0.1", 10001)
p1.readuntil("prefix: ")
p2.readuntil("prefix: ")
prefix1 = p1.readline().decode('base64')
prefix2 = p2.readline().decode('base64')
solve1, solve2 = pool.map(proof, [prefix1, prefix2])
p1.sendline(solve1.encode('base64').strip())
p2.sendline(solve2.encode('base64').strip())
p1.readuntil("p = ")
p2.readuntil("p = ")

prime1 = p1.readline()
prime2 = p2.readline()

while prime1 != prime2:
p2.close()
p2 = remote("127.0.0.1", 10001)
p2.readuntil("prefix: ")
prefix2 = p2.readline().decode('base64')
solve2 = proof(prefix2)
p2.sendline(solve2.encode('base64').strip())
p2.readuntil("p = ")
prime2 = p2.readline()

p1.readuntil("Server send ")
p2.readuntil("Server send ")
p1_r1_num = p1.readline()
p2_r1_num = p2.readline()
p1.send(p2_r1_num)
p2.send(p1_r1_num)

p1.readuntil("p = ")
p2.readuntil("p = ")
r2_prime1 = p1.readline()
r2_prime2 = p2.readline()
p1.readuntil("Server send ")
p2.readuntil("Server send ")
p1_r2_num = p1.readline()
p2_r2_num = p2.readline()

while True:
p3 = remote("127.0.0.1", 10001)
p3.readuntil("prefix: ")
prefix3 = p3.readline().decode('base64')
solve3 = proof(prefix3)
p3.sendline(solve3.encode('base64').strip())
p3.readuntil("p = ")
prime3 = p3.readline()
p3.readuntil("Server send ")
p3_r1_num = p3.readline()
if prime3 == r2_prime1:
p3.send(p1_r2_num)
elif prime3 == r2_prime2:
p3.send(p2_r2_num)
else:
p3.close()
continue
p3.readuntil("p = ")
r2_prime3 = p3.readline()
p3.readuntil("Server send ")
p3_r2_num = p3.readline()
if prime3 == r2_prime1 and r2_prime3 == r2_prime2:
p3.send(p2_r2_num)
p1.send(p3_r1_num)
p2.send(p3_r2_num)
elif prime3 == r2_prime2 and r2_prime3 == r2_prime1:
p3.send(p1_r2_num)
p2.send(p3_r1_num)
p1.send(p3_r2_num)
else:
p3.close()
continue
break

p1.readuntil("Flag is (of course after encryption :D): ")
p2.readuntil("Flag is (of course after encryption :D): ")
p3.readuntil("Flag is (of course after encryption :D): ")
enc1 = p1.readline()
enc2 = p2.readline()
enc3 = p3.readline()
p1.close()
p2.close()
p3.close()
flag = int(enc1) ^ int(enc2) ^ int(enc3)

print long_to_bytes(flag)

pake5

总结

这次的HITCON我一共看了四道密码学, 都挺有意思, 不过我还是太菜, 一道也没撸出来, 这里放了两道, 之后还会写一片OTP的分析, 关于随机数预测的CVE, RSA的目前还没发现wp, 然后还有几道我做了的web题的分析

总的来说这次HITCON收益良多, 有时间还会分析下bin的题

文章目录
  1. 1. PAKE(Crypto 250)
    1. 1.1. 原题复现
    2. 1.2. 分析源码
  2. 2. PAKE++(Crypto 150)
  3. 3. 总结