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~
