{"id":208,"date":"2013-11-28T01:54:41","date_gmt":"2013-11-27T23:54:41","guid":{"rendered":"http:\/\/calypt.com\/blog\/?p=208"},"modified":"2013-11-28T01:54:41","modified_gmt":"2013-11-27T23:54:41","slug":"grehack-2013-write-crypto-500-wiener","status":"publish","type":"post","link":"https:\/\/www.calypt.com\/blog\/index.php\/grehack-2013-write-crypto-500-wiener\/","title":{"rendered":"GreHack 2013 – Write-up CRYPTO 500 Wiener"},"content":{"rendered":"

\"Grehack\"\"wiener\"<\/h1>\n

 <\/p>\n

Dans ce write-up du challenge Crypto 500 – Wiener de GreHack, nous utilisons Sage<\/a> et OpenSSL<\/a>. Il est possible d’utiliser ses propres outils comme Pari\/GP<\/a> mais si vous n’avez pas d’outils de pr\u00e9dilection et \/ ou que RSA ne vous est pas familier, nous vous conseillons de lire l’article pr\u00e9c\u00e9dent<\/a> afin de comprendre la d\u00e9marche et l’utilisation des outils.<\/p>\n

<\/h1>\n

 <\/p>\n

Fichiers fournis par GreHack<\/h1>\n

Clef publique : Michael-Wiener.pub<\/a><\/p>\n

Fichier chiffr\u00e9 : flag.enc<\/a><\/p>\n

On a donc, a priori, un fichier chiffr\u00e9 avec un chiffrement asym\u00e9trique (RSA ?!). L’indice nous donne le nom du cryptanalyste Michael J. Wiener, dont une rapide recherche Google nous am\u00e8ne sur la page Wikipedia Wiener’s attack<\/a>. Cela confirme nos soup\u00e7ons sur RSA et il ne nous reste plus qu’a extraire les param\u00e8tres RSA, puis d’impl\u00e9menter en Sage<\/a> l’attaque de Wiener !<\/p>\n

 <\/p>\n

 <\/p>\n

Extraction des param\u00e8tres et attaque de Wiener<\/h1>\n
$><\/strong> openssl asn1parse -in Michael-Wiener.pub\u00a0 -i -strparse 19\u00a0\u00a0 \/\/obtention de n et e<\/span><\/span><\/pre>\n
    0:d=0  hl=4 l=1034 cons: SEQUENCE          \r\n    4:d=1  hl=4 l= 513 prim:  INTEGER           :0331702C5FE01F2401C9E44EC0BA79E4<\/span>[...]\r\n  521:d=1  hl=4 l= 513 prim:  INTEGER           :02C398BE3121D210E2F54DBA688A0F16<\/span>[...]<\/pre>\n
 <\/p>\n
$><\/strong> sage<\/p>\n
sage: n = 0x0331702C5FE01F2401C9E44EC0BA79E4<\/span>[...]\u00a0 \/\/ copi\u00e9 \/ coll\u00e9 depuis openssl\r\n<\/span><\/pre>\n
sage: e = 0x02C398BE3121D210E2F54DBA688A0F16<\/span>[...]\u00a0 \/\/ idem<\/span><\/pre>\n
sage: c_fracs = continued_fraction(e\/n).convergents()\u00a0 \/\/ calcul des fractions continues comme ici<\/a><\/span><\/pre>\n
sage: test_message = 42\u00a0 \/\/\u00a0 message qui nous servira \u00e0 v\u00e9rifier que l'on a bien trouv\u00e9 la clef priv\u00e9e<\/span><\/pre>\n
sage: test_message_encryted = pow(test_message,e,n)<\/pre>\n
 <\/p>\n
Gr\u00e2ce \u00e0 Wiener, on sait que la clef priv\u00e9e (d) est pr\u00e9sente parmi les d\u00e9nominateurs des fractions continues (c_fracs). On va donc parcourir l’ensemble des fractions continues et tenter de d\u00e9chiffrer notre test_message avec le d\u00e9nominateur actuel. Si le d\u00e9chiffrement est bon, c’est que l’on a trouv\u00e9 la clef.<\/p>\n
\r\nsage:<\/span> for i in xrange(len(c_fracs)):<\/pre>\n
if pow(test_message_encryted,c_fracs[i].denom(),n) == test_message:<\/pre>\n
d = c_fracs[i].denom()<\/pre>\n
break<\/pre>\n
sage:<\/span> file_flag = open(\"flag.enc\", 'r').read()\u00a0 \/\/ on lit le fichier chiffr\u00e9 contenant le flag<\/span><\/pre>\n
sage:<\/span> flag_encrypted = text2Int(file_flag)\u00a0 \/\/ binaire -> entier (voir Crypto 300 2.3.1<\/a>)<\/span><\/pre>\n
sage:<\/span> flag = pow(flag_encrypted,d,n) \/\/ d\u00e9chiffrement <\/span><\/pre>\n
sage:<\/span> int2Text(int(flag),45)\u00a0 \/\/ flag !<\/span><\/pre>\n","protected":false},"excerpt":{"rendered":"
  Dans ce write-up du challenge Crypto 500 – Wiener de GreHack, nous utilisons Sage et OpenSSL. Il est possible d’utiliser ses propres outils comme Pari\/GP mais si vous n’avez pas d’outils de pr\u00e9dilection et \/ ou que RSA ne vous est pas familier, nous vous conseillons de lire l’article pr\u00e9c\u00e9dent afin de comprendre la […]<\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_mi_skip_tracking":false},"categories":[17,23,41,40,39],"tags":[48,42,46,47,49],"yoast_head":"\n\n\n\n\n\n\n\n\n\n\n\n\t\n