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 !!!