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

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?}"

Max's Blog

samedi 11 octobre 2014