[WARGAME NDH 2016] Write-Up – Crypto: A balanced RSA a day keeps the security analyst away!

Write-up of the challenge “Crypto – A balanced RSA a day keeps the security analyst away!” of Nuit du Hack 2016 Wargame

The weekend of 02-03 july 2016 is the WARGAME of the Nuit du Hack 2016 as a Jeopardy CTF. Having had the opportunity and the time to participate with some colleagues and friends, here’s a write-up resolution of the challenges which we could participate.

• Category: Crypto
• Name: A balanced RSA a day keeps the security analyst away!
• Description : hey guys, i have intercepted a communication between freeman and majinboo about challs for tonight, and i wanted to troll them by divulgating flags… Unfortunately, i was not able to do so however i got some infos about the tool they use in their encrypted communication. here is what i have so far : rsa public key of freeman, used to encode an aes 256 key with no salt, which is then used to encode the flag.
• URL : http://static.wargame.ndh/rsa.zip (download rsa.zip)
• Points : 150

tl;dr : extract N and e from pub_key, factordb p and q, rsatool privatekey.pem, openssl to get the flag

A small crypto challenge! Start by looking at the contents of the archive:

root@kali 14:23 [~/ndh2k16/rsa/rsa] # ll
total 20
drwxrwxr-x 2 root root 4096 juin 23 19:42 .
drwxrwxr-x 3 root root 4096 juil. 6 14:23 ..
-rw-rw-r-- 1 root root 259 juin 12 12:16 aes_key_cipher
-rw-rw-r-- 1 root root 160 juin 23 19:41 ciphermessage
-rw-rw-r-- 1 root root 455 juin 12 12:10 pub_key

• pub_key : Public RSA asymmetric key of freeman;
• aes_key_cipher : the symmetric key AES 256 encrypted via RSA private key freeman without salt
• ciphermessage : the flag encrypted via AES with the previous key.

We have to :

• Find the RSA private key of freeman from his public key;
• Decrypt the content of “aes_key_cipher” from the private key to obtain the secret key AES;
• Decrypt “ciphermessage” from the secret key AES256 previously obtained.

Let’s look at the public key and in particular exponent (e) and modulus (N):

root@kali 13:49 [~/ndh2k16/rsa] # openssl rsa -pubin -in pub_key -text -modulus
Public-Key: (2072 bit)
Modulus:
 00:8d:a5:69:19:b5:26:d4:52:25:ac:ed:4b:e6:45:
 22:ce:f0:4a:63:91:0b:9f:6f:fe:a6:b1:12:55:41:
 01:3b:e4:5d:48:b6:fb:26:71:b7:54:0e:6a:4e:0b:
 55:e3:a9:e4:c4:5a:8d:5f:54:a0:69:9c:65:32:d4:
 a1:28:7f:ac:b0:08:b1:c5:6e:35:d6:01:dc:2a:9e:
 2e:66:51:89:ea:a3:5d:22:d7:be:a2:52:c1:ec:f2:
 70:31:ab:65:7d:5b:35:e8:2c:de:70:f8:25:9d:2e:
 14:e9:86:f3:62:e3:e8:6e:7b:d8:e4:81:2a:52:f2:
 e8:cc:2f:69:b8:b0:c9:59:77:8f:db:24:0a:8e:17:
 cb:95:72:45:70:12:d8:3b:6c:72:72:90:e5:0b:8e:
 7d:a2:8f:eb:df:ab:f5:23:da:03:b9:4b:94:32:2a:
 f4:21:f9:ca:02:ad:e6:04:da:ab:92:cd:9c:28:24:
 44:36:f1:15:fd:be:d7:6d:2c:85:00:7a:ca:7f:ce:
 49:89:3a:f8:0e:79:55:63:2e:c7:b8:9f:56:fa:b0:
 18:76:e0:fe:88:29:9a:37:34:0d:43:9c:b2:e0:1b:
 3c:07:e6:0c:88:47:42:1b:fe:04:9d:59:95:40:6b:
 26:f4:a0:8b:20:d1:49:b3:c6:1a:ae:a3:53:1d:62:
 f8:f8:d1:e2:87
Exponent: 65537 (0x10001)
Modulus=8DA56919B526D45225ACED4BE64522CEF04A63910B9F6FFEA6B1125541013BE45D48B6FB2671B7540E6A4E0B55E3A9E4C45A8D5F54A0699C6532D4A1287FACB008B1C56E35D601DC2A9E2E665189EAA35D22D7BEA252C1ECF27031AB657D5B35E82CDE70F8259D2E14E986F362E3E86E7BD8E4812A52F2E8CC2F69B8B0C959778FDB240A8E17CB9572457012D83B6C727290E50B8E7DA28FEBDFABF523DA03B94B94322AF421F9CA02ADE604DAAB92CD9C28244436F115FDBED76D2C85007ACA7FCE49893AF80E7955632EC7B89F56FAB01876E0FE88299A37340D439CB2E01B3C07E60C8847421BFE049D5995406B26F4A08B20D149B3C61AAEA3531D62F8F8D1E287
writing RSA key
-----BEGIN PUBLIC KEY-----
MIIBJTANBgkqhkiG9w0BAQEFAAOCARIAMIIBDQKCAQQAjaVpGbUm1FIlrO1L5kUi
zvBKY5ELn2/+prESVUEBO+RdSLb7JnG3VA5qTgtV46nkxFqNX1SgaZxlMtShKH+s
sAixxW411gHcKp4uZlGJ6qNdIte+olLB7PJwMatlfVs16CzecPglnS4U6YbzYuPo
bnvY5IEqUvLozC9puLDJWXeP2yQKjhfLlXJFcBLYO2xycpDlC459oo/r36v1I9oD
uUuUMir0IfnKAq3mBNqrks2cKCRENvEV/b7XbSyFAHrKf85JiTr4DnlVYy7HuJ9W
+rAYduD+iCmaNzQNQ5yy4Bs8B+YMiEdCG/4EnVmVQGsm9KCLINFJs8YarqNTHWL4
+NHihwIDAQAB
-----END PUBLIC KEY-----

We convert the hexadecimal value modulo (N) in decimal:

root@kali 13:50 [~/ndh2k16/rsa] # python -c "print int('8DA56919B526D45225ACED4BE64522CEF04A63910B9F6FFEA6B1125541013BE45D48B6FB2671B7540E6A4E0B55E3A9E4C45A8D5F54A0699C6532D4A1287FACB008B1C56E35D601DC2A9E2E665189EAA35D22D7BEA252C1ECF27031AB657D5B35E82CDE70F8259D2E14E986F362E3E86E7BD8E4812A52F2E8CC2F69B8B0C959778FDB240A8E17CB9572457012D83B6C727290E50B8E7DA28FEBDFABF523DA03B94B94322AF421F9CA02ADE604DAAB92CD9C28244436F115FDBED76D2C85007ACA7FCE49893AF80E7955632EC7B89F56FAB01876E0FE88299A37340D439CB2E01B3C07E60C8847421BFE049D5995406B26F4A08B20D149B3C61AAEA3531D62F8F8D1E287', 16)"

So we have :

• e : 65537
• N :

299996217561787292756826251240073744022587364427659002955601969311597453693948323421942282716737653493469667806494795328718748694431287426493332498123774403296361258944222401796946976412532226598881087042326060698386611304550152758781853605660146138394024484376984580234460609993575374222942038026173435262460884234328411077658271473762471945787635582916630508147146325427058379173689622281755189370552117476758492729644576568772220182957835384550972772092654842082706142246481708409910183742375894996805693099913395071166112170527842473265346582564838421321907545834628201837626578791668861148755559537560386588395858682503

Trying factorize N with “factordb“.

Yeah ! We get p and q :

• e : 65537
• N :

299996217561787292756826251240073744022587364427659002955601969311597453693948323421942282716737653493469667806494795328718748694431287426493332498123774403296361258944222401796946976412532226598881087042326060698386611304550152758781853605660146138394024484376984580234460609993575374222942038026173435262460884234328411077658271473762471945787635582916630508147146325427058379173689622281755189370552117476758492729644576568772220182957835384550972772092654842082706142246481708409910183742375894996805693099913395071166112170527842473265346582564838421321907545834628201837626578791668861148755559537560386588395858682503

• p : 10038779
• q :

29883735617826360432561196061799322808340273695402498944901762386799973751185111597928620872791168477109583526691323250438997481111127899766827469568139153506254222644429407380812644287968908031433014616849923750526494437675154793105999604698952545762191247000953460598590785791138083050034475111582139148840798690192144988714092767034962314220448082671869806890573676881128509669720752123515737259536455327561100082952775090354336935095177947890970881228947747737320060761022999750259487109176912351273565550144434404937703297435658507201458123798206776075248548238249711627044143395493501863997161361711457796649957

We must now determine d. The tool “rsatool.py” is particularly suitable for this. It can even regenerate “privatekey.pem” automatically:

wget https://raw.github.com/ius/rsatool/master/rsatool.py
sudo pip install rsa
sudo pip install gmpy

root@kali 13:56 [~/ndh2k16/rsa] # python rsatool.py
Usage: rsatool.py [options]

Options:
 -h, --help show this help message and exit
 -p P prime
 -q Q prime
 -n N modulus
 -d D private exponent
 -e E public exponent (default: 65537)
 -o FILENAME output filename
 -f FORMAT output format (DER, PEM) (default: PEM)
 -v also display CRT-RSA representation
Usage: rsatool.py [options]

rsatool.py: error: Either (p, q) or (n, d) needs to be specified

For reasons of visibility, the following command to launch “rsatool” does not include the full value of N, p and q:

root@kali 13:57 [~/ndh2k16/rsa] # python rsatool.py -p value_p -q value_q -n value_n -e 65537 -o privatekey.pem
Using (p, q) to initialise RSA instance

n =
8da56919b526d45225aced4be64522cef04a63910b9f6ffea6b1125541013be45d48b6fb2671b754
0e6a4e0b55e3a9e4c45a8d5f54a0699c6532d4a1287facb008b1c56e35d601dc2a9e2e665189eaa3
5d22d7bea252c1ecf27031ab657d5b35e82cde70f8259d2e14e986f362e3e86e7bd8e4812a52f2e8
cc2f69b8b0c959778fdb240a8e17cb9572457012d83b6c727290e50b8e7da28febdfabf523da03b9
4b94322af421f9ca02ade604daab92cd9c28244436f115fdbed76d2c85007aca7fce49893af80e79
55632ec7b89f56fab01876e0fe88299a37340d439cb2e01b3c07e60c8847421bfe049d5995406b26
f4a08b20d149b3c61aaea3531d62f8f8d1e287

e = 65537 (0x10001)

d =
832110ab2c16a116e1965b5a87800b80c7374bcd1dde39b22ffea11d47a31e0266364263206b696f
9b6d48e78aca4ad08d02ca47d421be8b1fcb2756e83234e3b143f1a30289c9414fe32af711a0b23e
faa244265d7220d49bfd36df47d47f1a65f35df7bb5e8f0ae7067ae7af31fb387df833e0eb66a425
3a268c5db5b37527cbd15b3de490334255ca3b59e0dd3e04b5bdc47a2997811f061bf5793e563007
54de5833c20f3d26e462590d27473cfcf10a20be329cb197389bc2476ce2d47648865fdff66034cd
47f90c3d83310841cb338eb6a58e577ff7624dad765559677bf638688edff35710010be99c86e355
a41bcd9b960d82b313c20da1dee473f3764759

p = 10038779 (0x992dfb)

q =
ecb98b849f081ab8e52f72310984d30963eea0069c8b9b8d43820228d5af136b93cc901481cbc932
009a3976d599457a9b128afddabb82d3be40e307bfa64c36868047f59a1e4dadade41a737c53612f
bc29c54b4ab461001144c18274d605145eba22e0c62c2a05ad884b0afb9ecd7cec9cf92c44ff05be
52271999b0cec6b7dfb3edba50be9ecd315cfd34247d4c5fa8c62b0e8a67d22bcfa7add17478c443
93b1524e048db062dbcb04bd04aeb8e338c969b84e746f7018e3cbacf5cb9d49fa4937aa183f9e25
13c45bd496f33aef03d894fa1194ba18909ad9f513f112b401c2418d7707c07cbf59cc0cd60dbb2c
7df8ef07e9784fd659e4adfedb2c73e5

Saving PEM as privatekey.pem

The private key of freeman was recreated by deducting the value of “d”. It is automatically saved by “rsatool” in “privatekey.pem”.

Go to recovery (decryption) of the AES symmetric key contained in “aes_key_cipher”

root@kali 14:10 [~/ndh2k16/rsa] # openssl rsautl -decrypt -in aes_key_cipher -out plaintext -inkey privatekey.pem && cat plaintext
rsa_hackerzvoice_for_win

We obtain the secret key “rsa_hackerzvoice_for_win” !

Decipher the final encrypted message to get the final flag:

root@kali 14:11 [~/ndh2k16/rsa] # openssl aes256 -d -in ciphermessage -out secrets.txt -nosalt && cat secrets.txt
enter aes-256-cbc decryption password: rsa_hackerzvoice_for_win
hey dude!
keep it up! https://www.youtube.com/watch?v=1F81S50xL8I
btw, i think the flag for this chall should be: ndh2k16_cac4015707
freeman

Flag : ndh2k16_cac4015707

Thank you to all the team of the NDH2K16 for this event and for the whole organization!

Greeting to nj8, St0rn, Emiya, Mido, downgrade, Ryuk@n and rikelm, ? // Gr3etZ

Sources & resources :

• FactorDB
• rsatool