(FR) Quals GreHack 2k18 – Network

Dans le cadre de la GreHack 2k18, une suite de challenge de qualification étaient proposés. Un en particulier m’a donné pas mal de fil à retordre, j’ai décidé d’en faire un writeup qui ne présente pas uniquement la solution, mais également mes pérégrinations.

Le challenge :


Le lien « DOWNLOAD FILE » permet de télécharger le pcap toujours dispo >ici< :

Objectif : trouver un « flag » de validation dans la capture réseau.

Spoiler : la solution est en dernière partie 😉

Tâtonnement 1

Ca ressemble à un peu à un scan de port fait depuis l’IP 5.135.166.161 lancé vers de multiples IP sur le port 443 :

Rien de classique ne m’a sauté aux yeux, je m’oriente vers la piste d’une faiblesse dans l’un des certificats (modulo de la clef publique factorisable …), je dump tous les certificats présents dans la capture (au nombre de 1683…) pour les analyser : (extraction massive faite avec NetworkMiner)

On les balances tous dans un rep de travail :

find ./ -name '*.cer' -exec cp {} ../grechall_cer \;

Je commence par le plus évident : chercher un certificat qui aurait une taille de clef publique trop faible.

 

Il n’y a que du >= 1024 bits, cette piste ne semble pas être la bonne….

Tâtonnement 2

J’ai quand même suivi la piste de la faiblesse dans les certificats, histoire d’être sûr et de pas juste me limiter à la taille de la clef publique.

Dans un premier temps j’ai extrait les différents modulus des clefs publiques des certificats utilisant RSA, et vérifié s’ils étaient dans la DB de factorisation de factorDB :

"""
extract modulus from cer and check if it had been factorized (thanks to factordb)
output csv : cer_name;status;modulus_hex;modulus_dec

status :
C   Composite, no factors known
CF  Composite, factors known
FF  Composite, fully factored
P   Definitely prime
Prp Probably prime
U   Unknown
Unit    Just for "1"
N   This number is not in database (and was not added due to your settings)
*   Added to database during this request
"""
import os
import subprocess
import requests
import time
import re

headers = {'User-Agent': 'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_10_1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/39.0.2171.95 Safari/537.36'}

for filename in os.listdir('.'):
    if filename.endswith("cer"):
        try :
            modulus_hex = subprocess.getoutput("openssl x509 -inform DER -in '%s' -modulus -noout |awk -F '=' '{print$2}'" % (filename))
        except subprocess.CalledProcessError :
            continue
        if "Wrong" not in modulus_hex :
            modulus_dec = int(modulus_hex,16)
            url = "http://www.factordb.com/index.php?query=" + str(modulus_dec)
            resp = requests.get(url, headers=headers)
            status = re.findall("</tr><tr><td>(.*?)</td>",resp.text)
            if 'F' in str(status) :
                print("====>") 
            print(filename + ";" + str(status) + ";" + str(modulus_hex) + ";" + str(modulus_dec) + "\n")
            with open('extrated_modulus.txt','a+') as outfile :
                outfile.write(filename + ";" + str(status) + ";" + str(modulus_hex) + ";" + str(modulus_dec) + "\n")
            time.sleep(1)

Rien dans factorDB, comme ça c’est réglé.

Par contre, j’ai pu remarquer que certains modulus (n) apparaissent plusieurs fois pour des certifs « différents » : ça pourrait eut être s’exploiter si les exposants publiques (e) sont égalements différents… mais ce n’est pas le cas ici.

A côté de ça j’ai récapitulé les algorithmes utilisés sur l’ensemble des sessions TLS :

  • RSA (1024)
  • RSA (2048)
  • RSA (4096)
  • ECC (256)
  • ECC (384)

Donc voilà voilà.. que du solide quoi.

Tâtonnement 3

J’ai creusé du côté d’éventuels weak ciphers en récupérant tous les ciphers utilisés dans chaque session TLS de la capture :

import scapy
from scapy_ssl_tls.ssl_tls import *
import sys

with open (sys.argv[2], 'w+') as outfile :
    outfile.write("ip serveur;version TLS;cipher used \n")

packets = rdpcap(sys.argv[1])
for packet in packets:
    if packet.haslayer(TLSServerHello) : 
        ip_srv = packet['IP'].src
        tls_ver = packet['SSL/TLS']['TLS Record'].version # TLS v1.0=769; TLS v1.1=770;TLS v1.2=771
        cipher = packet['SSL/TLS']['TLS Record']['TLS Handshake']['TLS Server Hello'].cipher_suite

        with open (sys.argv[2], 'a+') as outfile :
            outfile.write(str(ip_srv) + ";" + str(tls_ver) + ";" + str(cipher) + "\n")

Qui nous donne la liste suivante :

 

 

 

 

 

 

 

 

 

 

 

Là encore, que du solide.

Tâtonnement 4

J’ai continué à creuser la piste des certificats, pour voir si n’y a vraiment aucun moyen de « dériver » la clef privée de la clef publique : sans succès en essayant l’ensemble des attaques suivantes via RsaCtfTool (https://github.com/Ganapati/RsaCtfTool) sur chaque clef publique :

  • Weak public key factorization
  • Wiener’s attack
  • Hastad’s attack (Small public exponent attack)
  • Small q (q < 100,000)
  • Common factor between ciphertext and modulus attack
  • Fermat’s factorisation for close p and q
  • Gimmicky Primes method
  • Past CTF Primes method
  • Self-Initializing Quadratic Sieve (SIQS) using Yafu
  • Common factor attacks across multiple keys
  • Small fractions method when p/q is close to a small fraction
  • Boneh Durfee Method when the private exponent d is too small compared to the modulus (i.e d < n^0.292)
  • Pollards p-1 for relatively smooth numbers
  • Mersenne primes factorization

Mon CPU a brulé pendant près de 24h sans succès…

Tâtonnement 5

De retour sur le pcap en lui-même histoire de récapituler la base, au cas où quelque chose d’évident m’aurait échappé en premier lieu

– Aucune signature de fichier intéressante dans l’hexdump. Un coup de binwalk ne ressort que les certificats X509, et 2 classiques faux positifs de match de signature (mcrypt et unix path)

– Pas de pattern particulier au niveau de la valeur des ports sources ou IP dest, ça semble vraiment random

– QUE du 443 avec des sessions ouvertes depuis 5.135.166.161 qui héberge un site de présentation d’un tool « framework » de scan (IVRE — Network recon framework)

– C’est un chall « offline » et « self-contained » donc inutile de pousser du coté de IVRE

– Aucun flux TCP qui pourrait sortir du lot (443 mais non SSL/TLS, non SYN, SYN/ACK, ACK, et non RST) : Nada.

 

Solution ! (enfin :p)

A force de chercher tout ce que je pouvais, je suis finalement tombé là-dessus : https://factorable.net/weakkeys12.conference.pdf

Très bien repris et expliqué là : http://www.loyalty.org/~schoen/rsa/

Le but du jeu est de trouver, sur l’ensemble des modulos (différents) qu’on a récupéré, ceux qui peuvent partager un facteur en commun à grand coups de GCD (plutôt qu’en essayant de factoriser.  » Although factorization seems like a very hard problem, there’s a different problem that’s much easier — finding the greatest common divisor (« gcd ») of two numbers. ») en profitant de faiblesse de génération de grand nombres aléatoires de certains équipements (trop faible entropie des 2 facteurs p et q) (cf, par exemple : https://kb.juniper.net/InfoCenter/index?page=content&id=JSA10507).

Je me suis appuyé sur un outil qui implémente l’algo de calcul du GCD sur n modulus : https://github.com/sagi/fastgcd

Après avoir écarté les modulus en double, fastgcd nous remonte les certificats suivants  :

 

On commence par le premier :

récupération de tous les paramètres composant la clef privée (p, q, e) :

e étant l’exposant public : 65537 commun à toutes les clefs publiques de la capture.

Il y a peut être plus simple mais j’utilise un script qui a déjà fait ses preuves pour rassembler tout ce petit monde en une belle clef privée.

#!/usr/bin/python2
import pyasn1.codec.der.encoder  
import pyasn1.type.univ  
import base64
import sys

def recover_ke(p, q, e, output_file):  
    """Recoveres a RSA private key from:
        p: Prime p 
        q: Prime q
        e: Public exponent 
        output_file: File to write PEM-encoded private key to"""

    # SRC: https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
    def egcd(a, b):
        x,y, u,v = 0,1, 1,0
        while a != 0:
            q, r = b//a, b%a
            m, n = x-u*q, y-v*q
            b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
        return gcd, x, y

    def modinv(a, m):
        gcd, x, y = egcd(a, m)
        if gcd != 1:
            return None  # modular inverse does not exist
        else:
            return x % m

    # SRC: http://crypto.stackexchange.com/questions/25498/how-to-create-a-pem-file-for-storing-an-rsa-key/25499#25499
    def pempriv(n, e, d, p, q, dP, dQ, qInv):
        template = '-----BEGIN RSA PRIVATE KEY-----\n{}-----END RSA PRIVATE KEY-----\n'
        seq = pyasn1.type.univ.Sequence()
        for x in [0, n, e, d, p, q, dP, dQ, qInv]:
            seq.setComponentByPosition(len(seq), pyasn1.type.univ.Integer(x))
        der = pyasn1.codec.der.encoder.encode(seq)
        return template.format(base64.encodestring(der).decode('ascii'))

    n = p * q
    phi = (p -1)*(q-1)
    d = modinv(e, phi)
    dp = modinv(e,(p-1))
    dq = modinv(e,(q-1))
    qi = modinv(q,p)

    print "DEBUG : d=" + str(d) 

    key = pempriv(n, e, d, p, q, dp, dq, qi)

    f = open(output_file,"w")
    f.write(key)
    f.close()

def main(): 
    if len(sys.argv) == 5:
        print "[x] Starting ..."
        recover_ke(int(sys.argv[1]),int(sys.argv[2]),int(sys.argv[3]),sys.argv[4])
        print "[x] Done creating " + sys.argv[4]
    else :
        print "[!] Syntax : ./calc_d_from_pq.py p q e output_file"

if __name__ == "__main__":
    main()

Et on y va :

On va déjà essayer avec celle-là avant de toutes les créer pour voir si ça roule bien :

On ajoute la clef privée dans Wireshark pour les serveurs 64.203.166.189 et 70.52.248.249 qui partagent la même clef :

 

On retourne sur la capture : follow SSL stream sur le stream du serveur 64.203.166.189, coup de bol, la première est la bonne :), on voit dans le trafic déchiffré :

 

GH18{factoring_is_difficult_GCD_is_easy}

Merci à Securimag pour les challs 🙂

Conclusion

When trying hard doesn’t work, try harder.

./Kriss