0xkasper

CSCBE 2020 Qualifiers Write-Up

· ctf, crypto

Introduction

The Cybersecurity Challenge Belgium (CSCBE) is a CTF for students at Belgian universities. Although I’m not Belgian, I do study in Belgium, so I was able to participate. I did not have a team and played by myself, so I couldn’t score as many points and unfortunately did not qualify for the finals in Brussels. Nonetheless, there was one interesting challenge of which I want to share my solution with you.


Cryptography


A Pirate’s Life For Me

For this challenge we were given a challenge.py and a valid hash. Our task was to forge a signature for this specific hash, such that the server could verify it and give us the flag. The signature is supposed to be generated from a few specific bytes and the ASN.1 byte sequence as header, followed by the hash and then encrypted with RSA.

RSA is public-key cryptography, which means that someone can generated a new public and private key pair and where something encrypted with this public key can only be decrypted with its paired private key. It’s practically impossible to calculate the private key from the public key, which makes it secure. The person who generated the keys has to keep the private key secret (hence the name private key) and distribute the public key. Now people can encrypt something using the public key and safely send it to the person with the private key. With digital signatures it’s the other way around. To verify that something, e.g. a message, is originated from me, I have to encrypt it with my private key and append that ciphertext to the message. This ciphertext is my signature, since anyone can decrypt with my freely available public key, resulting in the message and thus people can confirm that I signed it.

Now, for this challenge we are given the modulus and the public key. As you can see in challenge.py, this public key exponent is only 3. An exponent of 3 works, but it’s not always secure. As I explained, we have to generate the signature for the given hash. But to generate the signature we need to encrypt the hash with the private key, since the server will use the public key to decrypt it. However, since the public key is only 3, we might be able to first construct a signature that adheres to the server’s requirements and then send the cube root of this number. This won’t give us a perfect signature, but because of a mistake in the signature verification function in the server, this doesn’t matter.

To verify the signature, the server first decrypts the given signature using the public key exponent (which is just taking a power of 3). It then checks if the result is 256 bytes and if the first two bytes are equal to 0x00 and 0x01. After that it looks for the next 0x00 byte and checks if all bytes before this zero byte are equal to 0xFF. Now, normally the number of 0xFF bytes matters, but this server doesn’t actually check the length, it just looks for the 0x00 byte. We can therefore just send one (or even zero) 0xFF byte. After that, it checks if the ASN.1 byte sequence is present and finally the actual hash.

So two bytes (0x00 and 0x01), one 0xFF byte, one 0x00 byte, the given ASN.1 sequence of 15 bytes and the hash of 20 bytes gives us a signature of 39 bytes. So that leaves 217 bytes for garbage because if doesn’t check the length of the 0xFF sequence. Now we can use a cube root, because we don’t care if some of the garbage bytes won’t be preserved.

from gmpy2 import mpz, iroot
from base64 import b64encode, b64decode

def cube_root(n):
    return int(iroot(mpz(n), 3)[0])

H = bytes.fromhex('3F34564B0A1FB3AFE3676911FF990B3127BEC0C2')
ASN = b'0!0\t\x06\x05+\x0e\x03\x02\x1a\x05\x00\x04\x14'
MODULUS = 0xE4D114A8D6BDA750718DC4865391DEAF71CDA4624DC92FC720B7C27A1E254F1F73F86888FFB37816ABB2BEDF98DFD35EDB10C40A05C7BE6D881E4C3F1C881E71026B5386E60A76AD5273B446D79901E5557BF1850C726EAEABCF7212F0C6173A61B8C1EF197DA2ACFA3A083FAA7F6246948E263F8F8CEA77562AC990090BB8F80C891ED8732AEE829D4850D8BE54C40F6051FDE7F6A8BA1A0E598EE67582E9FCD998480C23B7B987B830D94B6D054FC98DBD5E77620742524A876FBC7F189987600ABB7BE222C6700AFAE8E6DA3FB442BB772D5ECE4356C552293C2C102A14A2B59434941453E54E1D2F0E677E6E05F2CFA6BDEF8F794DED7F6477CD014C7A8D
EXPONENT = 3

prefix = b'\x00\x01\xff\x00' + ASN + H
garbage = (256 - len(prefix)) * b'\xfe'
signature = prefix + garbage
cbrt = cube_root(int.from_bytes(signature, 'big'))
decrypted = pow(cbrt, EXPONENT, MODULUS).to_bytes(256, 'big')

print(f'The signature is preserved: {prefix == decrypted[:len(prefix)]}')
print(b64encode(cbrt.to_bytes(256, 'big')).decode())

So we first construct the prefix that will pass us through the signature verification on the server. Then we fill it up to 256 bytes with garbage. After that we take the cube root and check if the first 39 bytes of the cube root decrypted with the public key exponent of 3 is equal to the prefix. If so, the server will accept the signature and give us the flag. And guess what, it did.