Crypto-Pwn2Win-2017-Asymmetric-Encryption


Asymmetric Encryption
Bloodsuckers use different asymmetric encryption algorithms to send messages to their partners. You may be able to exploit such communications, but first you should be able to recognize the used asymmetric algorithms.

Server: nc 200.136.213.110 7777

We fire netcat and we obtain the following:

1
2
3
4
5
q = 896922063827
g = 12424931089
h = 574559267769
enc(a) = (453104394915, 390471080026)
enc(3*a + 32)?

We notice that the cryptosystem here must be ElGamal.
One can obtain the encryption of 3*a, because ElGamal is homomorphic in relation to the multiplication, i.e. E(m1)*E(m2) = E(m1*m2). But, it is not in relation to the addition. Therefore, it is required to find the private key x such that g^x mod q = h. As the prime q only has 40 bits, it is easy to find out with the baby step giant step meet in the middle attack.
We used https://github.com/viralpoetry/Baby-step-giant-step to compute the discrete log. We obtain x = 202922528794.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
>>> x = 202922528794
>>> q = 896922063827
>>> h = 574559267769
>>> g = 12424931089
# we have now to find a
>>> enc = (453104394915, 390471080026)
>>> s = pow(enc[0], x, q)
>>> sinv = modinv(s, q)
# (modinv from https://stackoverflow.com/questions/4798654/modular-multiplicative-inverse-function-in-python)
>>> a = enc[1] * sinv % q
>>> a
108768066438L
>>> to_encrypt = 3*a + 32
>>> r = 5 # we chose a small random number for the encryption. it could be whatever you wanted < q
>>> result = (pow(g, r, q), to_encrypt * pow(h, r, q) % q)
>>> result
(801172058328L, 410122112192L)

Easy. We have our first correct answer.

1
2
3
4
5
6
7
8
9
10
11
q = 896922063827
g = 12424931089
h = 574559267769
enc(a) = (453104394915, 390471080026)
enc(3*a + 32)?
(801172058328, 410122112192)
Correct! Next...
n = 659381354716006369742363
e = 65537
enc(a) = 554863447144015806910906
enc(a^5 + 2*a + 41)?

Now, this is clearly RSA. The modulus is small. Let’s use yafu to compute the factors of 659381354716006369742363.
We obtain p = 864367132729 and q = 762848712947.

1
2
3
4
5
6
7
8
9
10
>>> p = 864367132729
>>> q = 762848712947
>>> n = p * q
>>> e = 65537
>>> d = modinv(e, (p-1)*(q-1))
>>> a = pow(554863447144015806910906, d, n)
>>> a
218624962707346537869456L
>>> pow(a**5 + 2*a + 41, e, n)
215275919603710085695724L

We have our second answer correct.

1
2
3
4
5
6
7
8
9
10
n = 659381354716006369742363
e = 65537
enc(a) = 554863447144015806910906
enc(a^5 + 2*a + 41)?
215275919603710085695724
Correct! Next...
n = 776738987646974637425039
g = 776738987646974637425040
enc(a) = 104466234975614190334351556746005105225005455760
enc(a^5)?

Now, this looks like Paillier cryptosystem. We used yafu to discover n = p * q. We obtain p = 952658582963 and q = 815338256053.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
>>> p = 952658582963
>>> q = 815338256053
>>> n = p * q
>>> g = 776738987646974637425040
>>> enc = 104466234975614190334351556746005105225005455760
>>> phi = (p-1)*(q-1)
>>> miu = modinv((pow(g, phi, n**2)-1)/n, n)
# decrypt and find a
>>> z = pow(enc, phi, n**2)
>>> z = (z - 1)/n
>>> a = z*miu % n
>>> a
593865001407021231568482L
# encrypt a^5
>>> r = 5 #whatever number
>>> (pow(g, a**5, n**2) * pow(r, n, n**2)) % (n**2)
551344609697032782258820295222867131320370770770L

Correct. Next we find again ElGamal.

1
2
3
4
5
6
7
8
9
10
11
n = 776738987646974637425039
g = 776738987646974637425040
enc(a) = 104466234975614190334351556746005105225005455760
enc(a^5)?
551344609697032782258820295222867131320370770770
Correct! Next...
q = 162468360679141142763506469479039044723348598131343445023537528281758038856725899813448600764965664562827243890486154155054547681581530078506256454819062823302171522262160978639320056038295558351438333626355253455829930861656788077110705347484186791527605530619097928023950578487542852122604132414043739150119
g = 71617122044994067303905663362038925673552248437100144808168324877801061768171815833721974961532703253044394601768959631644002378569370957141698573753120813269172546820898334296643254497348710964283337196775523365259211998702039022625622498418357561295233596431521761773785941196196533383471457791068304542860
h = 111066648693171887028924716387930536202901514118903026147266454463707523131763918297711469710662207420385870870164685517351171893585068487655691524361140991885848958718360460992751593253073812391597394918180851967495018510187596343611325247877606623904208279091478507563768905318293335621925954116646006910388
enc(a) = (21624535586567506603984186779885207318602579759808112698630259017417529498649485922951645341096345328763025063786609897082667076531258136422106222993285575007280223388512289362685146566945916187517382905780252904425034481330835615708515857702294263742141184959896884068790745261235435155068299465225574582560, 38537941029975848030592009789690349376115082020053275876066791343139798710924237464927608815778845257515757255006036413842443376625286738601962899180988337782103893434680014360059921519888813156293982852260141731565853893416439570684816679875490888188370627554793241614773190030997959436875113067106880655048)
enc(a^7)?

This one is easy. The ElGamal encryption of a is the following.

1
E(a) = (g^r mod q, a * h^r mod q)

To obtain the encryption of a^7, we elevate E(a) to the power of 7.

1
E(a)^7 = ((g^r mod q)^7, (a * h^r mod q)^7) = (g^(7r) mod q, a^7 * h^(7r) mod q) = E(a^7)

Therefore:

1
2
3
4
5
6
...
define q, h, g
...
>>> enc = (21624535586567506603984186779885207318602579759808112698630259017417529498649485922951645341096345328763025063786609897082667076531258136422106222993285575007280223388512289362685146566945916187517382905780252904425034481330835615708515857702294263742141184959896884068790745261235435155068299465225574582560, 38537941029975848030592009789690349376115082020053275876066791343139798710924237464927608815778845257515757255006036413842443376625286738601962899180988337782103893434680014360059921519888813156293982852260141731565853893416439570684816679875490888188370627554793241614773190030997959436875113067106880655048)
>>> (pow(enc[0], 7, q), pow(enc[1], 7, q))
(111943704492198613677284064414263835827314903408795497288196730523366749172531261312939368180540744924661825776170153157857298436145855968660805139686412343878802804331392369688765040244903208295888020856843171734022924414044150587927040617364297225555547079482268117880403242431146502775006475807941590243957, 146944962972196061304452302982428886923580067615704091332968984386866821167820106942309825648793805501664148988040753726356825992452196561280275962919553230491290426455421904803150216668843887712124953140424115672066452860798980586595286092420270643236030879120858647424877506090672990669173730588282484181475)

Correct. The next one is another RSA with the following parameters.

1
2
3
4
n = 116129573369269565162236051660667188158855673329540427297390499575862981989835841843866583577063083766954029063144621040623764875768299287457499920694511048949688694670794953791035923764107936680805021705444041635396218234076099965276137996734996446529395542124683260815237555361324912425749295153953132095761
e = 65537
enc(a) = 113404819639317667150945206046179254025822100958261129257002960505190359188994098567188808686386964857225447271200495440587539103432162087685650112552863460383570740714408941280241382042752738643406032354358166194009200674868816147437559543328518217678994594982357470461665835857915008170677398859755267093420
enc((31*a)^7)?

RSA is homomorphic to the multiplication and powers. Just do the following.

  1. Encrypt 31.
  2. Multiply the encryption of 31 to the encryption of a. (z = E(31) * E(a) % n)
  3. Power it. (result = pow(z, 7, n))
  4. Done. result is 79422070142774248998696748364536969928051026241019028333521995212847190464228596819898318295431833653185507986566295081274239311469462993984644730127173443271940560058698451295020485382667406426759092058704807263661852917928725084340240033097368645878075171977767675641790645116925564507723204703462264972052

Next. Another Paillier.

1
2
3
4
5
n = 8621606345813741778522514266054273377220780538934639795782688699674225088206322295464704691574306739432963387326203941438845912627154353843605597106654023
g = 8621606345813741778522514266054273377220780538934639795782688699674225088206322295464704691574306739432963387326203941438845912627154353843605597106654024
enc(a) = 7937660128690175325568344972823559278861468103813145508603245376730524355646304917359508580566100608589042820651231838238609822717639617861887063282742304194177278580800908754694218555803321746479637321316698926171902620676195782762387943008573984077258721183694556844093549693467565523559928218327284235089
enc(b) = 33387753148071257428905539518160221978694704069687353836469091655010096223312256529016397591008817430414577588510555623557614906758093969392417915817764626568693773437705685363505728318306424617495507184665856273528630405473435911817059436953757079883134497707484413544554359132244534862297762773379557525426
enc(31*a + 12*b + 56)?

Pallier is homomorphic to the addition and the multiplication, in the following way:

1
2
E(m1)^k = E(k*m1)
E(m1)E(m2) = E(m1 + m2)

The result is:

1
(pow(E(a),31,n**2) * pow(E(b), 12, n**2)) * E(56) % n**2 = 4970421455367244845374713137266537502697958490590659650451726192347671487410827360664416249739491204023927184480151500339026488270807023596092868579949981952165240250817692006905532570205653975588657894036033054920661457321178863796257037956921744588997061459597410104137746663293674207917309975395301044061

Finally, the flag is given to us:
CTF-BR{ASym3tric_partially_Homomorphic_3ncryPt1on}