Cryptopat

Sur ce challenge on a un échange de 5 messages entre Alice et Bob.

Les messages 3 et 4 sont intéressants:

Attention je pense que ta clé publique est vulnérable à Wiener, je te conseille fortement de la changer !  bzhctf{B3g1N_0f_Fl4g%

et :

Voilà, j'ai ajouté 15 bits de poids fort à ma nouvelle clé privée, maintenant je ne suis plus vulnérable à Wiener ;)
Tu peux m'envoyer le flag sans soucis ;)

Récupération de la clé privée vulnérable

On sait qu’on a également 2 clés publiques. La première est donc vulnérable à Wiener. On s’embete pas à réimplémenter l’attaque et on utilise un code déja bien utile.

Basé sur ces librairies, on crack la clé privée avec :

import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator

def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)

    for (k,d) in convergents:

        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = Arithmetic.is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("Hacked!")
                    return d

# On obtient les infos avec, par ex : cat chall_RSA_patch/alice_pubkey.pem | openssl rsa -pubin -inform PEM -text -noout

e = 16067237575020587365684949537420553336297887103135251158340199512381342010923839836839175967325518093593560110120570374561901329018544177783237636785681314899727902679813927972179168522909753478009724591422216350692572367061594386736432185783023783174089153239340683425146614617576982658612935026396194106151415411217524493358793036726760191073155065415520850657018370352272434786522789821689214574254518236229610852662142538480531553720751475315717565073720813420644610699973129707918058953693919886720862302627135853709794021492252785770199014347088152633180606499239183317651309326779783097912048103050277929517453
n = 19668895384782468617428677573059897654282052777686604193288890931972629730263752594043050215727581556020419030025989300425197017068567855834295602186567489002513877919398045507153107150792324033759448799017614520165391590806597724518388317704545844762755766458185677170257064294267886252344817753079174312360017739292971093257427286663401297480546601892171446675921974932462962749756778624464727641083529044275845408644143568929461484780731932975513371397929451759662214535107588638394467424289460888727462427676917688682426838016993903841720351970171165964384350925524138537598844548635355403058470705330268062646657
print hack_RSA(e,n)

En 2s on obtient:

$ python crack.py
Hacked!
3729092172867755527822307742234078358263625236042905659081826128798496778443873729251522535929523058146502134039291818305433125269108207522413691721413701

Guessing de la nouvelle clé

On a maintenant la clé privée vulnérable et on sait que la nouvelle clé a seulement 15 bits (de poids fort) de plus.

Autrement dit, il faut qu’on test toutes les clés privées de :

à:

Et on essaye de déchiffrer le message 5 avec. On pourrait générer une clé privée au format PEM et essayer de déchiffrer à chaque fois, mais ça ne sert pas à grand chose.

Pour rappel, soit :

le message déchiffré est de la forme:

D = C^d (mod n)

15 bits, cela nous laisse 32768 possibilités, ça se fait. Comme on ne sait pas trop quoi grep, on encode (vu qu’on a le modulus et l’exposant) une chaine test.

#!/usr/bin/env python2
import base64

f = open('message5.enc','r')
message=int(''.join(f.readlines()).encode('hex'),16)
print ("Decoding %s" % (message))

n=21366492123330192964924886088575120130580505285618005337598779393918158366095860314554624383933689053870136396844123653676006925524741292126254656621054312317488860350335644693660072975675200628822422500931919691892843464050189876133676632331854230569505119706533140321738621825798678419974354016241136135473558291408190378447009564861468655441762111819625530204222794596983686375221621285290161316292631745942916328382290893783027800227234537987550709843386531964868921678876556502069704928602524024016573461597745827047399490031977053086313049670592129066573978022028704080173611024083444448721653315439252412598269
e=13732360079110181240497677642215176108972109640426749948082012527371702942276535907897268515666425923651716194223110185976833857149823940477027664459847846465698314333714664894229797936194528230377354774167502776943806747294466329160071966807261130140612018061882530418266656946272804342401100046825871687041880398631430047689251191900448053221057251089983695108688262411466368305600843193430185646379147527635445503594868124985276184603136855197964909292552585042440140584014599152179794865999264471514598680594671108058750423041307860835401675889158127604590449840606756185017263994371070906353224669161795233799341
d=str(bin(3729092172867755527822307742234078358263625236042905659081826128798496778443873729251522535929523058146502134039291818305433125269108207522413691721413701)).replace('0b','')

test=int("testtest".encode('hex'),16)
encoded=pow(test,e,n)

for i in range(32768,0,-1):
    new_d=int((str(bin(i).replace('0b',''))) + d,2)
    decoded = pow(encoded, new_d, n)
    res = ("%0512x" % decoded).decode("hex")
    if "test" in res:
        print "Found %s with d=%s" % (res, new_d)
        print "Decoding message ..."
        flag = pow(message, new_d, n)
        print "Flag is %s" % flag

J’ai eu le présentiment que la valeur serait plutôt dans la 2eme moitié de l’interval (probablement un premier bit à 1), d’où le range inversé.

Et au final :

$ time python test.py
Decoding 8426452303336113530531862405729173452527546476364125612796157244664027393204265763905571614665064098073958364443217692230464705636940308067311403849008443940630842431947294008359992347944352937448881590966278948545361430258382541283450052595632573911658648010132478987353381310853980045242522464906170842633745205961806926411513966061649426299579742206398557069093849406944300257151805858097470857428154348848538454281413636390797206250968329856355934245955794613665643242310847330907437375441095867136357400575748414868839213817066295739698385318662924698446569153933534988504939386675860960880213049090998033926083
Found testtest with d=148830397114535695560799499787827126093379224233811609398390613851440379230594815316230056232188557570417500128004034456294973532337876034612935917659254879301
Decoding message ...
Flag is [...]RGUgOiBBbGljZQ0KQSA6IEJvYg0KXzNORF9vZl9GfGFHfQ==

On voit un joli base64 à la fin, qui une fois décodé donne :

$ echo "RGUgOiBBbGljZQ0KQSA6IEJvYg0KXzNORF9vZl9GfGFHfQ==" |base64 -d
De : Alice
A : Bob
_3ND_of_F|aG}

Note: Si on veut faire plus propre, on peut regénérer la clé privée complète :

$ rsatool.py -d 148830397114535695560799499787827126093379224233811609398390613851440379230594815316230056232188
557570417500128004034456294973532337876034612935917659254879301 -e 137323600791101812404976776422151761089721096404267499480820125273717
0294227653590789726851566642592365171619422311018597683385714982394047702766445984784646569831433371466489422979793619452823037735477416
7502776943806747294466329160071966807261130140612018061882530418266656946272804342401100046825871687041880398631430047689251191900448053
2210572510899836951086882624114663683056008431934301856463791475276354455035948681249852761846031368551979649092925525850424401405840145
9915217979486599926447151459868059467110805875042304130786083540167588915812760459044984060675618501726399437107090635322466916179523379
9341 -n 21366492123330192964924886088575120130580505285618005337598779393918158366095860314554624383933689053870136396844123653676006925
5247412921262546566210543123174888603503356446936600729756752006288224225009319196918928434640501898761336766323318542305695051197065331
40321738621825798678419974354016241136135473558291408190378447009564861468655441762111819625530204222794596983686375221621285290161316292631745942916328382290893783027800227234537987550709843386531964868921678876556502069704928602524024016573461597745827047399490031977053086313049670592129066573978022028704080173611024083444448721653315439252412598269  -o private.pem
[...]

$ openssl rsautl -decrypt -in message5.enc -inkey  privkey.pem |base64 -d
De : Alice
A : Bob
_3ND_of_F|aG}

Le flag est donc bzhctf{B3g1N_0f_Fl4g_3ND_of_F|aG}