r1ngs's blog

starCTF-crypto部分

2019-05-02

安全客已投,戳我跳转

前言

临近五一事情比较多,基本用的是零碎的时间玩的*ctf,有些题目还是很有趣的

babyprng

首先看一下主要代码:

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
def run(self, code):
stack = []
out = []
cnt = 0
random.seed(os.urandom(8))
self.TH = 0.7 + random.random()*0.25
for _ in xrange(self.SIZE):
stack.append(self.randbit())
try:
pos = 0
for _ in xrange(self.SIZE*10):
c = code[pos]
pos += 1
if c=='\x00':
out.append(stack[-1])
elif c=='\x01':
if stack[-1]==1:
pos += 1
elif c=='\x02':
del stack[-1]
elif c=='\x03':
stack[-1] = stack[-1]&stack[-2]
elif c=='\x04':
stack[-1] = stack[-1]|stack[-2]
elif c=='\x05':
stack[-1] = stack[-1]^stack[-2]
#elif c=='\x06':
# stack[-1] = 1-stack[-1]
#elif c=='\x06':
# stack.append(stack[-1])
elif ord(c)>=0x10 and ord(c)<=0x30:
pos += ord(c)-0x10
elif ord(c)>=0x30 and ord(c)<=0x50:
pos -= ord(c)-0x30

首先TH随机生成的值大概会在0.8左右,后面就以TH=0.8来讨论,那么按照算法,stack中大概有80%为0,20%为1

我们要做的是使得最终的out有大约一半的0和一半的1,而且元素的个数不能太少,我做这种题目喜欢在本地搭建,因为proof_of_work等待的时间实在有点长

我们关注第三个,第四个,第五个操作,列举出stack最后两个元素的可能情况和经过这些操作后的值:

出现的概率 最后两个元素可能的值 与操作 或操作 异或操作
64% 00 00 00 00
16% 01 00(改变) 01 01
16% 10 10 11(改变) 11(改变)
4% 11 11 11 10(改变)

自己的解法

观察到对于10来说^操作可以将其变为11而11又可以变成10,这样最后一位就可以在我们的控制下做周期性的交替了,而且最后两步操作是可以重新将pos指针重新指向code的任意位置的,如此一来就能实现周期性的循环操作,所以解法是在一个周期的前半周期里重复执行0的操作,然后中间执行一次异或操作,改变最后一元素的值,后半周期再重复执行0操作,这样就能再一个周期里取一半的0再取一半的1了

上面能成功的前提条件是stack最后两位的初始值为10或者11,可能的概率为16%+4%=20%,所以如果没有成功的话多尝试几次就可以了,exp:

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
from socket import *
from libnum import *
import string
from re import *
from hashlib import sha256

def connect(host, port):
s = socket()
s.connect((host, port))
return s

def cal(proof, ans, set):
for i in set:
for j in set:
for k in set:
for m in set:
if sha256(i+j+k+m+proof).hexdigest() == ans:
print i+j+k+m
return i+j+k+m

def proof_of_work(s):
msg = s.recv(1024)
print msg
set = string.ascii_letters+string.digits

reg = 'sha256\(XXXX\+(.+)\) == (.+)\n'
regexp = compile(reg)
res = regexp.findall(msg)

proof = res[0][0]
ans = res[0][1]

print s.recv(1024)
s.send(cal(proof, ans, set))
print s.recv(1024)


def main():
host = '34.92.185.118'
port = 10002
s = connect(host, port)
proof_of_work(s)

msg = chr(0)*15+chr(5)+chr(0)*15+chr(0x50)
print msg.encode('hex')
s.send(msg.encode('hex')+'\n')
print s.recv(1024)


if __name__ == '__main__':
main()

官方的解法

先来看exp(稍微有改动,因为我觉得有一步貌似没必要= =):

1
msg = '\x02\x02\x05\01\x35\x02'+'\x00'*10+'\x40'

上个自己画的图:

可以看到流程就是利用跳转来实现循环语句,直到异或以后最后一位为1,然后删掉1,取倒数第二位10次,然后再删除这一位,继续异或,重复操作。

通过异或使得最后一位为1只有两种可能10和01,且这两种情况等概率出现(均为16%),所以倒数第二位为0或者1的概率各为50%,也即算法等价于在每个周期等概率的取0或者1,这样的话成功的概率就很大了

babyprng2

核心代码:

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
def run(self, code):
stack = []
sequence = []
out = []
cnt = 0
random.seed(os.urandom(8))
self.TH = 0.7 + random.random()*0.25
for _ in xrange(self.SIZE):
stack.append(self.randbit())
try:
pos = 0
for _ in xrange(self.SIZE*0x10):
c = code[pos]
pos += 1
if c=='\x00':
out.append(stack[-1])
del stack[-1]
elif c=='\x01':
if stack[-1]==1:
pos += 1
elif c=='\x02':
stack[-1] = stack[-1]&stack[-2]
elif c=='\x03':
stack[-1] = stack[-1]|stack[-2]
elif c=='\x04':
stack[-1] = stack[-1]^stack[-2]
elif c=='\x05':
sequence.append(stack[-1])
del stack[-1]
elif c=='\x06':
sequence.insert(0,stack[-1])
del stack[-1]
elif c=='\x07':
if len(stack)>=2:
pos += 1
elif c=='\x08':
stack+=sequence[::-1]
sequence=[]
elif ord(c)>=0x10 and ord(c)<=0x1a:
pos += ord(c)-0x10
elif ord(c)>=0x30 and ord(c)<=0x3a:
pos -= ord(c)-0x30

这道题和上面题目的区别:

delta更小、out append的时候每次还会把栈删除、多了对seq的操作,循环的次数更多,而要求out的元素更少

自己的解法

由于可以做判断是否为一,那么我可以在一个周期里第一步取0,如果不是0就丢弃然后重复判断(送入seq),如果是0就判断下一个是否为1,如果是1就进入下一个周期,如果不是的话就丢弃然后再重复判断,这样相当于每个周期都在重复的取01

画成图就是这个样子:

或者这个样子

但是这样并不能实现,因为误删除元素(送入seq)的有很多,循环还没结束就会因为stack的元素全部没有了而报错,导致out的元素个数就不够了,本地测试最多也就在2万左右,达不到3万,但是我们有一个判断stack元素还剩多少的方法,当stack要空了的时候只要用第8个方法把seq的元素重新放回stack重复利用就行了,虽然构造有点麻烦,但总归是可以实现的:

对应poc:01140708053607080001140708003a0708053a

notcurves

题目有一个非常严重的Bug,导致了非常严重的非预期

1
2
3
4
5
6
7
8
9
self.dosend("please give me a point(pi,qi): \n")
R = self.recvpoint(30)
(u,v) = R
print R
if (u*v)%p == 0:
self.dosend("%s\n" % FLAG)
else:
self.dosend(">.<\n")
self.request.close()

没有检查参数R,所以R可以是(0, 0),直接就能过,应该大部分人都是这样做出来的吧。。。

比赛结束以后我还是很兴奋的重新看了一下,毕竟ECC椭圆曲线的题目很少,但是由于这道题没有官方wp,所以我也只能猜测一下出题人的预期解

首先在循环里能做的操作其实只有3个,第一个是ADD方法,实现的功能是求椭圆曲线上两点相加的结果,第二个是MUL方法,实现的功能是在椭圆曲线上求一个点的倍数,而我觉得预期解法应该是最后一个DIV方法

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
def DIV(self):
self.dosend('input point A: \n')
A = self.recvpoint(30)
self.dosend('input number t: \n')
t = self.recvnum(10)
C = div(t,A)
self.dosend("the result is :"+str(C)+'\n')


def div(t,A,B=0):
(u,v) = A
if (u*v) %p != 1:
#print u*v*sub((p,t))%p
return u*v*sub((p,t))%p
else:
return B


def sub(A):
(u,v) = A
v = v%p
if v > 2**11:
print u//v
return u//v
else:
return 0

仔细观察代码会发现这个方法并没有调用其他两个方法里的check_point方法,也就是不检查输入的点是否在椭圆曲线上,这就可以任意构造了,题目的要求是求出p的大小,而这个方法完全可以做到:

由于检查u、v不能直接为(1, 1),所以可以令uv为(1, 2)最后返回的结果除以2就能得到sub(p, t)的结果,而我们是大致知道p的范围的,因为p=getprime(15)*getprime(15)所以p的范围在pow(2, 29)到pow(2, 30)之间,如果令t也在pow(2, 29)到pow(2, 30)之间且p>=t的话,那么p//t结果一定是返回1,否则的话返回其他结果,那么我们就可以通过二分法查找来缩小范围,从而确定p的值(所以这道题和ecc有啥关系?。。。)

exp:

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
from socket import *
from libnum import *
import string
from re import *
from hashlib import sha256



def connect(host, port):
s = socket()
s.connect((host, port))
return s

def cal(proof, ans, set):
for i in set:
for j in set:
for k in set:
for m in set:
if sha256(i+j+k+m+proof).hexdigest() == ans:
print i+j+k+m
return i+j+k+m

def proof_of_work(s):
msg = s.recv(1024)
print msg
set = string.ascii_letters+string.digits

reg = 'sha256\(XXXX\+(.+)\) == (.+)\n'
regexp = compile(reg)
res = regexp.findall(msg)

proof = res[0][0]
ans = res[0][1]

print s.recv(1024)
s.send(cal(proof, ans, set))
print s.recv(1024)

def send4(s, msg):

print '4'
s.send('4\n')
print s.recv(1024)
print '(1,2)'
s.send('(1,2)\n')
print s.recv(1024)
print str(msg)
s.send(str(msg) + '\n')
res = s.recv(1024)
print res
print s.recv(1024)

reg = 'the result is :(.+)'
regexp = compile(reg)
r = regexp.findall(res)
num = r[0]
return int(num)



def main():
host ='127.0.0.1'
port = 20005
s = connect(host, port)
proof_of_work(s)


print s.recv(1024)

low = 2**29
high = 2**31
mid = (low + high) / 2
count = 0
while high>low:
if send4(s, mid)==2:
low = mid
else:
high = mid
tmp = mid
mid = (low + high) / 2
if mid == tmp:
count += 1
else:
count = 0
if count >5:
break

mid += 1

print 5
s.send('5\n')
print s.recv(1024)
print (1, mid)
s.send('(1,%d)\n'%mid)
print s.recv(1024)
print s.recv(1024)


if __name__ == '__main__':
main()

总结

不管是出题人有心还是无意,这次题目都有很多非预期的解法,也给题目增加了许多乐趣

Tags: CTF

1000000