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

Présentation d’un write-up de résolution du challenge « Crypto – A balanced RSA a day keeps the security analyst away! » du WARGAME de la Nuit du Hack 2016.

Le weekend du 02-03 juillet 2016 se déroulait le WARGAME de la Nuit du Hack 2016 sous forme d’un CTF Jeopardy. Ayant eu l’occasion et le temps d’y participer avec quelques collègues et amis, voici un write-up de résolution d’un des challenges auquel nous avons pu participer.

• Catégorie : Crypto
• Nom : 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 : extraction de N et e de pub_key, factordb p et q, rsatool privatekey.pem, openssl pour déchiffrer le flag

Un petit challenge de crypto ! Commençons par regarder le contenu de l’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 : la clé asymétrique publique RSA de freeman;
• aes_key_cipher : la clé symétrique AES256 chiffrée via la clé privée RSA de freeman sans salt (que l’on n’a pas…);
• ciphermessage : le flag chiffré via la clé AES précédente.

Il faut donc :

1. Retrouver la clé privée RSA de freeman à partir de sa clé publique;
2. Déchiffrer le contenu de « aes_key_cipher » à partir de la clé privée afin d’obtenir la clé secrète AES;
3. Déchiffrer « ciphermessage » à partir de la clé secrète AES256 précédemment obtenue.

Regardons de quoi est faite la clé publique de freeman et notamment son exposant (e) et son 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-----

On converti la valeur hexadécimale du modulus (N) en décimal :

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

On a donc :

• e : 65537
• N :

299996217561787292756826251240073744022587364427659002955601969311597453693948323421942282716737653493469667806494795328718748694431287426493332498123774403296361258944222401796946976412532226598881087042326060698386611304550152758781853605660146138394024484376984580234460609993575374222942038026173435262460884234328411077658271473762471945787635582916630508147146325427058379173689622281755189370552117476758492729644576568772220182957835384550972772092654842082706142246481708409910183742375894996805693099913395071166112170527842473265346582564838421321907545834628201837626578791668861148755559537560386588395858682503

Tentons de factoriser N via « factordb« .

Bingo ! On obtient p et q, ce qui nous fait :

• e : 65537
• N :

299996217561787292756826251240073744022587364427659002955601969311597453693948323421942282716737653493469667806494795328718748694431287426493332498123774403296361258944222401796946976412532226598881087042326060698386611304550152758781853605660146138394024484376984580234460609993575374222942038026173435262460884234328411077658271473762471945787635582916630508147146325427058379173689622281755189370552117476758492729644576568772220182957835384550972772092654842082706142246481708409910183742375894996805693099913395071166112170527842473265346582564838421321907545834628201837626578791668861148755559537560386588395858682503

• p : 10038779
• q :

29883735617826360432561196061799322808340273695402498944901762386799973751185111597928620872791168477109583526691323250438997481111127899766827469568139153506254222644429407380812644287968908031433014616849923750526494437675154793105999604698952545762191247000953460598590785791138083050034475111582139148840798690192144988714092767034962314220448082671869806890573676881128509669720752123515737259536455327561100082952775090354336935095177947890970881228947747737320060761022999750259487109176912351273565550144434404937703297435658507201458123798206776075248548238249711627044143395493501863997161361711457796649957

Il nous faut maintenant déterminer d. L’outil « rsatool.py » est particulièrement adapté pour cela. Il permet même de régénérer la « privatekey.pem » automatiquement :

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

Par soucis de visibilité, la commande qui suit de lancement de « rsatool » ne comprend pas les valeurs complètes de N, p et 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

La clé privée de freeman a été recréée via la déduction de la valeur de « d ». celle-ci est automatiquement sauvée par « rsatool » dans « privatekey.pem ».

Passons à la récupération (déchiffrement) de la clé symétrique AES contenue dans « 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

On a la clé secrète « rsa_hackerzvoice_for_win » !

Déchiffrons le cipher final pour obtenir le 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

Merci à toute l’équipe de la NDH2K16 pour cet événement et pour toute l’organisation !

Salutations à nj8, St0rn, Emiya, Mido, downgrade, Ryuk@n et tout ceux dont je n’ai hélas pas le pseudo :), on remet ça quand vous voulez ? // Gr3etZ

Sources & ressources :

• FactorDB
• rsatool