EnoWars CTF – Get On Board (500)

Category: crypto

There is also this nice new spaceship in the hangar just waiting for us. Some old-school mobil terminal describes it as:

“The Heart of Gold is the sleekest, most advanced, coolest spaceship in the galaxy.

“Its stunning good looks mirror its awesome speed and power. It is powered by the revolutionary new Infinite Improbability Drive, which lets the ship pass through every point in every univese simultaneously.”
It looks a bit out of place in this death moon, but why should we not use it. After entering the ship (spaceship.ivs.tu-berlin.de:1337) you realize that it fails to start due to a simple bug in the code. But again you are lucky and find a printed copy of the source code of the signature verification system.

verify.pl
spaceship_firmware

When we connect to the specified server, we receive a message, that “launch()” is deprecated and we should use “launchSpaceship()” instead. Also a connection is closed but we receive ftp credentials to a server, from which spaceship_firmware and spaceship_firmware.sig files are downloaded. So we have to replace “launch()” with “launchSpaceship()” and generate a valid signature for it.

Let’s take a look at the signature verifying code:

sub verifySignature{
    my($firmware,$firmwareSignature) = @_;
    my $shaRealValue = sha256_hex($firmware);
    # 8192 bit RSA should be enough (unless those damn hackers have brought a quantum computer with them).
    my $n = new Math::BigInt("0xda78cdbdee8067fb2...6ca8697");  # shortened
    my $e = new Math::BigInt("0x11");
    # Validate that the signature isn't too long and contains only valid characters
    if(length($firmwareSignature) > 5000 or $firmwareSignature !~ /^0x[0-9a-f]+$/){
	return 0;
    }
    # Convert the hexadecimal signature to a Math::BigInt number
    my $signature = new Math::BigInt($firmwareSignature);
    # Do the RSA Operation: $signature = ( $signature ** $e ) % $n
    $signature->bmodpow($e,$n);
    # The lower 256 bits (64 hex digits) should be equal to the sha256 value of the firmware.
    my $shaExpectedValue = substr($signature->as_hex(),-64);
    if($shaExpectedValue eq $shaRealValue){
	return 1;
    } else{
	return 0;
    }
}

So it’s basic RSA signature scheme with sha256 hash function, 8192 bits prime (ouch) and public exponent 0x11=17.

The mistake is here:

    my $shaExpectedValue = substr($signature->as_hex(),-64);

It means that only the last 64 hexes (256 bits) of the resulting number are meaningful. It’s ok if we pass a valid signature: all those bits would be nulls and cutting them off wouldn’t be wrong. But if we pass a “bad” one – due to mistake it can be accepted.

So, what do we have?

We know a hash of our message, and we must find such x that

$(x^{17} \bmod n) \bmod 2^{256} == hash$, where n is 8192 bit number.

If we take a number from range 0; 2^256, in 17th power it will take at most 17 * 256 = 4352 bits. So, then

$$x^{17} \bmod n = x^{17}$$

and our equation becomes:

$$x^{17} \bmod 2^{256} == hash$$

We can think it as 17-th root of hash modulo $2^{256}$, but thinking in RSA way is easier: we just replace original modulus (8192 bits) with $2^{256}$ and that is. We know it’s factorization, so we can easily find a secret exponent and sign the hash:

$$\phi(2^{256}) = 2^{255}*(2-1) = 2^{255}$$

$$d = e^{-1} \bmod \phi = 17^{-1} \bmod 2^{255}$$

$$x = hash^d \bmod 2^{256}$$

But there’s one problem: hash must be coprime to $2^{256}$, which means that we can sign only odd hashes in such way. Luckily, 50% of them are odd, so we can change a firmware (e.g. add some newlines) until we can sign it.

s = open("spaceship_firmware").read()
h = int(hashlib.sha256(s).hexdigest(), 16)
d = invmod(17, 2**255)
sign = pow(h, d, 2**256)
print hex(sign)
open("spaceship_firmware.sig", "wb").write(hex(sign).rstrip("L"))
print pow(sign, 17, 2**256) == h

$ py makesig.py
0x0L
False

Ouch.. Add a newline at the end of file

$ echo >>spaceship_firmware
$ py makesig.py
0x13b74ec3c4d771a3d023aa7cd419d74699a5e0b8194d868f29e6b8858ad50575L
True

Woohoo!

$ perl verify.pl spaceship_firmware
Signature verification ok

Great! Upload it to ftp (don’t forget to do it in a binary mode, because some \r symbols can spoil the hash).

Then, you get a nice ascii art with a flying flag: enod08c07f9fb3a4480a0e007ecff93773e72c78