{"id":151,"date":"2013-11-23T18:10:58","date_gmt":"2013-11-23T16:10:58","guid":{"rendered":"http:\/\/calypt.com\/blog\/?p=151"},"modified":"2013-11-28T00:33:32","modified_gmt":"2013-11-27T22:33:32","slug":"grehack-write-crypto-300","status":"publish","type":"post","link":"https:\/\/www.calypt.com\/blog\/index.php\/grehack-write-crypto-300\/","title":{"rendered":"GreHack 2013 – Write-up CRYPTO 300 Microsoft PKI"},"content":{"rendered":"

\"Grehack\"<\/p>\n

 <\/p>\n

Plus qu’un pur Write-Up, ce post est un \u00ab RSA CTF 101 \u00bb. En effet il nous servira de r\u00e9f\u00e9rence pour tous les prochains Write-Up de crypto contenant du RSA. Ce challenge est un excellent exemple pour un CTF, id\u00e9al pour une premi\u00e8re fois… mais les habitu\u00e9s se passeront s\u00fbrement de la lecture du chapitre 2.0 – Rappels sur RSA<\/em>. Merci \u00e0 GreHack<\/a> et SecurImag<\/a> pour leurs chall de qualit\u00e9 !<\/p>\n

<\/h1>\n

 <\/p>\n

1 – Reconnaissance<\/h1>\n

1.1 – Fichiers fournis par Grehack<\/h3>\n

Dans cette \u00e9preuve on a 3 fichiers :<\/p>\n

– clef publique de Bill Gates (bill-gates.pub<\/a>);<\/p>\n

– clef publique de Steve Ballmer (steeve-ballmer.pub<\/a>);<\/p>\n

– secret chiffr\u00e9 (secret.enc<\/a>).<\/p>\n

 <\/p>\n

1.2 – Indice et id\u00e9e de r\u00e9solution<\/h3>\n

Le texte descriptif du Readme nous indique que le secret est un mail de Ballmer, destin\u00e9 \u00e0 Gates<\/strong>. On a donc un syst\u00e8me de cryptographie asym\u00e9trique,<\/a> avec le secret chiffr\u00e9 par la clef publique de Gates. On va chercher \u00e0 r\u00e9cup\u00e9rer la clef priv\u00e9e de Gates<\/strong> afin de pouvoir d\u00e9chiffrer le secret et obtenir le flag de l’\u00e9preuve… et marquer 300 points pour GreHack !<\/p>\n

 <\/p>\n

 <\/p>\n

2 – Here we go, bitches<\/span><\/h1>\n

L’algo le plus courant de crypto asym\u00e9trique est RSA<\/a>. La m\u00e9thode la plus courante pour retrouver une clef priv\u00e9e RSA \u00e0 partir de la clef publique est la factorisation de n<\/strong> … un rappel s’impose.<\/p>\n

<\/h3>\n

2.0 – Rappels sur RSA<\/h3>\n

Comme quasiment tout le temps en crypto, je vais utiliser l\u2019excellent SAGE<\/a> (tr\u00e8s bon livre en pdf ici<\/a>). SAGE est une surcouche \u00e0 python permettant de faire du calcul math\u00e9matique. Toutes les commandes de ce post sont interpr\u00e9tables en Sage. Il existe bien sur d’autres solutions comme PARI\/gp<\/a>, ou bien des solutions commerciales comme Maple<\/a> ou Magma<\/a>.<\/p>\n

Clef publique : (n,e)<\/h4>\n

1 – Pour g\u00e9n\u00e9rer une clef publique RSA, on choisit 2 nombres premiers p<\/strong> et q<\/strong> et on calcule n<\/strong> tel que n = p*q<\/strong><\/p>\n

sage: p = random_prime(2^512)<\/em><\/p>\n

sage: <\/em>q = random_prime(2^512)<\/em><\/p>\n

sage: <\/em>n = p*q<\/em><\/p>\n

2 – e<\/strong> est choisi <\/strong> tel que (p-1)*(q-1) et e soient premiers entre eux<\/strong>. En pratique on choisit souvent e = 65537<\/p>\n

sage: <\/em>e = 65537<\/em><\/p>\n

Clef priv\u00e9e : d<\/h4>\n

La clef priv\u00e9e d <\/strong>est l’inverse de e<\/strong> modulo (p-1)*(q-1)<\/strong><\/p>\n

sage: <\/em>d = inverse_mod(e,(p-1)*(q-1))<\/em><\/p>\n

Chiffrement<\/h4>\n

On \u00e9l\u00e8ve le message \u00e0 chiffrer puissance e modulo n <\/strong>(en utilisant donc la clef publique (n,e)).<\/p>\n

sage: <\/em>message = 42<\/em><\/p>\n

sage: <\/em>chiffre = pow(message,e,n)<\/em><\/p>\n

D\u00e9chiffrement<\/h4>\n

On \u00e9leve le texte chiffr\u00e9 puissance d modulo n<\/strong> (clef priv\u00e9e d)<\/p>\n

sage: <\/em>message = pow(chiffre,d,n)<\/em><\/p>\n

Factorisation<\/h4>\n

Si n est petit, on peut retrouver p et q \u00e0 partir de n<\/strong>, et donc d, la clef priv\u00e9e (cf chiffrement).<\/p>\n

sage: <\/em>p,q=factor(n)<\/em><\/p>\n

<\/h3>\n

 <\/p>\n

2.1 – Clef publique de Bill Gates<\/h3>\n

Contenu de bill-gates.pub<\/strong><\/a> :<\/p>\n

-----BEGIN PUBLIC KEY-----\r\nMIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEB2CW7Y+cYYCBDFkNgqsDY\r\nYjZsapoerdCtdqHNL06htNhOARu22sU7rHcjiIK0sS0aeYjJN+gasQRwXTWUtERX\r\nTbvYQX\/Gq20DeHpVwMwh4Filo8WXglIqD2bMDmfz8ck4hEaCtWQERlA21XYuk1\/l\r\nCOQEHoN3hwIzaZuMLeY6qlYFl0\/Fx9BVDd3hYb+2RSFUJFrEL3I3p8BMFY6l14AN\r\n8E+yo9o\/CvYdB+HaWkUhL5ZCyQYpKc5b2R0MZzoHo0rUhGYm6HpT3OoYPih+Aswc\r\nX1WFVR9gTXIesiToYp5I2Q3vKOHfyVNmeUe5+EwdM3JG5MyClI5Oh2peJgqlPd9S\r\nhBvZTITWy3vUq0l6etStsVaiQEEQJIycQ5RYOWY8Fg\/0RzAwSNP1wj0fvvjpx+p\/\r\nuSgzc6d1mbduRbThJ7c+6wmOZIdZA9BzOeSWFH3DOKLxFRC6RanSgTyhqU1HfYAD\r\nvHA8d5vWYVwdc+rvd1IFQ2ydTg+AT9Pn1v4E5eZk\/UKcMHIWJopqbd2mwt1fLJYL\r\naSwMr3+rBGAtSumh7luYagtr3LXKsR+21A3eRv0LKk6eUtRMaHrkbWmiOvTiXd8r\r\nZMq\/i7vENvVk\/p9Sn5mMEUUp7evxL0t8P7SnEMGMe1M1EPaKKROqgMsa\/abEJ6sM\r\nNzOVAFVK62LymOaFO\/V0Ec8CAwEAAQ==\r\n-----END PUBLIC KEY-----<\/pre>\n
 <\/p>\n
La clef publique semble avoir une forme classique, on peut essayer de la d\u00e9coder avec un d\u00e9codeur ASN.1<\/a> :<\/p>\n
$> openssl asn1parse -in bill-gates.pub \/\/<\/span>\u00a0 les brebis \u00e9gar\u00e9es ne poss\u00e9dant pas openssl peuvent utiliser ce service en ligne : ASN1Decoder<\/a><\/span>
\n<\/em><\/p>\n
0:d=0\u00a0 hl=4 l= 546 cons: SEQUENCE\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \r\n4:d=1\u00a0 hl=2 l=\u00a0 13 cons: SEQUENCE\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \r\n6:d=2\u00a0 hl=2 l=\u00a0\u00a0 9 prim: OBJECT\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 :rsaEncryption\r\n17:d=2\u00a0 hl=2 l=\u00a0\u00a0 0 prim: NULL\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \r\n19:d=1\u00a0 hl=4 l= 527 prim: BIT STRING<\/pre>\n
 <\/p>\n
Le chiffrement RSA est donc confirm\u00e9 et on peut extraire la clef publique \u00e0 l’offset 19 dans le BIT STRING :<\/p>\n
$> openssl asn1parse -in bill-gates.pub -i -strparse 19<\/em><\/p>\n
 0:d=0\u00a0 hl=4 l= 522 cons: SEQUENCE\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \r\n4:d=1\u00a0 hl=4 l= 513 prim:\u00a0 INTEGER :01D825BB63E718602043164360AAC0D862366C6A9A1EADD0AD76A1CD2F4EA1B4D84E011BB6<\/span>[...]\r\n\u00a0521:d=1\u00a0 hl=2 l=\u00a0\u00a0 3 prim:\u00a0 INTEGER\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 :010001<\/pre>\n
 <\/p>\n
A\u00efe. On retrouve bien e<\/strong> = 0x010001 = 65537 mais n<\/strong> parait beaucoup trop grand pour \u00eatre factoris\u00e9 sans l’aide de la NSA.<\/p>\n
<\/h3>\n
 <\/p>\n
2.2 PGCD<\/h3>\n
On remarque que l’\u00e9preuve nous fournit aussi la clef publique de Ballmer (steeve-ballmer.pub<\/a>), a priori inutile, mais dont on peut se servir pour obtenir des informations. Bill Gates et Steve Ballmer \u00e9tant \u00ab q et chemise \u00bb il ne serait pas \u00e9tonnant qu’ils partagent jusqu’\u00e0 une partie de leur clef priv\u00e9e. Pour le v\u00e9rifier, calculer le PGCD<\/a> entre les 2 clefs publiques est une bonne solution. On r\u00e9cup\u00e8re la clef publique (n) de Ballmer avec openssl asn1pare,<\/em> et on calcul le PGCD avec SAGE :<\/p>\n
sage: <\/em>nBill = 0x01D825BB63E718602043164360AA<\/span>[…] \u00a0 \u00a0 \/\/copi\u00e9e coll\u00e9e depuis la sortie d’openssl asn1parse
\n<\/span><\/p>\n
sage: <\/em>nSteve = 0x02703BC6C9BE0489B3A[…]\u00a0\u00a0\u00a0 \/\/idem pour steeve-ballmer.pub
\n<\/span><\/p>\n
sage: <\/em>q = gcd(nBill,nSteve)\u00a0\u00a0\u00a0 \/\/si gcd() renvoi un nombre, c’est que nBill et nSteve partagent un facteur<\/span><\/p>\n
<\/h3>\n
 <\/p>\n
2.3 R\u00e9solution de l’\u00e9preuve Crypto 300 Microsoft PKI – Grehack<\/h3>\n
2.3.1 Fonctions n\u00e9cessaires \u00e0 la r\u00e9solution (r\u00e9cup\u00e9r\u00e9es ici<\/a><\/span>)<\/h4>\n
[pastacode provider=”manual” lang=”python”]<\/p>\n
def text2Int(text):\r\n    \"\"\"Convert a text string into an integer\"\"\"\r\n    return reduce(lambda x, y : (x << 8) + y, map(ord, text))\r\n\r\ndef int2Text(number, size):\r\n    \"\"\"Convert an integer into a text string\"\"\"\r\n    text = \"\".join([chr((number >> j) & 0xff) for j in reversed(range(0, size << 3, 8))])\r\n    return text.lstrip(\"\\x00\")<\/code><\/pre>\n
[\/pastacode]<\/p>\n
2.3.2 R\u00e9solution<\/h4>\n
sage: <\/em>pBill = nBill\/q    \/\/ n=p*q => p=n\/q<\/span><\/pre>\n
sage: <\/em>e = 0x010001    \/\/ e = 65537 <\/span><\/pre>\n
sage: <\/em>d = inverse_mod(e,(pBill-1)*(q-1))    \/\/ on calcule la clef priv\u00e9e de Bill<\/span><\/pre>\n
sage: <\/em>file = open(\"secret.enc\",'r',)<\/pre>\n
sage: <\/em>cipher = file.read()    \/\/ on met le fichier dans le buffer cipher<\/span><\/pre>\n
sage: <\/em>cipher_i  = text2Int(cipher)    \/\/ on transforme le binaire en INT pour pouvoir faire des op\u00e9rations dessus<\/span><\/pre>\n
sage: <\/em>clair_i = pow(cipher_i,d,nBill)    \/\/ d\u00e9chiffrement du message avec la clef priv\u00e9e d<\/span><\/pre>\n
sage: <\/em>int2Text(int(clair_i),38)    \/\/ obtention du FLAG !<\/span><\/pre>\n
 <\/p>\n
\u00c0 bient\u00f4t pour le Crypto 500 \ud83d\ude09<\/p>\n","protected":false},"excerpt":{"rendered":"
  Plus qu’un pur Write-Up, ce post est un \u00ab RSA CTF 101 \u00bb. En effet il nous servira de r\u00e9f\u00e9rence pour tous les prochains Write-Up de crypto contenant du RSA. Ce challenge est un excellent exemple pour un CTF, id\u00e9al pour une premi\u00e8re fois… mais les habitu\u00e9s se passeront s\u00fbrement de la lecture du […]<\/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":[50,48,42,46,47],"yoast_head":"\n\n\n\n\n\n\n\n\n\n\n\n\n\t\n