0%

2022-西湖论剑-wp-crypto

今年西湖论剑马上就要开始了,为了准备比赛,复现一下昨年的题目。

LockByLock

题目描述:

1
Lock Lock Lock…

题目:

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
101
102
103
104
105
106
from Crypto.Util.number import *
from gmpy2 import *
import random
from secret import flag

class Lock:
def __init__(self, p, q) -> None:
while True:
self.p = p
self.q = q
self.n = self.p * self.q
self.e = random.randint(10**14, 10**15)

if gcd(self.e, (self.p-1)*(self.q-1)) == 1:
self.d = invert(self.e, (self.p-1)*(self.q-1))
break

def lock(self, message: int) -> int:
assert 1 < message < self.n
return powmod(message, self.e, self.n)

def unlock(self, cipher: int) -> int:
assert 1 < cipher < self.n
return powmod(cipher, self.d, self.n)


def secureProcedure(A, B):
global flag
flag = bytes_to_long(flag)
print('Alice: lock lock lock lock unlock')
msg1 = A.lock(flag)
print(f'Alice: locked msg1 = {msg1}')
print('Alice: lock lock lock lock')

print('Bob: lock unlock lock lock')
msg2 = B.lock(msg1)
print(f'Bob: locked msg2 = {msg2}')
print('Bob: lock lock lock lock')

print('Alice: unlock unlock unlock...')
msg3 = A.unlock(msg2)
print(f'Alice: unlocked msg3 = {msg3}')
print('Alice: lock lock lock lock')

print('Bob: unlock unlock unlock...')
msg = B.unlock(msg3)

assert msg == flag
print('Bob: lock lock unlock')
print('Bob: lock by lock, lock lock right, unlock unlock unlock...')
print('Alice: right right, lock lock unlock')
print('Bob: lock lock lock, flag lock lock lock.')
print('Alice: lock unlock lock lock, unlock lock lock')
print('Bob: lock lock!')


def proxyProcedure(A, B):
print('Agent: lock lock, lock lock lock, unlock lock lock right')
print('Alice: lock!')
print('Bob: lock lock, unlock lock!')
omsg = int(input())

print('Alice: lock lock lock lock unlock')
msg1 = A.lock(omsg)
print(f'Alice: locked msg1 = {msg1}')
print('Alice: lock lock lock lock')

print('Bob: lock unlock lock lock')
msg2 = B.lock(msg1)
print(f'Bob: locked msg2 = {msg2}')
print('Bob: lock lock lock lock')

print('Alice: unlock unlock unlock...')
msg3 = A.unlock(msg2)
print(f'Alice: unlocked msg3 = {msg3}')
print('Alice: lock lock lock lock')

print('Bob: unlock unlock unlock...')
msg = B.unlock(msg3)


assert msg == omsg
print('Bob: lock, lock, locked lock lock lock unlock')
print('Bob: lock by lock, lock lock right, lock unlock unlock unlock...')
print('Alice: right right, locked lock lock lock unlock')
print('Bob: lock lock!')


def main():
p = getPrime(1024)
q = getPrime(1024)
AliceLock = Lock(p, q)
BobLock = Lock(p, q)

secureProcedure(AliceLock, BobLock)

try:
proxyProcedure(AliceLock, BobLock)
proxyProcedure(AliceLock, BobLock)
print('Lock: lock lock lock, unlock lock lock lock, lock lock unlock lock unlock lock, lock.')
except Exception:
print('lock unlock, lock locked, unlocked lock')


if __name__ == '__main__':
main()

题目比较长,但流程并不复杂。首先生成两个1024bit的素数p、q,然后以此为基础,生成两个Lock类AliceLock与BobLock,Lock类中的数据包含以下RSA密钥对,并提供加密和解密操作:

也就是说,两者只有加密指数e和解密指数d有区别,而模数n是完全一样的。同时e的数量级是10^14-10^15之间。

至此,题目完成了数据的准备工作。但是需要注意的是,我们不知道其中任何数据,包括公钥中的模数n与加密指数e。

然后就进入题目加密环节,首先,靶机会传送给我们:

m是flag值。然后,我们拥有两次机会,可以给靶机输入a,然后获得:

要想办法以此解出flag值。

那么首先就要想办法还原模数n,这一点很简单,我们只需要利用这两次机会,分别传入2和4,就能获得:

然后我们就可以借助2和4的平方关系,求解下面几个式子的GCD,并去除小因子得到n:

得到n过后就要想办法解出m,而e1、e2两个不同的加密指数很明显在提示共模,因此下一步就是要把e1、e2分别求出来。而突破点在于e1、e2的数量级在10^14-10^15之间,大约2^50左右,是可以用bsgs或Pollard’s kangaroo algorithm之类的方法求DLP的。而可供求解的组也不少,比如:

但是直觉上来说,肯定是求解以2为底的较好。但看别人wp和自己尝试确实都是求以4为底的更快一些,也许是因为阶的原因。

求出e1、e2后就是简单共模。

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
from Pwn4Sage.pwn import *
from Crypto.Util.number import *
from gmpy2 import *

r = remote("node4.anna.nssctf.cn",28184)

#part1 get msg about flag
r.recvuntil(b"Alice: locked msg1 = ")
m1 = int(r.recvline().strip().decode())
r.recvuntil(b"Bob: locked msg2 = ")
m12 = int(r.recvline().strip().decode())
r.recvuntil(b"Alice: unlocked msg3 = ")
m2 = int(r.recvline().strip().decode())

#part2 get n,send 2 and 4
r.sendline(b"2")
r.recvuntil(b"Alice: locked msg1 = ")
s1 = int(r.recvline().strip().decode())
r.recvuntil(b"Bob: locked msg2 = ")
s12 = int(r.recvline().strip().decode())
r.recvuntil(b"Alice: unlocked msg3 = ")
s2 = int(r.recvline().strip().decode())

r.sendline(b"4")
r.recvuntil(b"Alice: locked msg1 = ")
t1 = int(r.recvline().strip().decode())
r.recvuntil(b"Bob: locked msg2 = ")
t12 = int(r.recvline().strip().decode())
r.recvuntil(b"Alice: unlocked msg3 = ")
t2 = int(r.recvline().strip().decode())

def clear_small_factors(num):
for i in range(2,10000):
while(num % i == 0):
num //= i
return num
n = clear_small_factors(GCD(s1^2-t1,s2^2-t2))

#part3 DLP
F = Zmod(n)
e1 = discrete_log_lambda(F(t1),F(4),(10^14, 10^15))
e2 = discrete_log_lambda(F(t2),F(4),(10^14, 10^15))

d,x,y = gcdext(e1,e2)
flag = pow(m1,x,n)*pow(m2,y,n) % n
print(long_to_bytes(int(flag)))

#NSSCTF{9be90567-ffcd-400a-971f-b906f5d73706}



MyErrorLearn

题目描述:

1
Reach Learn With Error. Reach My Xenny Oracle.

题目:

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
from Crypto.Util.number import *
import random, os
from gmpy2 import *
flag = os.getenv('DASFLAG')

p = random.getrandbits(1024)

print('> mod =', p)
secret = random.randint(1, p-1)

def XennyOracle():
r = getPrime(512)
d = invert(secret+r, p) - getPrime(246)
print('> r =', r)
print('> d =', d)

def task():
for _ in range(3):
op = int(input())
if op == 1:
XennyOracle()
elif op == 2:
ss = int(input())

if ss == secret:
print('flag: ', flag)

try:
task()
except Exception:
print("Error. try again.")

很简洁的题目(接下来的几个题目都是这个风格,非常喜欢)。题目首先生成一个1024bit的随机数p,并且生成一个小于p的secret值,然后进入一个最多三次的交互,每次交互可以:

  • 输入1,可以进入XennyOracle,获取一组数据
  • 输入2,可以核验secret值,如果输入值等于secret则得到flag

那么也就是要输入两次1,用获取的两组数据解出secret,然后输入2获得flag。那么接下来就看看 XennyOracle究竟返回什么样的数据供使用。可以发现,他先生成512bit的素数r,然后按如下式子计算出d:

并返回给我们r和d的值,其中,e是一个246bit的素数。

由于我们有两组数据,所以我们可以列出如下式子:

而突破点就在于,两个e,也就是error,都是246bit的数量级,相较于p的1024bit来说都是小量。因此,如果联立两个方程消去secret后,就可以构造出一个可以二元copper的式子。具体来说消元过程如下。

首先把secret前的系数配相同:

然后简单作差就可以消去secret:

这就是二元copper的式子了,求出e1、e2后代入任意一个式子就能求出secret,从而获得flag。

但是由于题目p的生成方式是getrandbits(1024),所以p并不一定是个素数,因此求逆的操作不一定能成功,所以靶机返回”Error. try again.”也是常有的事,多交互几次就好。

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
from Pwn4Sage.pwn import *
from Crypto.Util.number import *
import itertools

#part1 get number
sh = remote("node4.anna.nssctf.cn",28597)
sh.recvuntil(b"> mod =")
p = int(sh.recvline().strip().decode())
r = []
d = []
for i in range(2):
sh.sendline(b"1")
sh.recvuntil(b"> r =")
r.append(int(sh.recvline().strip().decode()))
sh.recvuntil(b"> d =")
d.append(int(sh.recvline().strip().decode()))

#part2 bivariate copper
def small_roots(f, bounds, m=1, d=None):
if not d:
d = f.degree()
R = f.base_ring()
N = R.cardinality()
f /= f.coefficients().pop(0)
f = f.change_ring(ZZ)
G = Sequence([], f.parent())
for i in range(m + 1):
base = N ^ (m - i) * f ^ i
for shifts in itertools.product(range(d), repeat=f.nvariables()):
g = base * prod(map(power, f.variables(), shifts))
G.append(g)
B, monomials = G.coefficient_matrix()
monomials = vector(monomials)
factors = [monomial(*bounds) for monomial in monomials]
for i, factor in enumerate(factors):
B.rescale_col(i, factor)
B = B.dense_matrix().LLL()
B = B.change_ring(QQ)
for i, factor in enumerate(factors):
B.rescale_col(i, 1 / factor)
H = Sequence([], f.parent().change_ring(QQ))
for h in filter(None, B * monomials):
H.append(h)
I = H.ideal()
if I.dimension() == -1:
H.pop()
elif I.dimension() == 0:
roots = []
for root in I.variety(ring=ZZ):
root = tuple(R(root[var]) for var in f.variables())
roots.append(root)
return roots
return []

PR.<e0,e1>=Zmod(p)[]
f = (r[0]-r[1])*(d[0]+e0)*(d[1]+e1) + d[0] + e0 - d[1] - e1
e0,e1 = small_roots(f,bounds=(2^246,2^246))[0]

#part3 get flag
secret = (inverse(int(d[0]+e0),p)-r[0]) % p
sh.sendline(b"2")
sh.sendline(str(secret).encode())
sh.recvline()
sh.recvline()
print(sh.recvline())

#NSSCTF{87cfab12-9e93-4e8d-948b-21e2b4433696}



MyErrorLearnTwice

题目描述:

1
Cross my XennyOracle again.

题目:

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
from Crypto.Util.number import *
import random, os
from gmpy2 import *
flag = os.getenv('DASFLAG')

p = random.getrandbits(1024)

print('> mod =', p)
secret = random.randint(1, p-1)

def XennyOracle():
r = getPrime(512)
d = invert(secret+r, p) - getPrime(328)
print('> r =', r)
print('> d =', d)

def task():
for _ in range(16):
op = int(input())
if op == 1:
XennyOracle()
elif op == 2:
ss = int(input())

if ss == secret:
print('flag: ', flag)

try:
task()
except Exception:
print("Error. try again.")

这个题目就是上一个题目的进阶,他与上一个题目的区别在于:

  • error从246bit提升到了328bit
  • 可以获得的数据从最多2组变成了最多15组

可以想见这个数量级直接二元copper肯定不行了,但是328bit相较于1024bit来说,e是小量的这一性质依然没有变。而小量+多组数据的形式很容易就想到用格来解决。我们记获得的数据为 $r_i,d_i (0 \le i \le 14)$ ,那么用类似HNP的构造方式,将1-14组数据与第0组数据,做上一题一样的消元,得到14个如下形式的模等式:

其中ei、e0均是未知小量,为了更清楚地构造出格的结构,需要合并同类项得到对应系数:

为了看上去方便,把其中所有系数分别记作:

那么整个式子就变成:

写成等式形式:

然后用这个式子去造格就可以了,造出来的形式是:

这个格具有如下线性关系:

然后就是配平系数,使规约出来的向量数量级相当,同时可以在最后n列乘上大系数T保证规约出0。LLL得到目标向量后就能得到所有ei,仍然是代入任意一个式子就可以算出secret,并发送给靶机得到flag。

p不是素数导致逆元可能不存在的问题依然存在,所以可能还是要多交互几次。

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 Pwn4Sage.pwn import *
from Crypto.Util.number import *
import itertools

#part1 get number
sh = remote("node4.anna.nssctf.cn",28544)
sh.recvuntil(b"> mod =")
p = int(sh.recvline().strip().decode())
r = []
d = []
enum = 15
for i in range(enum):
sh.sendline(b"1")
sh.recvuntil(b"> r =")
r.append(int(sh.recvline().strip().decode()))
sh.recvuntil(b"> d =")
d.append(int(sh.recvline().strip().decode()))
A = [r[0]-r[i] for i in range(1,enum)]
B = [d[i]*(r[0]-r[i])+1 for i in range(1,enum)]
C = [d[0]*(r[0]-r[i])-1 for i in range(1,enum)]
D = [d[0]*d[i]*(r[0]-r[i])+d[0]-d[i] for i in range(1,enum)]

#part2 use Lattice
T = 2^1000
L = Matrix(ZZ,3*enum-1,3*enum-1)
for i in range(enum-1):
L[i,i] = 1
L[i,-(enum-1)+i] = A[i]*T

L[enum-1,-(enum-1)+i] = B[i]*T
L[i+enum,-(enum-1)+i] = C[i]*T

L[2*enum-1,-(enum-1)+i] = D[i]*T
L[i+2*enum,-(enum-1)+i] = p*T
for i in range(enum):
L[i+enum-1,i+enum-1] = 2^328
L[2*enum-1,2*enum-1] = 2^(328*2)

res = L.LLL()[0]
#e0 = int(res[14])//(2^328)
e0 = GCD(res[0],res[14])

#part3 get flag
secret = (inverse(int(d[0]+e0),p)-r[0]) % p
sh.sendline(b"2")
sh.sendline(str(secret).encode())
sh.recvline()
sh.recvline()
print(sh.recvline())

#NSSCTF{d15f053f-8bf0-4dc2-a299-017841518c7e}



MyCurveErrorLearn

题目描述:

1
Reach My XennyOracle base elliptic curve

题目:

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
from Crypto.Util.number import *
import os

flag = os.getenv('FLAG')

p = getPrime(1024)
a = getPrime(200)
b = getPrime(200)
E = EllipticCurve(GF(p), [a, b])
R = E.random_element()
P = E.random_element()

print('> mod =', p)
print('> a =', a)
print('> b =', b)
print(f'> R = ({R[0]}, {R[1]})', )

def XennyOracle(t):
O = P + t*R
return int(O[0]) - getPrime(163)


def task():
for _ in range(30):
op = int(input())
if op == 1:
XennyOracle(int(input()))
elif op == 2:
ss = int(input())

if ss == P[0]:
print('flag: ', flag)

try:
task()
except Exception:
print("Error. try again.")

仍然与前面的题目很像,只是背景换成了曲线。

题目首先会随机生成一条椭圆曲线,并发送给我们曲线的所有参数:

然后从曲线上取两个随机点R、P,并给出我们R的坐标,至此数据准备工作就全部结束,进入交互部分。

在交互部分,我们有最多30次交互机会,每一次仍然有两个选择:

  • 输入1,进入XennyOracle
  • 输入2,可以核验P点的横坐标,如果输入值与P横坐标相等则得到flag

目的也很明确,用前面最多29组数据来求出P的横坐标,从而获取flag。那么接下来看看这题里的XennyOracle又做了什么。每次进入XennyOracle,我们可以输入一个值t,靶机会计算一个O点:

但是靶机最终返回的是:

其中x(O)代表取O的横坐标,e是一个163bit的小量。

做了上一个题目也有一些经验,毕竟椭圆曲线其实本质上也就是模p下的一个多项式,所以这题依然是小量+多组数据的形式,肯定是要用多项式造格来解。而很自然地会先想到发送0-28给靶机,得到:

我们把点tR记作Qt,由于t的值以及R点我们都有,所以Qt点的坐标我们也知道,那么上式可以写作:

那么接下来就是根据点加法的计算表达式来构造等式:

即:

然后移项转化一下就能得到关于yP,xP,xO的多项式。

但是这样显然有冗余项,因为一个点在曲线上的横纵坐标是有椭圆曲线方程作支撑的,yP显然可以用xP表示出来。同时,这样构造多项式,不同的项会很多,难以构造一个简洁明了的格。

然后就想到椭圆曲线上点有如下性质:

也就是说,两个乘数互为相反数的倍点,其横坐标相等而纵坐标相反,而这就为消去纵坐标提供了一种便利。我们可以考虑按如下形式发送t:

  • 第一次发送0,得到的其实就是受干扰的P点横坐标
  • 后面依次成对发送不同的t,-t,每次得到一对:

对于得到的每一对ht、h(-t),我们把error移到左边:

那么两式相加,由于有刚才提到的横坐标相等而纵坐标相反这一特点,所以对于等式右侧而言就是:

即:

这样一来,化简后分子就只留有yP和yQ的二次形式,就可以用椭圆曲线的方程将他们完全转化掉,变成只关于横坐标的等式:

也就是:

而对于xP,我们在第一次发送0时,也得到了一组关于他的等式:

把这个代入上面的xP中就得到:

这样未知量就只剩下所有e了,化简之后合并同类项,就得到关于所有e的等式,简化出来的形式是:

这也是题目论文里的构造(其实上面的题目也是有论文的,但是其实这些题目要自己构造出格,也并不算极其困难的事情,只是化简过程比较繁琐且易错)。其中各项系数为:

1
2
3
4
5
A = [h[i] - 2*xQ[i] for i in range(1,n)]
A0 = [2*(h[0]-xQ[i]) for i in range(1,n)]
B = [2*(h[i]*(h[0]-xQ[i])-2*h[0]*xQ[i]-a-xQ[i]^2) for i in range(1,n)]
B0 = [(h[0]-xQ[i])^2 for i in range(1,n)]
C = [h[i]*(h[0]-xQ[i])^2-2*((h[0]^2+a)*xQ[i]+(a+xQ[i]^2)*h[0]+2*b) for i in range(1,n)]

然后就可以构造一个如下形式的格(构造的大体思路可以说与上一个题目完全相同):

这个格具有如下线性关系:

当然,这次要给前面2n+3列配对应系数,使目标向量中各项数量级相当。规约出目标向量后,用其中的e0加上h0就得到P的正确横坐标,发送给靶机就能得到flag了。

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
from Pwn4Sage.pwn import *
from Crypto.Util.number import *

#part1 get number
sh = remote("node4.anna.nssctf.cn",28005)
sh.recvuntil(b"> mod =")
p = int(sh.recvline().strip().decode())
sh.recvuntil(b"> a =")
a = int(sh.recvline().strip().decode())
sh.recvuntil(b"> b =")
b = int(sh.recvline().strip().decode())
sh.recvuntil(b"> R =")
R = eval(sh.recvline().strip().decode())
E = EllipticCurve(GF(p), [a, b])
R = E(R)

#part2 send t and -t to construct poly
h = []
xQ = [0]
#first get error_P
sh.sendline(b"1")
sh.sendline(b"0")
h.append(int(sh.recvline().strip().decode()))

n = 15
for t in range(1,n):
sh.sendline(b"1")
sh.sendline(str(t).encode())
h1 = int(sh.recvline().strip().decode())
sh.sendline(b"1")
sh.sendline(str(-t).encode())
h2 = int(sh.recvline().strip().decode())
h.append(h1+h2)

xQ.append(int((t*R)[0]))

A = [h[i] - 2*xQ[i] for i in range(1,n)]
A0 = [2*(h[0]-xQ[i]) for i in range(1,n)]
B = [2*(h[i]*(h[0]-xQ[i])-2*h[0]*xQ[i]-a-xQ[i]^2) for i in range(1,n)]
B0 = [(h[0]-xQ[i])^2 for i in range(1,n)]
C = [h[i]*(h[0]-xQ[i])^2-2*((h[0]^2+a)*xQ[i]+(a+xQ[i]^2)*h[0]+2*b) for i in range(1,n)]

#part3 use poly to get Lattice and LLL
delta = 2^163
n = n-1
L = Matrix(ZZ,3*n+3,3*n+3)

L[0,0] = delta^3
for i in range(n+1):
L[i+1,i+1] = delta^2
for i in range(n+1):
L[i+n+2,i+n+2] = delta
for i in range(n):
L[i+2*n+3,i+2*n+3] = p

for i in range(n):
L[0,i+2*n+3] = C[i]
L[1,i+2*n+3] = B[i]
L[2+i,i+2*n+3] = B0[i]
for i in range(n):
L[n+2,i+2*n+3] = A[i]
L[n+2+1+i,i+2*n+3] = A0[i]

res = L.LLL()[0]

#part4 get flag
e0 = int(GCD(res[1],res[n+2]) // delta)
print(isPrime(e0))
xP = h[0] + e0

sh.sendline(b"2")
sh.sendline(str(xP).encode())
print(sh.recvline())

#NSSCTF{676bdb2a-791d-466b-83e2-d54a2b3f64ab}

其实这题目格看着复杂,但其实主要难度在于繁琐的化简运算得到多项式,造格是化简正确后水到渠成的事情。同时,要想到发送t和-t来消去y,这一步也很关键。

想偷懒的话可以直接照着论文复现(包括上面的题目也是),不过自己造一造格其实也挺有乐趣的:

https://www.math.auckland.ac.nz/~sgal018/BarakShaniPhD.pdf



MyOracleTwice

题目描述:

1
Contact XennyOracle again.

题目:

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
from Crypto.Util.number import *
import random, os
from gmpy2 import *
flag = os.getenv('DASFLAG')

mod = random.getrandbits(1024)

# print('> mod =', mod)

def XennyOracle():
m = random.getrandbits(40)
e = random.getrandbits(40)
c = powmod(m, e, mod)
print('> c =', c & 0xffffffff)
msg = int(input('Input r:'))

if m == msg:
return True
return False

def task():
cnt = 0
while True:
if XennyOracle():
cnt += 1

if cnt == 100:
print('flag: ', flag)

task()

我只是明白这一题的思路,但这一题的脚本说实话感觉会比较麻烦,凭我的功力一时半会儿写不出来,因此就简单说一下大概思路好了。

题目仍然是用getrandbits(1024)生成一个模数n,并且也不发送给我们,然后就进入了不限次数的交互中。每次交互会:

  • 用getrandbits(40)生成m
  • 用getrandbits(40)生成e
  • 计算:
  • 将c的低32位发送给我们
  • 有一个核验机会,可以输入一个值,如果值等于m的话cnt就会加一,cnt达到100则获得flag

很明显的一点是,这个题目一直在用getrandbits()这个方法来生成伪随机数,而众所周知,getrandbits()用的是MT19937来生成随机数的,掌握足够的状态就可以往后预测随机数。所以这个题目就是想办法从给的信息中,去推出一个完整的624x32的state,然后就可以向后预测随机数了。

但问题就在于,模数n我们也不知道,我们唯一能获得的信息就是每次交互的c的低32位而已,那怎么才能获得随机数的bit信息呢?

答案就是:如果我们随机到的模数n是一个偶数(当然我们是没有办法知道他是不是偶数的,就碰那个二分之一的概率),那么对于运算:

c不会改变m的奇偶性,也就是说,c的LSB就是m的LSB。这也就等价于:每次交互我们可以获得m的最后一个比特。

而MT19937的整个运算过程都是线性的,因此可以用矩阵方程来表示出初始state和后面任意比特的线性关系。具体来说,初始state是624x32个比特位,我们把它展开成为一个长为624x32,也就是19968的向量:

而对于getrandbits()方法,他获取随机数的单位是32bit,如果获取的bit不是32的整数倍,那么他会获取32的整数倍个bit并截断。这也就是说,我们可以定位每一次交互中,m的最低比特在哪一个新state的哪一个位置。那么对于任意一个我们已知的m的最后一bit,记作mi,它都可以看作是初始state经过某个线性运算得到的结果,也就可以用矩阵方程表示:

其中ti组成的向量是未知的线性表达式对应的向量。而一旦我们收集到19968个m的最低bit,我们就可以把上方的矩阵方程写成一个满秩的矩阵方程:

把他抽象出来先写作:

而我们现在只有M,我们的目标是求出X也就是初始state,这样就可以预测之后的所有随机数。为此我们需要想办法求得矩阵T,如果能求出T,我们就可以直接求解上面的矩阵方程得到X了。

因此现在的问题就在于如何求出T,这里需要采用一种选择明文攻击的方法(类似于黑盒测试),具体来说,我们选择:

作为X向量也就是初始state,然后用MT19937去生成对应位置的M向量,就有:

而之所以这样选择明文,是因为可以发现,这样得到的M1向量其实就是T的第一行。那么接下来,如法炮制继续选择:

这样就能依次得到T的所有行从而构建出完整的T矩阵,此时用我们在题目中获取的M向量去解矩阵方程就能得到初始state,然后就从初始state开始往后预测随机数,一直预测到我们当前产生m的这个state,然后预测成功100次就能拿到flag了。

但是可想而知这个脚本应该不是很好写,所以exp就暂时放弃,先懂个思路。

(其实是想偷懒,等以后偷个别的师傅的exp来用(′@ω@‵))

如果你对MT19937还有其他的疑问,有两篇非常详细的文章可以参考:

MT19937 - Cryptography-Wiki

浅析MT19937伪随机数生成算法-安全客 - 安全资讯平台 (anquanke.com)



总结

昨年的西湖论剑是我打的第一场比赛,当时python也不会写,文件末尾的16进制隐写也不了解,就和室友一起蹭进了学长的队伍。那天上午,我和室友努力了好一会儿把签到做了出来,在那之后我自己到处查资料,捣鼓了一天MP3隐写那个题目,最后也没弄出个名堂,比赛也稀里糊涂之间就结束了。

虽然打完之后,一段时间内也没有入坑ctf(差不多是又被室友拉着打了NKCTF之后,才真正决定跨入ctf的大门),但是那场西湖论剑仍然是印象非常深刻、对我来说也很有纪念意义的一场比赛。而正好现在放寒假,我也了解了一些crypto知识并且掌握了一些技能,就复现了一下去年Xenny师傅出的几个题目。

入坑ctf差不多10个多月的时间里,学习密码,和室友、学长一起打比赛,研究题目,结识志同道合的师傅,这些都是非常美好的回忆,我想就算以后不打ctf的时候也会常常想起这段时光。新一届的西湖论剑马上就来了,希望这一次能有一个不错的发挥。