Solution to 35C3 Junior CTF challenge Decrypted

04/01/19 — capitol

cube_root

Name:

Decrypted

Category:

crypto

Points:

500 (variable)

Writeup

This challenge was a part of a group of 12 challenges that all shared the same large code base.

The function that we needed to crack in order to get the flag was this one:

@app.route("/wee/encryptiontest", methods=["GET"])
def encryptiontest():
    global encrypted
    if not encrypted:
        wee = """
        # we use weelang to encrypt secrets completely secret

        record pubkey
            n: string
            e: string
        end

        var key = pubkey('951477056381671188036079180681828396446164466568923964269373812360568216940258578681673755725586138473475522188240856850626984093905399964041687626629414562063470963902807801143023140969
20823423927677839717181758259182700869005678976353417411986304610681351575086373354375831981119478424684513892149555631145818047853885655084250969268639667911790304014860764271083257383802727400495207251674916842
54346976900167073270029894070147537353137306531896615417508808552131659375645782924643791678577787591364741734258313403069197056729334867119393339537506377299674551184754083697516025382028181906639397068860930465
26104043062374288648189070207772477271879494000411582080352364098957455090381238978031676375437980396931371164061080967754225429135119036489128165414029872153856547376448552882344531325480944511714482341088742350
11009737276674836492694100044152415782485951155734267352438805604935836260092517229999071999887386803819455546500803649793294581284534063885339973272198722848685819397907391376176037076960934762279549898730682241
31342367496077356579676679029666679967972413646887939190664453605477491938458252983426262889901587301497273983541920536923607163838510512716185590750480128002352503878370525735411578459589488569540357589151578719
93646182544696043757263004887914724250286341123038686355398997399922927237477691269351791943572679717263938613148630387793458838416117454016370454288153779764863162055098229903413503857354581027436855574871814478
74723799961787902440740395490598696972133680325877451439760094717565024267419349661465226715875381735013630562026807645781307072609924868164261206320317044245340505145587752470936697306277403704477207972070374382
86953511989843348305321935645259169014617255384187145173023908500495438565426993913390759768430286540045521692775713390171616970133736227701154066810802949947906265571171298204579880459740095301856221139515408199
39983153190486345031549722007896699102268137425607039925174692583738394816628508716999668221820730737934785438568198334912127263127241407430459511422030656861043544813130287622862247904749760983465608684778389799
70377087793187526885852470299176745072077367763985697993040450875510062484434182989649790682452018005103877912656386045303903577945538773305634383377680271619413807252827814278690190434340737764900098814225536986
0324110311816186668720584468851089864315465497405748709976389375632079690963423708940060402561050963276766635011726613211018206198125893007608417148033891841809', '3')

        fun encrypt(message: string, key: pubkey): string
            return bigModPow(strToBig(message), key.e, key.n)
        end

        fun get_cypher(key: pubkey): string
            var message = '{}'
            return encrypt(message, key)
        end

        alert(get_cypher(key))
        """.format(DECRYPTED)
        encrypted = runwee(wee)
    return jsonify({"enc": encrypted})

And calling that function gave us this ciphertext in form of a large number:

650802889626540392576254226480769958677174063746262298961949406725587937603370598056914641680440287141866554424868358513810586735136666559905873773370795301824775736764582520414393058823900835653671443326759384479590622850329114068561701339992264327486363426970702107667234446480134526246514585103292832378240690398119481568246551291749012927947948046185733533974179911092159848587

The encryption code is a simple school book example on how to implement RSA with a classical mistake of not using any padding.

The public key is also quite big, 2466 decimal digits, or 8192 bits. The encrypted flag is not that big however: 381 decimal digits, or 1266 bits. This makes the modulus part of RSA to not kick in, and the RSA algorithm is reduced from

y = x^e mod n

to

y = x^e

And this is trivially solved by taking the cube root of the number since the exponent, key.e, is 3.

We wrote this sage program to solve it:

from sage.crypto.util import bin_to_ascii, ascii_to_bin

a = Integer(650802889626540392576254226480769958677174063746262298961949406725587937603370598056914641680440287141866554424868358513810586735136666559905873773370795301824775736764582520414393058823900835653671443326759384479590622850329114068561701339992264327486363426970702107667234446480134526246514585103292832378240690398119481568246551291749012927947948046185733533974179911092159848587)
p = pow(a, 1/3)
pa = p.ceil().binary()
pb = "00" + pa;
print(bin_to_ascii(pb))

The flag was: 35C3_OUR_CRYPTO_IS_AS_LEGIT_AS_MOST_CRYPTO_CURRENCIES