I have been reading as much as possible, but I haven't so far found anything exactly like what I'm looking for. I have a couple of questions (given what I know below):
- One, is it possible to find d?
- If not, is there a practical way to forge a signature for an arbitrary message?
We all know the textbook RSA signature is:
σ = m^d mod N
Now, typically m is padded to avoid specific attacks. Also, I presume m is not normally known to an attacker (since it should be padded), only σ, e, and N.
In this case however, m is not padded at all - it's just an MD5 hash, which I can easily reconstruct. Additionally, I have many other signatures that were created with the same key and exponent. d is 1024 bits.
So since I know σ, m, N, and e=7, is it possible to reconstruct d? It doesn't appear to be possible, but my understanding is fuzzy at best.
A few attacks so far I have read about (this is a vast subject, there were more):
- Meet in the Middle
- Signature forgery
- Chosen Message (basically same as above)
- Small Exponent attack
- Common Modulus
- CRT Theorem
And obviously, brute force factoring of n - which is still not possible.
It seems to me that a likely option is signature forgery. The answer here seems like it's pretty complete, but I'm still trying to decipher it: RSA 1024 bit forge a new matching signature from a chosen message
The other possible attack I could think of would rely on the fact that I have ~100 valid signatures for the same key. The chosen message attack seems closest: Chosen-Message-Attack RSA-Signature
But it doesn't seem like the message can be arbitrary.
edit: I have remembered something else that might be helpful.
One of the key flaws in this RSA implementation (other than the lack of padding) is the signature verification step. I can change the definition of the size (and location in memory) of the message that the verification routine uses to calculate the MD5.
Indeed, this has already been used in some cases to permanently disable the RSA verification process from running in the future, by pointing it to a copy of the original message that already has a valid signature, fooling it into believing the actual message is valid.
The problem is that it's not always possible to alter the size/location of the message. And sometimes it's also not possible to disable the RSA verification process - the only options are a forgery or recovering d.
