糖醋小鸡块的blog
0%

2024-NSSCTF-Round19-Basic-wp-crypto

发表于 分类于 Valine：

出了三道题目，写一下题解。

Neighbors

题目描述：

1
2
3
4
5
6
where are you my neighbor?

hint：
你是我的邻居，那我也是你的邻居吧！
modular polynomial
待求的曲线j不变量与最终曲线是5^4-isogeny的邻居

题目：

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
from Crypto.Util.number import *
from random import *
from secret import flag

m = bytes_to_long(flag)

def nextPrime(p):
    while(not isPrime(p)):
        p += 1
    return p

a = 151
b = 172
p1 = 2^a*5^b - 1
F.<i> = GF(p1^2, modulus = x**2 + 1)
E = EllipticCurve(j=F(1728))

assert E.is_supersingular()

for i in range(50):
    P = E(0).division_points(5)[1:]
    shuffle(P)
    phi = E.isogeny(P[0])
    E = phi.codomain()
    j1 = E.j_invariant()

a = int(j1[0])
b = int(j1[1])
p = nextPrime(a+b)
q = getPrime(p.bit_length())
n = p*q
e = 65537
c = pow(m,e,n)
print("e =",e)
print("n =",n)
print("c =",c)


#leak
path = []
for i in range(4):
    P = E(0).division_points(5)[1:]
    shuffle(P)
    phi = E.isogeny(P[0])
    j1 = phi.codomain().j_invariant()
    while(j1 in path):
        shuffle(P)
        phi = E.isogeny(P[0])
        j1 = phi.codomain().j_invariant()
    path.append(j1)
    E = phi.codomain()

print("j1 =",j1)


#e = 65537
#n = 27660779504321925356006447667320327390150480983648690901006174352749339874518759333831733034192127427897623854124514212301624188883116023679233194726978962252585566329625462410597485158957857003260340456610951535430042915065253353543837935016496092356489028408052863701705400021364167367862977808597173766465657159249607404278555781
#c = 17137574768375613142899612121220754893579308480997275465013572460778148685559737592316898103173913046913093108521865424971517481171364906226416089569353963219436198051916581024399601607752314215085545336295450568344615872394961924295547685771955504826631319190372175753842519822279019714777697711192486128339049294501128261475088218
#j1 = 3298455770740418540320875487876272515859315516778722120913599648146333514148291435827951366406176762948612097557652865226784729596111676446684986604300101971837911163*i + 4537130021779297048213998573445169432922796703632002090410524491881919608982806774072433257149497571183513473757657759960381311229351179660958581657639633158226859944

题目定义了一个素数为$p = 2^{a}5^b-1$的$F_{p^2}$下j=1728的超奇异椭圆曲线，并以该曲线为起点，计算了一个度为$5^{50}$的同源后到达曲线E’，然后以曲线E’的j不变量生成了RSA的素数p，同时生成另一个大素数q，然后将flag进行RSA加密。

然后接下来是泄露信息的过程，具体来说，题目以E’为起点，又计算了一个度为$5^4$的同源，最终到达E’’，并且给出E’’的j不变量j1.

由于在同源图中，根据一个确定的同源的度n(在这个题目中也就是5)，相邻的两个超奇异椭圆曲线的j不变量拥有一个叫做modular polynomial的多项式关系$\Phi_n$，这个关系可以在如下网站找到：

Modular polynomials (mit.edu)

而由于超奇异椭圆曲线的同源一定存在一个对偶同源，也就是对于两条曲线E1、E2，如果E1能够经过一个度为n的同源到达E2，那么E2就一定能经过一个度为n的对偶同源返回E1，所以我们只需要利用modular polynomial去找出E’’的所有5-isogeny的邻居，然后再找这些邻居的5-isogeny的邻居，如此重复四次，就可以找到所有E’’的$5^4$-isogeny的邻居了，然后遍历这些邻居的j不变量去尝试生成p，检查是否能被n整除，就得到了n的分解然后进行RSA解密。

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

def nextPrime(p):
    while(not isPrime(p)):
        p += 1
    return p

#Φ5
def find_neighbors_phi5(X,j_prev=None):
    R.<Y> = PolynomialRing(X.parent())
    Φ5 = (
        X^6
        + Y^6
        - X^5*Y^5 
        + 3720*X^5*Y^4 
        + 3720*X^4*Y^5 
        - 4550940*X^5*Y^3 
        - 4550940*X^3*Y^5
        + 2028551200*X^5*Y^2 
        + 2028551200*X^2*Y^5
        - 246683410950*X^5*Y
        - 246683410950*X*Y^5 
        + 1963211489280*X^5 
        + 1963211489280*Y^5 
        + 1665999364600*X^4*Y^4 
        + 107878928185336800*X^4*Y^3 
        + 107878928185336800*X^3*Y^4 
        + 383083609779811215375*X^4*Y^2 
        + 383083609779811215375*X^2*Y^4
        + 128541798906828816384000*X^4*Y 
        + 128541798906828816384000*X*Y^4  
        + 1284733132841424456253440*X^4
        + 1284733132841424456253440*Y^4
        - 441206965512914835246100*X^3*Y^3  
        + 26898488858380731577417728000*X^3*Y^2 
        + 26898488858380731577417728000*X^2*Y^3 
        - 192457934618928299655108231168000*X^3*Y
        - 192457934618928299655108231168000*X*Y^3 
        + 280244777828439527804321565297868800*X^3
        + 280244777828439527804321565297868800*Y^3
        + 5110941777552418083110765199360000*X^2*Y^2 
        + 36554736583949629295706472332656640000*X^2*Y 
        + 36554736583949629295706472332656640000*X*Y^2        
        + 6692500042627997708487149415015068467200*X^2 
        - 264073457076620596259715790247978782949376*X*Y 
        + 6692500042627997708487149415015068467200*Y^2 
        + 53274330803424425450420160273356509151232000*X 
        + 53274330803424425450420160273356509151232000*Y 
        + 141359947154721358697753474691071362751004672000
    )

    res = Φ5.roots(multiplicities=False)
    if(j_prev == None):
        return res
    else:
        return list(set(res) - set([j_prev]))
    

a = 151
b = 172
p1 = 2^a*5^b - 1
F.<i> = GF(p1^2, modulus = x^2 + 1)
e = 65537
n = 27660779504321925356006447667320327390150480983648690901006174352749339874518759333831733034192127427897623854124514212301624188883116023679233194726978962252585566329625462410597485158957857003260340456610951535430042915065253353543837935016496092356489028408052863701705400021364167367862977808597173766465657159249607404278555781
c = 17137574768375613142899612121220754893579308480997275465013572460778148685559737592316898103173913046913093108521865424971517481171364906226416089569353963219436198051916581024399601607752314215085545336295450568344615872394961924295547685771955504826631319190372175753842519822279019714777697711192486128339049294501128261475088218
j1 = 3298455770740418540320875487876272515859315516778722120913599648146333514148291435827951366406176762948612097557652865226784729596111676446684986604300101971837911163*i + 4537130021779297048213998573445169432922796703632002090410524491881919608982806774072433257149497571183513473757657759960381311229351179660958581657639633158226859944

set1 = find_neighbors_phi5(j1)

set2 = []
for k in set1:
    set2 += find_neighbors_phi5(k)
set2 = set(set2)

set3 = []
for k in set2:
    set3 += find_neighbors_phi5(k)
set3 = set(set3)

set4 = []
for k in set3:
    set4 += find_neighbors_phi5(k)
set4 = set(set4)


for k in set4:
    a = int(k[0])
    b = int(k[1])
    p = nextPrime(a+b)
    if(n % p == 0):
        q = n // p
        d = inverse(e,(p-1)*(q-1))
        print(long_to_bytes(int(pow(c,d,n))))
        break


#NSSCTF{try_to_find_5-isogeny_neighbors_4nd_F@ctor_n}



3DES?

题目描述：

1
2
3
4
5
6
7
三个DES

hint:
怎么爆破会好一点呢？
correlation attack
打印Geffe生成器的真值表进行观察
DES的密钥似乎并不是每一位都有用

题目：

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
from Crypto.Util.number import *
from Crypto.Cipher import DES
from Crypto.Util.Padding import pad
from secret import flag
from random import *

class DEStream():
    def __init__(self):
        self.table = '0123456789'
        self.key = ("".join([choice(self.table) for i in range(8)])).encode()
        self.seed = b"!NSSCTF!"
        self.des = DES.new(self.key,mode=DES.MODE_ECB)

    def next(self):
        self.seed = (self.des).encrypt(self.seed)
        return bytes_to_long(self.seed) & 1
    
    def enc(self,m):
        return (self.des).encrypt(m)

def combine(x1,x2,x3):
    return (x1&x2)^(x2&x3)^x3

des1 =  DEStream()
des2 =  DEStream()
des3 =  DEStream()

output = ""
for i in range(2000):
    output += str(combine(des1.next(),des2.next(),des3.next()))

cipher = des1.enc(pad(flag,8))
cipher = des2.enc(cipher)
cipher = des3.enc(cipher)

print("output =",output)
print("cipher =",cipher)


'''
output = 10110101110110001000111000110101000110111100110110011010000010001110010010101111000101101100101011110101111011000000001110011001011001110010010000001010111101011110011011000111011101010000111011011110010001101001110010111100101111110001000110000110111010100010111010000110000001011010111100100011011010001101001001100000000001100101111110110011000101101100110101010000010101100001010010000010010011001011110000010101111000001110010100110110111011001010111111100010100111000110110010101101000001011000101110101100000110110000101101010100101010000100110011011110100110111101101100011100011100101000000100000000101001100101001010101001000110011110110000111111001111101110110110100001010000100110010100010101000001010001111100000010100000101101111010010011010100011000100111001101100001011111001100111101100011001001000001000100011011010000001101110000001111011000111000011001010011100110110111111101010110101110110110000101110110000000101110000011110101001100010000101001010010000011110111100001101011001110100011101111011001010110111000010000111000010010111111111000111100110000100100100011111100101111011001000000011000001100110100011100110010100010001110011001011100101001101001100110001010000011001001101010010101001111110100010111000000101011000100100000010011111011001011010001101101101001100111010110101001001111000111000001000001010000001100101110110010111111001001011111111000100110011100011000111011010100001011010000011110101001110101010011111000100010011010000101011100110110101000100010010001011101010010100100001011010101000010000110001100100010000010111110011111000011000100011001110001100100111111101000001001101110000100101011010010011001100100100100010000101100111001100110000110010001001010011011011101011010100110001100001000111010000100100100010110111100000100111010101100000111010111011000100011010111110010010000110111111001101000011111000111100110111110011110101001100110111000111111011010011100011000010010011010100000100110010011111011110111011111011011110010110000110011110000
cipher = b'\xe3\t\x13\xe2\x8b\xd1\xdeql\x94F\xb5}\xb8d\xfa~\x06&~\x8f\xcb-&\xf3q/j\xd3\xbe\x1f\xef\x18\x84hn\x1c[t\x03\x10\xb8\x8e?\x89\x8b\x00\xc5\xb9`5E\xeaC\xe9,'
'''

题目分别初始化三个DES，其密钥由8个数字组成。而每个DES执行的其实是流密钥的功能，也就是对于他的每一次输出，都是将种子进行一次DES加密得到新的种子，并且取其LSB作为该次流密钥的输出。

但是题目是将三个DES的流密钥进行combine之后输出的，共给出2000位输出序列，要求还原三个DES的密钥来解密得到flag。

注意到题目combine的方式是：

这其实是一个Geffe生成器，而他一个很脆弱的地方在于：他的输出与x1、x3都有相关性。打印真值表可以发现，对于Geffe生成器的每一位输出，都有75%的概率与x1相同或与x3相同，所以我们就可以分开爆破DES1和DES3的密钥，去观测其输出是否与200位给定的序列有接近75%的相似度，来判断密钥的正确性。

有了这个思路过后，剩下的问题就是如何爆破。由于题目的DES密钥均为8位数字组成，所以需要爆破的可能组合共有10^8种，复杂度依然比较高。但是需要注意到，DES的八字节密钥实际参与加密的只有56位，因为每个第8bit实际上本来是作为校验位的，在产生轮密钥之前就会被去掉，因此实际需要爆破的仅有5^8种可能。同时，由于正确密钥的输出应该和output有75%左右的相似度，因此200个比特基本上已经很难再有误判的可能性，并不需要把给出的2000bit全部用上，所以就只需要两分多钟就可以爆破出来DES1、DES3的密钥了。

有了正确的DES1、DES3的密钥，又有种子”!NSSCTF!”，就有了他们对应的两百位输出x1、x3，那么爆破x2就只需要看combine之后的结果是否与output完全相等即可。同时，由于密钥错误但依然连续50位均相等的概率已经非常低，所以只取前五十位参与爆破可以节省时间。

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
from Crypto.Util.number import *
from Crypto.Cipher import DES
from itertools import product
from tqdm import *

output = "10110101110110001000111000110101000110111100110110011010000010001110010010101111000101101100101011110101111011000000001110011001011001110010010000001010111101011110011011000111011101010000111011011110010001101001110010111100101111110001000110000110111010100010111010000110000001011010111100100011011010001101001001100000000001100101111110110011000101101100110101010000010101100001010010000010010011001011110000010101111000001110010100110110111011001010111111100010100111000110110010101101000001011000101110101100000110110000101101010100101010000100110011011110100110111101101100011100011100101000000100000000101001100101001010101001000110011110110000111111001111101110110110100001010000100110010100010101000001010001111100000010100000101101111010010011010100011000100111001101100001011111001100111101100011001001000001000100011011010000001101110000001111011000111000011001010011100110110111111101010110101110110110000101110110000000101110000011110101001100010000101001010010000011110111100001101011001110100011101111011001010110111000010000111000010010111111111000111100110000100100100011111100101111011001000000011000001100110100011100110010100010001110011001011100101001101001100110001010000011001001101010010101001111110100010111000000101011000100100000010011111011001011010001101101101001100111010110101001001111000111000001000001010000001100101110110010111111001001011111111000100110011100011000111011010100001011010000011110101001110101010011111000100010011010000101011100110110101000100010010001011101010010100100001011010101000010000110001100100010000010111110011111000011000100011001110001100100111111101000001001101110000100101011010010011001100100100100010000101100111001100110000110010001001010011011011101011010100110001100001000111010000100100100010110111100000100111010101100000111010111011000100011010111110010010000110111111001101000011111000111100110111110011110101001100110111000111111011010011100011000010010011010100000100110010011111011110111011111011011110010110000110011110000"
cipher = b'\xe3\t\x13\xe2\x8b\xd1\xdeql\x94F\xb5}\xb8d\xfa~\x06&~\x8f\xcb-&\xf3q/j\xd3\xbe\x1f\xef\x18\x84hn\x1c[t\x03\x10\xb8\x8e?\x89\x8b\x00\xc5\xb9`5E\xeaC\xe9,'

def compare(str1,str2):
    assert len(str1) == len(str2)
    count1 = 0
    for i in range(len(str1)):
        if(str1[i] == str2[i]):
            count1 += 1
    if(count1 / len(str1) > 0.7):
        return True
    else:
        return False

#part1 remove redundant data of table
table = "0123456789"
prefix_set = []
for i in table:
    temp = bin(ord(i) // 2)[2:].zfill(7)
    if(temp not in prefix_set):
        prefix_set.append(temp)


#part2 bruteforce LFSR1.key and LFSR3.key
key13 = []
for i in tqdm(product(prefix_set,repeat = 8),total=5**8):
    temp = ''.join(c + '0' for c in list(i))
    key = long_to_bytes(int(temp,2))

    DES1 = DES.new(key,mode=DES.MODE_ECB)

    seed = b"!NSSCTF!"
    output1 = ""
    for j in range(200):
        seed = DES1.encrypt(seed)
        output1 += str(bytes_to_long(seed) & 1)
    if(compare(output[:200],output1)):
        key13.append(key)


#part3 bruteforce LFSR2.key and decrypt
def combine(x1,x2,x3):
    return (x1&x2)^(x2&x3)^x3


#DES1 = DES.new(key13[0],mode=DES.MODE_ECB)
#DES3 = DES.new(key13[1],mode=DES.MODE_ECB)
DES1 = DES.new(key13[1],mode=DES.MODE_ECB)
DES3 = DES.new(key13[0],mode=DES.MODE_ECB)
for i in tqdm(product(prefix_set,repeat = 8),total=5**8):
    temp = ''.join(c + '0' for c in list(i))
    key = long_to_bytes(int(temp,2))

    DES2 = DES.new(key,mode=DES.MODE_ECB)

    seed1 = b"!NSSCTF!"
    seed2 = b"!NSSCTF!"
    seed3 = b"!NSSCTF!"
    judge = True
    for j in range(50):
        seed1 = DES1.encrypt(seed1)
        seed2 = DES2.encrypt(seed2)
        seed3 = DES3.encrypt(seed3)
        temp = combine(bytes_to_long(seed1) & 1 , bytes_to_long(seed2) & 1 , bytes_to_long(seed3) & 1)
        if(str(temp) != output[j]):
            judge = False
            break

    if(judge):
        flag = DES3.decrypt(cipher)
        flag = DES2.decrypt(flag)
        flag = DES1.decrypt(flag)
        print(flag)
        break


#NSSCTF{Y0U_C411_Th15_3DES???_;D_J4st_U53_CorreL@tion!}



Decision

题目描述：

1
2
3
4
5
6
7
Make your decision

hint:
初始状态好像并不是很随机
初始状态在模p下显得很小
MRG的递推过程可以写成矩阵形式
尝试利用该矩阵去LLL得到初始状态

题目：

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
from Crypto.Util.number import *
from random import *
from secret import flag
import string

class MRG:
    def __init__(self,para_len,p):
        self.init(para_len,p)

    def next(self):
        self.s = self.s[1: ] + [(sum([i * j for (i, j) in zip(self.a, self.s)]) + self.b) % self.p]
        return self.s[-1]

    def init(self,para_len,p):
        self.p = p
        self.b = randint(1, self.p)
        self.a = [randint(1, self.p) for i in range(para_len)]
        self.s = [ord(choice(string.printable)) for i in range(para_len)]
    
    def get_params(self):
        return [self.a,self.b,self.s[0]]


flag = bytes_to_long(flag)
flag_bin = bin(flag)[2:]

Round = 2024
A_len = 10
p = getPrime(256)

output = []
for i in flag_bin:
    if(i == "0"):
        temp = MRG(A_len,p)
        for j in range(Round):
            temp.next()
        output.append(temp.get_params())
    else:
        a = [randint(1,p) for i in range(A_len)]
        b = randint(1,p)
        s = randint(1,p)
        output.append([a,b,s])

with open("output.txt","w") as f:
    f.write(str(p))
    f.write(str(output))

题目基于一个系数共10项的MRG(Multiple Recursive Generator)，其递推公式为：

也就是说一个新状态由前十个状态共同决定。

题目的加密流程为：

  • 将flag转为二进制串
  • 依次遍历flag二进制串的每个bit，如果当前bit为0，则生成一个MRG，并且进行2024次迭代后，输出MRG的所有参数，包括系数a、b以及当前状态的第一个量；如果当前bit为1，则完全随机生成a、b、s

也就是说，我们需要判定每一组样本究竟是MRG样本还是随机样本，这有点像一个DLWE问题。但是判别的依据到底是什么？这里就需要注意到一个事实：每个新生成的MRG，其初始状态都是可见字符的ASCII码，这其实表明一个信息，那就是MRG的初始状态都是模p下的小量，所以就会联想到用格求解。

而MRG显然是一个线性的递推关系，因此每一次递推都可以用一个矩阵来表示(这个思路在之前0CTF也出现过)，比如说第一次递推就是：

那么2024次递推就有：

而假设当前bit是0，也就是说我们拥有一个MRG样本的a、b和s2024，那么首先我们就可以构造出上面的递推矩阵：

那么上面的式子可以简化写为：

转置一下就得到：

那么此时我们就拥有了一个关系式为：

由于我们只有最终状态的第一个量，也就是s2024，因此我们也只取L^T的第一列作为线性关系(当然最后一列的1也可以取上)，就得到：

那么就可以造出格M：

其中E是单位阵，O是0矩阵，这个格就具有线性关系：

配上大系数保证最后一列规约出0，然后检查规约出的向量前面是不是都在可见字符范围内，就可以完成该样本是不是MRG的判定了。由于格的维数并不大，所以判定完所有bit也花不了多长时间。

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

#matrix of MRG
def build_iter_Matrix(a,b,p,length):
    L = Matrix(Zmod(p),length+1,length+1)
    for i in range(length-1):
        L[i,i+1] = 1
    for i in range(length):
        L[length-1,i] = a[i]
    L[length-1,-1] = b
    L[-1,-1] = 1

    return L

Round = 2024
A_len = 10
leak_len = 1
p = 
output = 

flag = ""
for i in tqdm(output):
    a,b,s = i[0],i[1],[i[2]]
    L = build_iter_Matrix(a,b,p,A_len)
    L = L^Round
    L = (L.T)[:,:leak_len]
    T = block_matrix(
        [
            [identity_matrix(A_len+1+1),Matrix(ZZ,L).stack(-vector(ZZ,s))],
            [zero_matrix(leak_len,A_len+1+1),identity_matrix(leak_len)*p]
        ]
    )
    Q = diagonal_matrix([1]*(A_len+1+1) + [2^1000]*leak_len)
    T = T*Q
    T = T.LLL()
    T = T/Q
    res = T[0]
    if(abs(res[0]) < 128):
        flag += "0"
    else:
        flag += "1"

print(long_to_bytes(int(flag,2)))


#NSSCTF{D3c1s1on_MRG_I5n'7_diFFiCulT_R1GHT?}