crypto_signature

Signature server (crypto, 28 solved, 148p)

Quantum computing is on its way. 
That's why i implemented a post-quantum signature server. 
However, I believe Winternitz checksum can be broken, so I tweaked it a bit. 
Sign all you want, it's free!
nc crypto-02.v7frkwrfyhsjtbpfcppnu.ctfz.one 1337

Analysis

In the task we get the server source code.

We get access to application where we can:

• Send hi message, not very useful.
• Sign some payload
• Execture signed command

There are 2 commands available: switching to admin user and requesting flag. There are checks preventing us from signing either of those commands, at least theoretically.

The commands are:

show_flag_command = "show flag" + (MESSAGE_LENGTH - 9) * "\xff"
admin_command = "su admin" + (MESSAGE_LENGTH - 8) * "\x00"

If we look at how the signature is generated we can see:

def sign(self, data):
    decoded_data = base64.b64decode(data)
    if len(decoded_data) > MESSAGE_LENGTH:
        return "Error: message too large"
    if decoded_data == show_flag_command or decoded_data == admin_command:
        return "Error: nice try, punk"
    decoded_data += (MESSAGE_LENGTH - len(decoded_data)) * "\xff"
    decoded_data += self.wc_generate(decoded_data)
    signature = ""
    for i in range(0, CHANGED_MESSAGE_LENGTH):
        signature += self.sign_byte(ord(decoded_data[i]), i)
    return base64.b64encode(decoded_data) + ',' + base64.b64encode(signature)

It's important to notice here that the check for restricted commands is done before padding the command with \xff. This means we can actually sign show_flag_command with no problem at all, as long as we strip the\xff and just send show flag as payload to sign. Such string will pass the check, and then get padded with \xff, so in the end it will match the original show_flag_command.

This is the simple part, but we can't issue this command unless we're admin. We can't do a similar trick for su admin command, because this one is padded with \x00.

We will actually need to forge the signature somehow for this message.

If we examine closely how the signature is generated we will see that there are 2 parts:

• original payload, padded with \xff if necessary, extended with (presumably) Winternitz checksum
• some strong looking signature done byte-by-byte on the extended payload, however this signature takes into account not only the input byte but also the position of the byte

Both of those have to match, for the command to get executed. However, worth noticing, the server checks them in sequence and tells us which check failed.

Forging checksum

In the code we can see that CHECKSUM_LENGTH = 4. This is not a lot, we could most likely brute-force a 4-byte checksum for string of our choosing, if we could do a local brute-force. But it's remote...

However if we look at results we get from the server, it seems the last 2 bytes are actually always \x00\x00. So we have only 2 bytes to brute-force, instead of 4.

We can, therefore, try to send execute command with admin_command extended with random 2 bytes + \x00\x00 as checksum, and some random signature bytes. We've got only up to 256*256 payloads to send until we find the right checksum. Once we do, the server will complain about incorrect signature, instead of incorrect checksum:

def find_checkum_conflict(s, wanted_msg, signature):
    print("Looking for checksum conflict")
    for a in range(256):
        for b in range(256):
            forged = wanted_msg + chr(a) + chr(b) + "\x00\x00"
            result = execute_command(s, forged, signature)
            if 'wrong signature' in result:
                print('Found checksum conflict for', a, b)
                return a, b

Forging signature

Once we have the correct checksum for the payload, we need a proper signature. During the initial analysis we mentioned that signature is generated byte-for-byte. This is important, because it means that if we sign admin_command with last \x00 removed, we will actually get proper signature for the first 31 bytes, and actually also the last 2 bytes, since the checksum has always last \x00\x00.

What we're actually missing is only signature for 3 bytes -> \x00 at the end of the message and the first 2 bytes of checksum we calculated in the previous step. Again we can use the fact that the checksum has only 2 bytes of entropy. It means there have to be a lot of conflicts - it shouldn't be hard to find an input which gives us the same checksum as the one we calculated before. We can, therefore, sign random payloads ending with \x00 and wait until we get back the checksum we want, and then simply steal the signature bytes for them:

def get_proper_signature(checksum_we_need, s, original_signature_chunks):
    print("Looking for signature suffix for conflicting checksum")
    i = 0
    while True:
        msg = long_to_bytes(i)
        pad = 32 - len(msg)
        msg = msg + ('a' * (pad - 1)) + "\x00"
        result = sign(s, msg)
        ext_msg, signature = map(base64.b64decode, result.split(","))
        if ext_msg[32:36] == checksum_we_need:
            forged_signature_chunks = chunk(signature, 32)
            return "".join(original_signature_chunks[:-5] + forged_signature_chunks[-5:])
        i += 1

Last 5 chunks of the signature are for '\x00'+checksum, so we can take all of them, and combine with original signature we got for the admin_command without last \x00.

This way we get a proper signature, and we can issue admin and flag commands:

def main():
    url = "crypto-02.v7frkwrfyhsjtbpfcppnu.ctfz.one"
    port = 1337
    s = nc(url, port)
    receive_until_match(s, "You can sign any messages except for controlled ones")
    receive_until(s, "\n")
    msg = "show flag"
    show_flag_command = sign(s, msg)
    msg = "su admin" + (32 - 9) * "\x00"
    almost_admin_command = sign(s, msg)
    print(almost_admin_command)
    msg, signature = map(base64.b64decode, almost_admin_command.split(","))
    signature_chunks = chunk(signature, 32)
    wanted_msg = 'su admin\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
    a, b = find_checkum_conflict(s, wanted_msg, signature)
    checksum = chr(a) + chr(b) + "\x00\x00"
    forged_msg = wanted_msg + checksum
    signature = get_proper_signature(checksum, s, signature_chunks)
    print(execute_command(s, forged_msg, signature))
    send(s, 'execute_command:' + show_flag_command)
    interactive(s)


main()

And we get back ctfzone{15de95d830304c6d19c86a559718e935}