Apr 22

PlaidCTF 2013 Blech (Crypto 200)

You get arbitrary code execution…. as long as it’s code we approve of.
Source available at blech.py
Service running on 54.234.73.81 port 1234

blech.py

Summary: RSA cube root attack

Here’s the main part:

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)

That means we need to craft a payload, which starts with "\x00\x01\xff\xff" and ends with sha1 hash of our malicious code. Also we need to find a modular cube root of this payload as a number. It’s hard in general case and needs a factorization of modulus. But since have a lot of arbitrary bytes between the padding and the hash (128 – 4 – 20 = 104 bytes), we can find such values for which the payload will be a perfect cube itself, so we replace modular cube root with simple cube root (which is easy).

If the hash will be placed in the higher bits of the payload, then it will be very easy: we just extract a rounded cube root (with binary search, for example) of slighly increased payload and that’s it: its cube will change low bits but high bits with our hash will stay the same. But here the hash is placed in lower bits and also the necessary padding makes our payload huge (large numbers have smaller probability to be a cube than smaller ones).

We can use another trick here: since we won’t overflow the modulus with our cube, we can thinks there’s no modulus at all. And then we can define another modulus at our own choice. A good ideas is to use modulus as the size of the hash space: 2160, because the part of the payload which will be checked against hash (last 20 bytes) mean exactly the value of the payload mod 2160. We know its factorization and thus can extract modular cube roots.

What’s about the padding? We still can use the same trick as in easy case for padding and then just replace low 20 bytes with our modular cube root:

  • extract rounded cuberoot of 0x01ffff8000…000
  • extract modular cuberoot of our hash
  • replace low 20 bytes with modular cuberoot
  • that’s our final cuberoot!

An example:

Rounded cube root of
0001ffff80000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
=
01428a14b7fb9e89c8d1354505f123cc3151ad1048cedd20738afc929e8c6611d95407a29cde44b5611501
which cube is
0001ffff7fffffff
fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd28119ed5
5304260fe04e3b2b44a0c23ed31d79b62db55353d5d6674f73bace948f5037d7d4cd96a45f29c322
2ae1dc6d84077657ff97107c30a25272ab47f38dad562d37d393f31012a6044ce7f333c6104e3f01
 
Modular cube root of
# sha1 hash of "os.system('id; cat /home/*/key') # adcbe"
cfb08c3fefaf9a0ba1b2844a362f57cb2ba468f8
is
17e6a942efbe3a42532cc2b64753f3c38d9650be
 
Final cube root is
01428a14b7fb9e89c8d1354505f123cc3151ad1048cedd[17e6a942efbe3a42532cc2b64753f3c38d9650be]
 
which cube is
[0001ffff]7fffffff
ffffffffffffffffffffffffffffffffd7482082132fed76b058264d38e1ea7a144e0a52f509d0b2
94411862eac362938c3ca4d5a0976e46130354b0d46fabcbfffd7857f0c66370638212b40f46b6a4
2d8c71488c878b4d1842a4fb6d992d5e084b8b9a[cfb08c3fefaf9a0ba1b2844a362f57cb2ba468f8]

So, here’s the code:

import hashlib
from libnum import *
from sock import Sock
from struct import pack
 
n = 0xc3542f8b7b2c9f083912972d8d07312fce5cf549ae8b25e97a691d35a72f953dad939811e1ec4d46fafd5db3034fee45c5f700a57915a67238925361b3ea7ae58e392b92d13af8e1604298794f640db466642933825813bf329b228f773a5137a625bd23ffa1d8bb7ca9b49d6235a0e4f839226f14a9e7a42fa4f7d530725803
 
code = "os.system('id; cat /home/*/key') # adcbe"
h = hashlib.sha1(code).digest()
 
def cuberoot_mod_2k(a, k):
    """You can simply use pow(a, invmod(3, 2**(k-1)), 2**k) if a i odd"""
    e = 0
    while a & 1 == 0:
        e += 1
        a >>= 1
    if e % 3 != 0:
        raise ValueError("Not a cube residue")
    mod = 2 ** (k - e)
    phi = mod / 2
    d = invmod(3, phi)
    x = pow(a, d, mod)
    return x * (1 << (e // 3))
 
large = nroot(s2n("\x00\x01\xff\xff\x80".ljust(128, "\x00")), 3)
small = cuberoot_mod_2k(s2n(h), 160)
 
sign = n2s(large)[:-20] + n2s(small)
 
f = Sock("54.234.73.81", 1234, 100)
f.send(pack("<I", len(code)))
f.send(sign.rjust(0x80, "\x00"))
f.send(code)
print f.read_all()

I’ve used my libnum for nroot, invmod functions and lib sock.

Execute it:

$ py blech.py 
WE ONLY RUN SIGNED CODE, DO YOU HAVE SIGNED CODE?
uid=1001(blech) gid=1001(blech) groups=1001(blech)
I_ate_a_burger_last_night

So, the key: I_ate_a_burger_last_night

UPD:
Someone asked about even hashes. It’s easy too: we can overflow modulus one time, thus all values will change from r to n + r. Since n is odd, oddity of the result is changed, so even hash becomes odd.

So all stuff stays the same, except we need to extract rounded cube root of (n + 0x1ffff80...0) and modular cube root of (n + <hash>):

code = "os.system('cat /home/*/key')"
# hash is 21e20a6df646c2d008625e9f500bfb864cd28eb0, divides 16
h = hashlib.sha1(code).digest()
 
if ord(h[-1]) % 2 == 1:
    large_cube = s2n("\x00\x01\xff\xff\x80".ljust(128, "\x00"))
    small_cube = s2n(h)
else:
    large_cube = s2n("\x00\x01\xff\xff\x80".ljust(128, "\x00")) + n
    small_cube = (s2n(h) + n) % (1 << 160)
 
large = nroot(large_cube, 3)
small = cuberoot_mod_2k(small_cube, 160)
 
sign = n2s(large)[:-20] + n2s(small)

hellman

1 ping

  1. […] RSA CTF Challenge (no writeup, but I think it’s similart to this old one) […]

Leave a Reply

Your email address will not be published.