This defines a custom MAC `fmac` as follows, given a message `m`, a key `k1` and a stream `S0`:
* Append the length of `m` formatted as 16 bytes in big-endian order.* Append *b* = 1–16 copies of the byte *b* to pad the message to a multiple of 16 bytes.* Xor the padded message with `S0`.* Encrypt the result with AES-ECB with the key `k1`.* Xor all the resulting 16-byte blocks.
The stream `S0` is derived from a 128-bit key `k0` by repeating a sequence of 128 128-bit blocks where block number `i` is calculated by rotating `k0` right by `i` bits.
The MAC function operates by blocks. We don't know how each encrypted block is calculated, but we know that the result depends only on the content of that block in the message and on the block's index modulo 128. In particular, if a block is repeated at a 128*16=2048-byte interval, then the encrypted blocks will be identical. Since the MAC is a xor of all the encrypted blocks, these repeated blocks cancel out.
We can also deduce the MAC of a message with xor equations. Suppose that `m1` contains some block `B1` at position `i`, and `m2` is the same message except that position `i` contains `B2`. Then `fmac(m1) xor fmac(m2)` depends only on `B1`, `B2` and `i` modulo 128, and not on the rest of the message.
This MAC function is used in a remote shell where we can use the following commands:
* `tag tag` or `tag echo`: calculate the `fmac` of the command line consisting of `tag` or `echo` and the given parameters, joined with a single space.* `pwd`, `cd`, `ls`, `cat`: the usual Unix commands, which require a valid `fmac`. `pwd` takes no parameters, the others take exactly one parameter.
Null bytes are accepted in arguments but not in file names. Whitespace (spaces and bytes 0x09–0x0d) cannot appear in parameters.
Example: to list the current directory, we can run the command `ls .`, which is padded to the two blocks `ls .000000000000`, `0004CCCCCCCCCCCC` where `0`, `4` and `C` are the characters 0x00, 0x04 and 0x0c respectively. To calculate its MAC, we need to craft a message starting with `tag` and a space (or `echo` and a space), containing blocks that will cancel out, and containing the two blocks of the `ls` command at positions 128 and 129 (or 256 and 257, etc.).
Since we can't pass bytes 0x09–0x0d in parameters, we need to fiddle with the length of the command to avoid those bytes both in the encoding of the length and in the padding. The following command lengths are admissible: 0–2, 8, 14–18, 24–31, 33, 34, 40–50, 56–66,  etc. We can always make a command (other than `pwd`) longer by adding more slashes in a file name (or prepending `./` if it doesn't contain a slash). For example, instead of `ls .`, we can use `ls .////`.
Given a command `cmd` of admissible length that is less than 2032 bytes, we want the MAC of `cmd` at position 0. Query the tags of the following messages:
* `tag AAA…` where `AAA…` has the same length as `cmd`.* `tag BBB…B` of length 2048 bytes, then `cmd` followed by its length padding.* `tag BBB…B` of length 2048 bytes, then `tag AAA…` followed by its length padding (which is the same as `cmd`'s).
The xor of these three tags is the tag of `cmd`.
The following program takes a command line as argument, calculates its MAC by sending `tag` commands as described above, and finally runs the command.
    #!/usr/bin/env python3    import os, re, subprocess, sys    import pexpect    from pexpect import popen_spawn
    from fmac import to_blocks, fmac
    # A tag command with the same length as cmdline    def tag_cmd(cmdline):        return b'tag ' + b'A' * (len(cmdline) - 4)
    # A tag command containing the padded cmdline at position 2048    def expand_cmd(cmdline):        return b'tag ' + b'B' * 2044 + b''.join(to_blocks(cmdline))
    # Send tag<|>cmdline    def send(session, tag, cmdline):        session.sendline(tag.encode('utf-8') + b'<|>' + cmdline)
    # Receive input up to a prompt    def receive(session):        session.expect(r'\|\$\|> ')        return session.before
    def find_mac(session, cmdline):        receive(session)        send(session, '', b'tag ' + tag_cmd(cmdline))        mac1 = int(receive(session), 16)        send(session, '', b'tag ' + expand_cmd(cmdline))        mac2 = int(receive(session), 16)        send(session, '', b'tag ' + expand_cmd(tag_cmd(cmdline)))        mac3 = int(receive(session), 16)        return hex((mac1 ^ mac2 ^ mac3) | 1 << 128)[3:]
    def interact(server, cmdline):        session = pexpect.popen_spawn.PopenSpawn(server)        mac = find_mac(session, cmdline)        send(session, mac, cmdline)        sys.stdout.buffer.write(receive(session))
    if __name__ == '__main__':        interact(sys.argv[1], ' '.join(sys.argv[2:]).encode('utf-8'))
Let's see it in action.
    $ ./solve.py 'nc macsh.chal.pwning.xxx 64791' ls .////    __pycache__    flag.txt fmac.py macsh.py    .bashrc    .bash_logout    .profile    $ ./solve.py 'nc macsh.chal.pwning.xxx 64791' cat flag.txt    PCTF{fmac_is_busted_use_PMAC_instead}