Kata

Overview:

There is a secret web server that you are trying to gain unauthorized access too. It so happens that this server authenticates messages it receives with the PKSC#1 v1.5 RSA signature scheme and uses the weak public key exponent, e = 3. There just so happens to be an exploit that lets you spoof signatures for the messages without even needing the private key!

In this kata, you will implement code to exploit a vulnerability found in many implementations of the the PKSC#1 v1.5 RSA signature scheme. Completing this kata will require some basic knowledge of how RSA works. If you are new to RSA or need a refresher on the basics of how it works, see the Wikipedia article: https://en.wikipedia.org/wiki/RSA_(cryptosystem) You may also want to see the RFC about PKSC#1 v1.5 for more information: https://tools.ietf.org/html/rfc3447#section-8.2.2

Background:

When a low public exponent e is used in the RSA key (such as 3, 5, 7, etc.) and the encrypted message is small enough, the encrypted message will be smaller than the public modulus N. When this is the case, simply finding the e-th root is sufficient to decrypt the message. Since the e-th power of the message is not greater than N, the resulting ciphertext does not wrap around N, making it very easy to find the e-th modular root.

For example, if N = 187 and e = 3, the RSA encryption of m = 5 is c = 5^3 = 125. Since the result was greater than (or equal to) N = 187, we do not have to perform mod N on c. Because of this, we can easily retrieve m from c since we know the public exponent e: m = c^(1/e), or the e-th root of c. Thus, we don't even need to know the private exponent, d, to retrieve the original text. This is one of several reasons why plain "textbook" RSA is never used in practice (along with the fact that unlike symmetric ciphers like AES, RSA is deterministic and does not incorporate any randomness).

The PKSC#1 v1.5 RSA signing scheme uses a hash algorithm called SHA-1 (see here for more details on SHA-1: https://en.wikipedia.org/wiki/SHA-1) to make sure that the message was not tampered with, and to only encrypt the hash digest of the signed message (which should be fairly random in its content). When the signature for PKSC#1 v1.5 is received, it is first "encrypted" using RSA, which results in a structured sequence of bytes that has an equal length to the modulus, N, by inserting enough FF padding bytes:

00 01 FF FF FF ... FF 00 (ASN.1 hash identifier) (message hash)

(Note: the ASN.1 identifier for SHA-1 will be given to you in the initial solution)

In many verification implementations of PKSC#1 v1.5, verification failed to tell whether the message hash was appropriately placed, or in other words, whether the signature was correctly padded. Thus, the following would pass for verification:

00 01 FF 00 (ASN.1 hash identifier) (message hash) (padding bytes)

Assuming the public exponent e and message m are small enough such that m^e < N, then this signature is easily spoofed.

Note that since this bug was patched in crypto libraries, a custom verification will be used that still contains the bug when testing your solutions instead of a verification procedure from a crypto library.

Task:

Given the public key (N, e) and and a message, you must successfully spoof a signed PSCK #1 1.5 encryption of the message. For simplicity, use SHA-1 as the hash algorithm. You may use the crypto library in your language to compute the SHA-1 digest. Additionally, you may want to use a library for high precision modular arithmetic (i.e., gmpy2 for Python). Assume that for every public key/message pair given, m^e < N will always hold true.

Hint: when padding bytes at the end of the spoofed signature, you want to keep in mind that when you take the e-th root, you want the prefix to stay the same. This is more likely to happen if the integer value of the bytes is larger.