SUSCTF2022 Crypto Writeup

字数统计: 3.2k字   |   阅读时长≈ 17分

2022 SUSCTF nebula战队 crypto部分题解

 

large_case

题目源码：

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
from Crypto.Util.number import *
from secret import message,e

def pad(s):
    if len(s)<3*L:
        s+=bytes(3*L-len(s))
    return s

L=128
p=127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q=145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r=165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
n=p*q*r
c=2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892


assert isPrime(GCD(e,p-1)) and isPrime(GCD(e,q-1)) and isPrime(GCD(e,r-1)) and e==GCD(e,p-1)*GCD(e,q-1)*GCD(e,r-1)
assert len(message)>L and len(message)<2*L
assert b'SUSCTF' in message
m=bytes_to_long(pad(message))

c=pow(m,e,n)
print(c)
'''
2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892
'''

 

没给e，但是给了e的一个条件，由的三个素因子相乘得到。这样e肯定是整除n的阶了，所以考虑用AMM算法在有限域开根，并且e不会很大，否则穷举量很大。首先找找的素因子，取前一百万个素数（再大即使e对了穷举量也不能接受）:

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
# sage
G1=GF(p)
G2=GF(q)
G3=GF(r)
c1=G1(c)
c2=G2(c)
c3=G3(c)
prime_list=primes_first_n(1000000)
p_list=[]
q_list=[]
r_list=[]
phi_p=p-1
phi_q=q-1
phi_r=r-1

for prime in prime_list:
    while (phi_p)%prime==0:
        if prime not in p_list:
            p_list.append(prime)
        phi_p//=prime
        if is_prime(phi_p):
            print("phi_p factored")
    while (phi_q)%prime==0:
        if prime not in q_list:
            q_list.append(prime)
        phi_q//=prime
        if is_prime(phi_q):
            print("phi_q factored")
    while (phi_r)%prime==0:
        if prime not in r_list:
            r_list.append(prime)
        phi_r//=prime
        if is_prime(phi_r):
            print("phi_r factored")

 

然后验证结果c是否满足对应的e次剩余，方法就是直接开n次根，能够直接开出来就是e的可能素因子。sage求解时间太长，就单独试试AMM。

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
e1_list=[]
e2_list=[]
e3_list=[]            
for e1 in p_list:
    try:
        print("Trying: ",e1)
        AMM(c1,e1,p)
        # print(c1.nth_root(e1))
        e1_list.append(e1)
    except:
        pass
    # 757
    
for e2 in q_list:
    try:
        print("Trying: ",e2)
        # AMM(c2,e2,q)
        print(c2.nth_root(e2))
        e2_list.append(e2)
    except:
        pass    

for e3 in r_list:
    try:
        print(e3)
        # AMM(c3,e3,q)
        print("Trying: ",c3.nth_root(e3))
        e3_list.append(e3)
    except:
        pass

最后验证出最小的一个e是：

1
e=757*66553*5156273

 

刚好对应题目的small，little，large三个size，其中我们必须舍弃large size，因为穷举量真的太大了。所以我们必须要找到另外一个可代替的条件，注意到填充条件：

1
2
3
4
5
assert len(message)>L and len(message)<2*L
def pad(s):
    if len(s)<3*L:
        s+=bytes(3*L-len(s))
    return s

 

强行把message填充到3*1024比特，且后面1024比特是已知全零的，这就给了我们一个额外的条件，所以我们完全不用求解关于第三个素数上的有限域开根。由此脚本如下：

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
from Crypto.Util.number import *
from tqdm import tqdm
import random
import time

# About 3 seconds to run
def AMM(o, r, q):
    # start = time.time()
    # print('\n----------------------------------------------------------------------------------')
    # print('Start to run Adleman-Manders-Miller Root Extraction Method')
    # print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    # print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    # print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    # print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            # print('[+] Calculating DLP...')
            j = - discrete_log(a, d)
            # print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c ^ r
    result = o^alp * h
    assert pow(result,r,p)==o
    end = time.time()
    # print("Finished in {} seconds.".format(end - start))
    # print('Find one solution: {}'.format(result))
    return result

def findAllPRoot(p, e):
    print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
    start = time.time()
    proot = set()
    rounds=0
    try:
        while len(proot) < e:
            rounds+=1
            proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
            if rounds%10000==0:
                print("Find %d primitive roots"%len(proot))
    except:
        print("Find roots num : ",len(proot))
        end = time.time()
        print("Finished in {} seconds.".format(end - start))
        return proot
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return proot

def findAllSolutions(mp, proot, cp, p,e):
    print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
    start = time.time()
    all_mp = set()
    for root in proot:
        mp2 = mp * root % p
        assert(pow(mp2, e, p) == cp)
        all_mp.add(mp2)
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return all_mp

def AMM_nth_root(cp,p,e):
    mp = AMM(cp, e, p)
    p_proot = findAllPRoot(p, e)
    return findAllSolutions(mp, p_proot, cp, p,e)

def AMM_nth_root2(cp,p,e):
    G=GF(p)
    mp=G(cp.nth_root(e))
    p_proot = findAllPRoot(p, e)
    return findAllSolutions(mp, p_proot, cp, p,e)

p=127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q=145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r=165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
n=p*q*r
c=2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892
G1=GF(p)
G2=GF(q)
G3=GF(r)
c1=G1(c)
c2=G2(c)
c3=G3(c)
            
ep,eq,er=(757,66553,5156273)
dp=inverse(eq*er,p-1)
dq=inverse(ep*er,q-1)
dr=inverse(ep*eq,r-1)
rp=AMM_nth_root(c1^dp,p,ep)
rq=AMM_nth_root(c2^dq,q,eq)
# rr=AMM_nth_root(c3^dr,r,er)

inc=int(p*q*(2^1024))
for r1 in tqdm(list(rp)):
    for r2 in list(rq):
        m=int(crt([ZZ(r1),ZZ(r2),0],[p,q,2^1024]))
        # print(m.bit_length())
        while m.bit_length()<=3072:
            if b"SUSCTF" in long_to_bytes(m):
                print(long_to_bytes(m))
            m+=inc
# SUSCTF{N0n_c0prime_RSA_c1pher_cAn_a1s0_recover_me33age!!!}

跑完全部结果在我电脑这需要1个多小时，开服务器并行跑，几分钟就出了。

 

 

Ez_Pager_Tiper

data里面文件的名字是日期的base64编码，可以对应文件内容的第一行日期。这样对于每个文件我们知道固定格式开头的18个字节，也就是144比特。这很重要。然后重点关注magic_box里面的操作:

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
class lfsr():
    def __init__(self, seed, mask, length):
        self.length_mask = 2 ** length - 1
        self.mask = mask & self.length_mask
        self.state = seed & self.length_mask

    def next(self):
        next_state = (self.state << 1) & self.length_mask
        i = self.state & self.mask & self.length_mask
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        next_state ^= output
        self.state = next_state
        return output

    def getrandbit(self, nbit):
        output = 0
        for _ in range(nbit):
            output = (output << 1) ^ self.next()
        return output


class generator():
    def __init__(self, lfsr1, lfsr2, magic):
        self.lfsr1 = lfsr1
        self.lfsr2 = lfsr2
        self.magic = magic

    def infinit_power(self, magic):
        return int(magic)

    def malicious_magic(self, magic):
        now = (-magic & magic)
        magic ^= now
        return int(now), int(magic)

    def confusion(self, c1, c2):
        magic = self.magic
        output, cnt = magic, 0
        output ^= c1 ^ c2
        while magic:
            now, magic = self.malicious_magic(magic)
            cnt ^= now >> (now.bit_length() - 1)
            output ^= now
        output ^= cnt * c1
        return int(output)

    def getrandbit(self, nbit):
        output1 = self.lfsr1.getrandbit(nbit)
        output2 = self.lfsr2.getrandbit(nbit)
        return self.confusion(output1, output2)

 

confusion是个很神奇的操作，主要看看这个位运算：(-magic & magic)，相当于：取magic的最低位的一个1对应的数值。比如，它就会得到，也就是4，依此类推。然后我们再看confusion内的操作就很清楚了，while循环内output每次异或的值就是magic从低到高的每一位的数值，也就是出去之后，output的变化等价于：，再关注cnt的值，这个运算：now >> (now.bit_length() - 1)其实是恒为1的数，那么cnt也就是不断在0,1之间跳动。如果magic的二进制表示中有奇数个1，那么cnt就是1，反之为0。那么confusion的全部过程也就清楚了：

 

也就是：

  • magic二进制表示内有奇数个1：，从而cipher的密钥流也就是lfsr2的输出流，对应problem1的情况。
  • magic二进制表示内有偶数个1：，从而cipher的密钥流也就是lfsr1和lfsr2的输出流异或的结果，对应problem2的情况。

 

之后思路就是针对lfsr的攻击了。

注意到lfsr只有12比特长，这个穷举空间至多：，纯暴力穷举即可。几十秒结束，得到seed2和mask2。

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
from tqdm import tqdm

def xor(b1, b2):
    return bytes([x ^ y for x, y in zip(b1, b2)])

class lfsr():
    def __init__(self, seed, mask, length):
        self.length_mask = 2 ** length - 1
        self.mask = mask & self.length_mask
        self.state = seed & self.length_mask

    def next(self):
        next_state = (self.state << 1) & self.length_mask
        i = self.state & self.mask & self.length_mask
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        next_state ^= output
        self.state = next_state
        return output

    def getrandbit(self, nbit):
        output = 0
        for _ in range(nbit):
            output = (output << 1) ^ self.next()
        return output


class generator():
    def __init__(self, lfsr1, lfsr2, magic):
        self.lfsr1 = lfsr1
        self.lfsr2 = lfsr2
        self.magic = magic

    def infinit_power(self, magic):
        return int(magic)

    def malicious_magic(self, magic):
        now = (-magic & magic)
        magic ^= now
        return int(now), int(magic)

    def confusion(self, c1, c2):
        magic = self.magic
        output, cnt = magic, 0
        output ^= c1 ^ c2
        while magic:
            now, magic = self.malicious_magic(magic)
            cnt ^= now >> (now.bit_length() - 1)
            output ^= now
        output ^= cnt * c1
        return int(output)

    def getrandbit(self, nbit):
        output1 = self.lfsr1.getrandbit(nbit)
        output2 = self.lfsr2.getrandbit(nbit)
        return self.confusion(output1, output2)
    
encdata=open("./problem/MTk4NC0wNC0wMQ==_6d30.enc","rb").read()
known_plaintext=b"Date: 1984-04-01\r\n"
known_output=xor(known_plaintext,encdata[:len(known_plaintext)])

for seed in tqdm(range(2**12)):
    for mask in range(2**12):
        lfsr2=lfsr(seed,mask,12)
        fflag=True
        for i in range(len(known_output)):
            if lfsr2.getrandbit(8)!=known_output[i]:
                fflag=False
                break
        if fflag==True:
            print(seed,mask)
            continue
# 爆破得到seed2和mask2解密第一个文件            
seed2,mask2=2989 ,2053
xor_key=b""
lfsr2=lfsr(seed2,mask2,12)
for _ in range(len(encdata)):
    xor_key+=bytes([lfsr2.getrandbit(8)])

data=xor(xor_key,encdata)
open("./problem1.txt","wb").write(data)
print(xor(xor_key,encdata))

放一段解密出来的明文：

1
2
Date: 1984-04-01
The pursuit was renewed, till the water was again muddied.  But he could not wait.  He unstrapped the tin bucket and began to bale the pool.  He baled wildly at first, splashing himself and flinging the water so short a distance that it ran back into the pool.  He worked more carefully, striving to be cool, though his heart was pounding against his chest and his hands were trembling.  At the end of half an hour the pool was nearly dry.  Not a cupful of water remained.  And there was no fish.  He found a hidden crevice among the stones through which it had escaped to the adjoining and larger pool—a pool which he could not empty in a night and a day.  Had he known of the crevice, he could have closed it with a rock at the beginning and the fish would have been his.

 

可以去网上找到相关的文章：Love of life的第一章。把这篇文章存一下。之后第二个加密的文件里的部分文字也应该是这里面的。我们把这篇文章一段一段分开，所以密文2的原文大概有90+种可能的开头。

 

我们得到了mask2，先穷举可能的明文，然后同理直接爆破seed3（代码里写的seed2，无所谓了），得到lfsr2的输出流，进而得到lfsr1可能的输出（的穷举量，也需要执行这么多次BM算法，所以BM算法输入长度不能太大），对这个输出用BM算法解出来的多项式次数等于64就是正确解。

 

已知日期那行的长度是144比特，一般随机比特流BM算法输出的多项式次数为比特流长度的一般左右，这里也就是62，因此需要更长明文来作BM算法的输入保证结果的唯一性和正确性。拿上面文章的每一段开头放进去。（注意标点符号之类的）。直接下载原文，按照每一行进行穷举，大概90+行。输出长度只要取到取28字节就可以了（越长BM算法越慢），这时用BM算法每穷举2^12种输出流大概只要10s，并且长度也足够。上面的爆破得到mask1和seed3，从而就可以得到seed1了，从而解密得到flag。

 

脚本：

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
# sage
from tqdm import tqdm
from Crypto.Util.number import long_to_bytes,bytes_to_long
from sage.matrix.berlekamp_massey import berlekamp_massey

def xor(b1, b2):
    return bytes([x ^^ y for x, y in zip(b1, b2)])

class lfsr():
    def __init__(self, seed, mask, length):
        self.length_mask = 2 ** length - 1
        self.mask = mask & self.length_mask
        self.state = seed & self.length_mask

    def next(self):
        next_state = (self.state << 1) & self.length_mask
        i = self.state & self.mask & self.length_mask
        output = 0
        while i != 0:
            output ^^= (i & 1)
            i = i >> 1
        next_state ^^= output
        self.state = next_state
        return output

    def getrandbit(self, nbit):
        output = 0
        for _ in range(nbit):
            output = (output << 1) ^^ self.next()
        return output
    

def recover_initial(mask,N,known_output:bytes):
    #mask1= 9223372036854775811
    # 输入已知mask和对应LFSR的输出，得的初始的seed值
    b=known_output
    key = ''
    for i in range(N // 8):
        t = b[i]
        for j in range(7, -1, -1):
            key += str(t >> j & 1)
    idx = 0
    ans = ""
    key = key[N-1] + key[:(N-1)]
    while idx < 64:
        tmp = 0
        for i in range(N):
            if mask >> i & 1:
                tmp ^^= int(key[(N-1) - i])
        ans = str(tmp) + ans
        idx += 1
        key = key[N-1] + str(tmp) + key[1:N-1]
    num = int(ans, 2)
    return num

def complete_BM(known_output:bytes,N=None):
    # 不设置多项式的次数N，直接返回对应结果
    # 设置N后,只返回对应次数的多项式的lfsr，BM返回多项式次数不为N就否则返回None
    inp=list(bin(bytes_to_long(known_output))[2:].zfill(len(known_output)*8))
    inp=[GF(2)(int(i)) for i in inp]
    res=berlekamp_massey(inp)
    if N!=None and res.degree()==64:
        res_coff=res.coefficients(sparse=false)
        mask="".join([str(i) for i in res_coff[:-1]])
        mask=int(mask,2)
        seed=recover_initial(mask,N,known_output)
        return mask,seed
    elif N==None:
        N=res.degree()
        res_coff=res.coefficients(sparse=false)
        mask="".join([str(i) for i in res_coff[:-1]])
        mask=int(mask,2)
        seed=recover_initial(mask,N,known_output)
        return mask,seed
    return None

        
plain=open("./plaintext1.txt","rb").readlines()
possible_plain=[]
for l in plain:
    if l!=b"\r\n":
        possible_plain.append(l)

encdata=open("./problem/MTk4NC0xMi0yNQ==_76ff.enc","rb").read()
mask2=2053

for plaintext in possible_plain[48:49]:
    known_plaintext=b"Date: 1984-12-25\r\n"+plaintext
    t_len=min(28,len(known_plaintext))
    known_output=xor(known_plaintext[:t_len],encdata[:t_len])
    for seed2 in tqdm(range(2**12)):
        lfsr2=lfsr(seed2,mask2,12)
        xor_key=bytes([lfsr2.getrandbit(8) for _ in range(t_len)])
        out1_stream=xor(xor_key,known_output)
        res=complete_BM(out1_stream,64)
        if res!=None:
            print(f"valid parameters: mask1={res[0]}, seed1={res[1]}, seed2={seed2}")
# valid parameters: mask1=9223372036854775811, seed1=5071452738113266023, seed2=3054

 

然后用得到的参数解密即可，，挺不错的一道关于LFSR的题。

 

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true


Hi, this is tl2cents
Currently Ph.D at IIE of UCAS
Graduated from USTC (2018-2022)

CTFer
Focus on blockchain, crypto and reversing
Team member of NeSE and Nebula

Research
Blockchain | ETH | FHE
PQC | Cryptography | Android

Contact Me
echo Y2F4dWxhc2FlbGFAb3V0bG9vay5jb20K | base64 -d

Thanks for JoeyBling and Litten