Por un momento dejamos forense a un lado para volver con cripto, nos dan el siguiente enunciado y links:
Encrypted messages have been shared in a multi-user network. The goal is to get the sent message in plain text. Examine the contents of the file associated with this challenge to get the sent message.
https://s3.eu-central-1.amazonaws.com/cyberrange/cyb_2017_quals/objective9_a.txt
https://s3.eu-central-1.amazonaws.com/cyberrange/cyb_2017_quals/objective9_b.txt
Ambos ficheros son idénticos salvo que uno aparecen los datos en español y en el otro en inglés, por pereza me quede con el de inglés y al abrirlo me encontré con esto:
Ahí podemos ver los siguientes datos:
- Un número primo
- Un generator
- Mensajes cifrados
- Intercambio de claves
El enunciado no nos da ninguna pista sobre el tipo de cifrado pero los datos anteriormente mencionados nos dan una base para empezar a buscar.
Para empezar parece ser una clave de cifrado asimétrica del estilo de RSA, aunque esta utiliza dos números primos en lugar de un primo y un generator, así que centrémonos en esas características para nuestra búsqueda.
Después de andar rebuscando, viendo listados de cifrados, etc, etc finalmente volví a terminar en la wikipedia donde leí esto:
the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange.
Parece que cumple con el primer criterio y revisando el algoritmo efectivamente utilizan un número primo y un generator, parece que tenemos vencedor. No os penséis que esto fue tan fácil, realmente me tiré un buen rato buscando, leyendo, y probando jeje Diffie-Hellman precisamente me tuvo entretenido un rato pero fue la pista final para llegar a ElGamal.
Buscando sobre como poder atacar elGamal me encontré el siguiente artículo, muy interesante, donde explica todo el proceso: http://jceipek.com/Cracking-ElGamal/
Así que tenemos la siguiente información:
K = g^{a} (mod p)
p = 668086880889731962133523431807175727
g = 5
a = (desconocido)
Siendo K las claves públicas podemos intentar crackear «a» de forma relativamente sencilla:
p = 668086880889731962133523431807175727L g = 5 ks = [ 13676350792300656720415722840537517L, 203945637215597518230545505171659679L, 580366026388626537671567427495532104L, 44183384276523077372058753373688245L, 285030156272853013220480705095447260L, 357012145447722165249748761535461006L, 390029735669441452196274751955684179L, 601989706928792605813992011832479199L, 360961284583613898695965394387421236L, 139941716626953418230482445280581903L, 105881177968778568798759564195833907L, 390526685498939106176110574061595602L, 563639529202234758731368531968832147L, 324245072881445330437040962443118945L, 405610708257034412823729058735169540L, 650262519644970696024389370642695650L, 213432877935741336033450896689174194L, 353552678930580044120885303672148957L, 243663467386438261103795683502533121L, 60054856901287017831260389123964788L, 47619151582173839369440869144212671L ] for k in ks: print "Testing key: %s" % k for i in xrange(0, 10000): if k == pow(g,i,p): print "FOUND: %s " % i break elif i==9999: print "Password not found"
Como vemos en el script se itera por todas las claves públicas y por cada una se prueban 10000 posibles valores de «a», ejecutamos el script y obtenemos lo siguiente:
Hemos tenido suerte y hemos conseguido encontrar un valor valido: 5713
Ahora tenemos:
- Los mensajes cifrados utilizando las claves públicas y privadas.
- Las 21 claves públicas utilizadas.
- Una clave privada, 5713, utilizada para cifrar alguno de los mensajes.
El siguiente paso sera iterar por todos los mensajes utilizando la información que conocemos para encontrar aquellos cifrados con nuestra clave privada y ver que contienen:
import binascii, string
ks = [
13676350792300656720415722840537517L,
203945637215597518230545505171659679L,
580366026388626537671567427495532104L,
44183384276523077372058753373688245L,
285030156272853013220480705095447260L,
357012145447722165249748761535461006L,
390029735669441452196274751955684179L,
601989706928792605813992011832479199L,
360961284583613898695965394387421236L,
139941716626953418230482445280581903L,
105881177968778568798759564195833907L,
390526685498939106176110574061595602L,
563639529202234758731368531968832147L,
324245072881445330437040962443118945L,
405610708257034412823729058735169540L,
650262519644970696024389370642695650L,
213432877935741336033450896689174194L,
353552678930580044120885303672148957L,
243663467386438261103795683502533121L,
60054856901287017831260389123964788L,
47619151582173839369440869144212671L
]
ms = [
275023513241996465145375277081798608L,
447218054680404751018822774460718704L,
51995582795200573676963225532291674L,
193223721789665268065712251555969216L,
220335814464633181853626310867800188L,
656425673616840602129167597679995093L,
281892485332165528077148251112629012L,
620557294483014348860918835366093395L,
156345492853024516725256648981773406L,
132200864409682167694544306450049620L,
382432406296505241913643555684753752L,
172521731908572948160105617230206656L,
658413611309329150536039577629832733L,
470009248009045054893716168409231672L,
23596506422783336435053882014037130L,
383558469957245595047304146183172589L,
347874231426543687257153625634545539L,
67459688204264591154317629916556269L,
191215507340327093723036088461066387L,
115117630595934113621417863594045891L,
664015760731773907898900144736007853L,
595217394235485536046669899798176478L,
112023097890488836143086615204661790L,
608874679440735925600052610265281796L,
627004193985581843968567471204709309L,
400371059170563645226682976240507021L,
275561561380430753130008463891051319L,
200330734437451947551782935576820286L,
4050142404262389618647986897000959L,
23146488724874171376119071203201823L,
301084425566731188968143030280327612L,
661999379372886369576256038659921506L,
538840376896108158028033793328837055L,
628613307485444872721287063540568485L,
268637255868335003688434687411074993L,
381198387780204467302612163348706704L,
400162560639994092221980422692908055L,
399884623550765435890595082239306353L,
95290873877305597733967646180307586L,
641264950193834896903186128424472068L,
43114514832635661215282858829006066L,
68848632281350060105250861040771224L,
139026874478930635813093749231601370L,
655054596740951208790111828671407650L,
651375195158994899657890599658048856L,
285442090376771814189050634199458623L,
982626333322476170131864630408090L,
469354413955364991082951491284192153L,
103793433289712076190450408975699625L,
4766500844846659360508423238089711L,
377669527108872822305052284949357020L,
95920750238990748132617870809588151L,
127278808060571896803384740938668807L,
189601784199791219483320087267882549L,
344196550998639525901987791134561537L,
263650727383674608586010904392328918L,
459739916775104719487159379591490295L,
439037356963229048061191227105627374L,
186379926031613967999671113768565225L,
84951650617004032168830381676866149L,
656944761086661565220056094921318296L,
502980701175656560313734064531551071L,
107271094854895401072269844571403805L,
516400490889683786305851199913815487L,
606808728818715487827728440626551855L,
27411826797353775333603907921745463L,
524397563941504625880910396018932380L,
24021136517611978297227685711419170L,
219047882901615601296318017152053796L,
42988869817116390289497212345458978L,
356011675196335642115022112592576960L,
223494308152020204522016556367321846L,
346356309073576552673987939313043383L,
599172108441353432011552211209759120L,
286703909778039270880661258004633674L,
660051626702153873713990679214106770L,
141402079720691873145676175151050276L,
242429047870131231642110013163376117L,
193213311272454674555953883981535401L,
350431438249475996960516854823204070L,
406755029946632926255211620049600144L,
298956115564633149551111642911769177L,
624983588666681197516867067080227343L,
322865886478608435617642618336886528L,
484310864483152708576021119100590468L,
323317770963134415387616019546124150L,
664611512535013863159898484781401394L,
564091952146454446893647704186484295L,
612037128288224063949207003244931903L,
143546506514694697702580740506451057L,
474806893256685165420572727361313727L,
239612759211713177457242520864545373L,
74787785262221388851642570545110090L,
274719943084337263336901857643803025L,
502725889933552791883959493172359564L,
575862093313626652925425410032589465L,
505698177665487415454788766346780242L,
581461780713181428956776682676939535L,
530397494115930081791582949104886302L,
285801387076390876754579887639733109L,
510921457560136739170187973639958611L,
663500891194754312048932854322793679L,
463343466711415614750405955546091366L,
221203346954627052668479687662911260L,
189469132893167348761976530592996989L,
188603058226806753069769225787858738L,
616194194941484971188276658095704275L,
113202092462663629728701607894834865L,
309886466150813197844325706680318621L,
639471373224136177331540772282298710L,
192932334651310913857988456012323837L,
114816913019746305825440313210515565L,
74828199087438656125488068396634735L,
522732653872542903229762834179641882L,
191584423265039561925713828567071717L,
227787869970564063041296346104679887L,
306891653972344582241361176850584407L,
392274172021885022443850587414407011L,
125559738428408720475644102324838556L,
615364216773625903334625795559421169L,
500057421841703584877403678260138799L,
260070084421235847074282002455457252L,
187600596342100486089171096561896931L,
339635057512093364991610116021953342L,
339110300499989182998368511866157833L,
660779395639316212241686437332003362L,
329095027993074595919695551410540583L,
140605789490440930875187497544296460L,
257176879402866603529816355782375986L,
324120980584346851162216090452979977L,
194387168439381116078942591916009397L,
175995255161919702861081374240179288L,
259572006909692576380172420589925452L,
509638935328899883642651178414675943L,
298090377811497995789786927516761223L,
55053603143546713705199061614172199L,
211194736508204713045164972691471559L,
322643858284619135628948880605163328L,
439668266247815895970171643710455379L,
587820837884352136815268545013060251L,
95753039954214631842487951960885318L,
491620200566522347901236852867785307L,
301780054420658208572651245649627539L,
351451218715182319868764656094037520L,
89539648924955438094086602983260782L,
166704048535849478418519555410161074L,
389820252475886726351349233054499366L,
85845598060256819271577218812087780L,
118024352385516021924162367848038300L,
134454254807443906815016665983042484L,
635605035001932628742852236741891992L,
285472755901244094520983263238312924L,
242112294852247232052558862110026552L,
555253203134618755614672537833547733L,
255188187487970487505231795251002256L,
362408360464855976002489117110507504L,
497798205064839028989840950145093903L,
664598263130956335111813563348353854L,
176248945524152414626381741808780582L,
459320289109161198395771953215785644L,
352241435713696262643915518276547395L,
299109270475944905422148853708209824L,
605389275264832802088211224918956056L,
270428096336061713906253329149472894L,
118236816750358362845164515718656153L,
413485833771564678539647748788319049L,
523462356290280371241112889147181889L,
70447181971292666325002616079110879L,
94208126463978995542294456139862677L,
175200039423318692241081357349657280L,
33148743030138295425863598894494680L,
21237242841043549932136698852470846L,
71957619258305017989437299179723715L,
563661543710991717276574237793420753L,
639429223748100829821152259664648759L,
111682601189739995895306397620637428L,
86069271466041748677971387575107561L,
32781001024753003354920591047220459L,
304680222370252324708846074103480953L,
412468073256502561255069087528766427L,
281036079681016522949370175392467269L,
52602357085365575792478273909939590L,
521705544428555254953998581032264483L,
523357143576414494615671730610365650L,
49383328153585943265768459507402214L,
325319666760700489505055717374892372L,
571546298787029679777929059902713655L,
487909322255400265409025779925892990L,
393785198212849758008912370728252216L,
566956552334637565880432440938357002L,
34318900912105668553839995901038535L
]
p = 668086880889731962133523431807175727L
g = 5
a = 5713
def is_printable(input_str):
return all(ord(c) < 127 and c in string.printable for c in input_str)
def decrypt(r, c, a, p):
return (pow(r,p-1-a,p)*c) % p
for m in ms:
for k in ks:
dec = decrypt(k , m , a , p)
hexnum = hex(dec)
if len(hexnum)%2 == 0:
hexnum = "0x0" + hexnum[2:]
message = binascii.unhexlify(hexnum[2:-1])
if is_printable(message):
print "c1: %s \nc2: %s \nmessage: %s" % (k, m , message)
Ejecutamos el script y obtenemos el siguiente resultado:
Como solo hay un resultado está claro que nuestra flag es: crypt0_w0rld=)
Espero os haya gustado, un saludo!
