Y0L0 CTF

Découverte

ESNA

Hacker Guide

Mon terminal

Mon proxy

Mon Python

Ma Kali

Mon Compte

Mon Score

Top 20

Feedback

VMs

Le chiffrement RSA est un chiffrement asymétique à clef Publique/Clef Privée.
Il est utilisé pour chiffrer des petites quantités de données, les signer, ou authentifier un utilisateur.

Chiffrement

Tout le monde peut chiffrer un message avec la clef Publique.
Seul le destinataire peut le déchiffrer grâce à sa clef Privée.
Le RSA est un chiffrement relativement lent, il nécéssite des calculs sur des grand nombres.
Il peut être utilisé pour la distribution des clefs de chiffrement symétriques.

Signature

Un message est signé avec la clef Privée.
Tout le monde peut vérifier la signature avec la clef Publique.

Utilisation et CTF

Au quotidien le RSA est utilisé pour se loguer en ssh.
Les clefs sont enregistrées dans des fichiers au format PEM (~/.ssh/id_rsa, ~/.ssh/id_rsa.pub,..) qui contiennent les clefs.
En CTf, on utilise souvent les valeurs p,q,n,e,d,t ou phi. Qui permettent de faire les calculs et exploiter les failles du RSA.
``` p et q sont deux grand nombres premiers. n vaut pxq. Toute la sécurité du RSA est basée sur la difficulté à retrouver p et q à partir de n. e est en nombre arbitraire plus petit que (p-1)x(n-1) qui va servir à chiffrer. d est une valeur calculée à partir de e, p et q qui permet de déchiffer ce qui a été encodé par e. ```

Clef Publique : n et e

La clef Publique est constituée de deux chiffres: n et e.
n est le produit de deux nombres premiers p et q.
e est un chiffre arbitraire qui sert à chiffrer le texte en clair. Souvent 65537 ou 3.

Clef Privée : n et d

La clef Privée est constituée de deux chiffres: n et d.
n est le même que pour la clef Publique.
d a la propriété de déchiffrer les chiffrements réalisés avec le chiffre e.
Pour calculer d, il faut connaitre e et les deux nombres premier p et q.

Padding

Le chiffrement RSA possède des faiblesses, qui sont atténuées par l'ajout d'un algorithme de Padding comme PKCS ou OAEP

Limitations

Tous les calculs sont fait modulo n. Il n'est pas possible de chiffrer un message supérieur au modulo.
A la grande louche, une clef construite à partir de p et q de 1024 bits, permet de chiffrer un message d'environ 240 caractères maximum.

CVE-2017-15361: ROCA vulnerability

En 2017, une faille exploitable dans la génération des clef par la librairie libRSA a imposé la regénération de millions de clefs.
https://en.wikipedia.org/wiki/ROCA_vulnerability

Casser RSA

Petit p ou q
La robustesse du RSA est entièrement basée sur la complexité à retrouver p et q à partir de n.
n est publique, s'il est facilement factorisable, on peut retrouver p et q, donc le totient, donc d, et le message est déchiffrable.
Il est relativement rapide d'essayer de diviser n par la liste des 1000 premiers nombres premiers. Il faut donc éviter un n calculé à partir de petits nombre premiers

Petit message et petit e
p et q sont de grands nombres premiers. n est donc grand.
Mais e est petit. Par exemple e=3
Et aucun padding n'est utilisé.

Chiffrer un message m revient à calculer m^e mod n.
m étant petit et e étant petit, il est possible que m^e < n. Le message chiffré n'est donc pas affect& par le modulo.
Il suffit de calculer la racine eième de c pour retrouver e. Ici m = racine cubique de c.

Hastad Broadcast: Même message chiffré par des clefs différentes de même petit e
Cette attaque est appelée : Hastad’s Broadcast Attack

Fermat: p et q trop proches
Généralement p et q sont des clefs de même longueur en bit.
Mais s'ils sont trop proche, si (p - q) < (n^1/4), il est possible de factoriser n rapidement.
Cette attaque est appelée : Fermat's attack

Wiener: Petite clef Privé, e trés grand comparé à n
Si e est proche de n, d sera petit.
Cette attaque est appelée : Wiener's attack

Common modulus
La clef Publique utilisée pour chiffer a le même modulus n que notre clef Privée. Nous savons factoriser n et donc déchifrer les messages.

Common modulus
Un message a été chiffré deux fois avec deux clefs Publiques ayant le même n et des e différents.

Plusieurs chiffrements, même n
Un message est chifré 5 fois de suite avec 5 clef différentes qui ont le même n et des e différents.
Ca revient à chiffrer une fois avec e=e1xe2xe3xe4xe5

Signature des produits de facteurs
Si un message m est décomposable en produit de facteurs premiers. La signature de m est le produit des signatures de ses facteurs premiers.
Si m=a*b*c alors sig(m)=sig(a)*sig(b)*sig(c)

Lectures

Plus de détail: https://en.wikipedia.org/wiki/RSA_(cryptosystem)
RSA en CTF: https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-1/
Une synthèse des attaques contre RSA: RSA-survey.pdf

1 / 14 - Generer un nombre premier aléatoire

Pour générer un nombre premier de 1024 bits.
Shell:

$ openssl prime -generate -bits 1024

Python:

import subprocess 
p = int(subprocess.check_output('openssl prime -generate -bits 1024', shell=True))

2 / 14 - Calculer les n nombres premiers

Code python

#!/usr/bin/python3 
def primes(n): # simple Sieve of Eratosthenes 
 odds = range(3, n+1, 2) 
 sieve = set(sum([list(range(q*q, n+1, q+q)) for q in odds],[])) 
 return [2] + [p for p in odds if p not in sieve] 
print(primes(100))

3 / 14 - Vérifier si un nombre est premier

Pour un trés petit nombre en Python:

isPrime=lambda x: all(x % i != 0 for i in range(int(x**0.5)+1)[2:]) 
print(isPrime(5)) 
print(isPrime(15))

Pour un petit nombre: en shell:

$ factor 141080753378390635555451344762514009592 
141080753378390635555451344762514009592: 2 2 2 3 53 3019 277531129 132374960470064866635611

Pour un grand nombre, factordb.

http://factordb.com

4 / 14 - Décomposer en produit de nombre premiers

#!/usr/bin/python3 
def prime_factors(x): 
  factorlist=[] 
  loop=2 
  while loop<=x: 
      if x%loop==0: 
          x//=loop 
          factorlist.append(loop) 
      else: 
          loop+=1 
  return factorlist 
print(prime_factors(3*11*17))

5 / 14 - RSA Calculs des clefs

Pour construire une paire clef Privée/Clef Publique:
Choisir 2 grands nombres premiers: p et q

p = 17 
q = 11

Calculer leur multiple: n = pxq

n = p*q

Calculer le totient de n: totient(n) = (p-1)x(q-1)

totient = (p-1)*(q-1)

Choisir un nombre e plus grand que 1 et plus petit que le totient.
e et le totient ne doivent pas avoir de diviseurs communs.
On utilise souvent 3 pour un calcul rapide, ou 65537 si la taille des clefs le permet.
Ce nombre e va servir à chiffrer notre message.

e = 3

Chiffrer

Pour chiffer un message, on le convertit en nombre m, et on l'élève à la puissance e, modulo n.
Il n'est possible de chiffrer que les valeurs inférieures au modulo m.
Un long message devra être découpé en morçeaux.

import binascii 
p = 3641012789 
q = 4098717313 
n = p*q # n=14923482155128715957 
e = 17 
m_txt = b'FLAG' 
m_hex = binascii.hexlify(m_txt) # 464c4147 F=46 L=4c A=41 ... 
m = int (m_hex, 16) # m=1179402567 
c = pow (m,e,n) # c=8354331172360966993

Dechiffrer
On calcule d, qui est l'inverse de e, modulo le totient

from Crypto.Util.number import inverse 
totient = ( q - 1 ) * ( p - 1 ) 
d = inverse( e, totient ) # d=877851891022881521

Ce nombre d va servir à déchiffrer le message.
Pour déchiffer un message chiffré c, on l'élève à la puissance d modulo n

m = pow(c, d, n)   # m=1179402567 
print('m='+str(m)) 
m_hex = hex(m)     # m_hex: 0x464c4147L 
m_hex = m_hex[2:]  # on retire 0x 
m_hex = m_hex.replace('L','')  # on retire L 
m_txt = repr(binascii.unhexlify(m_hex)) # m_txt ='FLAG' 
print ("Message en clair: "+m_txt)

La clef publique est la paire : e et n
La clef privée est la paire : d et n

6 / 14 - Valeur de p, q et e valides

Pour générer des valeurs valides de p, q et e:
Il doit exister un inverse à q mod p, et un inverse à e modulo le totient.

7 / 14 - Ecrire des clefs au format PEM

Les fichiers de clefs RSA privées et publiques que l'on utilise au quotidien pour se connecter en ssh contiennent n et e ou d, plus quelques valeurs pré-calculées, encodées en base64.
Exemple de clef de 64 bits:

8 / 14 - Informations contenues dans les clefs au format PEM

Les clefs au format PEM contiennent les valeurs de n, e, d,... au format DER encodées ASN1 puis en base64.

openssl pkey -in newkey.pem -text 
-----BEGIN PRIVATE KEY----- 
MDICAQAwDQYJKoZIhvcNAQEBBQAEHjAcAgEAAgIAuwIBBwIBFwIBEQIBCwIBBwIB 
AwIBDg== 
-----END PRIVATE KEY----- 
RSA Private-Key: (8 bit, 2 primes) 
modulus: 187 (0xbb) 
publicExponent: 7 (0x7) 
privateExponent: 23 (0x17) 
prime1: 17 (0x11) 
prime2: 11 (0xb) 
exponent1: 7 (0x7) 
exponent2: 3 (0x3) 
coefficient: 14 (0xe)

$ openssl pkey -in newkey.pub -pubin -text 
-----BEGIN PUBLIC KEY----- 
MBswDQYJKoZIhvcNAQEBBQADCgAwBwICALsCAQc= 
-----END PUBLIC KEY----- 
RSA Public-Key: (8 bit) 
Modulus: 187 (0xbb) 
Exponent: 7 (0x7)

9 / 14 - Chiffrer avec une clef Privée au format PEM

On utilise openssl avec la commande rsautl:
Le fichier chiffré est au format binaire.

$ echo 'flag' > cleartext.txt 
$ openssl rsautl -encrypt -in cleartext.txt -out encrypted_with_pub_key -inkey newkey.pub -pubin -oaep 
$ cat encrypted_with_pub_key 
�./|�k,��d���kf

Un dump hexa ou un encodage en base64 permet de le copier/coller.

$ xxd -p encrypted_with_pub_key 
036f24d6f26b725fb068e9891589a271ff5679778926c9c043631c909c46 
1e0933 

$ xxd -p file | tr -d '\n' 
036f24d6f26b725fb068e9891589a271ff5679778926c9c043631c909c461e0933 

$ cat encrypted_with_pub_key | base64 
lS4vfBfHayyKnWTx9vhrZg==

-encrypt 
-in cleartext.txt 
-out encrypted_with_pub_key 
-inkey newkey.pub 
-pubin 
-oaep

10 / 14 - Dechiffrer avec une clefs au format PEM

Le message chiffré en dump hexa ou en base64, un padding oaep a été utilisé. Nous avons la clef privée au format PEM.

$ printf 'lS4vfBfHayyKnWTx9vhrZg=='  | base64 -d > encrypted_with_pub_key 
$ printf '036f24d31c909c461e0933' | xxd -r -ps > encrypted_with_pub_key 

$ openssl rsautl -decrypt -in encrypted_with_pub_key -inkey newkey.pem -oaep 
flag

11 / 14 - RSA Attack - Small primes

Intitulé: connaissant la clef publique et le message chiffré, retrouver le message clair.
Clef publique

-----BEGIN PUBLIC KEY----- 
MDowDQYJKoZIhvcNAQEBBQADKQAwJgIhCK/0nDYAb1hnFbxkjI3SnJ7+sF8CRpge 
rF2WVN5aQw6ZAgED 
-----END PUBLIC KEY-----

Message chiffré avec padding oaep

A28k1vJrcl+waOmJFYmicf9WeXeJJsnAQ2MckJxGHgkz

Extraire le modulus et e de la clef privée.

$ openssl pkey -in newkey.pub -pubin -text 
-----BEGIN PUBLIC KEY----- 
MDowDQYJKoZIhvcNAQEBBQADKQAwJgIhCK/0nDYAb1hnFbxkjI3SnJ7+sF8CRpge 
rF2WVN5aQw6ZAgED 
-----END PUBLIC KEY----- 
RSA Public-Key: (260 bit) 
Modulus: 
08:af:f4:9c:36:00:6f:58:67:15:bc:64:8c:8d:d2: 
9c:9e:fe:b0:5f:02:46:98:1e:ac:5d:96:54:de:5a: 
43:0e:99 
Exponent: 3 (0x3)

e vaut 3.
Le modulus, n, est un dup hexa. Pour retrouver sa valeur:

python -c "n='08:af:f4:9c:36:00:6f:58:67:15:bc:64:8c:8d:d2:9c:9e:fe:b0:5f:02:46:98:1e:ac:5d:96:54:de:5a:43:0e:99'; 
n = n.replace(':',''); 
n = n.replace(' ',''); 
n = n.strip(); 
print (int(n, 16))" 

1005923651212720131293491321374740703377422945370215435104917901916930260012697

Une requête sur factordb nous informe que 11 est un diviseur de n.
http://factordb.com/index.php?query=1005923651212720131293491321374740703377422945370215435104917901916930260012697
n = 11 x 91447604655701830117590120124976427579765722306383221373174354719720932728427
Connaissant p et q, nous pouvons regénérer le fichier de clef privée et décoder le message.

12 / 14 - RSA Attack - Common modulus

Un message a été chiffré par deux clefs Publiques ayant le même n.
Nous disposons des clef publiques (n,e1,e2) et des deux messages chiffrés (c1,c2).
Si gcd(e₁, e₂) = 1 et gcd(ct₂, n)=1, nous pouvons déchiffrer le message.

def rsa_common_modulus_attack(c1, c2, e1, e2, N): 
 s1 = modinv(e1,e2) 
 s2 = (gcd(e1,e2) - e1 * s1) / e2 
 temp = modinv(c2, N) 
 m1 = pow(c1,s1,N) 
 m2 = pow(temp,-s2,N) 
 return (m1 * m2) % N

Ref: https://medium.com/bugbountywriteup/rsa-attacks-common-modulus-7bdb34f331a5

13 / 14 - RSACtfTool

RsaCtfTool implémente plusieurs techniques d'attaque du RSA.

https://github.com/Ganapati/RsaCtfTool

14 / 14 - HTTPS Certificats

RSA est utilisé pour la sécurisation du protocle HTTPS

wget https://github.com/ANSSI-FR/ctf/raw/master/crypto-cqfd/capture.pcap 
sudo apt install ssldump 
ssldump -r capture.pcap

Hacker Lab