Posted Updated 16 minutes read (About 2385 words)0 visits

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

原题复现

源码已经有了, 还缺两个文件, passwords和flag1.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
100
#! /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的题

2016 HITCON Crypto -- PAKE(++)

https://nobb.site/2016/10/12/0x23/

Author

Hcamael

Posted on

2016-10-12

Updated on

2022-04-06

Licensed under

#

Like this article? Support the author with

Follow

Recents

Tags

CTF22
Crypto10
Driver4
GIT2
HardWare4
Hardware4
IoT2
Kernel1
Linux4
Pentest1
Python4
RE3
SQLi2
USB3
Web9
Windows1
android3
bin41
blockchain5
eBPF3
network4
old_blog1
php4
record1
research37
sb1
share1
shellcode1
tips3
v811
随笔1

Links

×