IJCTF 2021

 |  2021-07-24  | 

Intro

There were 5 crypto problems in this contest, and I solved 4 of them: Discrete Log, Square Sum, ECSign, and Quartic

The event link is here

Discrete Log

Description

We are given \(N\), \(e\), and ciphertext in the context of RSA. We are also given an oracle which solves the dicrete log problem modulo \(N\), in other word, outputs a \(x\) satisfy

\[ a^x \equiv b \pmod{N}\]

given input \(a\) and \(b\). There were no source code and we have no idea how it computes discrete log.

Solution

The first thing that came into my mind is that \(p\) and \(q\) must be special so that the discrete log problem can be solved easily. However, it is just too guessy and I quickly give up on this. Then I realized that if we give them \((a, 1)\) as input, they will give us an \(x\) such that

\[a^x \equiv 1 \pmod{N}\]

Therefore, \(x \mid \phi(N)\). Since \(\phi(N)\) is really close to \(N\), we can recover it from \(x\) easily. It turned out the server just give us \(x = 0\), which is trivial. However, with a simple modification, we can solve the problem! We send \((a, n - 1)\) as input, and they respond with a \(x\) such that

\[a^x \equiv -1 \pmod {N}\]

We have \(a^{2x} \equiv 1 \pmod {N}\) and \(x\) cannot be \(0\)! As such discrete log may not always exist, we try several values of \(a\) and wait for a valid \(x\). With \(x\), we find a multiple that is smaller but really close to \(N\) and that will be the \(\phi(N)\). The rest is trivial.

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
from pwn import *
from decimal import *
getcontext().prec = 500

r = remote('35.244.0.8', 34712)

r.recvuntil(b"Mod: ")
N = int(r.recvline().strip())
r.recvuntil(b"(e=65537)\n")
flag = int(r.recvline().strip())
r.recvuntil(b"base:")
e = 65537

for i in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]:
    print(i)
    r.sendline(str(i).encode())
    r.sendline(str(N - 1).encode())
    r.recvuntil(b"number: ")
    res = r.recvline()
    if res.startswith(b'discrete log is not found'):
        continue

    tmp = len('Here is the discrete log: ')
    res = int(res[tmp:].decode('ascii'))
    phi = N // res * res
    PLUS = N + 1 - phi
    _ = Decimal(PLUS * PLUS - N * 4) ** (1 / Decimal(2))
    _ = int(_)
    p = (PLUS + _) // 2
    q = PLUS - p
    assert p * q == N
    e = 65537
    d = pow(e, -1, (p - 1) * (q - 1))
    m = pow(flag, d, N)
    print(bytes.fromhex(hex(m)[2:]))
    exit(0)

Square Sum

Description

We are given \(n\), \(S = \left(\frac{p - 1}{2}\right)^2 + \left(\frac{q - 1}{2}\right)^2\) such that \(n = pq\), then we have a bunch of calculations 

1
2
3
4
5
6
7
n2 = n * n
k = randint(1, n-1)
g = 1 + k*n
r = randint(2, n2-1)

cmsg = (pow(g, bytes_to_long(MSG), n2) * pow(r, n2, n2)) % n2
c = (bytes_to_long(FLAG) * pow(r, n, n2)) % n2
and we only know cmsg and c.

Solution

The first step is to factorize \(n\). It is quite straight forward with a little math.

\[4S - 1 + 2n = p^2 + q^2 + 2pq - 2(p + q) + 1 = (p + q - 1)^2\] \[p = \frac{1}{2}\left((p + q) + \sqrt{(p + q)^2 - 4pq}\right)\]

The second step is to break down those weird calculations. We can get r % n by taking the first equation modulo \(n\) instead of \(n^2\) as we can drop the term with \(g\):

\[r^{n^2} \equiv \text{cmsg} \pmod{n}\]

Since the factorization of \(n\) is known, we can calculate r = pow(cmsg, pow(n^2, -1, phi)) where phi = (p - 1) * (q - 1). Move on to the next line, notice that

\[(r + n)^n \equiv r^n + \binom{n}{1} r^{n-1}n + \binom{n}{2} r^{n-2}n^2 + \cdots + n^n \equiv r^n \pmod{n^2}\]

\(x^n\) is periodic modulo \(n^2\) with period \(n\). Therefore, we can directly calculate FLAG = c * pow(r, -n, n2) % n2 without knowing r % n2. The message is not recover-able because of the randomness of \(k\), but the flag is retrieved.

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 decimal import *
getcontext().prec = 1500
n2=303520029249457721712088032629157671188675957478999814001107946377897435098262416944078032743694224547812111876508629629098790706348564683510627437608561667668817082232066690156773182947457415470637661555594387660242481075809061863866878134857767064271020275925358862373499666674028571177472256983693456175513694920187605044808723618380459789773493111510245511524263712883363099195516392023821523383273803607532258960986269523229557484356691226627296549458770890488302153036171491536959410916079515480053813267273641384674290430132960320985260531094724351210760834427441063392448845773608652498658579592730319172250637383076619273369963514086477217760274026803102575002211426718751927101891471494221058041179582203541771830433523526001577817599554252231872769532980390483401226639528096938277398399935682866324784993115812281877591865430215134442904551109441541036428784450911307551504003791948952027070850252232846043561327951083360866399333467139115782229855840846646026182204713128402629095939971393271042355316329494426040959059666926611479882720948473312355005677824274551575679913205670022022017139399175510998237850213737165974646339820009635040028632254754412047567426260382111848392850835481772030875035608845098368736718689
halfpq_sqr_sum=9472622129700199703245586196664170084403806786939405819609832782578112766576428480777927359491256761393588992261088804683630755557509473029147106633909601585974763553680654431838374713192695971152635135654980642968043058123569343691081887394840682085558030205578048546258148505272998984973693174088527063719679039240127298660482089717632821831294015315634267021396765367208053481029040950107066330391869209058343986685994748025768502912822369180563838868099092781901052919510720948179559741776416837917783632982451736331078296715767630096860173482291944176969440690386874499002706015031896162301715990323012706805065
cmsg=103078286643622880447473687471766764943564559811909431666893450054168818307349486985249638958378791065494084728451034371725501517686576282043339068765538253257675113627273797306564684365323509359273378294002601649860804748728163025522075672245295550880060720735463310260935029330499002606032562798724954111417118887527073957993508089754394967659543003785760047941879904675059060008485376318332423664374757995851806458605666638976841133899950278214115072866022244614110580100352950200691110948074551191407363470332793295773273747237585817004577206834980715049990997687288385068292724282066219625651831484886243730221023243574538535723396702634705817852703892641398427064494429830352214499320005058534474284577134432341253340519635081380378045892077000915627548861547061501696012768786270148594424943366660662587186418716670250433370555760184571143569773295737850383542649898270826382659942188410185848934468448568325496582525158048118061659983332451282069426273006110854670823360391164278996722155588697598627131803289512431866077055012911415395954770914537654639608929010542439756174537575923529600976400363945111089267192377586187238410504823191760221711696006651813981609780080767483863025507048248680195946925116086994713836313403
c=240819054139924192908276790404232331564539338066363967597355786532131090443403077278934264677782549578055871874639814497554138070603843470651529113660894021443057595391213699869840820555076709709812961373461750130612453785640822249347659164866017931889613080220570111764428471836538389725220257679376309813972857596742069449014122286177227320041653912468408726067139524231446702068292851152761999746103029142674572600075554585602575858028536948546991047817318676231622316199368535515883188272917775993105890398456057174036933873324756054332572569380343179450564438637126650504362820450286638292251182022086719737414761084603628504362175295748323721068857285078233340896776610403227874250072420794722246884387488198976386566266870301419765724246635936193987658699901284391726429640605754046472825878500017779396277376213443347956951870554421838859114868247676278966446582371758603658584495387466611294920606637857755221756257214625128936810241588259047215874829610442603034882068648615080256023583472836142327431962452607719206361748849195548395481842814703649891102211953579454296662259004591314057576449118621217086325140123543677458167848297604521746504718023238069208215956158087066756140657191702426263476717009016863723080567809

n = int(Decimal(n2).sqrt())
assert n * n == n2

_ = 4 * halfpq_sqr_sum - 2 + 2 * n + 1
PLUS = int(Decimal(_).sqrt()) + 1
assert PLUS % 2 == 0
MINUS = int(Decimal(PLUS * PLUS - 4 * n).sqrt())
assert MINUS % 2 == 0
p = (PLUS + MINUS) // 2
q = PLUS - p
assert p * q == n

phi = (p - 1) * (q - 1)
rnn = cmsg % n
r = pow(rnn, pow(n2, -1, phi), n)
assert pow(r, n2, n) == cmsg % n
flag = c * pow(r, -n, n2) % n2
assert (flag * pow(r, n, n2)) % n2 == c % n2
print(bytes.fromhex(hex(flag)[2:]))

ECSign

Description

The main part of this problem is to recover the private key with the EC sign. We are given 3 signatures of the same message, with the same r (which is really sus) and nonce k, k^0xffffffff, k^0xffffffff00000000. The algorithm of signing is

\[\text{sig} \equiv \frac{h + d_Ar}{k} \pmod{n}\]

where \(d_A\) is the private key, and \(h\) is the hash of the message.

Solution

Notice that the numerator of the signature is fixed in all 3 signatures. Let \(\alpha = h + d_Ar\), we have

\[k_i \equiv \frac{\alpha}{sig_i}\]

Since \(k_i\)s do not differ too much, both \(\alpha(sig_1^{-1} - sig_2^{-1})\) and \(\alpha(sig_1^{-1} - sig_3^{-1})\) have a small absolute value modulo \(n\). Let \(x = sig_1^{-1} - sig_2^{-1}\) and \(y = sig_1^{-1} - sig_3^{-1}\), then there exist small \((a, b)\) such that \(n \mid ax + by\). Therefore, we can construct a lattice:

\[\begin{pmatrix} 1 & 0 & x\\ 0 & 1 & y\\ 0 & 0 & n \end{pmatrix}\]

and solve \((a, b)\) and \(\alpha\) by LLL algorithm. We can recover the private key from \(\alpha\) easily.

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
import hashlib
import random
from Crypto.Util.number import inverse, bytes_to_long, long_to_bytes
from Crypto.Random import get_random_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from ecdsa import NIST256p
from ecdsa.ellipticcurve import Point

message = b"ECDSA prevents forging messages"

curve = NIST256p
G = curve.generator
n = int(curve.order)

hsh = int(hashlib.sha256(message).hexdigest(), 16)

pubkey = Point(curve.curve, 38745398585592404989617041657020362138123363380468846963780930586996547144750, 13643061224989896432264609612335708262502935494164515568037402963951605264829)
r = 77834524933954296097833315313842984664992628710802286706422333910202549804044
sig1 = pow(106047115067349115009621212644299274382951056066902044358604548248126784117113, -1, n)
sig2 = pow(77856639655128453708803009032309618307780628811843761077611198123911335033581, -1, n)
sig3 = pow(113246340396800206689440828533000149451101779708634101475318788958650261939751, -1, n)

x = (sig2 - sig1) % n
y = (sig3 - sig1) * pow(0x100000000, -1, n) % n

# x * (hsh + da * r) % n < 0xffffffff
# y * (hsh + da * r) % n < 0xffffffff

from olll import reduction
reduced_basis = reduction([[1, 0, x], [0, 1, y], [0, 0, n]], 0.75)
a, b, c = reduced_basis[0]
assert c == 0
# _ = hsh + da * r
_ = b * pow(x, -1, n)
privkey = (_ - hsh) * pow(r, -1, n) % n

pubkey2 = Point(curve.curve, 18408891362196717436082197656011814689561019672942300120844335017129989755383, 89780168462818288492260141231746707551390283872983535472764708240708422195758)
sharedkey = pubkey2 * privkey
key = long_to_bytes(int(sharedkey.x()))
iv=bytes.fromhex('1d828a4a93bc2026ae1c8ab1711a1991')
ct=bytes.fromhex('8c5350234cf12b0f4da1d344124fe76e29906fbf5a1ed45cc8c7a29009dc078a31a6150b8ec5be75e1f7cef7665f634b')
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = cipher.decrypt(ct)
print(ct)

Quartic

Description

\(N\) is the product of 1024-bit primes \(p\) and \(q\), and \(p'\) is a an approximation of \(p\) such that \(|p' - p| < 2^{80}\). We are given \(N\) and a quartic polynomial \(f\) such that \(N \mid f(p')\). The goal is to decrypt the ciphertext encrypted by RSA with \(N\).

Solution

This problem is the basic form of Coppersmith Attack. I used the script by mimoo to solve the challenge.

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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
from __future__ import print_function
import time

debug = False

# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print(a)

def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):
    """
    Coppersmith revisited by Howgrave-Graham
    
    finds a solution if:
    * b|modulus, b >= modulus^beta , 0 < beta <= 1
    * |x| < XX
    """
    #
    # init
    #
    dd = pol.degree()
    nn = dd * mm + tt

    #
    # checks
    #
    if not 0 < beta <= 1:
        raise ValueError("beta should belongs in (0, 1]")

    if not pol.is_monic():
        raise ArithmeticError("Polynomial must be monic.")

    #
    # calculate bounds and display them
    #
    """
    * we want to find g(x) such that ||g(xX)|| <= b^m / sqrt(n)
    * we know LLL will give us a short vector v such that:
    ||v|| <= 2^((n - 1)/4) * det(L)^(1/n)
    * we will use that vector as a coefficient vector for our g(x)
    
    * so we want to satisfy:
    2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)
    
    so we can obtain ||v|| < N^(beta*m) / sqrt(n) <= b^m / sqrt(n)
    (it's important to use N because we might not know b)
    """
    if debug:
        # t optimized?
        print("\n# Optimized t?\n")
        print("we want X^(n-1) < N^(beta*m) so that each vector is helpful")
        cond1 = RR(XX^(nn-1))
        print("* X^(n-1) = ", cond1)
        cond2 = pow(modulus, beta*mm)
        print("* N^(beta*m) = ", cond2)
        print("* X^(n-1) < N^(beta*m) \n-> GOOD" if cond1 < cond2 else "* X^(n-1) >= N^(beta*m) \n-> NOT GOOD")
        
        # bound for X
        print("\n# X bound respected?\n")
        print("we want X <= N^(((2*beta*m)/(n-1)) - ((delta*m*(m+1))/(n*(n-1)))) / 2 = M")
        print("* X =", XX)
        cond2 = RR(modulus^(((2*beta*mm)/(nn-1)) - ((dd*mm*(mm+1))/(nn*(nn-1)))) / 2)
        print("* M =", cond2)
        print("* X <= M \n-> GOOD" if XX <= cond2 else "* X > M \n-> NOT GOOD")

        # solution possible?
        print("\n# Solutions possible?\n")
        detL = RR(modulus^(dd * mm * (mm + 1) / 2) * XX^(nn * (nn - 1) / 2))
        print("we can find a solution if 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)")
        cond1 = RR(2^((nn - 1)/4) * detL^(1/nn))
        print("* 2^((n - 1)/4) * det(L)^(1/n) = ", cond1)
        cond2 = RR(modulus^(beta*mm) / sqrt(nn))
        print("* N^(beta*m) / sqrt(n) = ", cond2)
        print("* 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n) \n-> SOLUTION WILL BE FOUND" if cond1 < cond2 else "* 2^((n - 1)/4) * det(L)^(1/n) >= N^(beta*m) / sqroot(n) \n-> NO SOLUTIONS MIGHT BE FOUND (but we never know)")

        # warning about X
        print("\n# Note that no solutions will be found _for sure_ if you don't respect:\n* |root| < X \n* b >= modulus^beta\n")
    
    #
    # Coppersmith revisited algo for univariate
    #

    # change ring of pol and x
    polZ = pol.change_ring(ZZ)
    x = polZ.parent().gen()

    # compute polynomials
    gg = []
    for ii in range(mm):
        for jj in range(dd):
            gg.append((x * XX)**jj * modulus**(mm - ii) * polZ(x * XX)**ii)
    for ii in range(tt):
        gg.append((x * XX)**ii * polZ(x * XX)**mm)
    
    # construct lattice B
    BB = Matrix(ZZ, nn)

    for ii in range(nn):
        for jj in range(ii+1):
            BB[ii, jj] = gg[ii][jj]

    # display basis matrix
    if debug:
        matrix_overview(BB, modulus^mm)

    # LLL
    BB = BB.LLL()

    # transform shortest vector in polynomial    
    new_pol = 0
    for ii in range(nn):
        new_pol += x**ii * BB[0, ii] / XX**ii

    # factor polynomial
    potential_roots = new_pol.roots()
    print("potential roots:", potential_roots)

    # test roots
    roots = []
    for root in potential_roots:
        if root[0].is_integer():
            result = polZ(ZZ(root[0]))
            if gcd(modulus, result) >= modulus^beta:
                roots.append(ZZ(root[0]))

    # 
    return roots


N = 14696994372012287266063217731371465578678715866132272122977296158042664711913985707735240860887006104199660244194252732513872446957209707813718992065870009198350392025823708604809843097942852887153574791868863759677596709374574270980384013350507776841394348069047979081285459868079488308763109757234951918205929827395300302835788692873505186477300098666817569700699255710985965984118993464275972585327700080430955818549340143244083420792258768933607896874184152407531531128653324411725754823245939716911634247425735766453356062475072240421779566396468043043082651606158198150758975259067495695864660578493393106762631
ZmodN = Zmod(N)
e = 65537
c = 9750527994091121091786816841463772484970643350548409420602551052460114750376765234779160399774157114083542404212321500558790661890217330206975918220078382877833585674657160688057126517189623419338705483072993529673151815011674742481352311071675409754487654783078829059793691828971457847280715985552753121754286619544143717362922120309444897947012514213521135742738481921772607488909188240043132021160662803034095731089505604348170622399204914184546012322270024791178809723808523030967238028593150206277299911554652571555702651337880252089368970936855513446902610214801472036929625184874736910343726791265452474611050
seq = [158752811818711918978608809724046452901335596022391874487974890304998816699298753351923479802743256111682434826558127366354372655672162233383691616336809056589770476184830602519936915124324990526086510115052439516943494324074208205263728559181179209273336271456505648791496885861665659702772878794453617597935, 128112039454566836699268817573729682217733580513471579004092384875666907545736760938092529139116761787964524453230653391142195587208637498768853852534066440912659539891579333760989970185793933487448394446383099379350084438155354954554485354584606335545683635861714347785116146996111161679962531883524512245756, 125394898446858383529773530925952405484923255072498779305263565535739539843809683956661976383945903145655388058775285644922423567418124108556099444145910243884249123272753835196094595735828560593886549706202821360729966212919836071016187794411200454682068981836300681098224156531639842209297777220250045105015, 173287806459060855056978404566038662455264340360403434058797921467696881992461886820974507593896975956673635068182667307551397235117090256800473173760922218094509836540044524144073307976531893785817268555430923542035419459537615158405264410714554348532449071393153250670293668267831809663639016079737049993532, 110367489208453437299284319505293878991095171003329152569229822459210424547301175160255795581820578959629690051139383553782954098870270063851900045993344035739536369769062409357695761165417611332640635883761689554713983143014247113573513500943553569138485111921531165356036728439854269183574182361770067877382]
val = 4587129147169223135177082248247577247287230696838250360893151376678832017794662311496645432391215540389204568010806710075971796695505304027066300219073996196566364920871649278153101805335618485690679631760671100407668295798900270041393585528052410778685339781812407359874425601526059126165668484671578858665132491434454904136915398866378458071913624317667264519275308368507047649155997427360113558401018558028857800979164191767840984644802095146231460160633834780847547723464319670338864485176202467124809407088132810097750468091447438249060863489382657696069166135186865875148261692352214220481602521790532932330766

seq[4] -= val
iseq0 = pow(seq[0], -1, N)
seq = [x * iseq0 % N for x in seq]

# Problem to equation (default)
P.<x> = PolynomialRing(ZmodN) #, implementation='NTL')
pol = seq[0] * x^4 + seq[1] * x^3 + seq[2] * x^2 + seq[3] * x^1 + seq[4]
dd = pol.degree()

# Tweak those
beta = 1023 / 2048                               
epsilon = beta * beta / 4 - 81 / 2048   # <= beta / 7
mm = ceil(beta**2 / (dd * epsilon))     # optimized value
tt = floor(dd * mm * ((1/beta) - 1))    # optimized value
XX = ceil(N**((beta**2/dd) - epsilon))  # optimized value

# Coppersmith
start_time = time.time()
roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)

# output
print("\n# Solutions")
print("we found:", str(roots))
print(("in: %s seconds " % (time.time() - start_time)))
print("\n")

import math
# root = 821507932957358336850308
root = int(roots[0])
poly = seq[0] * (root ** 4) + seq[1] * (root ** 3) + seq[2] * (root ** 2) + seq[3] * root + seq[4]
p = math.gcd(poly, N)
q = N // p
assert p * q == N
d = pow(e, -1, (p - 1) * (q - 1))
pt = pow(c, d, N)
print(bytes.fromhex(hex(pt)[2:]))
tags:  #writeup
Expand all Back to top Go to bottom