Pirates Corporation & Co.

> Hop là ho ! une bouteille de rhum...

Misc. N°89 (NES Challenge-1) || Breaking RSA Cryptosystem

Il y a quelques mois est paru dans le magazine Misc. numéro 89 un challenge de sécurité. Une photo de l’annonce ci-dessous.

Le challenge commence par la lecture d’un QR Code. J’ai modifié l’image précédente pour ne garder que la partie correspondante à l’épreuve.

Pour lire les données du QR Code plusieurs solutions sont possibles. J’ai personnellement choisi de bricoler un bout de script (toujours pratique d’avoir cela sous la main).

#!/usr/bin/env python

def read_qr_message(img_filename) :
  from qrtools import QR

  qr_img = QR()
  qr_img.decode(img_filename)
  return(qr_img.data)

def main() :
  import sys
  from argparse import ArgumentParser

  parser  = ArgumentParser(prog=sys.argv[0])
  parser.add_argument('-f', '--filename', required=True, type=unicode, help='Specify image filename.')
  args    = parser.parse_args()

  message = read_qr_message(args.filename)
  print("-----BEGIN MESSAGE -----\n%s\n-----END MESSAGE -----" % (message))

if(__name__ == '__main__') :
  main()

j’exécute ainsi le script pour extraire les données de l’image…

Un coup d’œil suffit pour reconnaitre un encodage base64. Alors, voyons voir ce qui à été encodé la dedans.

Généralement, c’est à ce moment là qu’on se dit :

Ha, bin … merde, c’est un challenge de cryptographie.

Semble-t-il ! j’obtiens :

une clé publique, ce qui suggère un chiffrement asymétrique, sûrement RSA (Rivest Shamir Adleman) mais c’est juste une supposition.
un message à décrypter.

N’étant pas une bibliothèque ambulante, encore moins un expert en cryptographie je recherche des informations sur Internet. Plus précisément, je dois m’assurer que l’algorithme utilisé est bien celui auquel je pense.

Je commence par essayer de comprendre à quel type de certificat j’ai à faire. Je suis d’ailleurs tombé sur un article intéressant ASN.1 key structures in DER and PEM.

Alors, si je résume … J’ai un certificat encodé PEM (Privacy Enhanced Mail), c’est un format qui permet de partager facilement celui-ci avec d’autres personnes (caractères imprimables en base64, entêtes interprétables et … blah, blah, blah).

La charge base64 peut contenir beaucoup d’informations. Ici, il s’agit d’une structure de données ASN.1 (Abstract Syntax Notation One), codée dans un format appelé DER (Distinguished Encoding Rules).

Pour obtenir plus d’informations, sur la clé publique j’utilise la commande openssl suivante.

La colonne qui contient cons et prim donne des informations sur la structure hiérarchique des données.

cons désigne un champ construit, c’est-à-dire un champ qui encapsule d’autres champs.
prim signifie primitif.

La colonne suivante nous indique quel type de données est dans ce champ (le commutateur -i de la commande permet de visualiser l’indentation des objets de cette colonne).

Ainsi, Il y a un objet SEQUENCE racine. Cette SEQUENCE contient une autre SEQUENCE et une BIT STRING.

Cette SEQUENCE interne a un objet OBJECT et un terminateur NULL. Le champ OBJECT est en fait un Object Identifier – il contient une constante qui nous indique quel type d’objet nous décodons. Comme nous avons pu le suspecter, cela nous indique que nous décodons une clé RSA.

L’information que je cherche désormais, puisque je dois casser du RSA c’est, un modulus et un exposant publique. Cette information je vais la trouver dans la BIT STRING.

Qu’avons-nous ici ? Une SEQUENCE contenant deux INTEGER. Il s’avère que le premier INTEGER est notre modulus et que le second est l’exposant publique.

Ces deux nombres forment la clé publique RSA.

E = 7637DD73DE1F061A35888D4E88861BF4218B7F1277F0FC2066B7741826310CBCCD5C00E0117DAC2B055E6F010669685D333B4D1F172C4FAFCA586100D394F92DF22F186E00BABF42DD60E9E3EAAD27AB3CB944B9240BF47F97B8FA0520534C4C6ADF7B76676207FFD0E893081D27AE42807ACEB79C52637BBA513F62EF305633
N = 8D3A0F607BF2059A0CB98BDEE17DDEEAA898AF63A1826575898853FC00750A0A3D166341D7AECD889E98C8E35582E05705B0630D0DFF5B74B547A812D9C791512EA1897E8061B581778F68BE577A749CEDF020EB9EBDE8F19C7BF285284F91A2BC3EA4CAB96129ECF6409C16F651E96296E7883D7571699ED9A69DE00252F47D

Je ne suis pas mathématicien mais je sais rester factuel et … suivre les recettes de cuisine.

Cependant, je dois avouer que l’exposant publique m’a un peu piqué les yeux (à cause de sa taille). Et puis après quelques recherches il s’avère que ce n’est juste … pas conventionnel.

En effet, d’après ce que j’ai pu lire, il n’y a aucune faiblesse connue pour un exposant publique court ou long pour RSA, tant que l’exposant publique est « correct ». Généralement les exposants publiques utilisés sont { 3, 5, 17, 257 or 65537 }.

Ce que j’en ai retenu, l’utilisation d’un exposant publique différent de 65537 réduirait la compatibilité avec le matériel ou les logiciels existants et enfreindrait la conformité à certaines normes ou prescriptions des autorités de sécurité.

Tout exposant publique supérieur rendrait l’opération RSA utilisée pour le cryptage ou la vérification de signature, plus lente.

Il est cependant tout à fait possible d’utiliser 3 comme exposant publique sans qu’il y ai pour autant un impact sur la sécurité à condition d’avoir un padding approprié. Mais pour de nombreux schémas de bourrage moins que parfaits qui ont été (ou sont encore) utilisés, choisir une valeur élevée est généralement plus sûre.

A savoir, pour générer une paire de clé RSA. Basiquement j’ai besoin de :

Choisir deux nombres premiers distincts (p & q) ;
Calculer n = pq ;
- n est utilisé comme module pour les clés publiques et privées. Sa longueur, généralement exprimée en bits. C’est la longueur de la clé.
Calculer φ(n) = lcm (p – 1, q – 1) ;
Choisir un entier naturel 1 < e < φ(n) ;
- C’est l’exposant publique de chiffrement.
Calculer d, l’inverse modulaire multiplicatif de e(mod φ(n)) ;

Désolé les puristes … pour le script foireux mais fonctionnel qui illustre la génération d’une clé RSA.

#!/usr/bin/env python

def gcd(a, b) :
  while(b != 0) :
    a, b = b, a % b
  return(a)

def eea(a,b) :
  if(b == 0) : return(1, 0)
  (q, r) = (a // b, a % b)
  (s, t) = eea(b, r)
  return(t, s - (q * t))

def multiplicative_inverse(e, phi):
  inv = eea(e, phi)[0]
  if(inv < 1) : inv += phi
  return(inv)

def main() :
  from random import randrange

  p   = 37
  q   = 23
  n   = p * q
  phi = (p-1) * (q-1)

  e   = randrange(1, phi)
  g   = gcd(e, phi)
  while(g != 1) :
    e = randrange(1, phi)
    g = gcd(e, phi)
  
  d   = multiplicative_inverse(e, phi)
  
  print("-= Simple RSA Cryptosystem =-\n")
  print("e = %d" % (e))
  print("n = %d" % (n))
  print("d = %d" % (d))
  
  print("\n----- RSA Key Pair -----")
  print("Public  key: %d:%d" % (e, n))
  print("Private key: %d:%d" % (d, n))
  print("------------------------\n")

if(__name__ == '__main__') :
  main()

Dans l’exemple ci-dessus une paire de clés (publique / privée) est générée par le script.

Maintenant je note la clé publique 101:851 et voyons comment en retrouver la clé privée à partir de ces informations.

J’utilise RSATool2 dans cet exemple, mais j’aurais pu utiliser le logiciel Cryptool ou RsaCtfTool. Je n’ai pas de sources suffisamment sûre pour donner le lien de RSATool2 mais il peut être obtenu en cherchant un peu. A vos risques et périls.

Je travaille avec des valeurs en base10, je renseigne le modulus et je clique sur Factor N.

Comme résultat, j’obtiens les valeurs P et Q. Je peux ainsi calculer la clé privée.

Toutes les valeurs sont en décimales, sauf, l’exposant publique qui doit être renseigner en base16 (hexadécimal). Ainsi, la valeur 0x65h est l’équivalent de 101 en décimal.

Et voila… la clé privée 149:851.

Cependant, c’est une clé de 1024 bits qu’il faut casser pour ce challenge et RSATool2 plante lamentablement lors de l’étape de factorisation de N. Je dois pouvoir m’en sortir avec Cryptool mais je pense que tout ça va me bouffer beaucoup de ressources en calcul.

Il existe un service online pour factoriser un nombre de grande taille, FactorDB. Le résultat de la factorisation est stocké dans une base de données. Puisque ce challenge date de plusieurs mois il y a de grandes chances que la factorisation de notre nombre soit déjà réalisé.

Dans un premier temps je vais vérifier si FactorDB a la solution à mon problème. Juste pour démontrer que l’outil utilisé plus bas ne s’appuie pas sur de la sorcellerie (mais juste une histoire de … PQ).

Je converti le modulus de base16 (hexadécimal) en base10 (décimal) avant de l’envoyer.

J’observe le résultat ici.

P = F6189370867444DA192309146B88ECDA93293D794AFEBC2D4537E4D0496C03EDFD8AD13DDEAEF3D04BED8F9583DC638342A68E8443826746E58CD3ADF6A19C71
Q = 92E90F85DAE93DA2C25EAD4557E1DD7AF9485C321A20D67081C3399357D160C4612A021043059BD6EF4116B56EAC9326EB534BAD6A33E6A79A046F3A99428ECD

Je connais désormais P, Q, N et E. Je peux alors calculer D.

Manuellement, comme dans l’exemple précédent avec RSATool2. Sauf que, ci-dessous, je travaille en base16.

D = 19312E2686B1665B4BE8BFA1A9DAF7AEAFA3F30BE9E77C515D7C9A188D26FD3B

Et ainsi, avec de la documentation je peux essayer de m’amuser à reconstruire la clé privée dans un format interprétable par openssl. Mais là … je préfère passer mon tour.

Pour le reste, j’utilise RsaCtfTool pour générer automatiquement la clé privée.

Par contre, cette clé privée est au format PKCS#1, il faut la convertir au format PKCS#8.

Je peux vérifier l’exactitude des informations avec la commande suivante.

Et enfin, décryptage du message.

Après avoir galéré avec RSA ce n’est pas un Rot-13 qui va m’arrêter…