MMA CTF 2015 – Motto Mijikai Address (Crypto/Web 100+300)

Login as admin and get the flag1.
mmaddress.7z

Summary: breaking HMAC-CRC512

In this challenge we can register users, login and create shortened urls. Our first goal is to login as admin. Session data is stored in cookies, signed with some HMAC. Let’s look at the hash function used in HMAC:

  def hash(str, v = 0)
    hash = MASK ^ v
    str.unpack("C*").each do |v|
      hash = (table[((hash) >> (N - 8)) ^ v] ^ hash << 8) & MASK
    end
    hash ^ MASK
  end

This construction should be familiar: it is CRC code (together with table generation). Though here we don’t even know the polynomial. We can exploit linearity of CRC – it is known that CRC(a^b^c) = CRC(a) ^ CRC(b) ^ CRC(c). Easy to check that this property applies to HMAC too:

CRC[ K^opad || CRC(K^ipad || m1^m2^m3) ] =
    CRC[ K^opad || CRC(K^ipad || m1) ] ^
    CRC[ K^opad || CRC(K^ipad || m2) ] ^
    CRC[ K^opad || CRC(K^ipad || m3) ]

We can use this property to make valid HMAC for admin session. The exploit is very easy: register two user with random 5-char names, register third user with name equal to xor of two previous usernames and string “admin”. Then xor all session datas and xor all hmacs! Here’s python code:

import requests, os
from urllib import unquote, quote
from base64 import b64decode, b64encode
 
def xor(a, b):
    return "".join([chr(ord(a[i]) ^ ord(b[i % len(b)])) for i in xrange(len(a))])
 
def register(u, p):
    data = {"user": u, "password": p}
    r = requests.post("http://mmaddress.chal.mmactf.link/register", data=data)
    # print r.content
    return True
 
def login(u, p):
    data = {"user": u, "password": p}
    sess = requests.session()
    r = sess.post("http://mmaddress.chal.mmactf.link/login", data=data)
    a, b = unquote(list(sess.cookies)[0].value).split("-----")
    a = b64decode(a)
    b = b64decode(b)
    return a, b
 
r = os.urandom(2).encode("hex")
p = "1"
 
users = [r + "z", "z" + r]
users.append(xor("admin", xor(users[0], users[1])))
lsta = []
lstb = []
for u in users:
    print "Reg", u, p
    register(u, p)
    a, b = login(u, p)
    lsta.append(a)
    lstb.append(b)
 
aa = xor(xor(lsta[0], lsta[1]), lsta[2])
bb = xor(xor(lstb[0], lstb[1]), lstb[2])
print `aa`, `bb`
cook = quote(b64encode(aa)) + "-----" + quote(b64encode(bb))
print cook

Run and get cookie:

Reg 7313z 1
Reg z7313 1
Reg ,`ok' 1
{"user":"admin","password":"626cc181800cc661fe06600000033000000d5b567fe60006601983c560a60cc0192bab06635aa607f8000000aa00660d3d30000000660000019819864a8cbe2b"}'
eyJ1c2VyIjoiYWRtaW4iLCJwYXNzd29yZCI6IjYyNmNjMTgxODAwY2M2NjFmZTA2NjAwMDAwMDMzMDAwMDAwZDViNTY3ZmU2MDAwNjYwMTk4M2M1NjBhNjBjYzAxOTJiYWIwNjYzNWFhNjA3ZjgwMDAwMDBhYTAwNjYwZDNkMzAwMDAwMDA2NjAwMDAwMTk4MTk4NjRhOGNiZTJiIn0%3D-----5iLUP9hkSfI4/6inAtrceRLBkQflTLd%2BJz1gTgQXliwnWRE6k94kcOwMAIUYoSVZmWGxxrmut3csQl7e5aEOVw%3D%3D

Use cookie and see recent url https://gist.github.com/uecmma/25c38a6b18b41854cd68. The first flag is MMA{8f07ea4e3f79f483e3a81656b196af7d}.

The second flag

The second flag is the HMAC key used:

HMAC.hmac(json, FLAG, 512)

Learning the polynomial

The first thing we should do is to extract the CRC polynomial. CRC is basically polynomial modulo reduction in $\mathbb{F}_2[x]$ with additional masking before and after. We can write:

$$MyHash(m) = CRC_{512}(m) = (MASK \cdot (x^M + 1) + mx^{512}) \mod P(x).$$

, where $M = len(m)$ and $P(x)$ is the unknown polynomial.

Here $MASK \cdot x^M$ corresponds to the initial mask, $MASK \cdot 1$ corresponds to the final mask. $+$ and XOR are the same since we work in $\mathbb{F}_2[x]$. Multiplying by $x^M$ is the same as shifting value left by $M$ bit.

To learn $P(x)$ we need to obtain a few pairs $(m,CRC_{512}(m))$. A good thing is that besides HMAC we have direct access to the $CRC_{512}$ function – the hash of password is stored in the session json in the cookie. For each message we can compute $CRC_{512}$ without modulo reduction. From it we can subtract the reduced value (which we’ve got from the server) and get a multiple of $P(x)$:

$$(MASK \cdot (x^M + 1) + mx^{512}) – CRC_{512}(m) = R(x)P(x).$$

Finally we can compute $P(x)$ by running $gcd$ on several such values, until we stop at polynomial of degree 512:

$$P(x) = gcd(R_1(x)P(x), R_2(x)P(x), \ldots).$$

Let’s do it:

from sage.all import *
 
def ntopoly(npoly):
    return sum(c*X**e for e, c in enumerate(Integer(npoly).bits()))
 
def polyton(poly):
    return sum(int(poly[i])*(1 << i) for i in xrange(poly.degree() + 1))
 
X = GF(2).polynomial_ring().gen()
 
N = 512
MASK = (1 << N) - 1
pMASK = ntopoly(MASK)
 
data = {
    "password": 0x4910b1bb284eee2f49f41043c3a9e3d4f2deaa5319d689d4fa8c04732bc8d46a84b54ef3c52aa79883e56b225c87f68181522b28b71c7be29a98b528a791374f,
    "passwore": 0x4e18a1b9084efe274b741843c3a9e7d4f2deb857997609d4f28c247672d8547a8494ccb3cd2e371889e56b225d07f60193d62b28b71cfbe29a9ab508aff127ec,
}
 
multiples = []
for msg, crc in data.items():
    M = len(msg) * 8
    msgnum = int(msg.encode("hex"), 16)
    m = ntopoly(msgnum)
    rem = ntopoly(crc)
    mult = pMASK * (X**M + 1) + m * X**N - rem
    multiples.append(mult)
 
g = reduce(gcd, multiples)
print "Degree", g.degree()
print "G: 0x" + hex(polyton(g))

The poly is: 0x1070810022000100802800800000004000000120480a08000080020055910801000218240080490800a00000001800080128400000000800000020020086010a3.

Learning the key

Now we go back to HMAC and recover the key.

$$HMAC(m, K) = CRC_{512}( [K \oplus opad] || CRC_{512}( [K \oplus ipad] || m)).$$

Since everything is done modulo $P(x)$ which we know and XOR is the same as addition, we can work out a single nice formula for HMAC ($\mathbb{I}$ is ipad, $\mathbb{O}$ is opad).

$CRC_{512}( [K \oplus \mathbb{I}] || m) = $
$ = \quad(MASK \cdot (x^{512+M}+1) + mx^{512} + Kx^{512+M} + \mathbb{I} x^{512+M}) \mod P(x)$

$HMAC(m, K) = (MASK \cdot (x^{1024+M} + x^{1024} + x^{512})$
$+\quad mx^{1024} $
$+\quad \mathbb{O} x^{1024} $
$+\quad \mathbb{I} x^{1024+M} $
$+\quad K (x^{1024+M} + x^{1024}) $
$ ) \mod P(x)$

Since only $K$ is unknown now, we can solve for it::

$$K = (HMAC(m, K) – (…)) / (x^{1024+M} + x^{1024}) \pmod{P(x)}$$.

Here comes a problem: $(x^{1024+M} + x^{1024})$ is not invertible modulo $P(x)$! It is possible because $P(x)$ is not irreducible, more precisely, $x+1$ divides both $P(x)$ and $(x^{1024+M} + x^{1024})$ for all $M$. Luckily, this is the only common divizor. It means that we have lost information about $K \mod (x+1)$. It’s not a problem, there are only two possibilities: 0 and 1. So let’s drop $(x+1)$ and add it later using Chinese Remainder Theorem.

Note: even if the factor was large and there were many possibilities, any value will work for HMAC. Moreover, there is no way to distinguish which $K$ is actually used. However we know that real $K$ is a flag so we can check all candidates and check if any of them looks like flag.

# ... first part continued
poly = g
 
I = ntopoly(int(("36"*64), 16))
O = ntopoly(int(("5C"*64), 16))
 
msg = '{"user":"qwef7a6dbda","password":"4e18a1b9084efe274b741843c3a9e7d4f2deb857997609d4f28c247672d8547a8494ccb3cd2e371889e56b225d07f60193d62b28b71cfbe29a9ab508aff127ec"}'
real_hmac = 0xe13060504b419a311d271833b188e2479ba64c5f1b639897980f64670e4e4142d5b9045c1a20f91156ca9997eae47f4f6171849e0f00776ab5bb6984917a1667
M = len(msg) * 8
m = ntopoly(int(msg.encode("hex"), 16))
full = ntopoly(real_hmac)
 
part = pMASK * (X**(1024+M) + X**1024 + X**512 + 1)
part += O * X**1024
part += I * X**512 * X**(512+M)
part += m * X**512 * X**512
# part += K * X**1024 * (X**M + 1)
part %= poly
 
kc = full - part
c = X**1024 + X**(1024+M)
g = gcd(poly, c)  # (x + 1)
 
redK = (kc // g) * inverse_mod(c // g, poly // g)
redK %= poly // g
for guess in xrange(2):  # mod (x + 1)
    K = crt([redK, ntopoly(guess)], [poly // g, g])
    print "guess", guess, ":", hex(polyton(K))
    print "t", `hex(polyton(K)).decode("hex")`

And with guess=1 we have the second flag: MMA{CRC_HMAC_IS_NOT_SECURE}.

PS: If you want to try these tricks with the usual crc32, bear in mind that it is a bit weird: bits in each byte are processed from LSB to MSB, and also the polynomial (and so the result) is represented in reversed way (e.g. $x^{31}$ corresponds to the 1st LSB).