{"id":561,"date":"2018-05-21T11:45:51","date_gmt":"2018-05-21T11:45:51","guid":{"rendered":"https:\/\/devel0pment.de\/?p=561"},"modified":"2018-05-22T07:20:21","modified_gmt":"2018-05-22T07:20:21","slug":"rctf-2018-writeup-cpushop","status":"publish","type":"post","link":"https:\/\/devel0pment.de\/?p=561","title":{"rendered":"RCTF 2018 &#8211; writeup cpushop"},"content":{"rendered":"<style>\n  .spanFlag {\n    color:#0000ff;\n    font-weight:bold;\n  }\n<\/style>\n<p>The <a href=\"https:\/\/ctf.teamrois.cn\/\" target=\"_blank\" rel=\"noopener\">RCTF 2018<\/a> (<a href=\"https:\/\/ctftime.org\/event\/624\" target=\"_blank\" rel=\"noopener\">ctftime.org<\/a>) ran from 19\/05\/2018, 09:00 UTC to 21\/05\/2018 08:59 UTC.<\/p>\n<p>I wrote the following writeup for the crypto challenge <i>cpushop<\/i>.<\/p>\n<p><!--more--><\/p>\n<hr \/>\n<h1>cpushop (176 pts)<\/h1>\n<h3>Challenge description<\/h3>\n<p>The challenge provided a python-script (<code>cpushop.py<\/code>) and a hostname\/port of the server running the script (<code>cpushop.2018.teamrois.cn 43000<\/code>).<\/p>\n<p>Let&#8217;s examine the script:<\/p>\n<pre class=\"brush: python; first-line: 0; highlight: [14,15,16,22,32,36,41,49,50,56,59,64,72]; title: ; notranslate\" title=\"\">\r\nroot@kali:~\/Documents\/roisctf\/cpushop# cat cpushop.py\r\n#!\/usr\/bin\/env python\r\n# encoding: utf-8\r\n\r\nimport random\r\nimport string\r\nimport signal\r\nimport sys\r\nimport os\r\nimport time\r\nfrom hashlib import sha256\r\nfrom urlparse import parse_qsl\r\n\r\nos.chdir(os.path.dirname(os.path.abspath(__file__)))\r\nsignkey = ''.join(&#x5B;random.choice(string.letters+string.digits) for _ in xrange(random.randint(8,32))])\r\nitems = &#x5B;('Intel Core i9-7900X', 999), ('Intel Core i7-7820X', 599), ('Intel Core i7-7700K', 349), ('Intel Core i5-7600K', 249), ('Intel Core i3-7350K', 179), ('AMD Ryzen Threadripper 1950X', 999), ('AMD Ryzen 7 1800X', 499), ('AMD Ryzen 5 1600X', 249), ('AMD Ryzen 3 1300X', 149), ('Flag', 99999)]\r\nmoney = random.randint(1000, 10000)\r\n\r\ndef list_items():\r\n    for i,item in enumerate(items):\r\n        print '%2d - %-30s$%d' % (i, item&#x5B;0], item&#x5B;1])\r\n\r\ndef order():\r\n    n = input_int('Product ID: ')\r\n    if n &lt; 0 or n &gt;= len(items):\r\n        print 'Invalid ID!'\r\n        return\r\n    payment = 'product=%s&amp;price=%d&amp;timestamp=%d' % (items&#x5B;n]&#x5B;0], items&#x5B;n]&#x5B;1], time.time()*1000000)\r\n    sign = sha256(signkey+payment).hexdigest()\r\n    payment += '&amp;sign=%s' % sign\r\n    print 'Your order:\\n%s\\n' % payment\r\n\r\ndef pay():\r\n    global money\r\n    print 'Your order:'\r\n    sys.stdout.flush()\r\n    payment = raw_input().strip()\r\n    sp = payment.rfind('&amp;sign=')\r\n    if sp == -1:\r\n        print 'Invalid Order!'\r\n        return\r\n    sign = payment&#x5B;sp+6:]\r\n    try:\r\n        sign = sign.decode('hex')\r\n    except TypeError:\r\n        print 'Invalid Order!'\r\n        return\r\n\r\n    payment = payment&#x5B;:sp]\r\n    signchk = sha256(signkey+payment).digest()\r\n    if signchk != sign:\r\n        print 'Invalid Order!'\r\n        return\r\n\r\n    for k,v in parse_qsl(payment):\r\n        if k == 'product':\r\n            product = v\r\n        elif k == 'price':\r\n            try:\r\n                price = int(v)\r\n            except ValueError:\r\n                print 'Invalid Order!'\r\n                return\r\n\r\n    if money &lt; price:\r\n        print 'Go away you poor bastard!'\r\n        return\r\n\r\n    money -= price\r\n    print 'Your current money: $%d' % money\r\n    print 'You have bought %s' % product\r\n    if product == 'Flag':\r\n        print 'Good job! Here is your flag: %s' % open('flag').read().strip()\r\n\r\ndef input_int(prompt):\r\n    sys.stdout.write(prompt)\r\n    sys.stdout.flush()\r\n    try:\r\n        n = int(raw_input())\r\n        return n\r\n    except:\r\n        return 0\r\n\r\ndef menu():\r\n    print &quot;CPU Shop&quot;\r\n    while True:\r\n        print &quot;Money: $%d&quot; % money\r\n        print &quot;1. List Items&quot;\r\n        print &quot;2. Order&quot;\r\n        print &quot;3. Pay&quot;\r\n        print &quot;4. Exit&quot;\r\n        sys.stdout.flush()\r\n        choice = input_int(&quot;Command: &quot;)\r\n        {\r\n                1: list_items,\r\n                2: order,\r\n                3: pay,\r\n                4: exit,\r\n        }.get(choice, lambda *args:1)()\r\n        sys.stdout.flush()\r\n\r\nif __name__ == &quot;__main__&quot;:\r\n    signal.alarm(60)\r\n    menu()\r\n<\/pre>\n<h3>What does the script do?<\/h3>\n<p>&#8211;&gt; On line 14 a <code>signkey<\/code> is defined, which may consist of 8 to 32 letters (upper- and lowercase) and digits. The length (8-32) as well as the letters\/digits are random.<br \/>\n&#8211;&gt; When selecting <code>\"2. Order\"<\/code> in the menu being displayed, the user can choose one of the products from the <code>items<\/code> array defined on line 15.<br \/>\n&#8211;&gt; The last element of the <code>items<\/code> array is the <code>Flag<\/code> which costs <code>99.999$<\/code>.<br \/>\n&#8211;&gt; Since our available money is a random value between <code>1.000$<\/code> and <code>10.000$<\/code> (line 16), we obviously cannot afford the <code>Flag<\/code>.<br \/>\n&#8211;&gt; After having selected a product to order the <code>order<\/code> function is called (line 22) printing the four attributes, which identifiy an order:<br \/>\n&nbsp;&nbsp;&nbsp;&nbsp;&#8211; product (the name of the product, e.g. <code>Flag<\/code>)<br \/>\n&nbsp;&nbsp;&nbsp;&nbsp;&#8211; price (the price of the product, e.g. <code>99999<\/code>)<br \/>\n&nbsp;&nbsp;&nbsp;&nbsp;&#8211; timestamp (the current timestamp: <code>time.time()*1000000<\/code>)<br \/>\n&nbsp;&nbsp;&nbsp;&nbsp;&#8211; <b>sign<\/b> (the sha256-hash of the order prepended by the <code>signkey<\/code>: <code>sign = sha256(signkey+payment).hexdigest()<\/code>)<br \/>\n&#8211;&gt; When choosing <code>\"3. Pay\"<\/code>, the function <code>pay<\/code> is called (line 32). Within the function &#8230;<br \/>\n&nbsp;&nbsp;&nbsp;&nbsp;&#8211; &#8230; an order (formerly printed by the <code>order<\/code> function) is read (line 36).<br \/>\n&nbsp;&nbsp;&nbsp;&nbsp;&#8211; &#8230; the <code>sign<\/code> attribute is extracted (line 41).<br \/>\n&nbsp;&nbsp;&nbsp;&nbsp;&#8211; &#8230; the sign-value (<code>signchk<\/code>) for the order being read is calculated using the secret <code>signkey<\/code> (line 49).<br \/>\n&nbsp;&nbsp;&nbsp;&nbsp;&#8211; &#8230; the extracted <code>sign<\/code> is compared to <code>signchk<\/code> (line 50). If the comparison fails, the order is invalid and the function is quit.<br \/>\n&nbsp;&nbsp;&nbsp;&nbsp;&#8211; &#8230; the values of the attributes <code>product<\/code> and <code>price<\/code> are extracted (line 56 and 59).<br \/>\n&nbsp;&nbsp;&nbsp;&nbsp;&#8211; &#8230; the extracted <code>price<\/code> is compared to the available <code>money<\/code> (line 64). If the money does not suffice, the function is quit (<code>\"Go away you poor bastard!\"<\/code>).<br \/>\n&nbsp;&nbsp;&nbsp;&nbsp;&#8211; &#8230; if the order is valid, the available money suffices and the selected product is <code>Flag<\/code>, the contents of the file <code>flag<\/code> are printed: <code>open('flag').read().strip()<\/code> (line 72).<\/p>\n<h3>How can we afford the <code>Flag<\/code>?<\/h3>\n<p>If we would know the random <code>signkey<\/code>, we could sign an order of the product <code>Flag<\/code> with a <code>price<\/code> we can afford.<\/p>\n<p>Since the <code>signkey<\/code> has a minimum length of 8 and consists of letters and digits, the minimal key-space is <code>62**8 = 218.340.105.584.896<\/code>. So bruteforcing does not seem to be an option.<\/p>\n<p>Instead we can use a technique called <a href=\"https:\/\/en.wikipedia.org\/wiki\/Length_extension_attack\" target=\"_blank\" rel=\"noopener\">length extension attack<\/a>.<\/p>\n<p>The <i>length extension attack<\/i> is based on the fact that a hash-function like sha256 processes data block-by-block. Each processed block results in an internal state of the hash-function, which is the base for the calculation of the next block. After the last block is processed, the internal state is returned in the form of the hash-value. Since we know the hash-value (<code>sign<\/code>), we can restore the internal state and continue the calculation of the hash-value for additional data, which we would like to append to the order.<\/p>\n<p>For the attack to work for a hash <code>H(secret || message)<\/code> we need to know <code>message<\/code> and the length of <code>secret<\/code>. In our case <code>message<\/code> is the order (<code>payment<\/code>), which we know. <code>secret<\/code> is the <code>signkey<\/code>, which lengths we do not exactly know, but it must be between 8 and 32.<\/p>\n<p>If we append <code>&price=1<\/code> to the order and calculate the valid <code>sign<\/code> value, we can buy the product <code>Flag<\/code> for <code>1$<\/code>, since the original value of <code>price<\/code> (<code>99999<\/code>) is overwritten with the new value we append (<code>1<\/code>):<\/p>\n<pre class=\"brush: python; first-line: 54; highlight: [59]; title: ; notranslate\" title=\"\">\r\n    for k,v in parse_qsl(payment):\r\n        if k == 'product':\r\n            product = v\r\n        elif k == 'price':\r\n            try:\r\n                price = int(v)\r\n                ...\r\n<\/pre>\n<p>The following picture illustrates the attack:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/devel0pment.de\/wp-content\/uploads\/2018\/05\/cpushop.png\" alt=\"\" width=\"1357\" height=\"294\" class=\"alignnone size-full wp-image-573\" srcset=\"https:\/\/devel0pment.de\/wp-content\/uploads\/2018\/05\/cpushop.png 1357w, https:\/\/devel0pment.de\/wp-content\/uploads\/2018\/05\/cpushop-300x65.png 300w, https:\/\/devel0pment.de\/wp-content\/uploads\/2018\/05\/cpushop-768x166.png 768w, https:\/\/devel0pment.de\/wp-content\/uploads\/2018\/05\/cpushop-1024x222.png 1024w\" sizes=\"(max-width: 767px) 89vw, (max-width: 1000px) 54vw, (max-width: 1071px) 543px, 580px\" \/><\/p>\n<h3>Implementation<\/h3>\n<p>In order to carry out the length extension attack, which means to calculate the value for <code>sha256<sub>sign<\/sub>('<PADDING>&price=1')<\/code> from the picture above, we can use a tool called <a href=\"https:\/\/github.com\/bwall\/HashPump\" target=\"_blank\" rel=\"noopener\">HashPump<\/a>.<\/p>\n<p><i>HashPump<\/i> is available as a python-module:<\/p>\n<pre class=\"brush: bash; gutter: false; title: ; notranslate\" title=\"\">\r\nroot@kali:~# pip install hashpumpy\r\n...\r\n<\/pre>\n<p>The following script &#8230;<br \/>\n&#8211;&gt; &#8230; orders the <code>Flag<\/code>.<br \/>\n&#8211;&gt; &#8230; extracts the value for <code>sign<\/code> and <code>payment<\/code> from the order.<br \/>\n&#8211;&gt; &#8230; loops over the possible key length from 8 to 32.<br \/>\n&#8211;&gt; &#8230; uses <code>hashpumpy<\/code> to append <code>'&price=1'<\/code> to the order and calculate the new value for <code>sign<\/code> without knowing the secret <code>signkey<\/code>.<br \/>\n&#8211;&gt; &#8230; tries to submit the payment of <code>1$<\/code> to buy the <code>Flag<\/code>.<\/p>\n<pre class=\"brush: python; first-line: 0; title: ; notranslate\" title=\"\">\r\nroot@kali:~\/Documents\/roisctf\/cpushop# cat buyFlag.py\r\n#!\/usr\/bin\/env python\r\n\r\nfrom pwn import *\r\nimport hashpumpy\r\n\r\np = remote('cpushop.2018.teamrois.cn', 43000)\r\np.recv()\r\n\r\n# order Flag\r\np.sendline(&quot;2&quot;)\r\np.recvuntil(&quot;Product ID: &quot;)\r\np.sendline(&quot;9&quot;)\r\n\r\n# extract sign and payment from order\r\npayment = p.recv()\r\nsp = payment.find('&amp;sign=')\r\nsign = payment&#x5B;sp+6:]\r\nsign = sign&#x5B;:sign.find('\\n')]\r\npayment = payment&#x5B;payment.find('product'):payment.find('&amp;sign')]\r\n\r\nfor keylen in range(8,32):\r\n  log.info('trying keylen='+str(keylen))\r\n\r\n  n = hashpumpy.hashpump(sign, payment, '&amp;price=1', keylen)\r\n  order = n&#x5B;1] + &quot;&amp;sign=&quot;+n&#x5B;0]\r\n\r\n  p.sendline(&quot;3&quot;)\r\n  p.recvuntil(&quot;Your order:&quot;)\r\n  p.sendline(order)\r\n  p.recv(1000)\r\n  ret = p.recv(1000)\r\n  if (&quot;Invalid&quot; not in ret):\r\n    print(ret)\r\n    print(p.recvuntil(&quot;Money: &quot;))\r\n    quit()\r\n<\/pre>\n<p>Running the script yields the flag:<\/p>\n<pre class=\"brush: bash; gutter: false; title: ; notranslate\" title=\"\">\r\nroot@kali:~\/Documents\/roisctf\/cpushop# .\/buyFlag.py\r\n&#x5B;+] Opening connection to cpushop.2018.teamrois.cn on port 43000: Done\r\n&#x5B;*] trying keylen=8\r\n&#x5B;*] trying keylen=9\r\n&#x5B;*] trying keylen=10\r\n&#x5B;*] trying keylen=11\r\n&#x5B;*] trying keylen=12\r\n&#x5B;*] trying keylen=13\r\n&#x5B;*] trying keylen=14\r\n&#x5B;*] trying keylen=15\r\n&#x5B;*] trying keylen=16\r\n&#x5B;*] trying keylen=17\r\n&#x5B;*] trying keylen=18\r\n&#x5B;*] trying keylen=19\r\n&#x5B;*] trying keylen=20\r\n&#x5B;*] trying keylen=21\r\n&#x5B;*] trying keylen=22\r\n&#x5B;*] trying keylen=23\r\n&#x5B;*] trying keylen=24\r\n&#x5B;*] trying keylen=25\r\n&#x5B;*] trying keylen=26\r\n&#x5B;*] trying keylen=27\r\n&#x5B;*] trying keylen=28\r\n&#x5B;*] trying keylen=29\r\n&#x5B;*] trying keylen=30\r\nYour current money: $4908\r\n\r\nYou have bought Flag\r\nGood job! Here is your flag: RCTF{ha5h_l3ngth_ex7ens10n_a77ack_1s_ez}\r\n\r\nMoney:\r\n&#x5B;*] Closed connection to cpushop.2018.teamrois.cn port 43000\r\n<\/pre>\n<p>The flag is <code><span class=\"spanFlag\">RCTF{ha5h_l3ngth_ex7ens10n_a77ack_1s_ez}<\/span><\/code>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The RCTF 2018 (ctftime.org) ran from 19\/05\/2018, 09:00 UTC to 21\/05\/2018 08:59 UTC. I wrote the following writeup for the crypto challenge cpushop.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[24,7],"tags":[23,22],"class_list":["post-561","post","type-post","status-publish","format-standard","hentry","category-ctf","category-writeup","tag-crypto","tag-sha256"],"_links":{"self":[{"href":"https:\/\/devel0pment.de\/index.php?rest_route=\/wp\/v2\/posts\/561"}],"collection":[{"href":"https:\/\/devel0pment.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devel0pment.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devel0pment.de\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/devel0pment.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=561"}],"version-history":[{"count":18,"href":"https:\/\/devel0pment.de\/index.php?rest_route=\/wp\/v2\/posts\/561\/revisions"}],"predecessor-version":[{"id":584,"href":"https:\/\/devel0pment.de\/index.php?rest_route=\/wp\/v2\/posts\/561\/revisions\/584"}],"wp:attachment":[{"href":"https:\/\/devel0pment.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=561"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devel0pment.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=561"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devel0pment.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=561"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}