For this challenge we’re given a network address where we can access what looks like a simple shell, and the source code to this shell, which is thankfully python code.

Looking at macsh.py we see a set of commands, some of which are privileged. We can echo without privilege, and tag. What’s tag?

Looking at the tag implementation, it looks like it creates and prints the MAC of the specified args, as long as the args don’t start with a priveleged command. Looking at the command parsing, it looks like commands are expected to come in the format TAG<|>COMMAND, and the command will not execute unless the tag matches the mac of the command. The tag command, however, skips the check.

$ nc macsh.chal.pwning.xxx 64791
|$|> <|>tag hello world
3c3ddeeb2e5c6d7f06abc155690e2ec5
|$|> <|>tag cat flag
macsh: tag: Permission denied

The goal here is obvious: Take advantage of tag to get the MAC of a privileged command, so that I can find and eventually dump the flag file. Let’s see how the crypto is implemented.

def fmac(k0, k1, m):
    C = AES.new(k1, AES.MODE_ECB)
    bs = [C.encrypt(xor(b, f(k0, i))) for i,b in enumerate(to_blocks(m))]
    for i, blocks in enumerate(zip(bs, to_blocks(m))):
        cb, b = blocks
    return reduce(xor, bs, b"\x00" * N)

ECB mode! That means that each block is encrypted individually! The order and the neighbouring blocks don’t matter. This is easy: Just tag something that has a privileged command within its own block! Then snip out that part, and provide it on its own.

There’s a snag here: tag gives you a MAC, not the encryption of each block. Their mac combines all of the encrypted blocks by xoring them together. We can easily get rid of this by taking advantage of this property of xor:

A ^ A = 0

or rather

A ^ B ^ A = B

What this means is that if we can get the tag of a good block (A), and then the tag of the same good block plus a privileged block (A^B) we can xor these together and end up with the tag of just the privileged block!

I write some code to do this and… fail. Time to run this locally and add some debugging prints.

Notice that in the fmac function there are calls to to_blocks. This pads the input so that its length is a multiple of the block size (16 bytes) as also adds a padding block or two. Adding some prints we can see what’s happening:

|$|> <|>tag echo hello
Blocks:
0: b'6563686f2068656c6c6f000000000000' -> b'eba3ae8a1a00f6db419e625a2b4802db'
1: b'0000000000000000000a060606060606' -> b'c8b571a0faf80b49439c49ea2ca1953b'
2316df2ae0f8fd9202022bb007e997e0
|$|> <|>tag echo aaaaaaaaaaa
Blocks:
0: b'6563686f206161616161616161616161' -> b'1dd59512f963b859566b5dcf8aa2b8f8'
1: b'00000000000000000000000000000010' -> b'643600eae985916e0155e472099e8cd5'
2: b'10101010101010101010101010101010' -> b'383f4a034e7ad2e67b2ba196bcf9de5d'
41dcdffb5e9cfbd12c15182b3fc5ea70

This throws a bit of a wrench in our gears: If we tag GOOD|PRIV, because its length will be different than GOOD, the extra blocks will not be the same, meaning we cannot just ‘snip out’ the good part. We need the length to be the same. Let’s try that:

|$|> <|>tag echo aaaaaaaaaaacat ././flag.txt
Blocks:
0: b'6563686f206161616161616161616161' -> b'1dd59512f963b859566b5dcf8aa2b8f8'
1: b'636174202e2f2e2f666c61672e747874' -> b'a618de00b21a086d5ebc237480139199'
2: b'00000000000000000000000000000020' -> b'86998fd44e998eba9d99ab42730e19f4'
3: b'10101010101010101010101010101010' -> b'b391d29ba893e45655fdee555e9292fe'
8ec5165dad73dad8c0b33bac272da26b
|$|> <|>tag echo aaaaaaaaaaaBBBBBBBBBBBBBBBB
Blocks:
0: b'6563686f206161616161616161616161' -> b'1dd59512f963b859566b5dcf8aa2b8f8'
1: b'42424242424242424242424242424242' -> b'10412e29cbdc69e2bba87f7128cb70fe'
2: b'00000000000000000000000000000020' -> b'86998fd44e998eba9d99ab42730e19f4'
3: b'10101010101010101010101010101010' -> b'b391d29ba893e45655fdee555e9292fe'
389ce674d4b5bb5725a767a98ff5430c

That’s more like it! Now we have A^B^PAD, A^PRIV^PAD, but we want PRIV^SPAD, where SPAD is the padding of a short block (Since sending the privileged command on its own will be three blocks instead of four). We can use a combination of short and long commands to get what we want.

PRIV^SPAD = A^PAD ^ PRIV^PAD ^ A^SPAD

Now the two ‘A’ bogus commands cancel out, the two long pads cancel out, and we’re left with a privileged command with a short pad!

This is where I hit another snag: When debugging I noticed that the order of the blocks matter. That’s not the ECB I know! Turns out I missed an important part of fmac: C.encrypt(xor(b, f(k0, i))). What does f do?

def f(k0, i):
    return to_block(rot(to_int(k0), i % (8 * N)))

def rot(n, c):
    return (n >> c) | ((n & ((1 << c) - 1)) << (8 * N - c))

Ah! The key is being rotated by the block index! Shit! That means that the PRIV block I put at index 1 won’t be MACed with the same key at index 0! How do we solve this?

If you think about this key rotation you’ll realize that there are effectively 128 versions of this key, since there are 128 bits in the key. What happens when we’re on the 129th block? The key gets rotated all the way around… back to it’s original value! This means that for PRIV to work properly, I need it to be MACed in the 129th block. This is easy to do! I just need to lengthen A so that it’s 128 blocks long! The same math works out to cancel out PAD and A.

import sys

from pwn import *

def prompt():
    r.recvuntil("|$|> ")

def xor(x, y):
    return "".join([chr(ord(xe) ^ ord(ye)) for xe,ye in zip(x,y)])

def exploit():
    prompt()
    block = "****************"
    # Get the MAC of LONG ^ privcmd
    # privcmd =   "ls ././././././." # Trying to find the flag
    privcmd =   "cat ././flag.txt"
    # We pad 128 blocks so that privcmd is MACed with a key rotated 128 bits (back to orig)
    r.sendline("<|>tag "+block*128 + privcmd)
    buf = r.recvuntil("|$|> ").split("\n")
    tagpl = buf[-2]

    # Get the MAC of LONG ^ boguscmd
    cmd =   "xxxxxxxxxxxxxxxx"
    r.sendline("<|>tag "+block*128 + cmd)
    buf = r.recvuntil("|$|> ").split("\n")
    tagbl = buf[-2]

    # Get the MAC of SHORT ^ boguscmd
    r.sendline("<|>tag " + cmd)
    buf = r.recvuntil("|$|> ").split("\n")
    tagbs = buf[-2]

    # Now we want to send privcmd ^ SHORT
    # privcmd ^ SHORT = LONG ^ privcmd ^ LONG ^ boguscmd ^ SHORT ^ boguscmd
    tagpb = xor(tagpl.decode('hex'), tagbl.decode('hex')).encode('hex')
    tagps = xor(tagpb.decode('hex'), tagbs.decode('hex')).encode('hex')
    goodtag = tagps
    r.sendline(goodtag + "<|>"+privcmd)
    log.info(r.recvline())
    prompt()
    r.interactive()


if __name__ == "__main__":
    cmd = "python3 macsh.py".split()
    host, port = "macsh.chal.pwning.xxx:64791".split(":")
    if len(sys.argv) > 1:
        r = remote(host, port)
        exploit()
    else:
        r = process(cmd)
        exploit()

PCTF{fmac_is_busted_use_PMAC_instead}