Posted on Edited on In Word count in article: 4.4k Reading time ≈ 4 mins.

该更新更新blog了，总的来说今年体验不如去年，能学到东西的除了Card Shark的MT19937通用方法外，没啥新鲜的了

Choose_U_Flag

NTRU但不完全对。也没理解到出题人的意思，而且似乎题目的NTRU也有点问题。但不影响直接非预期解决。

题目流程挺简单的，服务端随机生成一个12bytes的可打印字符串，然后用NTRU加密，加密以后把密文coefficient发回来。

服务端提供了一次解密服务，但要求我们上传的密文coefficient不能是他发过来的那个，也就是说不能直接解密刚刚发回来的密文

对发送的密文的判断只是简单的判断和random_key的系数是否完全相同。哥们直接找个系数加个64不就不同了，反正到时候算的时候就被模掉了….

事实上我还可以旋转密文，还可以LLL日私钥，反正挺多解法的，就是不知道预期该是怎样的

exp

没有exp，key_coefficients复制下来找个你觉得喜欢的数字把他加个64发过去就拿到random_key了

有没有可能预期就是这样呢

Compare

题目要我们先传个表达式上去，这个表达式得够油，油到后面自己能根据，来控制这个表达式的True of False。

考的就是同态。看看加密

Encrypt：

所以计算，解密出来的就是了，但由于mod的存在让结果永远都是整数了。

n是512位的 所以如果 那么 大概率是小于 的，而 那大概率是大于的

所以我们传expr = MSG - 2 ** 511 < 0，每轮算一次发过去，服务器那边eval()的内容就会变成

这个式子与的正确性大概率是一样的了。

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from pwn import *
from Crypto.Util.number import getPrime, getRandomNBitInteger, inverse
import re

CHALLENGE_ID = ''
p = remote(CHALLENGE_ID + '.2022.capturetheflag.fun', 1337, ssl=True)
resp = p.recvuntil("expr:")
p.sendline('MSG - 2 ** 511 < 0')
for _ in range(100):
    resp = p.recvuntil("msg = ")
    n = int(re.findall(r'n = (.*)\n',resp.decode())[0])
    a = int(re.findall(r'a = (.*)\n',resp.decode())[0])
    b = int(re.findall(r'b = (.*)\n',resp.decode())[0])
    s = (a * inverse(b,n * n)) % (n * n)
    p.sendline(str(s))
print(p.recv(1024))

Card Shark

这题算是比较有意思的一题了（全靠其他题衬托。

就是单纯的日MT19937，通过前面的轮次来获得getrandbits()的输出，利用这些输出来还原生成器内部的状态，从而预测后续的随机数。

这里用到一个利用线性关系构造矩阵的解决办法。

这个办法很牛，理论上只要拿到19968位的输出，就能日烂MT19937，就是需要的时间有一点长。

如果对MT19937有了解过，就知道里面的所有操作线性的，也就是说每一次输出的每一位都是由一开始的624个状态线性变换得来的。

因为每个状态是32位，不妨记初始状态为，那么对于某次输出的某一位，会有

这里的就是一个线性关系。那么，对于19968个输出，可以有一整个矩阵的线性关系对应。

而这个攻击方法的核心就是只与是哪次输出的哪一位有关系。

也就是说，只要我们能知道19968位，并且知道它们都是第几次输出的第几位，就能够还原出。

首先，从到遍历，分别用这19968个状态去生成已知那19968位对应的。这里得到的由于取的都是1，所以它就是的每一行。

通过上面的构造拿到对应的以后，再用我们已知的那19968位去计算得到

然后就是由状态推后面的状态了

参考 https://www.anquanke.com/post/id/205861#h3-9 后面的扩展部分。

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
# sage
from random import Random
from tqdm import tqdm
LENGTH = 19968
mask = '11110000000000000000000000000000' 
# mask长度为32  比如输出的是高4位，那么mask = 11110000000000000000000000000000
knownbits = mask.count('1')
# 生成只有一个1的state
states = []
for i in tqdm(range(LENGTH)):
    state = ['0'] * LENGTH
    state[i] = '1'
    # 每32个组成一个数
    states.append((3,tuple([int(''.join(state[_:_ + 32]),2) for _ in range(0,LENGTH,32)] + [0]),None))
T = Matrix(GF(2),LENGTH,LENGTH)
for i in tqdm(range(LENGTH)):
    R = Random()
    R.setstate(states[i])
    # 利用mask生成向量Z，Z就是T的第i行
    Z = []
    for _ in range(LENGTH // knownbits):
        rd = bin(R.getrandbits(32))[2:].zfill(32)
        for r,j in zip(rd,mask):
            if j == '1':
                Z.append(int(r))
    for z in range(len(Z)):
        T[i,z] = Z[z] 
save(T,'Matrix.sobj')

生成完拿去还原状态就行了。

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
# sage
from random import Random
from tqdm import tqdm
def recoverState(leak):
    x = T.solve_left(vector(leak))
    x = ''.join([str(i) for i in x])
    state = []
    for i in range(624):
        tmp = int(x[i * 32:(i + 1) * 32], 2)
        state.append(tmp)
    return state

def backfirst(state):
    high = 0x80000000
    low = 0x7fffffff
    mask = 0x9908b0df
    tmp = state[623] ^^ state[396]
    if tmp & high == high:
        tmp = mask ^^ tmp
        tmp <<= 1
        tmp |= 1
    else:
        tmp <<= 1
    return int((1 << 32 - 1) | tmp & low), int(tmp & low)


def pwn(leak):
    state = recoverState(leak)
    L = [leak[i] for i in range(100 * knownbits)]
    prng = Random()
    guess1, guess2 = backfirst(state)
    state[0] = guess1
    s = state
    prng.setstate((3, tuple(s + [0]), None))
    g1 = []
    for _ in range(100):
        rd = bin(prng.getrandbits(32))[2:].zfill(32)
        for r,j in zip(rd,mask):
            if j == '1':
                g1.append(int(r))
    if g1 == L:
        print("first")
        prng.setstate((3, tuple(s + [0]), None))
        return prng

    state[0] = guess2
    s = state
    prng.setstate((3, tuple(s + [0]), None))
    g2 = []
    for _ in range(100):
        rd = bin(prng.getrandbits(32))[2:].zfill(32)
        for r,j in zip(rd,mask):
            if j == '1':
                g1.append(int(r))
    if g2 == L:
        print("second")
        print(s + [0])
        prng.setstate((3, tuple(s + [0]), None))
        return prng

T = load('Matrix.sobj')
length = 19968
mask = '11110000000000000000000000000000'
knownbits = mask.count('1')
prng = Random()
leaks = open('state','r').read()
leak = [int(i) for i in leaks]
R = pwn(leak)
# R就是最后还原得到的生成器