lundi 14 avril 2014

CTF Writeup: PlaidCTF 2014: RSA

Pour ce problème de forensics/crypto à 450 points, nous recevons en donnée les fichiers suivants:

Les données

"encrypted", en apparence aléatoire et inintelligible, d'exactement 128 bytes, soit 1024 bits:

00000000  9a 4b 89 34 b0 49 c8 0f  77 20 94 bf 1c 55 fe 9f  |.K.4.I..w ...U..|
00000010  d5 4f 55 2a 93 db 86 e3  2a 2b 32 d6 49 0f d2 6d  |.OU*....*+2.I..m|
00000020  8f 57 6d 8a 33 ec d4 bf  fd 20 25 e5 7f fb f1 5a  |.Wm.3.... %....Z|
00000030  4d ea 67 7a 29 3f 53 eb  b2 fd ba e1 c0 a5 5d f1  |M.gz)?S.......].|
00000040  02 4d 02 f9 a4 26 71 e5  5e e5 e4 49 e5 f7 8a 9e  |.M...&q.^..I....|
00000050  4f 37 db 2e 45 04 b0 fd  9d c9 13 9c 9c 76 4a e1  |O7..E........vJ.|
00000060  e3 6e fe a8 d9 81 3f 20  23 cb 0a 67 eb 78 c1 4d  |.n....? #..g.x.M|
00000070  95 75 7e 45 9b a4 66 cd  e6 36 14 e1 a8 2c 86 db  |.u~E..f..6...,..|
"public.pub", une clef publique au format openssl, de 1024 bits également:
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDb+r2xSV0ydudia4R5bp/CD6E8
F0TxDIw/PjwsYEDC5/MT36PR/hDRrld8/qt0UqpTEC7ve+AJnAIlYOV6XDDVCUBk
LRsJfdIQmuAvLc/4GYzVo5X8rEJmEHhIud1jw4fSU45QQVNDBCAz6gnAhBVeZSsP
BiNA1dRxekAqnYBqawIDAQAB
-----END PUBLIC KEY-----
Les détails de la clef:
max@truite ~/rsa $ openssl rsa -pubin -noout -text < public.pub 
Public-Key: (1024 bit)
Modulus:
    00:db:fa:bd:b1:49:5d:32:76:e7:62:6b:84:79:6e:
    9f:c2:0f:a1:3c:17:44:f1:0c:8c:3f:3e:3c:2c:60:
    40:c2:e7:f3:13:df:a3:d1:fe:10:d1:ae:57:7c:fe:
    ab:74:52:aa:53:10:2e:ef:7b:e0:09:9c:02:25:60:
    e5:7a:5c:30:d5:09:40:64:2d:1b:09:7d:d2:10:9a:
    e0:2f:2d:cf:f8:19:8c:d5:a3:95:fc:ac:42:66:10:
    78:48:b9:dd:63:c3:87:d2:53:8e:50:41:53:43:04:
    20:33:ea:09:c0:84:15:5e:65:2b:0f:06:23:40:d5:
    d4:71:7a:40:2a:9d:80:6a:6b
Exponent: 65537 (0x10001)
Et enfin, ce mystérieux fichier "corrupted.pem":
 r    e   y: (         
 o  lu :
      :d :f : d:b1:4 :5d: 2: 6:  : 2:  :8 :  :  :
      :c :0 : 1: c: 7:  :  :  :  : f:  :  :2c:6 :
      : 2:  : 3:  : f:  :d :  :  :  :a : 7:  : e:
     b:7 :  :  :5 : 0:2 :  :  : 0:  :9 :  :2 :  :
    e :7 :  :30:d :0 :  :  :  :  :  :  :  :  :  :
    e :  :  :  :  :  :  :  : 3:95:f : c:  :6 :  :
     8:  :b9:dd:  :  :  :  :5 :8e: 0:41: 3:  :  :
     0:3 :e :09: 0:  :1 :5 :6 :  :0 :0 : 3:  : 5:
     4:  :  :  :  :  :  :  : b
     c xpon n :   53  (0  0  1 
   v te xp   n :
     f:  :  : a: a:9 :e :  : 1: 2:  :  :e :  :1 :
    3 : 1:  :  :  : a:  :2 :  :  :  :  :  :  :  :
    9 : a:  :  :  :  :  : 5:c1: 0:b : 3: 2:0 :b0:
      :c : f:  :f :  :d2:  :  : d:  :1 :  :3 :  :
      :  :  :0 : 3:  :  : 5:c :  :3 :6 :  :a4:  :
    4 :  :  :8f:  :  :  :  : a:  : c:5f: 7: 6:  :
     1:  : b:  : 5:  :84:0 :b : f: 3:  :  : 4: 6:
      :  : 5:1 :  :d :  : f:  : c:  :  : 5:  :  :
      :e :f4:b :4 :8e:  :  
 r    :
    00:  :6 : 1:1 :  :b :0 : 2:c : b:2 :  : a:1 :
    c :  : 0:  :28:0 :  :cd:  : 8:  :  :20: c:  :
      : 5:  :9 : c:3 :  :  : a:b :c :3 :  :  :  :
     f:  :  : f: 1: 1:b :  : c:f : a:  :a :  :  :
     a:38:  :6 :  
  i   :
      :e :  :d :2 :6 : 7:  :33:  :46:  : 4:  :  :
      :5 :  : 4:6 :  : 6:  : e:d :  :  : 9: e:1 :
      :  :  :  :  :0 :  :  :  :c : 5:  :  :a :0 :
    6 :  :  :8 :e9:f : f:7 :5 : e:1 :  :  : 1:9 :
     4:d :e9: 6:  
 x  n   1:
     9:d : 5:  :c :67:  : 9:  :  :  : d:  :  : 3:
     f:6 : 0:c :  :6 :ad:  :2 :d :d :  :  :0 :7 :
      :5 : 6:  : 5:1 :f : d:  : 2:  :  : 2: 3:  :
    9 :  :  :  :  :67: 3:  :4 : 7:c0: 4:b :c :f :
      :3 :b : 1
 x on  t :
    1 : 9:47:8 :  :  :  : 3:  :  :  :6 :  :  :0 :
    e :e :8 :  :  :  :  : 1:c :74:  :  :d : 9:3 :
    5 : e:  : 2:  :7 : 2:c :  :  :  :  :5 :  : 8:
      :  :c :  : 1:  :a :  : 9: 5:  : 3:  : e:c :
      :  : 6:  
c e    i  t:
      :a :d :84:f :  : c:43:  :  :  : 6:  :  :  :
      : b:  :c :9 :  :  :  :  :  : 4:23:8b:  :6 :
    2 : 2:  :  : 7:5b:  :  :  :7 :  :  :  :  :  :
    f1:7 :1 :  :f : a:  : 5:  :  :  : 5:  : c: 1:
      :48: b: 6:  

Analyse

On reconnait le format texte d'openssl pour les clefs privées RSA. On peut comparer avec une clef privée générée pour l'occasion, pour connaitre les noms des différents champs:
max@truite ~/rsa $ openssl genrsa |openssl rsa -noout -text
Private-Key: (1024 bit)
modulus:
    00:ca:6d:bf:f1:cc:b4:8f:56:e7:c7:b3:29:7a:44:
...
Nous avons donc une clef privée dégradée, et selon toute vraisemblance, un fichier chiffré avec cette même clef
Heureusement, ce format de stockage est hautement redondant, pour des raisons de performance. En théorie, pour déchiffrer un message, seuls le module (n), déja présent dans la clef publique, et l'exposant de déchiffrement (d), sont nécessaires pour calculer un déchiffrement. Mais pour des raisons de performance, le format stocke aussi les deux nombres premiers ayant servi à la génération (p et q), les deux coefficients dp ≡ e-1 (mod p-1), et dq ≡ e-1 (mod q-1), et le coefficient c ≡ q-1 (mod p).
Ces valeurs supplémentaires servent à accélérer le calcul du déchiffrement, en appliquant le théorème des restes chinois. Cette optimisation existe uniquement pour le déchiffrement, pour deux raisons: d'abord, connaitre p et q permet le calcul de e à partir de d et vice-versa, ensuite parce que le choix d'un petit e rend déja le chiffrement suffisamment rapide (mais choisir un petit d est une très mauvaise idée puisqu'il devient possible de le retrouver par force brute)
Il faut noter que la connaissance de n'importe laquelle de ces valeurs permet de reconstruire les autres. Un algorithme pour reconstruire la clef est décrit dans un article de Nadia Heninger et Hovav Shacham, Reconstructing RSA Private Keys from Random Key Bits.

Une première attaque

Pour comprendre cet algorithme, réfléchissons à une première manière naive de reconstruire uniquement p et q à partir de leurs versions dégradées. On sait que n = p·q, nous avons donc n ≡ p·q (mod 2t). On peut donc essayer de reconstruire p et q bit par bit, en commençant par les lsb. Comme p et q sont premiers, ils ne sont pas divisibles par 2, donc leurs derniers bits respectifs sont 1. A chaque bit supplémentaire, nous devons considérer 4 possibilités (pour les 2 bits de p et q), mais 2 de ces possibilités sont éliminées par la contraite (n ≡ pq (mod 2t). Si un bit de p ou q est connu, on peut donc déduire le bit restant.
Malheureusement, si cette technique peut corriger quelques bits manquants, ici il y en a trop pour que l'attaque soit efficace; il nous faudra quand même tester par force brute un nombre considérable de combinaisons.

Une meilleure attaque

Nous allons exploiter les valeurs d, dpet dq pour aider la reconstruction. Je ne vais pas répéter ici les explications du papier, et sauter quelques optimisations mineures pour simplifier l'implémentation. Commençons par résumer les relations entre ces valeurs, en remplaçant les équivalences modulo par des coefficients explicites. Pour rappel, si a ≡ b (mod n), alors a = b + kn. Les équations, suivant la définition, sont:
  • e·d = 1 + k(p-1)(q-1) = 1 + k(n-p-q+1)
  • e·dp = 1 + kp(p-1)
  • e·dq = 1 + kq(q-1)
Ces équations restent valable après réduction modulo 2t, ce qui va nous permettre, la encore, de les reconstruire bit par bit. Mais il nous faut d'abord obtenir k, kp et kq.
Le code de l'attaque se trouve sur http://github.com/maugier/cctk dans PartialRSA.hs. Il utilise une lib maison, dans Partial.hs, pour la manipulation de chaînes de bits partiellement connues. Je ne reproduirai pas le code ici.
Pour reconstruire k, on va utiliser une approximation due à Boneh, Durfee et Frankel, qui nous indique d'une part que 1 < k < e, de l'autre que d' = ⌊(k·(n+1) + 1)/e⌋ est une bonne approximation de d, avec une marge d'erreur de (p+q), soit de l'ordre de la racine carrée de n, et donc la moitié des bits, si p et q sont a peu prs de la même taille.
On va donc simplement chercher la valeur de k par force brute. Le bon k sera celui pour lequel la moitié la plus significative des bits de d' correspond au d partiellement connu (il faut donc au moins log2(e) bits connus dans d pour avoir une solution unique à k.
breakK (n,e) d = [ k | k <- [1..(e-1)] 
                   , d >?< msb l . fromKnownInteger . approx $ k ] where
    approx k = (k * (n+1) + 1) `div` e
    l = (length (fromPartial d) `div` 2) + 2
Une fois k obtenu, nous pouvons calculer kp et kq. Je vous épargne le développement mathématique qui est dans le papier, nous allons simplement chercher les solutions de l'équation k'(k' - k(n-1) - 1) - k ≡ 0 (mod e). Les valeurs de kp et kq sont parmi les solutions pour k'. S'il n'y en a qu'une, kp = kq, s'il y en a deux il faut tester les deux permutations de la paire.
breakKPQ (n,e) k = [ k' | k' <- [1..(e-1)], (k'*(k' - c) - k) `mod` e == 0 ]
        where c = k*(n-1)+1

Maintenant que nous connaissons k, kp et kq, nous pouvons tenter de reconstruire les valeurs secretes, par une descente récursive dans l'arbre des solutions. Chaque étage i de cet arbre représente la connaissance des i bits les moins significatifs des 5 valeurs secrètes. Dans cet arbre, chaque noeud a potentiellement 25 enfants (1 bit supplémentaire inconnu pour chacun des 5 secrets), mais nous disposons de 4 équations, grâce auxquelles il ne reste que 2 enfants valide à chaque noeud. Attaquer les 5 valeurs simultanément est donc aussi cher (en complexité) qu'attaquer une seule des 5; mais en attaquant les 5 simultanément, nous pouvons éliminer les solutions intermédiaires incohérentes avec les fragments de valeurs connues. Avec suffisamment de bits connus, l'attaque se fait donc en temps linéaire sur la taille de la clef.
Comme solution de départ, toutes les valeurs secrètes sont impaires (p et q sont premiers; d, dp, dq sont tous inversibles modulo un nombre pair (respectivement (p-1)(q-1), (p-1) et (q-1)) et sont donc impairs.)
Nous pourrions faire tourner l'algorithme jusqu'a la récupération complète de dp ou dq, mais cela n'est pas nécessaire. Le plus simple est de récupérer p ou q, dont la taille est la moitié de n, et les autres valeurs suivront. (On pourrait aussi récupérer d, puisque la première phase du calcul du k nous révèle l'intégralité de la moitié supérieure des bits de d.) Notre fonction s'exécute dans la monade List, et backtracke automatiquement en cas de contradiction.

-- Une fonction qui étend une séquence partielle d'un bit, tout en fournissant sa valeur entière mod 2^i, et produit
-- les valeurs possible avec la valeur numérique correspondante
(>><) :: [Int] -> PartialBits -> [([Int],Integer)]
x >>< y = (extend (fromKnown x) >< y) >>= exhaustBit  

breakKey (n,e) s@[p,q,d,dp,dq] = do

    k <- breakK (n,e) d
    
    -- tester les deux permutations
    (kp, kq) <- case breakKPQ (n,e) k of
        [x]   -> [(x,x)]
        [x,y] -> [(x,y),(y,x)]

 
    -- tous les secrets sont impairs
    let slice0 = [[1],[1],[1],[1],[1]]

    -- extension d'un bit et pruning:
    let slice 0 = slice0
        slice i = do
           let m = 2^(i+1)
           -- on procède a l'extension de l'état précédent 
           -- légèrement sous-optimal mais plus concis
           -- (on pourrait étendre les variables séparément et déclarer
           -- les contraintes plus tôt.
           s' <- slice (i-1)  
           s'' <- zipWithM (>><) s' s

           -- les valeurs des chaines de bits
           let [pv,qv,dv,dpv,dqv] = map fromBits s''

           -- nos équations mod 2^i
           guard $ (pv * qv - n)                  `mod` m == 0
           guard $ (e * dv - (k*(n-pv-qv+1) + 1)) `mod` m == 0
           guard $ (e * dpv - (kp*(pv-1) + 1))    `mod` m == 0
           guard $ (e * dqv - (kq*(qv-1) + 1))    `mod` m == 0

           return s''

     -- on retourne q, le plus petit nombre premier
     [_,q,_,_,_] <- slice (length (fromPartial q))
     return q

On copie-colle ensuite les valeurs dégradées et on lance l'attaque:
n = fromHex "00:db:fa:bd:b1:49:5d:32:76...
e = 65537

d = fromPartialHex " f:  :  : a: a:9 :e :...
p = fromPartialHex "00:  :6 : 1:1 :  :b :...
q = fromPartialHex "  :e :  :d :2 :6 : 7:...
dp = fromPartialHex " 9:d : 5:  :c :67:  :...
dq = fromPartialHex "1 : 9:47:8 :  :  :  :...

main = print $ breakKey n e (p,q,d,dp,dq)
et on obtient la valeur de q: e945de2261e7b73317461ec48599715f2be4630866f99eda58a149ae102d1a91c4f909687f56ce65d7faab0f649d8e8ae9fc2f7e535e1d5aa76197b4d7e9a6cf.

Les finitions

Reste a transformer ce nombre en quelque chose d'utilisable. Puisque la clef était originellement au format OpenSSL, essayons de la recréer. Pour ça, j'utilise d'abord mes fonctions utilitaires en haskell pour recalculer p et d, puis j'utilise Crypto.PublicKey.RSA de pycryptopp:
max@truite ~/rsa $ python2
>>> from Crypto.PublicKey import RSA
>>> n = 15447482797676392...
>>> e = long(65537)
>>> p =  1264374063739511065289...
>>> q = 122174942057803188748651...
>>> d =  11066410079053154785483305869421...
>>> k = RSA.construct((n,e,d,p,q))
>>> print k.exportKey()
-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQDb+r2xSV0ydudia4R5bp/CD6E8F0TxDIw/PjwsYEDC5/MT36PR
/hDRrld8/qt0UqpTEC7ve+AJnAIlYOV6XDDVCUBkLRsJfdIQmuAvLc/4GYzVo5X8
rEJmEHhIud1jw4fSU45QQVNDBCAz6gnAhBVeZSsPBiNA1dRxekAqnYBqawIDAQAB
AoGAD8JTypqd4ZqhEuzu7aAeM9HY1Cw6lSY3+ePkfa1bllr1kAvqeYXBALSDsgGw
mMG/T/oN0rxGHYoeoTzi07Q9DzP71RXFBT5p56SYTCa7j6THXXyqMLxfd+YFgVsr
ehXMhAi97yMeMoTmoQ91GN/cqW9n/MflJdm0aOv0skSOA0kCQQDxaVEeZr4GIsKr
LsFaF8DHoMcoCK7NuijH9SDsrSNlspzMNTHbGrzAPmk5aF/iFK/RQbqfbP06c6X6
6Fo482mlAkEA6UXeImHntzMXRh7EhZlxXyvkYwhm+Z7aWKFJrhAtGpHE+Qlof1bO
Zdf6qw9knY6K6fwvflNeHVqnYZe01+mmzwJAOdUVDcdnNmkVYZTt1Ptjv28QxtJt
rfMu2dgrbwd7N122mmUT8H1TQmqxIoOSlMKH7AVnA9JER8B0vsry8jm90QJAEllH
jsbKtjNTmlVjOesG6uiF73BCwVHIdP5C0Gk/Uv6yUrB1wsZuN76UXg446NfEf4Ex
rysZlQ+DaP7I387mKwJBAKXQhPcX/EP6kOMGR8eGc8sVy5tg55GQVpQjixZlIlLs
QrdbuK0Ad4szHWCm8XkRafba9EW966JFipzRfkg7Vjw=
-----END RSA PRIVATE KEY-----
On colle ça dans un fichier, rebuilt.pem, et on vérifie que la clef est bien celle que l'on attendait:
max@truite ~/rsa $ openssl rsa -noout -text < rebuilt.pem
Private-Key: (1024 bit)
modulus:
    00:db:fa:bd:b1:49:5d:32:76:e7:62:6b:84:79:6e:
    9f:c2:0f:a1:3c:17:44:f1:0c:8c:3f:3e:3c:2c:60:
    40:c2:e7:f3:13:df:a3:d1:fe:10:d1:ae:57:7c:fe:
    ab:74:52:aa:53:10:2e:ef:7b:e0:09:9c:02:25:60:
    e5:7a:5c:30:d5:09:40:64:2d:1b:09:7d:d2:10:9a:
    e0:2f:2d:cf:f8:19:8c:d5:a3:95:fc:ac:42:66:10:
    78:48:b9:dd:63:c3:87:d2:53:8e:50:41:53:43:04:
    20:33:ea:09:c0:84:15:5e:65:2b:0f:06:23:40:d5:
    d4:71:7a:40:2a:9d:80:6a:6b
publicExponent: 65537 (0x10001)
privateExponent:
    0f:c2:53:ca:9a:9d:e1:9a:a1:12:ec:ee:ed:a0:1e:
    33:d1:d8:d4:2c:3a:95:26:37:f9:e3:e4:7d:ad:5b:
    96:5a:f5:90:0b:ea:79:85:c1:00:b4:83:b2:01:b0:
    98:c1:bf:4f:fa:0d:d2:bc:46:1d:8a:1e:a1:3c:e2:
    d3:b4:3d:0f:33:fb:d5:15:c5:05:3e:69:e7:a4:98:
    4c:26:bb:8f:a4:c7:5d:7c:aa:30:bc:5f:77:e6:05:
    81:5b:2b:7a:15:cc:84:08:bd:ef:23:1e:32:84:e6:
    a1:0f:75:18:df:dc:a9:6f:67:fc:c7:e5:25:d9:b4:
    68:eb:f4:b2:44:8e:03:49
prime1:
    00:f1:69:51:1e:66:be:06:22:c2:ab:2e:c1:5a:17:
    c0:c7:a0:c7:28:08:ae:cd:ba:28:c7:f5:20:ec:ad:
    23:65:b2:9c:cc:35:31:db:1a:bc:c0:3e:69:39:68:
    5f:e2:14:af:d1:41:ba:9f:6c:fd:3a:73:a5:fa:e8:
    5a:38:f3:69:a5
prime2:
    00:e9:45:de:22:61:e7:b7:33:17:46:1e:c4:85:99:
    71:5f:2b:e4:63:08:66:f9:9e:da:58:a1:49:ae:10:
    2d:1a:91:c4:f9:09:68:7f:56:ce:65:d7:fa:ab:0f:
    64:9d:8e:8a:e9:fc:2f:7e:53:5e:1d:5a:a7:61:97:
    b4:d7:e9:a6:cf
exponent1:
    39:d5:15:0d:c7:67:36:69:15:61:94:ed:d4:fb:63:
    bf:6f:10:c6:d2:6d:ad:f3:2e:d9:d8:2b:6f:07:7b:
    37:5d:b6:9a:65:13:f0:7d:53:42:6a:b1:22:83:92:
    94:c2:87:ec:05:67:03:d2:44:47:c0:74:be:ca:f2:
    f2:39:bd:d1
exponent2:
    12:59:47:8e:c6:ca:b6:33:53:9a:55:63:39:eb:06:
    ea:e8:85:ef:70:42:c1:51:c8:74:fe:42:d0:69:3f:
    52:fe:b2:52:b0:75:c2:c6:6e:37:be:94:5e:0e:38:
    e8:d7:c4:7f:81:31:af:2b:19:95:0f:83:68:fe:c8:
    df:ce:e6:2b
coefficient:
    00:a5:d0:84:f7:17:fc:43:fa:90:e3:06:47:c7:86:
    73:cb:15:cb:9b:60:e7:91:90:56:94:23:8b:16:65:
    22:52:ec:42:b7:5b:b8:ad:00:77:8b:33:1d:60:a6:
    f1:79:11:69:f6:da:f4:45:bd:eb:a2:45:8a:9c:d1:
    7e:48:3b:56:3c
En effet, ça colle bien avec le fichier de départ. Puisque nous avons maintenant la clef au bon format, voyons si l'outil de déchiffrement d'openssl fonctionne:
max@truite ~/rsa $ openssl pkeyutl -decrypt -inkey rebuilt.pem < encrypted 
crypt0>>>f0rensics3~

SUCCESS !

 
Also check me out on Mastodon