Max's Blog

mardi 29 juillet 2014

L'homme qui ne savait pas cuisiner

Il était une fois un homme, appelons-le monsieur B., qui ne savait pas cuisiner.

Aucune honte à cela, notez bien; chacun son métier, on ne peut pas tout savoir. Monsieur B était très doué dans son travail, mais n'avait aucun don aux fourneaux. Célibataire, il se nourrissait principalement de sandwiches et de plats précuisinés. C'est très pratique, les plats précuisinés: 3 minutes au micro-ondes, et on mange chaud.

Un jour, en discutant avec quelques amis aux tendances bobo/écolo/gauchistes, ceux-ci lui soutiennent qu'il existe une alternative infiniment supérieure à ses plats favoris: les produits frais.

Les produits frais n'ont que des avantages: ils sont moins chers (pour monsieur B., c'est important), et ils sont mieux tolérés par les estomacs fragiles des personnes agées. Le choix est beaucoup plus varié, on peut plus facilement personnaliser ses plats. Il paraîtrait même que dans les restaurants haut de gamme, on les utilise.

Monsieur B. connait le restaurant de l'entreprise, mais il n'a jamais été guigner dans les cuisines. Il s'imagine que la cuisine du restaurant ressemble probablement à la sienne, en plus grand; une rangée de fours micro-ondes, un grand frigo pour stocker les plats, un lave-vaisselle pour laver les plats, rien besoin de plus.

Néanmoins, il décide d'expérimenter ces fameux produits frais aux innombrables vertus. Il se rend donc au supermarché, et pour la première fois de sa vie, il explore d'autres rayons que celui des sandwiches et des plats micro-ondes.

Le choc est plutôt violent, il trouve des centaines de produits aux formes et couleurs étranges. Il achète un brocoli, rentre chez-lui, met son brocoli 3 minutes au micro-ondes. Il goûte, c'est dégueulasse.

Monsieur B. se dit qu'il n'a peut-être pas choisi le bon produit. Il observe un peu ce que les gens achètent, et choisit quelques produits au hasard: une pastèque, un camembert, une douzaine d'oeufs. Il les teste successivement,3 minutes au micro-ondes. C'est dégueulasse, son micro-ondes est couvert de bouillie de pastèque, d'oeuf explosé, et toute sa cuisine schmecte le camembert.

Monsieur B. est furieux d'avoir ruiné son micro-ondes et se plaint a ses amis. Ceux-ci l'écoutent d'abord, incrédules; puis, ne sachant trop par où commencer, lui suggèrent qu'il faut en fait, pour manger des produits frais, suivre une recette.

Monsieur B. se rend sur Gougle, et commence à chercher sur le Ouaibe des recettes de cuisine. Très vite, il s'énerve; la plupart des recettes contiennent du jargon incompréhensible, des expressions comme "brunoise de légumes", "déglacer au Grand Marnier" ou "épaissir au roux blond". Totalement incompréhensible pour un non-cuisinier.

Changeant d'approche, Monsieur B. s'inscrit sur un forum et poste une demande d'aide: "HELP, j'ai mis des oeufs au four, 3 minutes à 900W, tout à explosé, que faire ?". Le premier intervenant à lui répondre lui fait remarquer qu'il faut dire "four MICRO-ONDES" et pas "four", pour ne pas prêter à confusion. Monsieur B est un peu agacé par la pédanterie de ces cuisiniers, qui ergotent sur la terminologie au lieu de lui proposer des solutions.

Lassé, Monsieur B. décide qu'il lui sera plus simple, pour sa première dégustation de produits frais, de faire appel à un professionnel, et se rend au restaurant. Il commande un steak de boeuf aux champignons. Arrive l'addition, il s'étrangle: 48.- le steak de boeuf. Au supermarché, le steak coute 10.- et les champignons 2.- maximum. Comment ces cuisiniers osent-ils surfacturer à ce point leurs prestations ? 36 francs pour glisser une barquette dans un four, le régler sur 3 minutes et appuyer sur start ? inadmissible.

Monsieur B. retourne sur Internet, et tombe par hasard sur le forum d'une émission consacrée a la cuisine. Il y rédige une longue diatribe décriant les produits frais. Il y explique posément que les produits frais, c'est immangeable; il en a essayé une cinquantaine, à chaque fois c'était dégueulasse. On lui avait aussi dit que c'était moins cher, mais c'est un mensonge éhonté; au final, il faut payer un cuisinier très cher pour les préparer. C'est n'importe quoi, des produits qu'on ne peut pas préparer en les mettant 3 minutes au micro-ondes, ce qui est pourtant le standard universel de la cuisine. Vraiment, ça n'a aucun intérêt; ça ne peut que rester qu'un fantasme dans l'esprit de quelques cuisiniers.

Ami lecteur, si tu ne vois pas le rapport entre cette histoire et le logiciel libre, jette un oeil à cette rubrique et au premier commentaire posté dedans...

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:

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 d_p ≡ e^-1 (mod p-1), et d_q ≡ 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 2^t). 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 2^t). 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, d_pet d_q 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·d_p = 1 + k_p(p-1)
e·d_q = 1 + k_q(q-1)

Ces équations restent valable après réduction modulo 2^t, ce qui va nous permettre, la encore, de les reconstruire bit par bit. Mais il nous faut d'abord obtenir k, k_p et k_q.

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 log₂(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 k_p et k_q. 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 k_p et k_q sont parmi les solutions pour k'. S'il n'y en a qu'une, k_p = k_{q, 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, k_p et k_q, 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 2⁵ 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, d_p, d_q 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 d_p ou d_q, 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 !

samedi 22 mars 2014

CTF Writeup: Insomni'hack 2014: encoding

On fait face à un serveur web, disons http://insomni.hack/. Sur la page d'accueil, on trouve un lien vers la "Page d'administration", http://insomni.hack/control.php/admin, qui nous gratifie d'un beau "Please authenticate.".

On tape dans le robots.txt, on y découvre:

User-Agent: *
Disallow: /backup
Disallow: /

Aha. Le répertoire backup nous offre un listing, on y découvre le fichier suivant, qu'on sauvegarde dans encoded.php:

gzuncompress(str_rot13(base64_decode('a5yVkVhCwzAMgM/1rzDVDq00sQc7rYxdKBIXBt3jgtCUtd5NEZIqWoQQ6n8n3bRUVCfEMY4/+7N9O87THKCVsw3hCAuzKrTyTct2GC3C6NWNwpdsOJ0t59Gj+9butns3fgAtlnxx4myH/MXgDiGlpLLpwmMeAEC2U8+zXCY2/na90Qjd7dP1v8E5YL0AVyReQ43bTV9MohNYoZXk12maQZ3s71a00Qtdeol91CieQywT8o7/fkjQqVrdmBaAZnlIM2NXKGoz/7PrqWNw0vnGHIpGia5BCdecejArYza5n7iVw1K135t6vgienwSg+MxnnNq5tuHKIHO2i9fzhweZL3ZDECWoJTJw1YTOb6apkmVJith7sMf6J9igO8AnqfFOGpHUZRNNM8P18Bgqbnz3A8Wt1kk=')));

On utilise php pour évaluer cette expression facilement:

$ php -r 'echo(gzuncompress(str_rot13(base64_decode('a5yVkVhCwzAMgM/1rzDVDq00sQc7rYxdKBIXBt3jgtCUtd5NEZIqWoQQ6n8n3bRUVCfEMY4/+7N9O87THKCVsw3hCAuzKrTyTct2GC3C6NWNwpdsOJ0t59Gj+9butns3fgAtlnxx4myH/MXgDiGlpLLpwmMeAEC2U8+zXCY2/na90Qjd7dP1v8E5YL0AVyReQ43bTV9MohNYoZXk12maQZ3s71a00Qtdeol91CieQywT8o7/fkjQqVrdmBaAZnlIM2NXKGoz/7PrqWNw0vnGHIpGia5BCdecejArYza5n7iVw1K135t6vgienwSg+MxnnNq5tuHKIHO2i9fzhweZL3ZDECWoJTJw1YTOb6apkmVJith7sMf6J9igO8AnqfFOGpHUZRNNM8P18Bgqbnz3A8Wt1kk='))));'

$page = substr($_SERVER["REQUEST_URI"],0,13);
$adminPage =  substr($_SERVER["REQUEST_URI"], 13);
$error = null;


if ((string)$adminPage === "admin"){
        $error = 1;
} elseif ((string)$page != "/control.php/"){
        $error = 2;
} else {
        if ((string)$adminPage != (string)urldecode($adminPage)){
                $adminPage = urldecode($adminPage);
        } else {
                $error = 2;
        }
}

if ($adminPage != (string)urldecode($adminPage)){
        if ((string)urldecode($adminPage) === "admin"){
                echo "the flag is TODO";
        }else {
                $error = 2;
        }
} elseif ((string)$adminPage === "admin") {
        $error = 1;
}

switch ($error){
        case (1):
                echo "you need to authenticate";
                break;
        case (2):
                echo "404 Not Found";
                break;
        default:
                break;
}

Pour déclencher la branche de code qui révèle le flag, les conditions suivants doivent être remplies:

(string)adminPage === "admin" => FALSE
(string)adminPage != (string)urldecode(adminPage)  => TRUE

adminPage = urldecode(adminPage);

$adminPage != (string)urldecode($adminPage)) => TRUE
(string)urldecode($adminPage) === "admin" => TRUE

Par la première condition, on doit donc remplacer le chemin d'accès, "admin", par autre chose. La deuxième condition impose que la nouvelle chaine contienne au moins une séquence d'échappement interprétée par urldecode.
Après décodage, la 3e condition impose que la chaine contienne encore une fois une séquence d'échappement, et que cette séquence, une fois décodée une deuxième fois, soit égale à "admin".
On choisit donc un caractère au hasard, ici le "i". La séquence après le premier décodage sera donc "adm%69n". On passe ensuite cette chaine dans urlencode une deuxième fois, pour obtenir "adm%3069n".
Il suffit donc de visiter http://insomni.hack/control.php/adm%3069n, et hop !

CTF Writeup: Insomni'hack 2014: Leeeetcrypto

La donnée du problème consiste en une longue suite de nombres, séparés par des espaces.

52568362028447315123743948788053644459577411882456257531616135268537279675960870614430475573303102032918797133050913 52727929746007441720068082686756949179073655255531676829839480670880742558336965750100665996845187331498825064459186 201158324192401598932420659686637057233217007355201796046752494579206057840824741418635158750620395621617197903012628 28130137328108864733654457574649869546226965870669213292484603118885398856280073620722817153185715356950196877471039 80484565918589639155839282503441828047447393078860552265541334592733372319489211090676853869300071705818380141734553 327884935077457453113605219951670824692959814316520336632744473695392968704109006664884646461226287506677371413786816 71320589399616119392997612087604459808872826741986236180026121617993570092370114471863111200409714142046077511450033 222751634152401318446067973538013344568447280940195394615901147009774216683554748179893081969917861424112117226026325 28130137328108864733654457574649869546226965870669213292484603118885398856280073620722817153185715356950196877471039 80484565918589639155839282503441828047447393078860552265541334592733372319489211090676853869300071705818380141734553 139898042261876853301455727625774012475698643685395021760275568789054192063562822563098057540361718346301097569068285 290458508376731263921252055316868138470702882414424357263569140840448897025047660176505033785801971649974769416580828 11782118315742696825087904229204586109210704966361563810081222896447101063588246593812259079361925308894139998117784 39752644457197524816840681265913188543326108820355516805599867640545430987920927262238504378204278859183980221246355 301118090575689790044304143985657097761186152450376594357207609156541662901869839587261599850312495649532760148859125 80484565918589639155839282503441828047447393078860552265541334592733372319489211090676853869300071705818380141734553 222751634152401318446067973538013344568447280940195394615901147009774216683554748179893081969917861424112117226026325 76309999578481760278134186167064490139180297738713651148555706607615754191408415493954631393292274058258783002375297 312440510356542990832274139310717029606738136784317835051579720866508272813085512326169432510915628987511601361100755 312440510356542990832274139310717029606738136784317835051579720866508272813085512326169432510915628987511601361100755 76309999578481760278134186167064490139180297738713651148555706607615754191408415493954631393292274058258783002375297 11782118315742696825087904229204586109210704966361563810081222896447101063588246593812259079361925308894139998117784 39752644457197524816840681265913188543326108820355516805599867640545430987920927262238504378204278859183980221246355 71320589399616119392997612087604459808872826741986236180026121617993570092370114471863111200409714142046077511450033 11782118315742696825087904229204586109210704966361563810081222896447101063588246593812259079361925308894139998117784 39752644457197524816840681265913188543326108820355516805599867640545430987920927262238504378204278859183980221246355 301118090575689790044304143985657097761186152450376594357207609156541662901869839587261599850312495649532760148859125 71320589399616119392997612087604459808872826741986236180026121617993570092370114471863111200409714142046077511450033 39752644457197524816840681265913188543326108820355516805599867640545430987920927262238504378204278859183980221246355 301118090575689790044304143985657097761186152450376594357207609156541662901869839587261599850312495649532760148859125 11782118315742696825087904229204586109210704966361563810081222896447101063588246593812259079361925308894139998117784 71320589399616119392997612087604459808872826741986236180026121617993570092370114471863111200409714142046077511450033 231618262599702676973845832517759334021176525056072833529569269456564473604609355284495911481371096877656941135244359 139898042261876853301455727625774012475698643685395021760275568789054192063562822563098057540361718346301097569068285 76309999578481760278134186167064490139180297738713651148555706607615754191408415493954631393292274058258783002375297 28130137328108864733654457574649869546226965870669213292484603118885398856280073620722817153185715356950196877471039 301118090575689790044304143985657097761186152450376594357207609156541662901869839587261599850312495649532760148859125 11782118315742696825087904229204586109210704966361563810081222896447101063588246593812259079361925308894139998117784 231609473505895645459311620779424869497767062819966540784040891362418669395322439617108666258332519877710534676878307 139898042261876853301455727625774012475698643685395021760275568789054192063562822563098057540361718346301097569068285 80484565918589639155839282503441828047447393078860552265541334592733372319489211090676853869300071705818380141734553 222751634152401318446067973538013344568447280940195394615901147009774216683554748179893081969917861424112117226026325 181895177774870499268628883221214310423523857203344119754826804608066049315978476367118679395919668261312392452153631 231618262599702676973845832517759334021176525056072833529569269456564473604609355284495911481371096877656941135244359 231609473505895645459311620779424869497767062819966540784040891362418669395322439617108666258332519877710534676878307 205884448854259361864211375336005072036904149095927464741554161540888665349683555934701608904819901412468420531999589
-----BEGIN PUBLIC KEY-----
MEwwDQYJKoZIhvcNAQEBBQADOwAwOAIxCGVV/7bWB7CH0Z2UsUJgM/s6zW2UCiid
twBq/aXZxGfqX0gBgwwgAAAAAAAAAGFvjQIDAQAB
-----END PUBLIC KEY-----

On reconnait le format PEM standard de stockage de clefs publiques, et on utilise openssl pour obtenir les données de la clef:

$ openssl rsa -text -noout -pubin < leet
Public-Key: (388 bit)
Modulus:
    08:65:55:ff:b6:d6:07:b0:87:d1:9d:94:b1:42:60:
    33:fb:3a:cd:6d:94:0a:28:9d:b7:00:6a:fd:a5:d9:
    c4:67:ea:5f:48:01:83:0c:20:00:00:00:00:00:00:
    00:61:6f:8d
Exponent: 65537 (0x10001)

La clef est très petite, et pourra probablement être aisément factorisée. On pourrait aussi supposer, vu le grand nombre de ciphertexts, qui collent avec la taille de la clef, que chacun est une toute petite valeur (un byte, au hasard ?) et on pourrait construire un dictionnaire de petites valeurs chiffrées avec la clef publique. Mais comme le module est petit, attaquons-le directement. Pour ça, on télécharge et on compile gmp-ecm.

wget https://gforge.inria.fr/frs/download.php/32159/ecm-6.4.4.tar.gz
tar xvzf ecm-6.4.4.tar.gz
cd ecm-6.4.4
./configure
make

gmp-ecm lit les nombres en décimal, convertissons donc ce nombre en décimal:

$ sed -e 's/://g' < modulus |tr a-f A-F
86555FFB6D607B087D19D94B1426033FB3ACD6D940A289DB7006AFDA5D9C467EA5F4801830C2000000000000000616F8D
$ tr a-f A-F <<< "16 i 86555FFB6D607B087D19D94B1426033FB3ACD6D940A289DB7006AFDA5D9C467EA5F4801830C2000000000000000616F8D p" |dc
330813077170623813868916447047968257225466236033071266804905080468565157617117193466673715216384000000000000006385549

On passe ce nombre à gmp-ecm:

$ ./ecm 100000 <<< 330813077170623813868916447047968257225466236033071266804905080468565157617117193466673715216384000000000000006385549
GMP-ECM 6.4.4 [configured with GMP 5.1.3, --enable-asm-redc] [ECM]
Input number is 330813077170623813868916447047968257225466236033071266804905080468565157617117193466673715216384000000000000006385549 (117 digits)
Using B1=100000, B2=40868532, polynomial x^2, sigma=3677913806
Step 1 took 471ms
********** Factor found in step 1: 13331
Found probable prime factor of  5 digits: 13331
Probable prime cofactor 24815323469403931728221172233738523533528335161133543380459461440894543366372904768334987264000000000000000000479 has 113 digits

Parfait, les deux facteurs sont premiers selon toute vraisemblance. Supposons qu'une version minimale de RSA a été utilisée, calculons l'exposant de déchiffrement avec un petit programme Haskell:

-- Puissance modulaire rapide:
-- emod a e n = (a^e `mod` n)
emod _ 0 _ = 1
emod a e n | odd e     = (a * square (emod a (e `div` 2) n)) `mod` n
           | otherwise = square (emod a (e `div` 2) n) `mod` n

-- Algorithme d'Euclide étendu, pour résoudre l'équation de Bézout
-- euclid a b = (i,j,k) | a*i + b*j = k
euclid a b
  | b > a = let (j,i,k) = euclid b a in (i,j,k)
  | otherwise = euclid' (1,0,a) (0,1,b) where
      euclid' p@(i,j,k) q@(i',j',k')
        | k' == 0   = p
        | otherwise = let f = k `div` k'
                in euclid' q (i-i'*f, j-j'*f, k-k'*f)


n = 330813077170623813868916447047968257225466236033071266804905080468565157617117193466673715216384000000000000006385549
p = 13331
q = n `div` p

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

e = 65537

-- Résoudre d*e + k*phi = g, pour g = PGCD(e,phi)
(d,k,g) = euclid e phi
-- On vérifie que g == 1

decrypt c = emod c (d `mod` phi) n

-- Les ciphertexts en dur, on découpe sur les espaces.
ciphers :: [Integer]
ciphers = map read $ words "5256...0913 5272792...31999589"

On teste dans GHCi:

*Main> map decrypt ciphers
[73,78,83,49,52,123,55,50,49,52,51,100,57,102,97,52,50,48,53,53,48,57,102,55,57,102,97,55,102,97,57,55,99,51,48,49,97,57,56,51,52,50,54,99,56,125]

Clairement un résultat intéressant, on dirait de l'ascii.

*Main Data.Char> map (chr.fromInteger.decrypt) c
"INS14{72143d9fa4205509f79fa7fa97c301a983426c8}"

Success !!!

CTF Writeup: Insomni'hack 2014: protocrypt

Au début du problème, nous avons à disposition 3 informations: une capture réseau, un programme client, et l'addresse du serveur.

capture.pcapng: pcap-ng capture file - version 1.0
client:         ELF 64-bit LSB executable, x86-64, version 1 (GNU/Linux), statically linked, for GNU/Linux 2.6.32, BuildID[sha1]=04d200ccd619d8bc33a87567b74b2e3910515eaf, not stripped

Je décide de regarder la capture réseau en premier, et l'ouvre avec Wireshark. Il contient un seul flot tcp:

.zw.t]u.....t.]P]e{.W...k.......zk...z]..Z]gy.t.]..]z.]~{..]y.t.].w]wy.]....zwZ

Initelligible. Je décide de ne pas regarder le serveur, et commence de suite à analyser le binaire. Malheureusement, c'est un binaire 64bits, donc la version gratuire d'IDA ne l'analysera pas. Qu'a cela ne tienne, je l'attaque avec Objdump. Heureusement, le binaire n'a pas été strippé, et parmi les symboles, on voit deux routines, "encrypt" et "decrypt".
Le désassemblage de la routine "encrypt", commenté à la main:

0000000000400f7e :
  400f7e: 55                    push   rbp
  400f7f: 48 89 e5              mov    rbp,rsp

  // Save registers on stack
  400f82: 48 89 7d e8           mov    QWORD PTR [rbp-0x18],rdi  // char *destination;
  400f86: 89 75 e4              mov    DWORD PTR [rbp-0x1c],esi  // int length;
  400f89: 48 89 55 d8           mov    QWORD PTR [rbp-0x28],rdx  // int *key
  400f8d: c7 45 fc 00 00 00 00  mov    DWORD PTR [rbp-0x4],0x0   // int counter;
  400f94: c7 45 fc 00 00 00 00  mov    DWORD PTR [rbp-0x4],0x0


  // while (counter = 0; counter < length; counter++) {
  400f9b: e9 8f 00 00 00        jmp    40102f 


  //// rdx = &destination[counter]
  400fa0: 8b 45 fc              mov    eax,DWORD PTR [rbp-0x4]
  400fa3: 48 63 d0              movsxd rdx,eax
  400fa6: 48 8b 45 e8           mov    rax,QWORD PTR [rbp-0x18]
  400faa: 48 01 c2              add    rdx,rax
  //// rax = &destination[counter]
  400fad: 8b 45 fc              mov    eax,DWORD PTR [rbp-0x4]
  400fb0: 48 63 c8              movsxd rcx,eax
  400fb3: 48 8b 45 e8           mov    rax,QWORD PTR [rbp-0x18]
  400fb7: 48 01 c8              add    rax,rcx

  //// eax = *rax
  400fba: 0f b6 00              movzx  eax,BYTE PTR [rax]
  400fbd: 89 c1                 mov    ecx,eax
  400fbf: 48 8b 45 d8           mov    rax,QWORD PTR [rbp-0x28]
  400fc3: 8b 00                 mov    eax,DWORD PTR [rax]
  ///// eax ^= key[0]
  400fc5: 31 c8                 xor    eax,ecx
  ///// destination[counter] = eax
  400fc7: 88 02                 mov    BYTE PTR [rdx],al

  //// rdx = &destination[counter]
  400fc9: 8b 45 fc              mov    eax,DWORD PTR [rbp-0x4]
  400fcc: 48 63 d0              movsxd rdx,eax
  400fcf: 48 8b 45 e8           mov    rax,QWORD PTR [rbp-0x18]
  400fd3: 48 01 c2              add    rdx,rax

  //// rax = &destination[counter]
  400fd6: 8b 45 fc              mov    eax,DWORD PTR [rbp-0x4]
  400fd9: 48 63 c8              movsxd rcx,eax
  400fdc: 48 8b 45 e8           mov    rax,QWORD PTR [rbp-0x18]
  400fe0: 48 01 c8              add    rax,rcx

  //// esi = *rax
  400fe3: 0f b6 00              movzx  eax,BYTE PTR [rax]
  400fe6: 0f b6 f0              movzx  esi,al

  //// ecx = key[1]
  400fe9: 48 8b 45 d8           mov    rax,QWORD PTR [rbp-0x28]
  400fed: 48 83 c0 04           add    rax,0x4
  400ff1: 8b 00                 mov    eax,DWORD PTR [rax]
  400ff3: 89 c1                 mov    ecx,eax

  //// esi < ecx
  400ff5: d3 e6                 shl    esi,cl

  //// rax = &destination[counter]
  400ffb: 8b 45 fc              mov    eax,DWORD PTR [rbp-0x4]
  400ffe: 48 63 c8              movsxd rcx,eax
  401001: 48 8b 45 e8           mov    rax,QWORD PTR [rbp-0x18]
  401005: 48 01 c8              add    rax,rcx

  //// edi = *rax
  401008: 0f b6 00              movzx  eax,BYTE PTR [rax]
  40100b: 0f b6 f8              movzx  edi,al

  //// ecx = 8 - key[1]
  40100e: 48 8b 45 d8           mov    rax,QWORD PTR [rbp-0x28]
  401012: 48 83 c0 04           add    rax,0x4
  401016: 8b 00                 mov    eax,DWORD PTR [rax]
  401018: b9 08 00 00 00        mov    ecx,0x8
  40101d: 29 c1                 sub    ecx,eax
  40101f: 89 c8                 mov    eax,ecx
  401021: 89 c1                 mov    ecx,eax

  //// edi < ecx
  401023: d3 ff                 sar    edi,cl

  //// *rdx = esi | edi
  401025: 89 f8                 mov    eax,edi
  401027: 09 f0                 or     eax,esi
  401029: 88 02                 mov    BYTE PTR [rdx],al

  // }
  40102b: 83 45 fc 01           add    DWORD PTR [rbp-0x4],0x1
  40102f: 8b 45 fc              mov    eax,DWORD PTR [rbp-0x4]
  401032: 3b 45 e4              cmp    eax,DWORD PTR [rbp-0x1c]
  401035: 0f 8c 65 ff ff ff     jl     400fa0 


  40103b: 90                    nop
  40103c: 5d                    pop    rbp
  40103d: c3                    ret

Une routine particulièrement peu optimisée pour le code C suivant:

void encrypt(char *data, int length, int *key) {
    int counter = 0;
    for (counter = 0; counter < length; counter++) {
        data[counter] ^= key[0];
        data[counter] = (data[counter] << key[1]) | (data[counter] >> (8 - key[1]));
    }
}

Je vous épargne la routine de déchiffrement, tout aussi sous-optimisée, mais cohérente avec le reste.

Il n'y a que 256 valeurs effectives possibles pour key[0], et 8 pour key[1], soit 2048 clefs possibles au total. Le client, quand il est exécuté, demande une seule valeur de 4 chiffres comme clef. Le client et le serveur utilisent donc probablement la même pour communiquer. Nous allons bruteforcer la clef utilisée pour la capture.

Pour commencer, il nous faut des statistiques sur la probabilité d'apparition des bytes individuels dans le texte clair. Je commence par supposer que le protocole contient du texte.

Ne trouvant rien de probant sur internet, je commence par collecter des bouts de fichier texte un peu partout dans mon système:

find /home/max -name "*.txt" |head -n100 |xargs cat > bigrandomtextfile.txt

Puis j'utilise le fragment de Haskell suivant pour générer des statistiques:

import qualified Data.ByteString as B
import qualified Data.Map as M

main = do
        text <- B.readFile "textfiles"
        let stats = M.fromListWith (+) . (`zip` [1,1..]) $ [0..255] ++ B.unpack text
        print stats

On découpe le fichier en bytes avec B.unpack, on y ajout une fois chaque bytes de 0 à 255 pour ne pas avoir de 0 dans la map, et on affiche le résultat.

frequencyTable = M.fromList [(0,1),(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,1),(8,1),(9,144),(10,172065),(11,1),(12,10),(13,6359),(14,1),(15,1),(16,1),(17,1),(18,1),(19,1),(20,1),(21,1),(22,1),(23,1),(24,1),(25,1),(26,1),(27,1),(28,1),(29,1),(30,1),(31,1),(32,903319),(33,431),(34,1358),(35,460),(36,75),(37,511),(38,9356),(39,6813),(40,13377),(41,13489),(42,646),(43,4551),(44,12776),(45,9806),(46,47367),(47,179551),(48,138265),(49,30661),(50,55552),(51,48834),(52,28428),(53,45934),(54,24841),(55,26279),(56,38631),(57,25568),(58,48597),(59,9702),(60,227703),(61,2944),(62,227708),(63,1713),(64,1541),(65,7344),(66,27714),(67,22095),(68,20877),(69,21439),(70,6026),(71,3751),(72,3768),(73,11286),(74,776),(75,523),(76,9283),(77,4458),(78,13869),(79,7889),(80,10272),(81,239),(82,30229),(83,13744),(84,22801),(85,29150),(86,784),(87,2025),(88,459),(89,6076),(90,137),(91,5841),(92,53),(93,5841),(94,16),(95,282275),(96,36),(97,308952),(98,82152),(99,185842),(100,163847),(101,561599),(102,183557),(103,113944),(104,62272),(105,340221),(106,2968),(107,37168),(108,277212),(109,112984),(110,259352),(111,393856),(112,143240),(113,13026),(114,362535),(115,263072),(116,422578),(117,185756),(118,28394),(119,51245),(120,15040),(121,40527),(122,5384),(123,1),(124,4),(125,1),(126,8),(127,1),(128,253),(129,154),(130,133),(131,415),(132,106),(133,44),(134,34),(135,70),(136,173),(137,108),(138,113),(139,104),(140,60),(141,87),(142,102),(143,25),(144,178),(145,131),(146,27),(147,28),(148,293),(149,335),(150,72),(151,47),(152,57),(153,85),(154,61),(155,65),(156,44),(157,73),(158,51),(159,18),(160,605),(161,63),(162,66),(163,37),(164,23),(165,52),(166,30),(167,22),(168,32),(169,19),(170,46),(171,41),(172,11),(173,52),(174,10),(175,5),(176,72),(177,130),(178,74),(179,91),(180,40),(181,99),(182,34),(183,33),(184,395),(185,184),(186,47),(187,50),(188,85),(189,246),(190,89),(191,128),(192,1),(193,1),(194,14),(195,19),(196,3),(197,4),(198,1),(199,1),(200,1),(201,10),(202,6),(203,9),(204,3),(205,1),(206,454),(207,249),(208,220),(209,110),(210,1),(211,1),(212,1),(213,1),(214,1),(215,1),(216,1),(217,1),(218,1),(219,1),(220,1),(221,1),(222,1),(223,1),(224,413),(225,934),(226,1322),(227,5),(228,1),(229,1),(230,1),(231,1),(232,1),(233,1),(234,1),(235,1),(236,1),(237,1),(238,1),(239,2),(240,1),(241,1),(242,1),(243,1),(244,1),(245,1),(246,1),(247,1),(248,1),(249,1),(250,1),(251,1),(252,1),(253,1),(254,1),(255,1)]

Après avoir sauvegardé, avec wireshark, le dialogue chiffré dans un fichier "encrypted", j'utilise le programme Haskell suivant pour bruteforcer la clef:

type Key = (Word8, Int)

decrypt :: Key -> B.ByteString -> String
decrypt (k0, k1) = map (chr . fromIntegral . flip rotateL k1 . xor k0) . B.unpack

encrypt :: Key -> String -> B.ByteString
encrypt (k0, k1) = B.pack . map (xor k0 . flip rotateR k1 . fromIntegral . ord)

allKeys :: [(Word8, Int)]
allKeys = [ (k0, k1) | k0 <- [0..255], k1 <- [0..7] ]

score s = product [ frequencyTable M.! (ord c) | c <- s ]

bestDecryption = do
        f <- B.readFile "encrypted"
        let cipher = B.unpack f
        let clears = [ (k, decrypt k cipher) | k <- allKeys ]
        let best = last . sortBy (comparing (score.snd)) $ clears
        return best

On obtient k = (77,1), et le message déchiffré:
Enter password : Ple4s3_L37_m3_1nLogin OK. There is no flag here at the moment.
Pour tester, plutot que d'essayer de désassembler le main, j'utilise rapidement gdb pour comprendre le format de clef du programme client. Je mets un breakpoint sur decrypt, lance le programme avec diverses valeurs et inspecte les valeurs de la variable key[]. Le client accepte une clef de 4 chiffres au format "xxxy", x est k[0] en décimal, y est k[1].

J'essaie de lancer le client sur le serveur de production, avec la clef "0771", mais le client refuse, indiquant qu'il ne peut déchiffrer la réponse du serveur.
Je suppose donc que le client attend la chaîne fixe "Enter password : " avant de continuer, et visiblement, le serveur utilise une clef différente. Quelques essais avec netcat montrent que la clef change à chaque connexion. Nous allons donc implémenter un programme qui se connecte au serveur, lit la réponse, bruteforce la clef en live, sur le texte clair connu que nous avons, puis envoie le mot de passe connu avec la clef détectée, et lit la réponse.


password = "Ple4s3_L37_m3_1n"

witness = "Enter password : "

attack = do
        (addr:_) <- getAddrInfo Nothing (Just "10.13.37.101") (Just "21345")
        sock <- socket (addrFamily addr) Stream defaultProtocol
        connect sock (addrAddress addr)
        hello <- recv sock (length witness)
        case [ k | k <- allKeys, decrypt k hello == witness ] of
                [key] -> do
                        print $ "Key found : " ++ show key
                        sendAll sock (encrypt key password)
                        flag <- recv sock 2048
                        print $ "Received: " ++ decrypt key flag
                _ -> print "Could not find key :("

On exécute le programme:

"Key found : (27, 6)"
"Received: INS{blablablaflag}"

Merci à Delraich pour la relecture et les corrections !

lundi 8 juillet 2013

SIGINT CTF 2013: RSA

Quelques explications sur le problème RSA du SIGINT CTF 2013:

Les deux fichiers suivants sont donnés:

genrsa.py

#!/usr/bin/env python

from time import time
from os import system
from Crypto.PublicKey import RSA


SEED = int(time())


def randfunc(n):
    def rand():
        global SEED
        ret = SEED*0x1333370023004200babe004141414100e9a1192355de965ab8cc1239cf015a4e35 + 1
        SEED = ret
        return (ret >> 0x10) & 0x7fff
    ret = ""
    while len(ret) < n:
        ret += chr(rand() & 0xff)
    return ret

if __name__ == "__main__":

    keypair = RSA.generate(1024, randfunc)


    with open("pub", "w") as pubfile, open("id_rsa", "w") as privfile:
        privfile.write(keypair.exportKey())
        pubfile.write(keypair.publickey().exportKey())

    system("ssh-keygen -m PKCS8 -i -f pub > id_rsa.pub && rm pub")

Et le fichier authorized_keys

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAAAgQC+K6w1yodieqyryJnUYHw/ZuycabT0Ehwg4XFqZYfh/euE4QIXPJ23widXJUKIq8Gqwi5M/Pa+7/gAPeVcrcF65pUkeIYeZBXoAeDj0EqpFxiHdSB/K1Ovt/lIFmBG3hy+MVJLYfz6lBRxQwj+CJRkFX2Xf/5JyZWSK5UwXOlh0w==

On a donc la partie publique d'une clef RSA générée avec un RNG faible.

La première observation est que ce RNG fait grandir SEED de manière arbitrairement grande; ce RNG est donc très, très lent. Cependant, on observe qu'en sortie, seuls les bits 16-24 de SEED sont utilisés (on à SEED >> 0x10 & 0xff). Autrement dit, ce générateur non borné est congru a un autre modulo 2^24. Ou, pour voir plus simplement les choses: après multiplication par la grande constante, un bit changé dans la seed en entrée ne peut affecter que des bits de poids plus fort. on peut donc joyeusement ignorer les bits au dela du 24e.

On peut donc remplacer la grande constante 0x1333...5a4e35, par sa réduction modulo 2^25, soit 0x15a4e35. On peut également réduire SEED à chaque iteration, avec SEED &= 0x1ffffff. Ceci a pour effet d'accélérer considérablement le RNG.

Pour le bruteforce, l'espace des seeds est quand même assez grand, nous allons donc essayer de la deviner. Le header de la réponse HTTP du fichier authorized_keys nous indique:

Last-Modified: Fri, 05 Jul 2013 17:50:05 GMT

La génération de la clef est donc antérieure à cette date. On va commencer à bruteforcer en partant de cette valeur, et en descendant.

Pour ne pas perdre de temps, on lit le code de PyCrypto concernant la génération de clefs RSA, et on s'aperçoit que ce code appelle pubkey.getStrongPrime une première fois, avec la moitié de la taille souhaitée, puis autant de fois que nécessaire pour obtenir le deuxième nombre. Pour gagner un peu de temps, plutôt que de chercher a générer la clef exacte, nous allons seulement générer le premier nombre premier p, et tester si ce nombre divise le n connu; si c'est le cas, le résultat de la division nous donnera le deuxième nombre q.

On commence par extraire le e et le n de la clef ssh, avec

ssh-keygen -e -f authorized_keys -m PKCS8 |openssl rsa -pubin -text

Ceci nous révèle l'exposant 65537 (comme prévu suivant le code de génération) et le module 0xBE2BAC35CA87627AACABC899D4607C3F66EC9C69B4F4121C20E1716A6587E1FDEB84E102173C9DB7C22757254288ABC1AAC22E4CFCF6BEEFF8003DE55CADC17AE6952478861E6415E801E0E3D04AA917188775207F2B53AFB7F948166046DE1CBE31524B61FCFA9414714308FE089464157D977FFE49C995922B95305CE961D3

On lance le bruteforce avec le script d'attaque suivant:

#!/usr/bin/env python

from time import time
from os import system
from Crypto.PublicKey import pubkey

target = 0xBE2BAC35CA87627AACABC899D4607C3F66EC9C69B4F4121C20E1716A6587E1FDEB84E102173C9DB7C22757254288ABC1AAC22E4CFCF6BEEFF8003DE55CADC17AE6952478861E6415E801E0E3D04AA917188775207F2B53AFB7F948166046DE1CBE31524B61FCFA9414714308FE089464157D977FFE49C995922B95305CE961D3

SEED2 = 0

def randfunc2(n):
    def rand():
        global SEED2
        ret = SEED2 * 0x15a4e35 + 1
        SEED2 = ret & 0xffffffff
        return (ret >> 0x10) & 0x7fff
    ret = ""
    while len(ret) < n:
        ret += chr(rand() & 0xff)
    return ret.encode('latin1')


if __name__ == "__main__":
    x = 1373046605
    while True:
        SEED2 = x
        x -= 1
        prime = pubkey.getStrongPrime(512, 65537, 1e-12, randfunc2)
        if target % prime == 0:
                print("BROKEN!!! p={0}".format(prime));
                exit(0);
        if x % 10 == 0:

En quelque minutes, on obtient les valeurs p = 13097286606179453667665592444299109782484218865253457545521978739889248320232481682880143106432871469494586765663594908396375009598486558938138835723794021 et q = 10196183246368760603869192593971202143897281417220455881063414616103901438182656326076501376638806928762094749150020638960102206987607293047096627515275223

On utilise Crypto.PublicKey.RSA.construct() pour construire la clef, on l'exporte dans un fichier, elle est utilisable directement par openssh.

jeudi 2 mai 2013

Un élusif problème de DNS

J'ai compris la cause récente du problème récurrent et aléatoire de DNSSEC sur ma zone principale. Comme la plupart du temps, c'est une erreur très bête.

Le programme dnssec-signzone prend en entrée une zone DNS non-signée et produit un fichier de zone augmenté d'enregistrements contenant les signatures. C'est le fichier signé qui est ensuite chargé dans le serveur de noms.

dnssec-signzone dispose d'une option, -N, pour contrôler le numéro de séquence du SOA de la zone. Les valeurs possibles sont "keep" pour conserver le SOA sans modification, "unixtime" pour remplacer le n° de séquence par le temps unix, et "increment" pour incrémenter le numéro de série de la zone.

En effet, lorsqu'on active la signature d'une zone, il est nécessaire de pousser la nouvelle version de la zone, contenant les signatures, et donc d'incrémenter le n° de série.

Ayant auparavant utilisé le format classique de n° de série (année-mois-jour + deux chiffres de série), le timestamp unix ne me convenait pas, j'ai donc utilisé le mode "increment".

Les signatures étant limitées dans le temps, j'ai mis un cron pour resigner périodiquement ma zone.

Lo and Behold, dnssec-signzone en mode incrément, ne contrôle pas le numéro de séquence de l'ancienne zone signée, seulement celle de la zone source. Et comme j'ai deux fichiers séparés, seule la première signature après une mise a jour de la zone disposait d'une signature fraîche. Une fois le premier round de signatures expirées, les suivantes n'étaient jamais envoyées vers les serveurs esclaves, causant des problèmes aléatoires de signatures invalides. DUH.

Moralité: utiliser le mode Unix Timestamp, ou incrémenter le n° de séquence a la main.