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 corespondante à 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’éxécute ainsi le script pour extraire les données de l’image …

Un coup d’oeil 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. »

-----BEGIN PUBLIC KEY-----
MIIBHzANBgkqhkiG9w0BAQEFAAOCAQwAMIIBBwKBgQCNOg9ge/IFmgy5i97hfd7q
qJivY6GCZXWJiFP8AHUKCj0WY0HXrs2InpjI41WC4FcFsGMNDf9bdLVHqBLZx5FR
LqGJfoBhtYF3j2i+V3p0nO3wIOuevejxnHvyhShPkaK8PqTKuWEp7PZAnBb2Ueli
lueIPXVxaZ7Zpp3gAlL0fQKBgHY33XPeHwYaNYiNToiGG/Qhi38Sd/D8IGa3dBgm
MQy8zVwA4BF9rCsFXm8BBmloXTM7TR8XLE+vylhhANOU+S3yLxhuALq/Qt1g6ePq
rSerPLlEuSQL9H+XuPoFIFNMTGrfe3ZnYgf/0OiTCB0nrkKAes63nFJje7pRP2Lv
MFYz
-----END PUBLIC KEY-----

-----BEGIN ENCRYPTED MESSAGE-----
X9HcTR1eaTjHGIqeEXQbCgic++FV+16XnP+uOE20XSuuSCJAkzbnmKJT5OgvEpF8KUbqeUSi2M8o
1TK6msKZv9Irilm0wf+IG0biHyPCP0ihgG/zxwccPGCUg3b7a31xtLmkb96JDi4xaGBN63dqzY6i
ASaUPfsjRrlExs/9MDY=
-----END ENCRYPTED MESSAGE-----

Semble-t-il ! j’obtiens :

  • Une clé publique, ce qui suggère un chiffrement asymétique, 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 desormais, 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 :

  1. Choisir deux nombres premiers distincts (p & q) ;
  2. Calculer n = pq ;
    1. 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é.
  3. Calculer φ(n) = lcm (p – 1, q – 1) ;
  4. Choisir un entier naturel 1 < e < φ(n) ;
    1. C’est l’exposant publique de chiffrement.
  5. 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« . Je n’ai pas de sources suffisament 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 « 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, 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 …

Ce contenu a été publié dans Write-Ups. Vous pouvez le mettre en favoris avec ce permalien.