本文第一发布平台为安全客：https://www.anquanke.com/post/id/233827

简介

AntCTF x D^3CTF 2021中共有四道Crypto方向的题目，题目难度适中，本文对这四道题目及本人的解题思路进行介绍，如有错误还请各位师傅指教。

babyLattice

题目分析

这道题的题目如下

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
from collections import namedtuple

PublicKey = namedtuple('PublicKey', ['n', 'b'])
SecretKey = namedtuple('SecretKey', ['p', 'q', 'A'])


def gen_key():
    p = random_prime(2^512, lbound=2^511)
    q = random_prime(2^512, lbound=2^511)
    n = p * q

    a11, a12, a21 = [random_prime(2^100) for _ in range(3)]
    a22 = random_prime(2^100)
    while a11 * a22 == a12 * a21:
        a22 = random_prime(2^100)
    A = Matrix(ZZ, [[a11, a12], [a21, a22]])

    a1 = crt([a11, a21], [p, q])
    a2 = crt([a12, a22], [p, q])
    b = a1 * inverse_mod(a2, n) % n

    PK = PublicKey(n, b)
    SK = SecretKey(p, q, A)

    return (PK, SK)

def encrypt(m, pk):
    assert 0 < m < 2^400
    r = randint(0, 2^400-1)
    c = (pk.b*m + r) % pk.n
    return c

def decrypt(c, sk):
    a2 = crt([sk.A[0,1], sk.A[1,1]], [sk.p, sk.q])
    s1 = a2 * c % sk.p
    s2 = a2 * c % sk.q
    m, r = sk.A.solve_right(vector([s1, s2]))
    return m

def test(pk, sk, num=3):
    for _ in range(num):
        m = randint(0, 2^400-1)
        c = encrypt(m, pk)
        mm = decrypt(c, sk)
        assert m == mm


if __name__ == '__main__':
    from hashlib import sha256
    from secret import m, FLAG

    assert FLAG == 'd3ctf{%s}' % sha256(int(m).to_bytes(50, 'big')).hexdigest()

    PK, SK = gen_key()
    test(PK, SK)

    c = encrypt(m, PK)

    print(f"PK = {PK}")
    print(f"c = {c}")

我们重点看看加密函数

也就是

那么我们可以得到

这样就可以通过LLL算法还原出m了

EXP

1
2
3
4
5
6
7
8
9
10
from hashlib import sha256
n = 69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361
b = 65473938578022920848984901484624361251869406821863616908777213906525858437236185832214198627510663632409869363143982594947164139220013904654196960829350642413348771918422220404777505345053202159200378935309593802916875681436442734667249049535670986673774487031873808527230023029662915806344014429627710399196
c = 64666354938466194052720591810783769030566504653409465121173331362654665231573809234913985758725048071311571549777481776826624728742086174609897160897118750243192791021577348181130302572185911750797457793921069473730039225991755755340927506766395262125949939309337338656431876690470938261261164556850871338570

A = Matrix(ZZ,[[1,0,b],[0,2^400,c],[0,0,n]])
A = A.LLL()
m = int(A[0][0])
flag = 'd3ctf{%s}' % sha256(int(m).to_bytes(50, 'big')).hexdigest()
print(flag)

simpleGroup

题目分析

这道题的题目如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from random import randint
from secret import FLAG


# A gift for key recovery in challenge [babyLattice]
n = 69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361
y = 12064801545723347322936991186738560311049061235541031580807549422258814170771738262264930441670708308259694588963224372530498305648578520552038029773849342206125074212912788823834152785756697757209804475031974445963691941515756901268376267360542656449669715367587909233618109269372332127072063171947435639328
e = 1928983487

M = int.from_bytes(FLAG, 'big')
C = []
while M != 0:
    m = M % e
    M //= e
    r = randint(0, n-1)
    c = power_mod(y, m, n) * power_mod(r, e, n)
    C.append(c % n)

print(f"C = {C}")

通过注释我们可以大概猜测babyLattice本来是需要分解n的，但是因为被非预期了所以又出了这道题目

那么我们回到babyLattice题目里面，我们知道的参数实际上只有b,c,n，分解n应该和b有关，通过阅读b的生成代码我们可以得到

我们展开后两个式子

也就是

两边相乘得到

展开并变形得到

也就是

由于

所以我们同样可以用LLL还原出目标向量，然后使用factor进行分解（a11,a12,a21,a22它们都是素数）

当分解完毕后，通过猜测它们对应的值来分解n，即

得到p,q后，我们回来看题目里面的加密，其会对FLAG进行取模并分段加密余数，其中c的生成公式如下

r是随机生成的数字，而e可以被分解为e1和e2两个素数，这两个素数又分别是p-1和q-1的因子

那么我们可以得到

那么通过遍历j并判断得到的c'是不是为模p的e1次剩余，我们就可以得到m模e1的值

同样我们也可以用q得到m模e2的值，然后使用中国剩余定理即可还原m并最终得到flag

EXP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
n = 69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361
b = 65473938578022920848984901484624361251869406821863616908777213906525858437236185832214198627510663632409869363143982594947164139220013904654196960829350642413348771918422220404777505345053202159200378935309593802916875681436442734667249049535670986673774487031873808527230023029662915806344014429627710399196
c = 64666354938466194052720591810783769030566504653409465121173331362654665231573809234913985758725048071311571549777481776826624728742086174609897160897118750243192791021577348181130302572185911750797457793921069473730039225991755755340927506766395262125949939309337338656431876690470938261261164556850871338570

A = Matrix(ZZ,[[1,0,b^2],[0,1,b],[0,0,n]])
A = A.LLL()

x1 = -A[0][0]
x3 = A[0][2]
print(factor(x1))
print(factor(x3))

a12 = 1018979931854255696816714991181
a22 = 1151291153120610849180830073509
a11 = 1017199123798810531137951821909
a21 = 207806651167586080788016046729
print(gcd(b * a12 - a11,n))
print(gcd(b * a22 - a21,n))

p = 7669036313101194621345265255994200133006921565596653797956940811601516306410232120057637504305295677357422367597831138570269733177579895994340511712373309
q = 9102122415165681824420871673621781250311822805618731863628192549895693024247220594372897360668046264863189831887100676431439200352775676467952192600956629
assert(p * q == n)
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
#!/usr/bin/env python
from Crypto.Util.number import *
import gmpy2

p = 7669036313101194621345265255994200133006921565596653797956940811601516306410232120057637504305295677357422367597831138570269733177579895994340511712373309
q = 9102122415165681824420871673621781250311822805618731863628192549895693024247220594372897360668046264863189831887100676431439200352775676467952192600956629
n = 69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361
y = 12064801545723347322936991186738560311049061235541031580807549422258814170771738262264930441670708308259694588963224372530498305648578520552038029773849342206125074212912788823834152785756697757209804475031974445963691941515756901268376267360542656449669715367587909233618109269372332127072063171947435639328
e = 1928983487
e1 = 36493
e2 = 52859

def GCRT(mi, ai):
    assert (isinstance(mi, list) and isinstance(ai, list))
    curm, cura = mi[0], ai[0]
    for (m, a) in zip(mi[1:], ai[1:]):
        d = gmpy2.gcd(curm, m)
        c = a - cura
        assert (c % d == 0)
        K = c // d * gmpy2.invert(curm // d, m // d)
        cura += curm * K
        curm = curm * m // d
        cura %= curm
    return (cura % curm, curm) 

def check(d,p,n):
    if((p - 1) % n == 0):
        return pow(d,(p - 1) // n,p) == 1
    else:
        k = gmpy2.gcd(n, p - 1)
        return pow(d,(p - 1) // k,p) == 1

def getM(c,e,p):
    for i in range(2,e):
        tmpc = (c * gmpy2.invert(pow(y,i,p),p)) % p
        if check(tmpc,p,e):
            return i
    exit(0)

C = [63173987757788284988620600191109581820396865828379773315280703314093571300861961873159324234626635582246705378908610341772657840682572386153960342976445563045427986000105931341168525422286612417662391801508953619857648844420751306271090777865836201978470895906780036112804110135446130976275516908136806153488, 9763526786754236516067080717710975805995955013877681492195771779269768465872108434027813610978940562101906769209984501196515248675767910499405415921162131390513502065270491854965819776080041506584540996447044249409209699608342257964093713589580983775580171905489797513718769578177025063630080394722500351718, 37602000735227732258462226884765737048138920479521815995321941033382094711120810035265327876995207117707635304728511052367297062940325564085193593024741832905771507189762521426736369667607865137900432117426385504101413622851293642219573920971637080154905579082646915297543490131171875075081464735374022745371, 1072671768043618032698040622345664216689606325179075270470875647188092538287671951027561894188700732117175202207361845034630743422559130952899064461493359903596018309221581071025635286144053941851624510600383725195476917014535032481197737938329722082022363122585603600777143850326268988298415885565240343957, 27796821408982345007197248748277202310092789604135169328103109167649193262824176309353412519763498156841477483757818317945381469765077400076181689745139555466187324921460327576193198145058918081061285618767976454153221256648341316332169223400180283361166887912012807743326710962143011946929516083281306203120, 27578857139265869760149251280906035333246393024444009493717159606257881466594628022512140403127178174789296810502616834123420723261733024810610501421455454191654733275226507268803879479462533730695515454997186867769363797096196096976825300792616487723840475500246639213793315097434400920355043141319680299224, 29771574667682104634602808909981269404867338382394257360936831559517858873826664867201410081659799334286847985842898792091629138292008512383903137248343194156307703071975381090326280520578349920827357328925184297610245746674712939135025013001878893129144027068837197196517160934998930493581708256039240833145, 33576194603243117173665354646070700520263517823066685882273435337247665798346350495639466826097821472152582124503891668755684596123245873216775681469053052037610568862670212856073776960384038120245095140019195900547005026888186973915360493993404372991791346105083429461661784366706770467146420310246467262823, 5843375768465467361166168452576092245582688894123491517095586796557653258335684018047406320846455642101431751502161722135934408574660609773328141061123577914919960794180555848119813522996120885320995386856042271846703291295871836092712205058173403525430851695443361660808933971009396237274706384697230238104, 61258574367240969784057122450219123953816453759807167817741267194076389100252707986788076240792732730306129067314036402554937862139293741371969020708475839483175856346263848768229357814022084723576192520349994310793246498385086373753553311071932502861084141758640546428958475211765697766922596613007928849964, 13558124437758868592198924133563305430225927636261069774349770018130041045454468021737709434182703704611453555980636131119350668691330635012675418568518296882257236341035371057355328669188453984172750580977924222375208440790994249194313841200024395796760938258751149376135149958855550611392962977597279393428]
m = 0
for c in C[::-1]:
    cp = c % p
    cq = c % q
    m1 = getM(cp,e1,p)
    m2 = getM(cq,e2,q)
    mm,lcm = GCRT([e1,e2],[m1,m2])
    print("Get mm: " + hex(mm))
    m *= e
    m += mm

flag = long_to_bytes(m)
print(flag)

EasyCurve

题目分析

这道题目的主要部分如下

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
import socketserver
from Crypto.PublicKey import RSA
from Crypto.Util.number import getPrime , bytes_to_long
from Curve import MyCurve
from hashlib import sha256
import os
import string
import random
import signal
from secret import flag

BIT = 2048
p = 9688074905643914060390149833064012354277254244638141162997888145741631958242340092013958501673928921327767591959476890238698855704376126231923819603296257

class Task(socketserver.BaseRequestHandler):

    def proof_of_work(self):
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
        _hexdigest = sha256(proof.encode()).hexdigest()
        self.send(f"sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
        self.send(b'Give me XXXX: ')
        x = self.recv()
        if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
            self.send('wrong')
            return False
        return True

    def recv(self):
        data = self.request.recv(1024)
        return data.strip()

    def send(self, msg, newline=True):
        if isinstance(msg , bytes):
            msg += b'\n'
        else:
            msg += '\n'
            msg = msg.encode()
        self.request.sendall(msg)

    def key_gen(self , bit):
        key = RSA.generate(bit)
        return key

    def ot(self , point):
        x , y = point
        random.seed(os.urandom(8))

        key = self.key_gen(BIT)
        self.send('n = ' + str(key.n))
        self.send('e = ' + str(key.e))
        x0 = random.randint(1 , key.n)
        x1 = random.randint(1 , key.n)
        self.send("x0 = " + str(x0))
        self.send("x1 = " + str(x1))

        self.send("v = ")
        v = int(self.recv())
        m0_ = (x + pow(v - x0, key.d, key.n)) % key.n
        m1_ = (y + pow(v - x1, key.d, key.n)) % key.n
        self.send("m0_ = " + str(m0_))
        self.send("m1_ = " + str(m1_))
        
    def handle(self):
        signal.alarm(180)
        if not self.proof_of_work():
            return 0
        e = bytes_to_long(os.urandom(32))
        u = random.randint(1 , p)
        D = random.randint(1 , p)
        curve = MyCurve(p , D , u)
        self.send('p = ' + str(p))
        self.send('D = ' + str(D))
        for i in range(3):
            G = curve.getPoint()
            self.ot(G)
            P = curve.mul(e , G)
            self.ot(P)
            self.send("do you know my e?")
            guess = int(self.recv())
            if guess == e:
                self.send("oh no!")
                self.send(flag)
                return 0
            else:
                self.send("Ha, I know you can't get it.")

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10000
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

其使用了一个随机生成参数的MyCurve并生成了随机的e，给我们三次交互的机会，每次机会会随机生成点G和点P并使用OT将这两个点的信息传递给我们，点P是e倍的点G，当我们给服务器正确的e的时候我们可以得到flag

这其实就是一个离散对数问题，我们首先关注服务器的参数，MyCurve所使用的p是512比特的，而OT中RSA的n是2048比特的，这样生成的点的x和y乘起来也没有n的大。那么可以参考2020hackergame的不经意传输中的攻击方式来同时获取点的x和y坐标

之后便是如何通过点G和点P来获取e了，我们可以注意到p-1是光滑的

1
2
sage: factor(p-1)
2^21 * 3^10 * 7^4 * 11 * 13^2 * 17 * 19 * 29 * 31 * 37 * 43^3 * 47 * 71 * 83 * 89 * 97 * 223 * 293 * 587 * 631 * 709 * 761 * 1327 * 1433 * 1733 * 1889 * 2503 * 3121 * 6043 * 6301 * 49523 * 98429 * 140683 * 205589 * 1277369 * 1635649 * 5062909 * 45698189 * 67111151 * 226584089 * 342469397

那么我们可以通过Pohlig-Hellman algorithm来解决离散对数问题并最终得到flag

EXP

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
#!/usr/bin/env python
import string, gmpy2
from hashlib import sha256
from pwn import *
context.log_level = "debug"

dic = string.ascii_letters + string.digits

def solvePow(prefix,h):
    for a1 in dic:
        for a2 in dic:
            for a3 in dic:
                for a4 in dic:
                    x = a1 + a2 + a3 + a4
                    proof = x + prefix.decode("utf-8")
                    _hexdigest = sha256(proof.encode()).hexdigest()
                    if _hexdigest == h.decode("utf-8"):
                        return x

def getData():
    r.recvuntil("n = ")
    n = int(r.recvuntil("\n", drop = True))
    r.recvuntil("e = ")
    e = int(r.recvuntil("\n", drop = True))
    r.recvuntil("x0 = ")
    x0 = int(r.recvuntil("\n", drop = True))
    r.recvuntil("x1 = ")
    x1 = int(r.recvuntil("\n", drop = True))
    offset = 2 << 1024
    offset_e = int(pow(offset, e, n))
    v = ((offset_e * x0 - x1) * gmpy2.invert(offset_e - 1, n)) % n
    r.sendlineafter("v = ",str(v))
    r.recvuntil("m0_ = ")
    m0 = int(r.recvuntil("\n", drop = True))
    r.recvuntil("m1_ = ")
    m1 = int(r.recvuntil("\n", drop = True))
    m = (m0 * offset - m1) % n
    x = m // offset + 1
    y = x * offset - m
    return x,y

r = remote("47.100.50.252",10000)
r.recvuntil("sha256(XXXX+")
prefix = r.recvuntil(") == ", drop = True)
h = r.recvuntil("\n", drop = True)
result = solvePow(prefix,h)
r.sendlineafter("Give me XXXX: \n",result)

r.recvuntil("p = ")
r.recvuntil("\n", drop = True)
r.recvuntil("D = ")
D = int(r.recvuntil("\n", drop = True))

Gx,Gy = getData()
Px,Py = getData()

with open("data.txt","wb") as f:
    f.write(str(D).encode() + b"\n")
    f.write(str(Gx).encode() + b"\n")
    f.write(str(Gy).encode() + b"\n")
    f.write(str(Px).encode() + b"\n")
    f.write(str(Py).encode() + b"\n")

s = process(argv=["sage", "exp.sage"])
e = int(s.recv())
s.close()
r.sendline(str(e))

r.interactive()
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
# exp.sage
load("Curve.sage")
import os, random
from Crypto.Util.number import *

p = 9688074905643914060390149833064012354277254244638141162997888145741631958242340092013958501673928921327767591959476890238698855704376126231923819603296257
F = GF(p)
fac = [2^21,3^10,7^4,11,13^2,17,19,29,31,37,43^3,47,71,83,89,97,223,293,587,631,709,761,1327,1433,1733,1889,2503,3121,6043,6301,49523,98429,140683,205589,1277369,1635649,5062909,45698189,67111151,226584089,342469397]

def bsgs(g, y, p):
    m = int(ceil(sqrt(p - 1)))
    S = {}
    point = (u,0)
    for i in range(m):
        point = curve.add(point,g)
        pointg = point[0] << 800 | point[1]
        S[pointg] = i

    gs = curve.mul(m,g)
    for i in range(m):
        pointy = y[0] << 800 | y[1]
        if pointy in S:
            return S[pointy] - i * m + 1
        y = curve.add(y,gs)
    return None

def Pohlig_Hellman(G,P):
    ea = []
    na = []
    for i in range(len(fac)):
        c = fac[i]
        n = (p - 1) // c
        gi = curve.mul(n, G)
        yi = curve.mul(n, P)
        ei = bsgs(gi,yi,c)
        ea.append(ei%c)
        na.append(c)
    ee = crt(ea,na)
    return ee

data = open("data.txt","rb").read().decode("utf-8")
data = data.split("\n")

D = int(data[0])
Gx = int(data[1])
Gy = int(data[2])
Px = int(data[3])
Py = int(data[4])

G = (F(Gx),F(Gy))
P = (F(Px),F(Py))

u2 = (Gx ^ 2 - D * Gy ^ 2)
u2 = F(u2)
u = int(u2.sqrt())
curve = MyCurve(p , D , u)
e = Pohlig_Hellman(G,P)
print(e)

AliceWantFlag

题目分析

这道题目分为server端和Alice端，其中server端的代码如下

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
from elgamal import elgamal
import socketserver
from prikey import server_prikey , AlicePasswd
from pubkey import Alice_pubkey
from secret import Alice_flag , ctfer_flag
import random
import signal
from os import urandom
from Crypto.Util.number import long_to_bytes , bytes_to_long
from Crypto.Cipher import AES

MENU = "1. signup  2.signin"
XOR = lambda s1,s2 :bytes([x1^x2 for x1 , x2 in zip(s1,s2)])
def pad(m):
    m += bytes([16 - len(m) % 16] * (16 - len(m) % 16))
    return m

def unpad(m):
    padlen = m[-1]
    for i in range(1 , padlen + 1):
        if m[-i] != m[-1]:
            return b''
    return m[:-m[-1]]
    
class server(socketserver.BaseRequestHandler):
    
    def setup(self):
        self.pubkey = {}
        self.passwd = {}
        self.prikey = elgamal(server_prikey)
        self.pubkey[b'Alice'] = elgamal(Alice_pubkey)
        self.passwd[b'Alice'] = AlicePasswd

    def _recv(self):
        data = self.request.recv(1024)
        return data.strip()

    def _send(self, msg, newline=True):
        if isinstance(msg , bytes):
            msg += b'\n'
        else:
            msg += '\n'
            msg = msg.encode()
        self.request.sendall(msg)

    def enc_send(self, msg , usrid , enc_key = b''):
        if enc_key == b'':
            pubenc = self.pubkey[usrid]
            y1 , y2 = pubenc.encrypt(bytes_to_long(msg))
            self._send(str(y1) + ', ' + str(y2))
        else:
            assert len(enc_key) == 16
            aes = AES.new(enc_key , AES.MODE_ECB)
            self._send(aes.encrypt(pad(msg)))
    
    def dec_recv(self,  enc_key = b''):
        msg = self._recv()
        if enc_key == b'':
            c = [int(i) for i in msg.split(b', ')]
            m = self.prikey.decrypt(c)
            print(long_to_bytes(m))
            return long_to_bytes(m)
        else:
            assert len(enc_key) == 16
            aes = AES.new(enc_key , AES.MODE_ECB)
            return unpad(aes.decrypt(msg))
            
    def signup(self):
        if len(self.passwd) > 5:
            self._send('sorry, the number of users is out of limit')
            return 0
        self._send('please give me your name')
        userid = self._recv()
        if len(userid) > 20:
            self._send('your id can\'t be too long')
            return 0
        elif userid in self.passwd:
            self._send('the name has been used')
            return 0
        else:
            self._send('please give me your passwd(encrypted)')
            userpasswd = self.dec_recv()
            if len(userpasswd) > 11:
                self._send('your password can\'t be too long')
                return 0
            else:
                self.passwd[userid] = userpasswd
            self._send('please give me your publickey')
            userpubkey = self._recv()
            try:
                userpubkey = [int(i) for i in userpubkey[1:-1].split(', ')]
            except:
                self._send('publickey format error')
                self.passwd.pop(userid)
                return 0
            self.pubkey[userid] = elgamal(userpubkey)
            self._send('sign up success')
            return 1

    def signin(self):
        self._send('please give me your name')
        userid = self._recv()
        if userid not in self.passwd:
            self._send('sorry the userid is not existed')
            return 0
        while 1:
            random.seed(urandom(8))
            r = random.getrandbits(8 * 11)
            self._send('please give me your passwd(encrypted and xored by r)')
            self._send(str(r))
            userdata = self.dec_recv()
            if bytes_to_long(userdata) == r ^ bytes_to_long(self.passwd[userid]):
                self._send('signin success')
                break
            else:
                self._send('password error')
        endkey = urandom(5)
        key = userdata + endkey
        self._send('now let\'s communicate with this key')
        self.enc_send(endkey , userid)
        return userid , key

    def handle(self):
        signal.alarm(240)
        key = b''
        userid = ''
        while 1:
            self._send(MENU)
            choice = self._recv()
            if choice == b'1':
                self.signup()
            elif choice == b'2':
                temp = self.signin()
                if temp != 0:
                    userid , key = temp
                    break
            else:
                self._send('error')
        msg = self.dec_recv(enc_key = key)
        if msg == b'I am a ctfer.Please give me flag':
            self.enc_send(b'ok, your flag is here ' + ctfer_flag , userid , enc_key= key)
        elif msg == b'I am Alice, Please give me true flag' and userid == b'Alice':
            self.enc_send(b'Hi Alice, your flag is ' + Alice_flag , userid , enc_key= key)
        return 0

    def finish(self):
        self.request.close()

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10001
    server = ForkedServer((HOST, PORT), server)
    server.allow_reuse_address = True
    server.serve_forever()

Alice端的代码如下

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
import socket
from elgamal import elgamal
from pubkey import server_pubkey
from prikey import Alice_prikey , AlicePasswd
from Crypto.Util.number import long_to_bytes , bytes_to_long
from Crypto.Cipher import AES
import socketserver , signal
def pad(m):
    m += bytes([16 - len(m) % 16] * (16 - len(m) % 16))
    return m

def unpad(m):
    return m[:-m[-1]]
    
class Alice:
    def __init__(self , ip , port):
        self.pridec = elgamal(Alice_prikey)
        self.pubenc = elgamal(server_pubkey)
        self.s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        self.s.connect((ip, port))
    
    def _recv(self):
        data = self.s.recv(1024)
        return data.strip()

    def _send(self, msg):
        if isinstance(msg , str):
            msg = msg.encode()
        self.s.send(msg)

    def enc_send(self, msg , enc_key = b''):
        if enc_key == b'':
            y1 , y2 = self.pubenc.encrypt(bytes_to_long(msg))

            self._send(str(y1) + ', ' + str(y2))
        else:
            assert len(enc_key) == 16
            aes = AES.new(enc_key , AES.MODE_ECB)
            self._send(aes.encrypt(pad(msg)))
    
    def dec_recv(self,  enc_key = b''):
        msg = self._recv()
        if enc_key == b'':
            c = [int(i) for i in msg.split(b', ')]
            m = self.pridec.decrypt(c)
            return long_to_bytes(m)
        else:
            assert len(enc_key) == 16
            aes = AES.new(enc_key , AES.MODE_ECB)
            return unpad(aes.decrypt(msg))

    def main(self):
        firstmsg = self._recv()
        if firstmsg != b'1. signup  2.signin':
            return 0
        self._send('2')
        self._recv()
        self._send('Alice')
        self._recv()
        r = int(self._recv())
        userdata = long_to_bytes(bytes_to_long(AlicePasswd) ^ r)
        self.enc_send(userdata)
        self._recv()
        self._recv()
        endkey = self.dec_recv()
        key = userdata + endkey
        self.enc_send(b'I am a ctfer.Please give me flag' , enc_key = key)
        return self.dec_recv(enc_key = key)

class Task(socketserver.BaseRequestHandler):
    def _recv(self):
        data = self.request.recv(1024)
        return data.strip()

    def _send(self, msg, newline=True):
        if isinstance(msg , bytes):
            msg += b'\n'
        else:
            msg += '\n'
            msg = msg.encode()
        self.request.sendall(msg)
    
    def handle(self):
        signal.alarm(60)
        self._send('Hello, I am Alice, can you tell me the address of the server?\nIn return, I will give you the ctf_flag')
        try:
            addr = self._recv()
            ip, port = [x.strip() for x in addr.split(b':')]
            
            port = int(port)
        except:
            ip, port = '0.0.0.0', 10001
        a = Alice(ip , port)
        msg = a.main()
        self._send(b'Thanks, here is your flag')
        self._send(msg)

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10003
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

server和Alice的密钥生成和使用都和elgamal算法一致，这里不再阐述

服务端的大概逻辑如下

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
U: User
S: Server
UserPasswd = UserPublicKey

Sign Up:
S -> U : 'please give me your name'
U -> S : userid
S : assert len(userid) < 20 and userid not in passwd
S -> U : 'please give me your passwd(encrypted)'
U -> S : c = elgamal.enc(UserPasswd,ServerPublicKey)
S : passwd[userid] = elgamal.dec(c,ServerPrivateKey)
S -> U : 'sign up success'

Sign In:
S -> U : 'please give me your name'
U -> S : userid
S : assert userid in passwd
S -> U : 'please give me your passwd(encrypted and xored by r)'
S -> U : r
U -> S : c = elgamal.enc(UserPassWord ^ r,ServerPublicKey)
S : assert elgamal.dec(c,ServerPrivateKey) == passwd[userid] ^ r
S : key = userdata + endkey, userdata = passwd[userid] ^ r, endkey = urandom(5)
S -> U : 'now let\'s communicate with this key'
S -> U : k = elgamal.enc(key,UserPasswd)
U -> S : m = AES.enc(key,msg)
S : dm = AES.dec(key,m)
S : if dm == 'I am a ctfer.Please give me flag':
    S -> U : r1 = AES.enc(key,ctfer_flag)
S : if dm == 'I am Alice, Please give me true flag' and userid == 'Alice'
    S -> U : r2 = AES.enc(key,Alice_flag)

大概理解下来就是一个利用elgamal进行密钥交换然后加密通信的逻辑

由于这里我们需要已Alice的身份登陆并使用交换的AES通信密钥进行密文的加密，所以我们需要知道AlicePasswd和key

这道题目中由于也有Alice端的服务，所以我们可以伪装成服务端来和Alice端进行通信，也就是进行中间人攻击

首先来看看如何获得AlicePasswd，观察Alice端的如下代码

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
 def main(self):
    firstmsg = self._recv()
    if firstmsg != b'1. signup  2.signin':
        return 0
    self._send('2')
    self._recv()
    self._send('Alice')
    self._recv()
    r = int(self._recv())
    userdata = long_to_bytes(bytes_to_long(AlicePasswd) ^ r)
    self.enc_send(userdata)
    self._recv()
    self._recv()
    endkey = self.dec_recv()
    key = userdata + endkey
    self.enc_send(b'I am a ctfer.Please give me flag' , enc_key = key)
    return self.dec_recv(enc_key = key)
 
def dec_recv(self,  enc_key = b''):
    msg = self._recv()
    if enc_key == b'':
        c = [int(i) for i in msg.split(b', ')]
        m = self.pridec.decrypt(c)
        return long_to_bytes(m)
    else:
        assert len(enc_key) == 16
        aes = AES.new(enc_key , AES.MODE_ECB)
        return unpad(aes.decrypt(msg))

由于endkey长度为5，而key的长度是16，那么可以自然推断出userdata的长度为11

但是如果我们控制r使得userdata的第一个字节异或为了\x00，那么userdata的长度就变成了10，如果endkey的长度不变，再使用userdata + endkey作为AES的key，那么会通不过assert len(enc_key) == 16，即连接会断开

这样我们可以通过单字节爆破AlicePasswd的值使得key的长度从16变成15，这样就能获得AlicePasswd的第一个字节，然后重复该过程便可以获得AlicePasswd（每爆破出一个字节，在爆破下一个字节的时候将endkey的长度变长一位即可连续爆破）

PS：实际上的操作过程中AlicePasswd的最后一个字节爆破不出来，我们使用服务端的Sign In功能来爆破最后一个字节即可

在拿到了AlicePasswd之后，我们便可以伪造成Alice登陆服务端，但是由于endkey是使用AlicePublicKey来进行加密的，所以我们还需要拿到endkey的值才能获得AES的key并进行任意文本加解密

前面我们提过，endkey长度为5，但是实际上elgamal的p是512比特的，也就是说endkey远比p小

如果我们将elgamal加密后的endkey的y2乘以一个倍数k，那么elgamal解密后的endkey就会变大k倍，这个值如果特别大，则userdata + endkey就也会变大，这样便会通不过assert len(enc_key) == 16，即连接会断开

那么我们就可以通过遍历k并查看连接是否断开来得到endkey的大致范围，然后通过控制r让userdata的长度变小来使得我们的k可以不断变大，进而将endkey的取值范围不断缩小来得到endkey

最后我们便可以进行任意文本加解密来获取flag

EXP

爆破AlicePasswd的脚本（除了最后一个字节）

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
#!/usr/bin/env python
from elgamal import elgamal
from os import urandom
from Crypto.Util.number import *
from pwn import *
from time import *
import random
#context.log_level = 'debug'

Alice_pubkey = (10701440058624032601015137538928332495339102166449611910023158626004456760436930147541475696463030881833656888220652983522600176918743749340172660134163173, 1564399668655593150166497641453625075939863931648697579307, 7485644640971189066076867813504769638089749022750276585841131549227880841063823940682209946365975810625990180843110530957715179877761206203179636693608929, 10399272689500457356753299445284422908920074489727610618928888372268024186959263604721857776550008093778901180936272708522371781846820901338928077050396521)
pubenc = elgamal(Alice_pubkey)

def enc(msg):
    y1 , y2 = pubenc.encrypt(bytes_to_long(msg))
    return [y1,y2]

def attackAlice(rr,m):
    try:
        middle_shell = listen(8888)
        alice_shell = remote("47.100.0.15",10003)
        alice_shell.recvuntil(b"Hello, I am Alice, can you tell me the address of the server?\nIn return, I will give you the ctf_flag\n")
        alice_shell.sendline("xxxx:8888") # xxxx -> your vps's ip
        middle_shell.sendline(b'1. signup  2.signin')
        middle_shell.recv()
        middle_shell.sendline(b'please give me your name')
        middle_shell.recv()
        middle_shell.sendline(b'please give me your passwd(encrypted and xored by r)')
        middle_shell.sendline(str(rr))
        middle_shell.recv()
        middle_shell.sendline(b'signin success')
        middle_shell.sendline(b'now let\'s communicate with this key')
        middle_shell.sendline(str(m[0]) + ', ' + str(m[1]))
        sleep(0.3)
        result = middle_shell.recv()
        if result != b"":
            middle_shell.close()
            alice_shell.close()
            return True
    except:
        if middle_shell:
            middle_shell.close()
        if alice_shell:
            alice_shell.close()
    return False

known_pwd = b""

# 0x35343764643163636333xx
for i in range(11):
    for r in range(0,256):
        rr = ((bytes_to_long(known_pwd) << 8) + r) << ((11 - i - 1) * 8)
        print("try:" + hex(rr))
        msg = b"A" * (5 + i)
        c = enc(msg)
        if not attackAlice(rr,c):
            known_pwd += long_to_bytes(r)
            print(known_pwd.hex())
            break

爆破AlicePasswd的最后一个字节的脚本

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
#!/usr/bin/env python
from elgamal import elgamal
from os import urandom
from Crypto.Util.number import *
from pwn import *
from time import *
import random
#context.log_level = 'debug'

dic = "0123456789abced"
server_pubkey = (8299337325013713958100496214277076548352330213422739951900206795659160881192662528217175848727001874097369338994314737585158671248737646741717255122339339, 1168114014665994438995759247944846107956060291607878556427, 6500863983405565947154848535503122330952083500341721347265599161478330537510643776384164499549064061675517930495094496645911948535824156417648599603482256, 1567838365897620258270310904624368598290758028096181970817619626094906443214320401208038763050717813632540079799097716376430981907783174222429828480377116)
pubenc = elgamal(server_pubkey)


known_pwd = "547dd1ccc3"
server_shell = remote("47.100.0.15",10001)
server_shell.sendlineafter("\n","2")
server_shell.recvuntil("please give me your name\n")
server_shell.sendline("Alice")
for c in dic:
    server_shell.recvuntil("please give me your passwd(encrypted and xored by r)\n")
    rr = int(server_shell.recvline())
    pwd = bytes_to_long((known_pwd + c).encode())
    prefix = long_to_bytes(pwd ^ rr)
    assert(len(prefix) == 11)
    y1 , y2 = pubenc.encrypt(pwd ^ rr)
    server_shell.sendline(str(y1) + ', ' + str(y2))
    result = server_shell.recv()
    if b"success" in result:
        print(known_pwd + c)
        break

server_shell.interactive()

获取endkey并进行中间人攻击的脚本

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#!/usr/bin/env python
from pwn import *
from Crypto.Util.number import *
from Crypto.Cipher import AES
from elgamal import elgamal
#context.log_level = "debug"

pwd = "547dd1ccc38".encode()
pwd = bytes_to_long(pwd)
server_pubkey = (8299337325013713958100496214277076548352330213422739951900206795659160881192662528217175848727001874097369338994314737585158671248737646741717255122339339, 1168114014665994438995759247944846107956060291607878556427, 6500863983405565947154848535503122330952083500341721347265599161478330537510643776384164499549064061675517930495094496645911948535824156417648599603482256, 1567838365897620258270310904624368598290758028096181970817619626094906443214320401208038763050717813632540079799097716376430981907783174222429828480377116)
pubenc = elgamal(server_pubkey)
p = 10701440058624032601015137538928332495339102166449611910023158626004456760436930147541475696463030881833656888220652983522600176918743749340172660134163173

def pad(m):
    m += bytes([16 - len(m) % 16] * (16 - len(m) % 16))
    return m

def unpad(m):
    padlen = m[-1]
    for i in range(1 , padlen + 1):
        if m[-i] != m[-1]:
            return b''
    return m[:-m[-1]]

def oracle(m,n,p):
    y1 = m[0]
    y2 = m[1]
    y2 = (y2 * n) % p
    return [y1,y2]


def combineKey(m,rr):
    for i in range(3):
        sleep(0.3)
        try:
            middle_shell = listen(8888)
            alice_shell = remote("47.100.0.15",10003)
            alice_shell.recvuntil(b"Hello, I am Alice, can you tell me the address of the server?\nIn return, I will give you the ctf_flag\n")
            alice_shell.sendline("xxxx:8888") # xxxx -> your vps's ip
            middle_shell.sendline(b'1. signup  2.signin')
            middle_shell.recv()
            middle_shell.sendline(b'please give me your name')
            middle_shell.recv()
            middle_shell.sendline(b'please give me your passwd(encrypted and xored by r)')
            middle_shell.sendline(str(rr))
            middle_shell.recv()
            middle_shell.sendline(b'signin success')
            middle_shell.sendline(b'now let\'s communicate with this key')
            middle_shell.sendline(str(m[0]) + ', ' + str(m[1]))
            sleep(0.5)
            result = middle_shell.recv()
            print(result)
            if result != b"":
                middle_shell.close()
                alice_shell.close()
                return True
        except:
            if middle_shell:
                middle_shell.close()
            if alice_shell:
                alice_shell.close()
    return False

server_shell = remote("47.100.0.15",10001)
server_shell.sendlineafter("\n","2")
server_shell.recvuntil("please give me your name\n")
server_shell.sendline("Alice")
server_shell.recvuntil("please give me your passwd(encrypted and xored by r)\n")
rr = int(server_shell.recvline())
prefix = long_to_bytes(pwd ^ rr)
assert(len(prefix) == 11)
y1 , y2 = pubenc.encrypt(pwd ^ rr)
server_shell.sendline(str(y1) + ', ' + str(y2))
server_shell.recvuntil("now let's communicate with this key\n")
y1,y2 = [int(i) for i in server_shell.recvuntil("\n", drop = True).decode("utf-8").split(", ")]
print(y1,y2)
success("Get communicate key:" + str(y1) + "," + str(y2))

l = 0
h = 2**40
idx = 0
prefix_length = 0
bound = 2**40
count = 0
flag = False


for _ in range(11):
    if flag:
        break
    binary_ptr = 0x80
    diff = binary_ptr // 2
    assert_arr = [-1] * 256
    for i in range(10):
        count += 1
        if binary_ptr != 0 and assert_arr[binary_ptr-1] ^ assert_arr[binary_ptr] == 1:
            prefix_length += 1
            l = bound // multiple
            h = bound // (multiple - 1)
            idx = multiple - 1
            print(hex(l),hex(h),count)
            bound *= 0x100
            if abs(h - l) < 2:
                flag = True
            break
        if binary_ptr != 255 and assert_arr[binary_ptr] ^ assert_arr[binary_ptr+1] == 1:
            prefix_length += 1
            l = bound // (multiple + 1)
            h = bound // multiple
            idx = multiple
            print(hex(l),hex(h),count)
            bound *= 0x100
            if abs(h - l) < 2:
                flag = True
            break
        rr = bytes_to_long(long_to_bytes(pwd)[:prefix_length]) * 2**(8*(11 - prefix_length))
        multiple = idx * 0x100 + binary_ptr
        m = oracle([y1,y2],multiple,p)
        if combineKey(m,rr):
            if binary_ptr == 255:
                prefix_length += 1
                h = bound // (multiple + 1)
                idx = multiple + 1
                print(hex(l),hex(h),count)
                bound *= 0x100
                if abs(h - l) < 2:
                    exit(0)
                break
            assert_arr[binary_ptr] = 0
            binary_ptr += diff
            diff //= 2
        else:
            assert_arr[binary_ptr] = 1
            binary_ptr -= diff
            diff //= 2

context.log_level = "debug"
endkey = long_to_bytes(h)
key = prefix + endkey
success("get key:" + key.hex())
data = b'I am Alice, Please give me true flag'
cipher = AES.new(key , AES.MODE_ECB)
data = cipher.encrypt(pad(data))
server_shell.sendline(data)
msg = server_shell.recvuntil("\n",drop = True)
print(cipher.decrypt(msg))

参考

https://github.com/USTC-Hackergame/hackergame2020-writeups/blob/master/official/不经意传输/README.md

https://ctf-wiki.org/crypto/asymmetric/discrete-log/discrete-log/#pohlig-hellman-algorithm