Consider the following custom crypto:
- We have a signed message
M1with corresponding signature
- We have the 1024-bit modulus
Nand their small public exponent
e(with an exact value of 3).
- The message
M1is too large to sign directly, so instead they sign the SHA1 hash (160 bits) of the message. The SHA1 hash forms the least significant bits and the remaining 864 bits (i.e. 1024-160) are zeroes.
So far, so good.
However, the signature verification is flawed:
- To verify the signature, we calculate
S^e mod N.
- We don't verify all of the padding is zeroes. Instead, we XOR the 160 lowest and 160 highest bits, then compare that result with
SHA1(M1). If the results match, we trust the signature.
The XOR is so that if any of the high 160 bits are non-zero, the XOR would damage the results of the low 160 bits (the SHA1 hash).
Question: given this flawed signature verification, how would you go about forging a signature for a different message,
If they key used a slightly larger public exponent, say 17, would the forgery be much harder?
Here's what I've come up with so far:
We don't need the forged signature to be perfect. The obvious goal is to create a signature that, after exponentiation, results in (from most to least significant bits):
[- 160 zero bits -] [---- 704 arbitrary bits ----] [- correct 160-bit hash -]
In practice, this means the forged signature needs to be:
- Somewhat small, so after exponentiation, the high 160 bits are all zero. (i.e.
S^e mod M < 2^864)
- After exponentiation, it only needs to end with the correct 160 bits. (i.e.
S^e mod M mod 2^160 = SHA1(M2))
As the attacker, we can append random bytes to
M2 to generate different hashes, but we cannot predict the resulting SHA1 hash. This gives us the ability to create SHA1 hashes with desirable properties, although I'm not sure what properties would be helpful. (Factors into small primes?)
In a perfect world, we would simply keep trying new messages until we generate a hash that has an integer 3rd or 17th root, but this seems extremely unlikely.
Instead, I was thinking of taking the hash and prepending up to 704 bits so the resulting number does have a 3rd or 17th root.
This seems like a good candidate technique given that the ratio of fixed bits (160) is small in comparison to the number of free bits (704).
Unfortunately, I'm not sure how to construct such a number and brute force is too slow for a 2^704 search space.