Rating: 5.0
# 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](signature.py).
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:
```python
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:
```python
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:
```python
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:
```python
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:
```python
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}`