{"id":2746,"date":"2016-09-08T23:52:45","date_gmt":"2016-09-08T21:52:45","guid":{"rendered":"https:\/\/0x90r00t.com\/fr\/?p=2746"},"modified":"2016-09-08T23:52:45","modified_gmt":"2016-09-08T21:52:45","slug":"mma-ctf-2016-crypto-180-esper-write-up","status":"publish","type":"post","link":"https:\/\/0x90r00t.com\/fr\/2016\/09\/08\/mma-ctf-2016-crypto-180-esper-write-up\/","title":{"rendered":"[MMA CTF 2016] [Crypto 180 – ESPer] Write Up"},"content":{"rendered":"

Description<\/h2>\n

\nnc cry1.chal.ctf.westerns.tokyo 37992<\/p>\n


\n============================= About ===============================
\nYou are very good ESPer, so that you can change any local variable
\nvalue to 2048 bit random integer.<\/p>\n

You should specify the ESP string as the line number and variables'
\nname to change separated by colon.<\/p>\n

For example, if the source code is below and your input is \"2:x\",
\nthe line 2 works the same as \"x = rand(2 ** 2048); puts x\". So the
\noutput is random number.
\n+---+-------------------------------------------------------------------------+
\n| 1| x = 3 |
\n| 2| puts x |
\n+---+-------------------------------------------------------------------------+
\nEncryption Source code is here.
\n+---+-------------------------------------------------------------------------+
\n| 1| n, e = read_publickey(ARGV[0]) |
\n| 2| print \"Message m: \" |
\n| 3| STDOUT.flush |
\n| 4| m = STDIN.gets.to_i |
\n| 5| c = encrypt(m, e, n) |
\n| 6| puts \"Encrypted: #{c}\" |
\n| 7| STDOUT.flush |
\n+---+-------------------------------------------------------------------------+<\/p>\n

Decryption Source code is here
\n+---+-------------------------------------------------------------------------+
\n| 1| p, q, dp, dq, qinvp = read_privkey(ARGV[0]) |
\n| 2| print \"Encrypted Message c: \" |
\n| 3| STDOUT.flush |
\n| 4| c = STDIN.gets.to_i |
\n| 5| m1 = decrypt(c, dp, p) |
\n| 6| m2 = decrypt(c, dq, q) |
\n| 7| m = merge(m1, m2, p, q, qinvp) |
\n| 8| puts \"Decrypted: #{m}\" |
\n| 9| STDOUT.flush |
\n+---+-------------------------------------------------------------------------+
\n<\/code><\/p>\n<\/blockquote>\n

<\/p>\n

Resolution<\/h2>\n

Apr\u00e8s un d\u00e9fi SHA classique pour emp\u00eacher le bruteforce du challenge (la r\u00e9solution du probl\u00e8me se fait en 5\/6 secondes), le programme g\u00e9n\u00e8re une cl\u00e9 priv\u00e9e suffisamment forte qui change donc \u00e0 chaque fois. Ensuite on a 4 envois possibles avant que le programme nous retourne le flag (avec un padding al\u00e9atoire) chiffr\u00e9 avec la cl\u00e9 priv\u00e9e g\u00e9n\u00e9r\u00e9e (il faut donc \u00e0 ce moment l\u00e0 disposer de la cl\u00e9 priv\u00e9e pour \u00eatre capable de l’obtenir).
\nA chaque envoi, on peut demander au programme soit de chiffrer un message, soit de d\u00e9chiffrer un message. Avec une possibilit\u00e9 comme indiqu\u00e9e dans l’\u00e9nonc\u00e9 de rendre une variable al\u00e9atoire parmi toutes les variables utilis\u00e9es.
\nA premi\u00e8re vue, on se demande en quoi cela va pouvoir nous \u00eatre utile. Mais regardons de plus pr\u00e8s les \u00e9quations de chiffrement\/d\u00e9chiffrement :<\/p>\n

\r\nc = m^e [N]\r\n<\/pre>\n
donc c – m^e est un multiple de N.
\nOr on peut demander au programme de chiffrer ce qu’on veut, par exemple 2 et 3, qui sont des nombres suffisamment petits pour que leur puissance e = 65537 (e ne varie pas \u00e0 chaque lancement du programme), soit repr\u00e9sentable avec assez peu de chiffres (de l’ordre d’une dizaine de milliers).
\nEn demandant le chiffrement de 2 et 3, on obtient donc c1 – 2^65537 et c2 – 3^65537 qui sont des multiples de N. Avec un peu de chance, on a donc :<\/p>\n
\r\npgcd(c1 - 2^65537, c2 - 3^65537) = N\r\n<\/pre>\n
On dispose maintenant de N, \u00e0 partir de deux op\u00e9rations. Si on trouve p ou q, c’est gagn\u00e9 !<\/p>\n
Observons maintenant les \u00e9quations de d\u00e9chiffrement, avec la m\u00e9thode des restes chinois (http:\/\/www.di-mgt.com.au\/crt_rsa.html) :<\/p>\n
\r\ndp = e^-1 [p-1]\r\ndq = e^-1 [q-1]\r\nqinvp = q^-1 [p]\r\nm1 = c^dp [p]\r\nm2 = c^dq [q]\r\nh = qinvp (m1-m2) [p]\r\nm = m2 + hq\r\n<\/pre>\n
On peut voir que si on d\u00e9chiffre un message c une premi\u00e8re fois et qu’on d\u00e9chiffre le m\u00eame message avec qinv diff\u00e9rent, on obtient m = m2 + h1*q et m = m2 + h2*q et donc en soustrayant les clairs obtenus :<\/p>\n
\r\n0 = (h1-h2)*q\r\n<\/pre>\n
On obtient donc un multiple de q. Or on sait que N est \u00e9galement un multiple de q, donc si on a bien des qinv diff\u00e9rents, on a de fortes chances d’obtenir :<\/p>\n
\r\npgcd(N, (h1-h2)*q) = q\r\n<\/pre>\n
On a donc 2 op\u00e9rations suppl\u00e9mentaires, la derni\u00e8re en demandant un qinvp al\u00e9atoire. On arrive \u00e0 4 op\u00e9rations, le programme nous renvoie le flag chiffr\u00e9 et quitte. Mais c’est suffisant pour terminer !
\nOn a N et q, donc p, et on peut tout reconstruire pour d\u00e9chiffrer le flag !<\/p>\n
\r\nimport sys\r\nimport socket\r\nimport string\r\nimport re, time\r\nimport base64,binascii,hashlib\r\nfrom pwn import *\r\n# coding:utf-8\r\nfrom Crypto.Util.number import *\r\nimport Crypto.PublicKey.RSA as RSA\r\nimport os,binascii\r\n\r\nHOST = &quot;cry1.chal.ctf.westerns.tokyo&quot;\r\nPORT = 37992\r\n\r\nmyreg=re.compile(r'hashlib.(\\w*)\\(str\\(number\\)\\)\\.hexdigest\\(\\)\\.startswith\\(\\'(\\w*)\\'\\) == true and (\\d*) &lt;= number &lt;= (\\d*)')\r\n\r\n\r\ndef test_connexion(HOST, PORT):\r\n    print &quot;-=-=-= Starting -=-=-=-&quot;\r\n    sh = remote(HOST, PORT)\r\n    datas = sh.recvuntil('\\n')\r\n    print datas\r\n    datas = sh.recvuntil('\\n')\r\n    print datas\r\n    res=myreg.findall(datas)\r\n    print res\r\n    found_value=calculate(algo=res[0][0],startvalue=res[0][1],min=int(res[0][2]),max=int(res[0][3]))\r\n    sh.sendline(str(found_value))\r\n    datas = sh.recvuntil('Your choice&gt;')\r\n    print datas\r\n    ######\r\n    M = &quot;4&quot;*129\r\n    m = message_to_int(M)\r\n    encrypted1 = enc_with_choice(sh, '', message=M)\r\n    encrypted2 = enc_with_choice(sh, '', message=&quot;\\x02&quot;)\r\n    encrypted3 = enc_with_choice(sh, '', message=&quot;\\x03&quot;)\r\n    decrypted1 = m\r\n    decrypted2 = dec_with_choice(sh, '5:qinvp', message=str(encrypted1))\r\n   \r\n    kp1 = (pow(2,65537)-encrypted2)\r\n    kp2 = (pow(3,65537)-encrypted3)\r\n    N = gcd(kp1,kp2)\r\n\r\n    print(N)\r\n\r\n    q = gcd(decrypted1-decrypted2,N)\r\n    if q&lt;0:\r\n        q *= -1\r\n    p = N\/q\r\n\r\n    print(&quot;P=&quot;+str(p))\r\n    print(&quot;Q=&quot;+str(q))\r\n    print(N==p*q)\r\n\r\n    sh.interactive()\r\n\r\n\r\ndef enc_with_choice(sh,my_esp,message):\r\n    sh.sendline('1')\r\n    datas = sh.recvuntil('string:')\r\n    print datas\r\n    sh.sendline(my_esp)\r\n    print '&gt;',my_esp\r\n    datas = sh.recvuntil('m:')\r\n    print datas\r\n    sh.sendline(str(message_to_int(message)))\r\n    print '&gt;',message_to_int(message)\r\n    datas = sh.recvuntil('Encrypted:')\r\n    print datas\r\n    datas = sh.recvuntil('\\n')\r\n    encrypted = int(datas)\r\n    print encrypted\r\n    return encrypted\r\n\r\ndef dec_with_choice(sh,my_esp,message):\r\n    sh.sendline('2')\r\n    datas = sh.recvuntil('string:')\r\n    print datas\r\n    sh.sendline(my_esp)\r\n    datas = sh.recvuntil('c:')\r\n    print datas\r\n    sh.sendline(str(message))\r\n    datas = sh.recvuntil('Decrypted:')\r\n    print datas\r\n    datas = sh.recvuntil('\\n')\r\n    decrypted = int(datas)\r\n    print decrypted\r\n    print &quot;Decrypted message is :&quot;,int_to_message(decrypted)\r\n    return decrypted\r\n\r\ndef message_to_int(message):\r\n    return int(binascii.hexlify(message),16)\r\ndef int_to_message(value):\r\n    return binascii.unhexlify(hex(value)[2:].replace('L',''))\r\n\r\n\r\ndef calculate(algo='sha1',min=0,max=0,startvalue='00000'):\r\n    value = min\r\n    while value &lt; max:\r\n        if algo=='sha1':\r\n            if hashlib.sha1(str(value)).hexdigest().startswith(startvalue):\r\n                print &quot;Found : &quot;,value,' : ',hashlib.sha1(str(value)).hexdigest()\r\n                return value\r\n\r\n        if algo == 'md5':\r\n            if hashlib.md5(str(value)).hexdigest().startswith(startvalue):\r\n                print &quot;Found : &quot;, value, ' : ', hashlib.md5(str(value)).hexdigest()\r\n                return value\r\n\r\n        else :\r\n            value+=1\r\n\r\n\r\nif __name__ == '__main__':\r\n    test_connexion(HOST, PORT)\r\n\r\n\r\nc = 20942956699330319872158409337924190768213456440565922005083726149156131319192722266288327376512373093552743741537930146382601041542929377509300469883924139257384027475699337072356975755181363855026874101098018831259509230510614253551911419783143187866166090002439803837394314492529167063370411308830963711887986514763550997451779965339957895690182830706313809461304944934907671556696483912876601762427437849527918472117274401661397336225404466434179028166762919079103353579947811270492811254517930142583940861572063335290025091077596774000201919743055015057170449334693390974291566063266101608180982168026191439705859\r\np = 152337050375069076443241765930164873212779468869178184814666105307945151519389973978733969613680584364143135979268598609761681856569421887186735180153106187906765810044628863040395244931778690492117035090747931829041031964467601572873479004054439845004053698991546208889514048762758247627755719714630055191923\r\nq = 148841929038545009318690416092183995236183322684180431048606510674672413170977265381738608407239792487225483072439344038384029523766183714339920751585959898774873888725434712835014635204105183878500741908493814854395896721022995104642305763922731222897928475518252168472146918176790825627840600871705120989089\r\n\r\ne = 65537\r\nN = p*q\r\nphi = (p-1)*(q-1)\r\n\r\n\r\ndef egcd(a, b):\r\n   if a == 0:\r\n       return (b, 0, 1)\r\n   else:\r\n       g, y, x = egcd(b % a, a)\r\n       return (g, x - (b \/\/ a) * y, y)\r\n\r\ndef modinv(a, m):\r\n   g, x, y = egcd(a, m)\r\n   if g != 1:\r\n       raise Exception('modular inverse does not exist')\r\n   else:\r\n       return x % m\r\n\r\nd = modinv(e,phi)\r\n\r\nm = pow(c,d,N)\r\n\r\nimport binascii\r\nprint(binascii.unhexlify(hex(m).replace('0x','').replace('L','')))\r\n<\/pre>\n
TWCTF{I_don't_Lik3_ESPer_problems!}<\/code><\/p>\n","protected":false},"excerpt":{"rendered":"
Description nc cry1.chal.ctf.westerns.tokyo 37992 ============================= About =============================== You are very good ESPer, so that you can change any local variable value to 2048 bit random integer. You should specify the ESP string as the line number and variables’ name to change separated by colon. For example, if the source code is below and your input … Continuer la lecture de [MMA CTF 2016] [Crypto 180 – ESPer] Write Up<\/span>  →<\/span><\/a><\/p>\n","protected":false},"author":12,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[138,35,201],"tags":[128,202,203],"class_list":["post-2746","post","type-post","status-publish","format-standard","hentry","category-2016-fr-2","category-ctf-fr","category-mma-2016-fr","tag-2016-fr","tag-crypto-fr","tag-mma-fr"],"_links":{"self":[{"href":"https:\/\/0x90r00t.com\/fr\/wp-json\/wp\/v2\/posts\/2746","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/0x90r00t.com\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/0x90r00t.com\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/0x90r00t.com\/fr\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/0x90r00t.com\/fr\/wp-json\/wp\/v2\/comments?post=2746"}],"version-history":[{"count":2,"href":"https:\/\/0x90r00t.com\/fr\/wp-json\/wp\/v2\/posts\/2746\/revisions"}],"predecessor-version":[{"id":2748,"href":"https:\/\/0x90r00t.com\/fr\/wp-json\/wp\/v2\/posts\/2746\/revisions\/2748"}],"wp:attachment":[{"href":"https:\/\/0x90r00t.com\/fr\/wp-json\/wp\/v2\/media?parent=2746"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/0x90r00t.com\/fr\/wp-json\/wp\/v2\/categories?post=2746"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/0x90r00t.com\/fr\/wp-json\/wp\/v2\/tags?post=2746"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}