mardi 14 octobre 2014

CTF Writeup: ASIS CTF 2014: Crypto 400 - Paillier

En donnée, on nous fournit l'addresse du service suivant:

max@truite ~ $ nc -v asis-ctf.ir 12445
DNS fwd/rev mismatch: asis-ctf.ir != mail.depository.ir
asis-ctf.ir [87.107.124.12] 12455 (?) open

        Here we use a well-known cryptosystem, which introduced in late 90s as a part of PhD 
        Thesis. This cryptosystem is a probabilistic asymmetric algorithm, so computer nerds 
        are familiar with the basics. The power of this cryptosystem is based on the fact that 
        no efficient general method for computing discrete logarithms on conventional computers 
        is known. In real world it could be used in a situation where there is a need for 
        anonymity and a mechanism to validate, like election.

    What's the name of this cryptosystem? 

Après quelques essais, on trouve Paillier:

    What's the name of this cryptosystem? 
Paillier 
The secret is: 9875676257636701658620619485901408458156381957610287297432150752657594971112130734695398259742040350122954870324237948599808827532539278700745263553319482092460456957407527479335203333233299470927024366020632206967357797846981812988215039671606873392079187791573839733015708764105651394898965004633566072121653336961074172004673994159863360102994472700677843818502473936852657203606418773655065969394463059460646887148864238467101809097431545413094791408119903360268021677565512905315679155054822925595572277268025072732035284201497048421809084512809302973116027126313140282915561007559382521979998979794092988861921 

Tell us your choise:
------------------------ 
[E]ncrypt: [D]ecrypt:  

Le nom du système est donc le bon. Nous avons une valeur secrète, un nombre en décimal, et apparemment la possibilité d'utiliser le service comme oracle, sans disposer directement de la clef.

Le service accepte de déchiffrer des valeurs abritraires, mais pas la fameuse valeur secrète:

Tell us your choise: 
------------------------ 
[E]ncrypt: [D]ecrypt: D  
Tell us your secret to decrypt: 98756 
Your original message is: 950874...........209298 
[E]ncrypt: [D]ecrypt: D
Tell us your secret to decrypt: 987567..........861921
Don't fool me! X-(

(J'ai raccourci les grands nombres par souci de lisibilité, mais le service donne les nombres complets)

La caractéristique distinctive du cryptosystème de Paillier réside dans ses propriétés homomorphiques. Si, par exemple, on à 3 messages clairs m, m1 et m2 tels que

m = m1 + m2 (mod n)

il est possible de calculer un texte chiffré c correspondant au message m, sans connaitre m1 et m2, en prenant

c = c1 c2 (mod n²)

Ici, notre objectif va donc être de retrouver le message m de notre secret, sans procéder à son déchiffrement. Pour ceci, nous allons d'abord trouver un c1 et un c2 acceptables, puis les déchiffrer, et il ne nous restera plus qu'a les additionner (mod n) pour retrouver le message original.

En supposant que le message m a été choisi arbitrairement, sans rechercher une valeur particulière de c, c est uniformément distribué dans le groupe multiplicatif M(n²), il est donc hautement probable qu'il contienne des petits facteurs. Essayons de trouver un petit facteur, avec haskell, par une technique tout à fait rudimentaire:

Prelude> let c = 98756762576...92988861921
Prelude> head [ k | k <- [2..], c `mod` k == 0 ]
11

On identifie presque immédiatement le petit facteur 11, et on calcule son cofacteur par division:

Prelude> c `div` c1
8977887.........362623811

On soumet alors les deux valeurs c1 et c2 à notre oracle: Tell us your choise: ------------------------ [E]ncrypt: [D]ecrypt: d Tell us your secret to decrypt: 11 Your original message is: 151709608361226950608367113680465803878157243458154889691251326923018155715697619180502339981181175975825978824071269220455262079491432880547349570206488156562505637347940621075801863098020222566004446665582027684319850545795810085447457566869848890807713892527339364953877439451805024781681882111584734863530 Tell us your choise: ------------------------ [E]ncrypt: [D]ecrypt: d Tell us your secret to decrypt: 89778875....23811 Your original message is: 6242769198942584817411105473450672386047972883716325422178669503309780681241088351102877529576142539995828596461517120317457326548163994292246457822325179469736425807552956065728181142742368861833271780719984831097410099764709060287670942937998909474785496814133308188930429303413286386679766196777006675616

On repasse ces messages dans Haskell:

Prelude> let m1 = 15170....863530
Prelude> let m2 = 62427....675616

Problème: nous savons maintenant que m = m1 + m2 (mod n), mais nous ne connaissons pas n. Comment le trouver ? En exploitant la propriété homorphique pour créer des valeurs équivalentes mod n, et en regardant leur hypothétique différence.

Par exemple, si on génère au hasard un texte chiffré ca, et qu'on soumet à l'oracle ca, puis ca², on obtiendra en retour deux valeurs ma et m2a telles que m2a = 2 ma (mod n); si on calcule x = m2a - 2 ma, x sera un multiple de n.

On peut faire le test avec quelques paires de valeurs simples: 2 et 4, 3 et 9, 5 et 25... coup de chance, le premier essai nous révèle immédiatement la valeur

157952377560169535425778219153916476264205216341871215113429996426327936396938707531605217510757318515821807420532786340772719406039596874839596028028813336032242063155493577141530044240762591427837718446302012515417260613072710825491978074491263004126928295563734080003249704892308810330085722662911791521557

Dont la taille est relativement proche du n recherché. On vérifie si cela est suffisant pour déchiffrer:

Prelude> let n = 157952...521557
Prelude> let m = (m1 + m2) `mod` n
Prelude> m
32487808320243150435316584796155571093777738593139558163862909500838275925645449950017589

Cette valeur est beaucoup plus petite que n, il est donc hautement probable qu'il s'agisse du bon message, sans padding. Mais comment l'interpréter ?

Prelude> import Numeric
Prelude Numeric> showHex m []
"415349535f3835633966656264346331353935306162316631396136626437613934663835"

Voila qui ressemble fortement à du décimal, affichons le en ascii:

Prelude Numeric> import qualified Data.ByteString as BS
Prelude Numeric BS> BS.reverse $ BS.unfoldr (\x -> if x == 0 then Nothing else Just (fromIntegral (x `mod` 256), x `div` 256)) m 
"ASIS_85c9febd4c15950ab1f19a6bd7a94f85"

samedi 11 octobre 2014

CTF Writeup: TinyCTF 2014: Crypto 200

CTF Writeup: TinyCTF 2014: Crypto 200

Analyse

Pour ce problème, on nous donne les deux fichiers suivants:

BJQOmVgJuDRqciWk748XXvMDHTP5dbU5jK4R4KzLkZXE41EnS7nbrB0bmBmuZ56NMARX8+X48xFQ
ZI+Dk8v1A+QLERQLiopR0ivFvHT9v9oOjavMZwTRKKop/kgFOIAb1N5CLm8aIh5HH3XYVaSQMyie
H1jg216NKi2rRzkSsbNe0FUokMi3MkYmbCftuQsVCaLV0gkjbiMFDEWs+BLfmLG+OovN/5iRx3Pa
oXty2z/VnNK2XuED7Hsk4TWOvhTMuGgxphffEGdN2EKTnd1FXnQdT8jxQhkXt4LRZgZRpTlpKKlG
Ybzfnw0vlW/GyiOEeO9EcB7vs7DlYQ3VVi/OZr4RsbXZ/8pjalIDfXzmzUTqgQuoTEnAKuKb0t4/
+gOujwWz5jPw8RxRNSjxQExmIXudVgXm8IacJb8CS5PONa7yqxbQ8U80yFDsHRPHPka9WGhpA79j
dAFCV5CV19KT+L01q/ZTcp7NDoSVSnOgfYUEygPTqkSmsI13bs+JScW3HVLiAA69ZhCj4Y9/c55J
WOBw7JuclJPJkNY3hQ0qrXUvtghZ9nanb8Hz4pVqvt0r2460n4isC5rgHTyEgYdTaAPHqZ5h6eTZ
4QrWCVLpOHtCQsJNBvP9skf0yLhUJbSajbanFhRKDmInPLcicJ+W+cJU6unV/JsaCrrjCvnaSa92
VXKQglHpm+rxYFpABDt86M+91JzbwzwCFtlmFlpfBFmds9zCQEE5JJvmyueLV5QpNFGmkCwYt3GX
WUdbMbl25AyNV5+EICgIg29d3wTUoe3yJVXHYS3xlz5Fs0MEXQK1qQp2DOu2nvhi/+LAI+4+5fOW
jAcSDpuNA2/ezK7Z8bfOZ49Ew+UHv1AVdRB4+ZDv4kj+94fzRXATRnkgfVmcqy1YUkJlFn068iCD
JaZx+aDO2UuQISHqpu6YLUwjtUP4Y1gCkaqxNP6oLJpxHRLSvBnvoWjAW+BwJYRCxG2pWrbx2/W+
+EX6SFJOvNox1eGcy2mDW9UIEu8BF/8z9DGQcvlDWctp65URM6+y1y4nc6VIDQSWk4kVPYMb5gB5
FcVx+IF9bVbtbtXf2l2FXk3asy7P2rwrXSI1cS0TImCTvaxsfCg0Fc3eVZtjjUKhnKl6hCwBv4i9
w+xV9x3M5bDa0lJwBGAa4rScXBoT7Pt+cXCTg4K3dyTCCK7Y18sfsjooWWweQ7ZNRjNsENrhgUb6
9NXrjELBZ0EJA9dvgP3eR5vv+1age7nO96VZV5tjfWJbeD50xJXElbFiqYNAwRzNw/1qEn8WN1f5
TL/8RUK5E+mTJY/9+F97BL5jcSbcGVp6aRDZQsyHAhShmKXphKRKksCCd4ZRUoC/c3m+ve/lecfl
qaaRFvYDkR0BAQ0cqTiCyP5Hkb9YCmBzFETrCfH1D8oN37nZkxCp7WmVUesXwWQz

et

-----BEGIN PUBLIC KEY-----
MIIEUzANBgkqhkiG9w0BAQEFAAOCBEAAMIIEOwKCBDIGLT1hySRSYwFH6JZw////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
//8CAwEAAQ==
-----END PUBLIC KEY-----

On remarque immédiatement la structure étrange de la clef. Affichons là avec openssl:

openssl rsa -pubin -noout -text <crypto200.pub
Public-Key: (8587 bit)
Modulus:
    06:2d:3d:61:c9:24:52:63:01:47:e8:96:70:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
...
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff
Exponent: 65537 (0x10001)

La clef est très grande, mais remplie de bits 1. Le deuxième fichier, une fois décodé, fait 1074 bytes, soit 8592 bits; tout juste assez pour contenir un nombrebrut de la même taille de la clef.

Casser la clef

La clef publique exhibe une forme particulière. Pouvons nous l'exploiter ?

La clef fait 8587 bits, le préfixe du module (06:2d:3d:61:c9:24:52:63:01:47:e8:96:70) fait exactement 99 bits, il reste donc 8488 bits à 1, soit 1061 bytes.

Si on additionne 1 à cette valeur, on obtient le préfixe + 1, suivi d'une longe suite de zéros. On peut donc écrire:

n = 2^8488*x - 1

Ou x vaut 06:2d:3d:61:c9:24:52:63:01:47:e8:96:71.

Se pourrait-il que x soit un carré parfait ? si c'est le cas, on pose x = y^2, et on déduit immédiatement une factorisation de n en appliquant l'identité remarquable

(a-b)(a+b) = (a^2-b^2)

Qui nous donne

n = (2^4244*y - 1)(2^4244*y + 1).

x est de taille tout juste suffisante pour que y tienne dans un flottant à double précision. Essayons donc une racine carrée sur des flottants:

max@truite ~ $ ghci
Prelude> sqrt 0x062d3d61c92452630147e89671
6.99549860111847e14

Probablement suffisamment bon:

Prelude Numeric> let y = 699549860111847
Prelude Numeric> showHex y*y []
"62d3d61c92452630147e89671"

x est donc bien un carré parfait, et l'approximation du double n'a pas causé de problème, parfait. On obtient donc p et q:

Prelude Numeric> let p = 2^4244*y - 1
Prelude Numeric> let q = 2^4244*y + 1
Prelude Numeric> p
260687538913047604611581784183499992008451760653
...
6814857060351
Prelude Numeric> q
260687538913047604611581784183499992008451760653
...
6814857060353

Récupérer le flag

Puisque le message est au format brut, faisons les opérations nécessaires à la main avec haskell:

Prelude Numeric> let phi = (p-1)*(q-1)
Prelude Numeric> import EGCD
Prelude Numeric EGCD> let d = modInv 65537 phi
Just 619821027857093873....
....
385645407120058494507347279873

On charge le fichier et on décode la valeur en little-endian:

> import qualified Data.ByteString as B
> bytes <- B.readFile "ciphertext"
> let c = B.foldl' (\x y -> x*256 + fromIntegral y) 0 bytes

On calcule la version déchiffrée:

> let square x = x*x
> let modexp a e n = if e == 0 then 1 else if odd e then (a * modexp a (e-1) n) `mod` n else (square (modexp a (e `div` 2) n)) `mod` n
> let m = modexp c d n
> m
65151540921271072284844432466479370480767208216346753189456545359642913474452048348256443821114706423834256667231412670290529080763567179189546344566636337924315868233088893

Une valeur très petite par rapport à n, il est donc certain que ce déchiffrement est correct. Reste à l'interpréter correctement. On l'écrit simplement sous forme de bytes, little endian (c'est plus facile):

>  B.unfoldr (\x -> if x == 0 then Nothing else Just (fromIntegral (x `mod` 256), x `div` 256)) m
"}?n0_siht_nru7_uoy_0d_woh{galf :uoy rof taert a si ereH !snoitalutargnoC"

Bon, c'était du big endian:

> B.reverse $ B.unfoldr (\x -> if x == 0 then Nothing else Just (fromIntegral (x `mod` 256), x `div` 256)) m
"Congratulations! Here is a treat for you: flag{how_d0_you_7urn_this_0n?}"