# CQFD

## Énoncé

Pas d'énoncé ¯_(ツ)_/¯

## État de l'art

Le fichier du challenge est une capture de traffic réseau.

$ file capture.pcap 
capture.pcap: pcap capture file, microsecond ts (little-endian) - version 2.4 (Ethernet, capture length 262144)

$ trid capture.pcap 

TrID/32 - File Identifier v2.24 - (C) 2003-16 By M.Pontello
Definitions found:  10792
Analyzing...

Collecting data from file: capture.pcap
100.0% (.PCAP/ACP) TCPDUMP's style capture (little-endian) (4000/1)


### Statistiques

Wireshark nous indique les éléments suivants.

- 84 packets **(Statistics > Conversations > Ethernet : Packets)**
- 2 adresse ethernet différentes **(Statistics > Endpoints > Ethernet)**
- 4 adresses IPv4 différentes **(Statistics > Endpoints > IPv4)**
- Aucune adresse IPv6 **(Statistics > Endpoints > IPv6)**
- 8 connections TCP différentes **(Statistics > Conversations > TCP)**
- Aucune connection UDP **(Statistics > Conversations > TCP)**

### Contextualisation

On peut facilement traiter manuellement cette quantité de données. Les communications sont toutes en HTTP ou TLSv1.2. Le challenge étant dans la catégorie `crypto`, il s'agit probablement de déchiffrer les flux TLS.

4 certificats sont dans la capture. Nous pouvons extraire chaque certificat en sélectionnant le paquet `Server Hello, Certificate, Server Hello Done`. Clic droit sur `SSL > TLS Certificate > Handshake > Certificates > Certificate` puis `Export packet bytes...`.


Nous pouvons également obtenir des informations sur ces certificats avec l'outil `ssldump`.

$ ssldump -r capture.pcap
New TCP connection #1: 172.30.24.1(56706) <-> 84-139-15-51.rev.cloud.scaleway.com(443)
[...]
          server_name
              host_name: www.iluvprimes.com
[...]

New TCP connection #3: 172.30.24.1(39238) <-> 213.56.166.109(443)
[...]
          server_name
              host_name: www.ssi.gouv.fr
[...]

New TCP connection #4: 172.30.24.1(58356) <-> 95-198-15-51.rev.cloud.scaleway.com(443)
[...]
          server_name
              host_name: www.cryptoftw.fr     
[...]

On peut supposer que le second certificat est suffisamment solide et que ça n'est pas le sujet ici. Les `server_name` des deux autres sont déjà plus folkloriques.

### Certificats

Soit `pub1.der` et `pub2.der` respectivement les certificats pour les server_name `www.iluvprimes.com` et `www.cryptoftw.fr`.

$ openssl x509 -inform DER -in pub1.der -pubkey -noout > pub1.key
$ openssl x509 -inform DER -in pub2.der -pubkey -noout > pub2.key
$ openssl rsa -pubin -in pub1.key -text -noout 
RSA Public-Key: (2047 bit)
Modulus:
    65:e3:8a:08:e4:ed:c7:40:c8:cc:92:db:b0:9d:59:
    db:4a:c5:ba:2a:ca:75:c9:5f:17:e4:0b:df:48:44:
    9f:b7:e0:d7:fb:35:36:51:96:f0:43:14:d9:ce:9f:
    a9:f9:d4:6b:a1:c7:f4:61:df:f9:e4:08:a4:95:f7:
    c9:70:ca:77:92:c7:26:4d:6c:ec:89:e3:b6:a2:ab:
    86:a3:32:6f:fe:44:04:0e:b4:d8:70:f2:5c:d0:58:
    f4:29:c8:6b:da:1a:12:ed:fd:3c:dc:83:89:01:a2:
    43:74:b1:46:8d:69:bd:6c:60:86:ff:13:89:4a:ab:
    dc:77:40:43:b9:90:b4:cd:16:6f:10:c0:e8:2e:a5:
    bd:d6:82:00:ab:91:e8:38:3c:53:e8:9f:e3:27:89:
    e7:00:85:14:af:82:18:d2:fc:46:1e:8e:4f:16:9c:
    67:fd:1b:7f:d6:df:6a:00:a1:59:14:b4:8f:b3:e5:
    79:29:7d:07:0a:f8:48:71:1c:de:95:5c:34:e6:f3:
    4a:fa:60:97:98:95:90:8c:21:ac:b3:a1:2e:bf:68:
    ae:b1:68:2a:d1:23:d0:14:35:50:fc:60:59:bb:0d:
    98:02:88:69:f8:64:bf:98:5a:be:c3:b9:fe:4d:8b:
    2e:02:da:73:fc:63:12:2b:17:d5:f9:80:dd:c5:7d:
    f1
Exponent: 65537 (0x10001)

$ openssl rsa -pubin -in pub2.key -text -noout
RSA Public-Key: (2048 bit)
Modulus:
    00:8f:02:91:66:fd:f2:a6:b4:54:99:9a:f0:85:54:
    80:01:8c:bd:3a:de:ea:ab:93:fe:af:6d:3c:07:fa:
    1c:1c:d9:cb:ce:ef:31:28:b7:55:96:0d:34:80:48:
    fc:87:98:85:2a:5c:5b:e4:89:35:b6:ce:1a:63:9f:
    19:f9:ab:31:5a:ef:4d:c8:1b:62:33:2a:6e:9a:d4:
    5a:c8:20:e0:c0:50:8e:44:67:76:16:12:0a:5f:67:
    f2:b2:e5:5c:cf:6e:16:2a:5a:a4:37:4e:99:64:24:
    58:2d:f7:74:27:4c:5e:5d:7f:e2:55:b1:65:84:bb:
    81:00:84:fe:ae:14:a0:d3:9f:ed:7a:de:42:bd:9e:
    55:ca:80:a2:b4:91:78:d8:b2:3a:f6:15:e4:3c:75:
    86:b4:38:7f:8d:c6:17:51:7a:57:cb:be:67:42:29:
    f3:4b:35:45:c0:e5:4b:30:63:64:d6:a1:b5:82:55:
    de:92:c3:d8:47:fe:cd:ac:27:40:e8:5d:1c:db:fa:
    3a:ac:3c:8b:73:4d:4a:40:53:f8:98:a9:11:40:bf:
    9a:b6:01:ab:6f:de:2d:a0:93:9f:89:e3:79:8b:0b:
    54:72:d0:9b:a6:8b:b6:7d:b7:74:5a:f2:20:c4:de:
    4e:17:9c:df:85:80:9d:54:a1:51:6a:74:b4:5b:c2:
    f1:b3
Exponent: 65537 (0x10001)

On a ici deux clés publiques RSA-2048. À ce jour, personne n’a pu publiquement factoriser RSA-2048. Nous allons donc probablement devoir trouver un autre moyen d'attaquer le module de ces certificats.

## Attaque des clés publiques

### RsaCtfTool

Sans rentrer dans détails techniques de chaque attaque, il en existe une multitude. Voyons si quelque chose marche.

L'outil [RsaCtfTool](https://github.com/Ganapati/RsaCtfTool) est un très bon outil (de CTF surtout) pour attaquer des clés publiques. Le script va notamment :
- Chercher les facteurs premiers du module dans des bases telles que factordb;
- Tenter d'attaquer le module et voir si la factorisation est "faible";
- Tenter l'attaque Hastad (exposant public petit);
- Et bien d'autres attaques (mersenne_primes, noveltyprimes, smallq, wiener, comfact_cn, primefac, fermat, siqs, Pollard_p_1,all).

Malheureusement, `RsaCtfTool` ne donne rien.

$ rsactftool --verbose --private --publickey pub1.key
[*] Performing hastads attack.
[*] Performing factordb attack.
[*] Performing pastctfprimes attack.
[*] Loaded 71 primes
[*] Performing mersenne_primes attack.
[*] Performing noveltyprimes attack.
[*] Performing smallq attack.
[*] Performing wiener attack.
[*] Performing comfact_cn attack.
[*] Performing primefac attack.
[*] Performing fermat attack.
[*] Performing siqs attack.
[!] Warning: Modulus too large for SIQS attack module
[*] Performing Pollard_p_1 attack.
[-] Sorry, cracking failed

$ rsactftool --verbose --private --publickey pub2.key
[idem]

### Attaque ROCA

Quelques recherches sur les attaques possibeles sur une clé publique RSA-2048 m'amènent [ici](https://ctftime.org/writeup/8805). Il est question ici d'attaque ROCA.

> Une implémentation de l’algorithme RSA au sein des puces Infineon est vulnérable à l’attaque dénommée ROCA (Return of Coppersmith’s Attack) qui touche la génération des clés par la librairie cryptographique. Toute clé privée RSA inférieure ou égale à 2048 bits et générée par les puces d’Infineon Technologies AG peut être retrouvée à partir de la clé publique correspondante. (cf. [cyberveille-sante.gouv.fr](https://www.cyberveille-sante.gouv.fr/cyberveille/264-vulnerabilite-critique-impactant-lalgorithme-de-generation-des-cles-rsa-roca-2017))

$ git clone https://gitlab.com/jix/neca
$ sudo apt-get install cmake
$ cd neca
$ cmake .
$ make
$ python -c "print(int(\"$(openssl rsa -pubin -in ../pub1.key -modulus -noout | cut -d "=" -f2)\", 16))" 
12862272562103424721436654564272304657609534482185665387600821410880521595524480937003540764964868094076026072506938788276319781278760050706594940055306345783111506068623090529020904720840323597550392798019777140032752947813309214536936857545104051608274551357465157572571547853159799500153864387715109447611346236295086674020094149039310293386230081483725119888010418464290176729751485892981968533726813150894269074250237445299088035980653939821337253721972102525176865299992319914895220563812837475572503917276817276445943174224296660112124422839613356296081387438965212164340903794474969142246462653812069150064113

$ ./neca $(python -c "print(int(\"$(openssl rsa -pubin -in ../pub1.key -modulus -noout | cut -d "=" -f2)\", 16))" | tr -d "\n")
[...]
Given key does not seem to be weak.

$ ./neca $(python -c "print(int(\"$(openssl rsa -pubin -in ../pub2.key -modulus -noout | cut -d "=" -f2)\", 16))" | tr -d "\n")
[...]
Given key does not seem to be weak.

Raté...

### Attaque par facteur commun

Quelques ~~(une quantité astronomique de)~~ recherches plus tard, je tombe sur [ce writeup](https://zonesec.org/fr-quals-grehack-2k18-network/). Une autre façon d'attaquer un couple de module est de chercher un facteur commun en tirant partie de la difficulté pour certains systèmes de générer des grands nombres aléatoires.

$ git clone https://github.com/sagi/fastgcd
$ cd fastgcd
$ ./install.sh
$ openssl rsa -pubin -in pub1.key -modulus -noout | cut -d "=" -f 2 > modules.moduli
$ openssl rsa -pubin -in pub2.key -modulus -noout | cut -d "=" -f 2 >> modules.moduli
$ ./fastgcd modules.moduli
$ cat vulnerable_moduli
[module1]
[module2]
$ cat gcds
91b19518125d563294f1aba371ebd06cb4a851dbdbe62e25767f0b7f80ef69627baab904c999af0c02df0ac36c254a6c7b82ebcce3d650862065f1022d7dedc1480399e16c98c56983b48c363d38c5d4a4dbf0719474f22eb356da2a1acca0810791da56b2bee7ce3a4f5f0f869e386a9a177aa4985479d7316c59c1c82fe35f
91b19518125d563294f1aba371ebd06cb4a851dbdbe62e25767f0b7f80ef69627baab904c999af0c02df0ac36c254a6c7b82ebcce3d650862065f1022d7dedc1480399e16c98c56983b48c363d38c5d4a4dbf0719474f22eb356da2a1acca0810791da56b2bee7ce3a4f5f0f869e386a9a177aa4985479d7316c59c1c82fe35f

Bingo! On trouve un facteur premier commun pour les deux modules. On peut donc maintenant trouver le seul paramètre manquant pour générer des clés privées : le second facteur premier.

$ python -c 'print(int("91b19518125d563294f1aba371ebd06cb4a851dbdbe62e25767f0b7f80ef69627baab904c999af0c02df0ac36c254a6c7b82ebcce3d650862065f1022d7dedc1480399e16c98c56983b48c363d38c5d4a4dbf0719474f22eb356da2a1acca0810791da56b2bee7ce3a4f5f0f869e386a9a177aa4985479d7316c59c1c82fe35f",16))'
$ python
>>> mod1 = 12862272562103424721436654564272304657609534482185665387600821410880521595524480937003540764964868094076026072506938788276319781278760050706594940055306345783111506068623090529020904720840323597550392798019777140032752947813309214536936857545104051608274551357465157572571547853159799500153864387715109447611346236295086674020094149039310293386230081483725119888010418464290176729751485892981968533726813150894269074250237445299088035980653939821337253721972102525176865299992319914895220563812837475572503917276817276445943174224296660112124422839613356296081387438965212164340903794474969142246462653812069150064113
>>> mod2 = 18053343927187441108441676210352812208841821342176375072626907832579120529616542004286898021310125324177396453091146242892059023480248994812385743745829080533443709021801626752988504702779717383968935903480999751947593336274820105521875042566841237938309494595847368546040134225853055300125071970318904115478019359346905077910568516541409230598529104099513308295900154736804341485288504384483587566258326282352342852431455293545691814140471361311559581606313563521176326293297059267560469065513610526391626949122116277529307127764052525170569813954351374019777288115175379547188764678814330441682477499584967168160179
>>> p = 102309582252265727725340345451462353412917609251698470327358369038596447497782878994409403649899367357603426088862355403689989422161491768264328621320078645274330159165477896764608597302037237479418618729362585728029980211269117774589439387986392752717360615171973810177719407580656540183624752965381895742303
>>> q1 = mod1 / p
>>> q2 = mod2 / p
>>> print q1
125719138705784123981847760107353155221882767209282696996965365992026982759758663118724123157393002768533176626973097645949189824701082982581701050294390522480835951921853654312282010346776587123903192192907425920069889168729347508276355649273626333244122472994469367988621590243736589293453607998476471300271
>>> print q2
176457996697446541797078410681787975133044515403509374804191105369011520443365030282337656325217135953227384636548119123621186869405770201501319516665267152735988889608562764690464368640847985329674996378162898832997914646190946704515696039119406636883505009715464637237568076162984205812746062622257115842093

## Résolution

### Génération des clés privées

Nous avons maintenant tous les paramètres nécessaires pour générer des clés privées.

$ rsactftool -n 12862272562103424721436654564272304657609534482185665387600821410880521595524480937003540764964868094076026072506938788276319781278760050706594940055306345783111506068623090529020904720840323597550392798019777140032752947813309214536936857545104051608274551357465157572571547853159799500153864387715109447611346236295086674020094149039310293386230081483725119888010418464290176729751485892981968533726813150894269074250237445299088035980653939821337253721972102525176865299992319914895220563812837475572503917276817276445943174224296660112124422839613356296081387438965212164340903794474969142246462653812069150064113 -p 102309582252265727725340345451462353412917609251698470327358369038596447497782878994409403649899367357603426088862355403689989422161491768264328621320078645274330159165477896764608597302037237479418618729362585728029980211269117774589439387986392752717360615171973810177719407580656540183624752965381895742303 -q 125719138705784123981847760107353155221882767209282696996965365992026982759758663118724123157393002768533176626973097645949189824701082982581701050294390522480835951921853654312282010346776587123903192192907425920069889168729347508276355649273626333244122472994469367988621590243736589293453607998476471300271 -e 65537 --private > priv1.key
$ rsactftool -n 18053343927187441108441676210352812208841821342176375072626907832579120529616542004286898021310125324177396453091146242892059023480248994812385743745829080533443709021801626752988504702779717383968935903480999751947593336274820105521875042566841237938309494595847368546040134225853055300125071970318904115478019359346905077910568516541409230598529104099513308295900154736804341485288504384483587566258326282352342852431455293545691814140471361311559581606313563521176326293297059267560469065513610526391626949122116277529307127764052525170569813954351374019777288115175379547188764678814330441682477499584967168160179 -p 102309582252265727725340345451462353412917609251698470327358369038596447497782878994409403649899367357603426088862355403689989422161491768264328621320078645274330159165477896764608597302037237479418618729362585728029980211269117774589439387986392752717360615171973810177719407580656540183624752965381895742303 -q 176457996697446541797078410681787975133044515403509374804191105369011520443365030282337656325217135953227384636548119123621186869405770201501319516665267152735988889608562764690464368640847985329674996378162898832997914646190946704515696039119406636883505009715464637237568076162984205812746062622257115842093 -e 65537 --private > priv2.key

### Déchiffrement des flux TLS

Pour déchiffrer les flux TLS, il faut importer les clés privées dans les préférences de Wireshark **(Edit > Preferences > Protocols > SSL > RSA keys list)**.


Dans les versions les plus récentes de Wireshark il n'est normalement pas nécessaires de renseigner d'autres informations que le chemin des clés.


Certaines communications sont déchiffrées. On peut renseigner le filtre `http.response.code == 200` pour retrouver les 2 parties du flag (paquets 11 et 79).

Le flag est **ECSC{77ee6f654aaec8d8a01f0a3e053315120252d484}**.