RSA Signature Forgery - Low Public Exponent + Improper Padding Validation? [duplicate]

Consider the following custom crypto:

• We have a signed message M1 with corresponding signature S.
• We have the 1024-bit modulus N and their small public exponent e (with an exact value of 3).
• The message M1 is 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, M2?

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.

• @SqueamishOssifrage - That does seem promising. However, it seems to lack some pertinent details, such as how to solve $x^3 = h \pmod{2^n}$ and whether or not the technique works for higher exponents. – Mr. Llama Apr 7 '19 at 17:51
• Start by solving ${x_1}^3 \equiv h \pmod 2$; then iteratively solve ${x_{i+1}}^3 \equiv h \pmod{2^{i + 1}}$ by trying $x_{i+1} := x_i$ or $x_{i+1} := x_i + 2^i$, until you have $x_{160}$. This will work as long as $160\cdot e$ fits within the width of the modulus, so with a 2048-bit modulus it works up to $e = 11$, with 3072-bit up to 19, and with 4096-bit up to 25. – Squeamish Ossifrage Apr 7 '19 at 20:26
• @Mr.Llama Also check out my answer to the nearly-identical question crypto.stackexchange.com/questions/68745/… – Myria Apr 15 '19 at 19:55