4
$\begingroup$

I assume that most of you know this, but just for the sake of context; Bleichenbacher's signature forgery (https://www.ietf.org/mail-archive/web/openpgp/current/msg00999.html) basically abuses implementations that do not check that the PKCS#1 1.5 padding of a decrypted signature is correctly layed out. Most vulnerable implementations accept cases where the embedded hash is not right-justified. With a reduced padding, the hash can be moved forward (more to the left) then the remaining bytes can be treated as "garbage", which in turn make enough room for organizing so that this number is a perfect cube. In case of public exponent 3, it means that the cuberoot of the latter number is a valid signature as seen by the wrong implementation. Actually what happens is that you're basically good with the rounded cube root of a number of your choice of the form (line29, https://github.com/akalin/cryptopals-python3/blob/master/challenge42.py), and cubing it only messes up the garbage digits/places anyway.

Now, I'm wondering about the case where an implementation does check that the hash is right-justified, but doesn't check the previous bytes at all. Assuming that we're still talking about exponent 3, someone could imagine that there might be a way to find a perfect cube that ends with that particular hash, thereby utilizing the more significant digits that are not checked by the code. On the other hand, the ending digits are already restricted just by the value being a cube number. Let hashlen be the length of the hash in bits, and rsalen the much bigger length of the signature. Giving up on forging a signature for a particular hash, my intuition would tell me that if you take the last hashlen bits of the possible cube numbers for the signature (for which there are possibilities on the order of 2^1/3*rsalen*) then this set would have a non-negligible intersection/overlap with the possible hash values of size hashlen. Is it possible to sign some message feasibly by somehow utilizing the structure of the particular hash in context of these (hash, perfect cube) pairs? Conversely, is there a quick and profound argument that shows that the outlined "signature checking" (looking at only the hash at the end) does not weaken the implementation?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

Now, I'm wondering about the case where an implementation does check that the hash is right-justified, but doesn't check the previous bytes at all.

That case is completely broken for $e=3$

Assuming that we're still talking about exponent 3, someone could imagine that there might be a way to find a perfect cube that ends with that particular hash, thereby utilizing the more significant digits that are not checked by the code.

That actually pretty easy, with the assumption that the lsbit of the hash is a 1 (or more generally, that the number of 0's at the end of the hash is a multiple of 3); this assumption is necessary, because if it is not true, no perfect cube will exist. It turns out if this assumption is true, then a cube will always exist.

The most straight-forward approach to find it is to do it iteratively; if we have a value $x^3 = h \pmod{2^n}$, then we can easily find a value $y^3 = h \pmod {2^{n+1}}$, as either $y = x$ or $y = x + 2^n$, and it's easy to check which one it is. So, we just start with a small $n$, and just repeatedly add bits to $x$ until, when cubed, it generates the entire hash in its $n$ least significant bits.

Is it possible to sign some message feasibly by somehow utilizing the structure of the particular hash in context of these (hash, perfect cube) pairs?

The above procedure works for more than half of all possible messages (assuming the hash function acts as random), hence the attacker can easily pick a message that he likes.

Improve this answer
$\endgroup$
5
  • $\begingroup$ How would one go about initially solving $x^3 = h \pmod{2^n}$? How would (or wouldn't) this method work if a higher exponent were used, say 17? $\endgroup$
    – Mr. Llama
    Commented Apr 7, 2019 at 17:50
  • $\begingroup$ @Mr.Llama: suppose we had a magic oracle that was able to solve $x^3 = h \pmod{2^{n-1}}$; how would you use that to solve $x^3 = h \pmod{2^n}$? How would you then use that to solve $x^3 = h \pmod{2^{n+1}}$ (and so on...)? $\endgroup$
    – poncho
    Commented Apr 7, 2019 at 17:59
  • $\begingroup$ @Mr.Llama: as for higher exponents, say, 17, the same technique works; however if find a 256 bit value x with $x^3 = h \pmod{2^n}$, that gives us a forgery only if $x^{17}$ (circa 4350 bits) is smaller than the RSA modulus $\endgroup$
    – poncho
    Commented Apr 7, 2019 at 18:02
  • $\begingroup$ @ponco - Maybe I'm misunderstanding. If we had an oracle that could solve $x^3 = h \pmod{2^{n-1}}$, then the suggested technique of extending the solution to $y^3 = h \pmod{2^{n}}$ only seems like it would work around half the time, right? We'd need the next most significant bit to match that of our target hash, but if we need the new MSB to be zero and $y = x + 2^n$ is the next cube, we'd be out of luck. $\endgroup$
    – Mr. Llama
    Commented Apr 7, 2019 at 18:11
  • $\begingroup$ @Mr.Llama: if you know that $x^3 = h \pmod{2^{n-1}}$, then you know the solution to $y^3 = h \pmod{2^n}$ is either $y = x$ or $y = x + 2^{n-1}$. I believe that a brute force search to find the correct $y$ value may be feasible... $\endgroup$
    – poncho
    Commented Apr 7, 2019 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.