**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.

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**