Plus qu’un pur Write-Up, ce post est un « RSA CTF 101 ». En effet il nous servira de référence pour tous les prochains Write-Up de crypto contenant du RSA. Ce challenge est un excellent exemple pour un CTF, idéal pour une première fois… mais les habitués se passeront sûrement de la lecture du chapitre 2.0 – Rappels sur RSA. Merci à GreHack et SecurImag pour leurs chall de qualité !

 

1 – Reconnaissance

1.1 – Fichiers fournis par Grehack

Dans cette épreuve on a 3 fichiers :

– clef publique de Bill Gates (bill-gates.pub);

– clef publique de Steve Ballmer (steeve-ballmer.pub);

– secret chiffré (secret.enc).

 

1.2 – Indice et idée de résolution

Le texte descriptif du Readme nous indique que le secret est un mail de Ballmer, destiné à Gates. On a donc un système de cryptographie asymétrique, avec le secret chiffré par la clef publique de Gates. On va chercher à récupérer la clef privée de Gates afin de pouvoir déchiffrer le secret et obtenir le flag de l’épreuve… et marquer 300 points pour GreHack !

 

 

2 – Here we go, bitches

L’algo le plus courant de crypto asymétrique est RSA. La méthode la plus courante pour retrouver une clef privée RSA à partir de la clef publique est la factorisation de n … un rappel s’impose.

2.0 – Rappels sur RSA

Comme quasiment tout le temps en crypto, je vais utiliser l’excellent SAGE (très bon livre en pdf ici). SAGE est une surcouche à python permettant de faire du calcul mathématique. Toutes les commandes de ce post sont interprétables en Sage. Il existe bien sur d’autres solutions comme PARI/gp, ou bien des solutions commerciales comme Maple ou Magma.

Clef publique : (n,e)

1 – Pour générer une clef publique RSA, on choisit 2 nombres premiers p et q et on calcule n tel que n = p*q

sage: p = random_prime(2^512)

sage: q = random_prime(2^512)

sage: n = p*q

2 – e est choisi tel que (p-1)*(q-1) et e soient premiers entre eux. En pratique on choisit souvent e = 65537

sage: e = 65537

Clef privée : d

La clef privée d est l’inverse de e modulo (p-1)*(q-1)

sage: d = inverse_mod(e,(p-1)*(q-1))

Chiffrement

On élève le message à chiffrer puissance e modulo n (en utilisant donc la clef publique (n,e)).

sage: message = 42

sage: chiffre = pow(message,e,n)

Déchiffrement

On éleve le texte chiffré puissance d modulo n (clef privée d)

sage: message = pow(chiffre,d,n)

Factorisation

Si n est petit, on peut retrouver p et q à partir de n, et donc d, la clef privée (cf chiffrement).

sage: p,q=factor(n)

 

2.1 – Clef publique de Bill Gates

Contenu de bill-gates.pub :

-----BEGIN PUBLIC KEY-----
MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEB2CW7Y+cYYCBDFkNgqsDY
YjZsapoerdCtdqHNL06htNhOARu22sU7rHcjiIK0sS0aeYjJN+gasQRwXTWUtERX
TbvYQX/Gq20DeHpVwMwh4Filo8WXglIqD2bMDmfz8ck4hEaCtWQERlA21XYuk1/l
COQEHoN3hwIzaZuMLeY6qlYFl0/Fx9BVDd3hYb+2RSFUJFrEL3I3p8BMFY6l14AN
8E+yo9o/CvYdB+HaWkUhL5ZCyQYpKc5b2R0MZzoHo0rUhGYm6HpT3OoYPih+Aswc
X1WFVR9gTXIesiToYp5I2Q3vKOHfyVNmeUe5+EwdM3JG5MyClI5Oh2peJgqlPd9S
hBvZTITWy3vUq0l6etStsVaiQEEQJIycQ5RYOWY8Fg/0RzAwSNP1wj0fvvjpx+p/
uSgzc6d1mbduRbThJ7c+6wmOZIdZA9BzOeSWFH3DOKLxFRC6RanSgTyhqU1HfYAD
vHA8d5vWYVwdc+rvd1IFQ2ydTg+AT9Pn1v4E5eZk/UKcMHIWJopqbd2mwt1fLJYL
aSwMr3+rBGAtSumh7luYagtr3LXKsR+21A3eRv0LKk6eUtRMaHrkbWmiOvTiXd8r
ZMq/i7vENvVk/p9Sn5mMEUUp7evxL0t8P7SnEMGMe1M1EPaKKROqgMsa/abEJ6sM
NzOVAFVK62LymOaFO/V0Ec8CAwEAAQ==
-----END PUBLIC KEY-----

 

La clef publique semble avoir une forme classique, on peut essayer de la décoder avec un décodeur ASN.1 :

$> openssl asn1parse -in bill-gates.pub //  les brebis égarées ne possédant pas openssl peuvent utiliser ce service en ligne : ASN1Decoder

0:d=0  hl=4 l= 546 cons: SEQUENCE          
4:d=1  hl=2 l=  13 cons: SEQUENCE          
6:d=2  hl=2 l=   9 prim: OBJECT            :rsaEncryption
17:d=2  hl=2 l=   0 prim: NULL              
19:d=1  hl=4 l= 527 prim: BIT STRING

 

Le chiffrement RSA est donc confirmé et on peut extraire la clef publique à l’offset 19 dans le BIT STRING :

$> openssl asn1parse -in bill-gates.pub -i -strparse 19

 0:d=0  hl=4 l= 522 cons: SEQUENCE          
4:d=1  hl=4 l= 513 prim:  INTEGER :01D825BB63E718602043164360AAC0D862366C6A9A1EADD0AD76A1CD2F4EA1B4D84E011BB6[...]
 521:d=1  hl=2 l=   3 prim:  INTEGER           :010001

 

Aïe. On retrouve bien e = 0x010001 = 65537 mais n parait beaucoup trop grand pour être factorisé sans l’aide de la NSA.

 

2.2 PGCD

On remarque que l’épreuve nous fournit aussi la clef publique de Ballmer (steeve-ballmer.pub), a priori inutile, mais dont on peut se servir pour obtenir des informations. Bill Gates et Steve Ballmer étant « q et chemise » il ne serait pas étonnant qu’ils partagent jusqu’à une partie de leur clef privée. Pour le vérifier, calculer le PGCD entre les 2 clefs publiques est une bonne solution. On récupère la clef publique (n) de Ballmer avec openssl asn1pare, et on calcul le PGCD avec SAGE :

sage: nBill = 0x01D825BB63E718602043164360AA[…]     //copiée collée depuis la sortie d’openssl asn1parse

sage: nSteve = 0x02703BC6C9BE0489B3A[…]    //idem pour steeve-ballmer.pub

sage: q = gcd(nBill,nSteve)    //si gcd() renvoi un nombre, c’est que nBill et nSteve partagent un facteur

 

2.3 Résolution de l’épreuve Crypto 300 Microsoft PKI – Grehack

2.3.1 Fonctions nécessaires à la résolution (récupérées ici)

[pastacode provider=”manual” lang=”python”]

def text2Int(text):
    """Convert a text string into an integer"""
    return reduce(lambda x, y : (x << 8) + y, map(ord, text))

def int2Text(number, size):
    """Convert an integer into a text string"""
    text = "".join([chr((number >> j) & 0xff) for j in reversed(range(0, size << 3, 8))])
    return text.lstrip("\x00")

[/pastacode]

2.3.2 Résolution

sage: pBill = nBill/q    // n=p*q => p=n/q

sage: e = 0x010001    // e = 65537 

sage: d = inverse_mod(e,(pBill-1)*(q-1))    // on calcule la clef privée de Bill

sage: file = open("secret.enc",'r',)

sage: cipher = file.read()    // on met le fichier dans le buffer cipher

sage: cipher_i  = text2Int(cipher)    // on transforme le binaire en INT pour pouvoir faire des opérations dessus

sage: clair_i = pow(cipher_i,d,nBill)    // déchiffrement du message avec la clef privée d

sage: int2Text(int(clair_i),38)    // obtention du FLAG !

 

À bientôt pour le Crypto 500 😉