# COMPFEST13: Snab

## September 13, 2021

Didn’t realise this CTF was on until the last few hours but here’s one challenge I got done. Snab?

#### Snab? Yes, Snab - Crypto - 168 points

``````Snab? Yes, Snab

Snab likes to give you a challenge. It is a simple challenge of RSA
encrypted messages, and you only have to find out what those messages
really are! Be careful though, Snab has some trick up his sleeve.

Solvers
``````

Along with the challenge comes one file:

• `snab-yes-snab-master-public.zip`

This ZIP file contains two interesting files: `Snab.py` and `output.txt`. The Python script is as below:

``````from Cryptodome.Util.number import*

e = 0x10001
s = pow(p + q, 2)
n = p*q
a = pow(s, 3, r)
b = (s - q*(2*p + q))*r

m_list = [findme]

c_list = []
for i in range(len(m_list)):
m = bytes_to_long(m_list[i])
c = pow(m*r, e, n)

c_list.append(c)

output = open("output.txt", "w")
output.writelines([str(i) + "\n" for i in [e, s, n, a, b, c_list]])
output.close()
``````

And the output predictably has the `e`,`s`,`n`,`a`,`b`and`c_list`within:

``````65537
518521484172073259043145502034694599512935443283076107003494840643504150663248402410462928864122818999731280619095755616648044687630285476363367234348295346345048643618601901838740100
121789376487960809489253386587170686658768726657045553214623415992384832614485249137256874454267032401365173859563210814953487893574413409932117585950570225259024509903129746392143101
14910
1443061772954701335732136128869248910288995712185482317126411260349775148932784597588115548780067761993841192961205698418501468762734686695975550561598140253475710348439640002745286347562
[95844532553991737600355244654272099305361975575150371319709729091243030203575898742071987199800250922501746626433985253038713853151746857514762678605619742310839669559545627531098676, 42098262117872607180245376226279234844537189667792611290978137770131205295202393318329675438677406769928295941768074280915365884838027414974072838410934952571392616562898636004189303, 8604504123043858588289398284978073629384165878986588408956445422750740896636700840713408309772547146776823067482307495576552057400894861616123713400577813256614795674220942022738198, 66896916235028791010554130879834163456721897024453929564151545727202320039792487273512943832159287883050106923587075192390665897004465138382234040927275478139131450371794658563343368, 88176130128782413821390318550151008388570132120182664342566671328546119423517817326934034720909238554168653863093116429325532932401977519369212892117707167802400008407395125896733332, 42250039274640778630603717605163827961176577828564055370588929192401015587247485151024369147022833032549004175634147831360114651662490704138925606397505368573040950634048151235675964, 106267843822546752528780879737401351948170741446817769684516569656816005147897267321452764634553751488085440938706773625287154372645991244141121226180609731226228509942129690482744498, 7344462713592491879813960159075800353984094813742489003735150623847056840460595091048879286634691169764793649426176975158414555454778075430233699780146900520609629142406422725693811, 68155732896092345896827379516624133280166986984023541993085330906321960888421556683672078055376548346464764100036149614632795220030187229733989823788323988946361921828069707823065198, 2456638129741631242062051214133833843357605035108383884677777076160879939756985403557604264648903511528401478876871578775440101482814072714355366084122429853207060638683606389504551, 99671982271645788903414016384550975165361965345980177928115018027271173062935625698434769263846972984813377601618481025600240081090732166957299336765744471217496851539810214590361856]
``````

So pretty interesting challenge.

Of course we are not given `p` or`q` and we also are missing this number `r`. What we do know though is the `r` is a factor of `b` and I realised that `b` is fully factored on factordb.com. One of the other interesting things is that one of the factors of `b` is a 91digit prime. That makes sense that `q` is also a factor of `b`. So now we have one of the primes we can trivially recover the private key.

``````\$ echo 8585355817076401598233531634118333310111591335583994461813636725445826748939381988061054123 > prime.txt
\$ echo n = 121789376487960809489253386587170686658768726657045553214623415992384832614485249137256874454267032401365173859563210814953487893574413409932117585950570225259024509903129746392143101 > key.pub
\$ echo e = 65537 >> key.pub
\$ goRsaTool -key key.pub -pastprimes prime.txt -attack pastctf > key.priv
\$ goRsaTool -key key.priv -dumpkey
n = 121789376487960809489253386587170686658768726657045553214623415992384832614485249137256874454267032401365173859563210814953487893574413409932117585950570225259024509903129746392143101
e = 65537
d = 3107127843628339311625977117868522942665384606719565512227449403226687827203249104437088881844778589959320904165795305079628357257734814176811715079256657090738894096459940267520225
p = 8585355817076401598233531634118333310111591335583994461813636725445826748939381988061054123
q = 14185711004047137036261660694588980151883775114595904600722314160246358704504599968072432887
``````

So now we have `p` and `q` we can derive `r` exactly via `b`:

``````b1 = (s - q*(2*p + q))
r = b//b1
``````

So we get `r = 19578` nice.

Now we can do our decryption and learn the plaintext by dividing `m//r`, the final code for this part being:

``````from Cryptodome.Util.number import *

e = 65537
s = 518521484172073259043145502034694599512935443283076107003494840643504150663248402410462928864122818999731280619095755616648044687630285476363367234348295346345048643618601901838740100
a = 14910
b = 1443061772954701335732136128869248910288995712185482317126411260349775148932784597588115548780067761993841192961205698418501468762734686695975550561598140253475710348439640002745286347562
n = 121789376487960809489253386587170686658768726657045553214623415992384832614485249137256874454267032401365173859563210814953487893574413409932117585950570225259024509903129746392143101
c_list = [95844532553991737600355244654272099305361975575150371319709729091243030203575898742071987199800250922501746626433985253038713853151746857514762678605619742310839669559545627531098676, 42098262117872607180245376226279234844537189667792611290978137770131205295202393318329675438677406769928295941768074280915365884838027414974072838410934952571392616562898636004189303, 8604504123043858588289398284978073629384165878986588408956445422750740896636700840713408309772547146776823067482307495576552057400894861616123713400577813256614795674220942022738198, 66896916235028791010554130879834163456721897024453929564151545727202320039792487273512943832159287883050106923587075192390665897004465138382234040927275478139131450371794658563343368, 88176130128782413821390318550151008388570132120182664342566671328546119423517817326934034720909238554168653863093116429325532932401977519369212892117707167802400008407395125896733332, 42250039274640778630603717605163827961176577828564055370588929192401015587247485151024369147022833032549004175634147831360114651662490704138925606397505368573040950634048151235675964, 106267843822546752528780879737401351948170741446817769684516569656816005147897267321452764634553751488085440938706773625287154372645991244141121226180609731226228509942129690482744498, 7344462713592491879813960159075800353984094813742489003735150623847056840460595091048879286634691169764793649426176975158414555454778075430233699780146900520609629142406422725693811, 68155732896092345896827379516624133280166986984023541993085330906321960888421556683672078055376548346464764100036149614632795220030187229733989823788323988946361921828069707823065198, 2456638129741631242062051214133833843357605035108383884677777076160879939756985403557604264648903511528401478876871578775440101482814072714355366084122429853207060638683606389504551, 99671982271645788903414016384550975165361965345980177928115018027271173062935625698434769263846972984813377601618481025600240081090732166957299336765744471217496851539810214590361856]

p = 8585355817076401598233531634118333310111591335583994461813636725445826748939381988061054123
q = 14185711004047137036261660694588980151883775114595904600722314160246358704504599968072432887
d = 3107127843628339311625977117868522942665384606719565512227449403226687827203249104437088881844778589959320904165795305079628357257734814176811715079256657090738894096459940267520225

b1 = (s - q*(2*p + q))
r = b//b1

for c in c_list:
print(long_to_bytes(pow(c,d,n)//r).decode().strip())
``````

Which gives us part 2 - yes part 2 - argh!

``````#Snab says good job! But you're not done yet
flag = findme
halfa = ''.join([flag[i] for i in range (0, len(flag), 2)])
halfb = ''.join([flag[i] for i in range (1, len(flag), 2)]
p = bytes_to_long(bytes(halfa, encoding = 'utf-8'))
q = bytes_to_long(bytes(halfb, encoding = 'utf-8'))
r = 0
while (not(isPrime(p) and isPrime(q))):
p += 1
q += 1
r += 1
``````

Ok so I was stumped here for a bit. Without any reference this seems not doable. But if we work backwards from known values of `r`, `p`and`q` from Part 1 its pretty easy, all we need to do is subtract `r` from `p`and`q` and see what happens:

``````r = 19578
p = 8585355817076401598233531634118333310111591335583994461813636725445826748939381988061054123
q = 14185711004047137036261660694588980151883775114595904600722314160246358704504599968072432887

pmr = p-r
qmr = q-r

pwords = long_to_bytes(pmr)
qwords = long_to_bytes(qmr)

out = ""
for i in range(len(pwords)):
out += chr(pwords[i]) + chr(qwords[i])

print(out)
``````

Which fortunately does NOT result in part 3 - we just get…

``````\$ ./p2.py
Cool! You did it! {y0U_d1DnT_3xpEcT_t0_FinD_pQ_4s_a_fl4g_DiD_y0u_7e1877a801}
``````

Which was the flag. Phew~!

### niteCTF - CBC-Jail

A unique combination of Python jailbreak and crypto flaw that had me learning a lot about AES-CBC mode. Super fun for me to get this solu...… Continue reading

#### niteCTF - Rabin to the Rescue

Published on December 12, 2021

#### HTB CyberSanta 2021 - Crypto Writeups

Published on December 04, 2021