27
Apr
2013

pCTF 2013 – blech (crypto 200)

You get arbitrary code execution…. as long as it’s code we approve of.

This challenge consisted of a service which allowed running arbitrary python code, as long as you had a valid RSA signature for it…

This time the pCTF guys were nice enough to provide the source code for the challenge:

#!/usr/bin/python -u
import sys
import struct
import os
import hashlib

def strtonum(s):
  ret = 0
  for h in s:
    ret *= 256
    ret |= ord(h)
  return ret

def numtostr(s, l):
  ret = ""
  for i in range(0, l):
    ret = chr(s&0xFF) + ret
    s >>= 8
  return ret

port = 1234

# RSA modulus(factor me)
N = 0xc3542f8b7b2c9f083912972d8d07312fce5cf549ae8b25e97a691d35a72f953dad939811e1ec4d46fafd5db3034fee45c5f700a57915a67238925361b3ea7ae58e392b92d13af8e1604298794f640db466642933825813bf329b228f773a5137a625bd23ffa1d8bb7ca9b49d6235a0e4f839226f14a9e7a42fa4f7d530725803

print "WE ONLY RUN SIGNED CODE, DO YOU HAVE SIGNED CODE?"
l = struct.unpack("I", sys.stdin.read(4))[0]
hashee = sys.stdin.read(0x80)
msg = numtostr(pow(strtonum(hashee), 3, N), 0x80)
code = sys.stdin.read(l)
if msg[0:4] != "\x00\x01\xFF\xFF":
  print "BAD PADDING"
  sys.exit(0)
h = hashlib.sha1(code).digest()
if msg[len(msg)-len(h):] != h:
  print "BAD HASH"
  sys.exit(0)
eval(code)

So the service reads a piece of code and an RSA signature, checks the signature and if the signature is valid it runs the code. The signature checking looks pretty decent, except for some ‘minor’ details: the padding is not fully validated, only the first 4 bytes of padding are checked and the rest of the padding is ignored. Also the public exponent is 3. We can use this combination to our advantage and construct a fake signature that will pass the (partial) padding check and contains the SHA-1 hash of the code.

We found a nice academic paper explaining how to perform these types of attacks: http://www.cdc.informatik.tu-darmstadt.de/reports/reports/sigflaw.pdf converting that into working exploit code proved rather difficult after 24 hours of straight hacking and beer, but we managed to do it.

Let h be the SHA-1 hash of the code we wish to execute. The attack only works for odd values of h, so if h is not odd we add a space and try again until h is odd. Now we have an odd h we can construct a value xh which will contain h at the end when raised to the power three. The paper explains an easy way to do this by calculating the inverse of 3 mod 2**160 (where 160 is the number of bits in a SHA-1 hash).

def inv(p, q):
    def xgcd(x, y):
        s1, s0 = 0, 1
        t1, t0 = 1, 0
        while y:
            q = x // y
            x, y = y, x % y
            s1, s0 = s0 - q * s1, s1
            t1, t0 = t0 - q * t1, t1
        return x, s0, t0

    s, t = xgcd(p, q)[0:2]
    assert s == 1
    if t < 0:
        t += q
    return t

h = 0xee5306c1cb28315ee0aa5fdabab2eef4460e9c9b # sha-1 hash of os.system('id')
inv3 = inv(3,2**159)
xh = pow(h,inv3,2**160)
print hex(pow(xh,3))

Output: x2699e2007c8219cc4c1c281bf6840b214055ac7613f93f906cfbd984bf33a233f146cc5b5d822c1cee5306c1cb28315ee0aa5fdabab2eef4460e9c9b

We now have an xh value which can serve as a fake signature for h: if xh is raised to the power 3 the result ends in our hash h. Now we only need to add to the padding. This time around the problem is slightly different, we are now searching for a value which when raised to the power 3 will start with 0x001ffff. For this we took the cubic root of 0x001ffff00000000.

print hex(int(pow(0x1ffff00000000,1.0/3)+1))
0x1428a
print hex(pow(0x1428a,3))
0x1ffff1d5571e8

This value is already 64-bits long when raised to the power 3, but we need something which is 1024-bits long. We can do that by multiplying it with 2**((1024-64)/3) = 2**320.


print hex(pow(0x1428a * 2**320,3))
0x1ffff1d5571e8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L

Now we can fix both padding and a fake hash we can construct our final exploit:

import hashlib,struct,sys

code = "os.system('%s')" % sys.argv[1]
while True:
    h = int(hashlib.sha1(code).hexdigest(), 16)
    if (h % 2): break
    code += ' '

n = 0xc3542f8b7b2c9f083912972d8d07312fce5cf549ae8b25e97a691d35a72f953dad939811e1ec4d46fafd5db3034fee45c5f700a57915a67238925361b3ea7ae58e392b92d13af8e1604298794f640db466642933825813bf329b228f773a5137a625bd23ffa1d8bb7ca9b49d6235a0e4f839226f14a9e7a42fa4f7d530725803
def inv(p, q):
    def xgcd(x, y):
        s1, s0 = 0, 1
        t1, t0 = 1, 0
        while y:
            q = x // y
            x, y = y, x % y
            s1, s0 = s0 - q * s1, s1
            t1, t0 = t0 - q * t1, t1
        return x, s0, t0

    s, t = xgcd(p, q)[0:2]
    assert s == 1
    if t < 0:
        t += q
    return t

b = 124
inv3 = inv(3,2**159)
xh = pow(h,inv3,2**160)

yp = (0x1428a * 2**320)
fake = yp + xh

sys.stdout.write(struct.pack('<L', len(code)))
sys.stdout.write(("%.256X" % fake).decode('hex'))
sys.stdout.write(code)

Running this yields the flag:

(python exp.py 'cat /home/*/key'; sleep 1) | nc 54.234.73.81 1234
WE ONLY RUN SIGNED CODE, DO YOU HAVE SIGNED CODE?
I_ate_a_burger_last_night

Comments are closed.