At 23:40  +1200 2006/09/14, Peter Gutmann wrote:
But wait, there's more!  From what I understand of the attack, all you need
for it to work is for the sig.value to be a perfect cube.  To do this, all you
need to do is vary a few of the bytes of the hash value, which you can do via
a simple brute-force search.  So even with a perfect implementation that does
a memcmp() of a fixed binary string for all the data present but the hash, the
attack still works.

I thought this for a while, but no, it isn't true. Take a number k, which is of the order of 2^1008 (which is what a properly padded 1024-bit RSA signature will look like numerically). So the cube root of K is a real number of the order of 2^336... call this k'. Now on average it will be within +/- 0.25 of the nearest integer, so for sake of argument let i = k' + 0.25 be an integer.

i^3 - k = (k' + 0.25)^3 - k
        = k + 0.25*k'^2 +0.0625*k' + 1/64 - k

which is of order 0.25*k^2/3, ie, 2^670. Unless you are using very large hashes indeed, the chance of a properly padded RSA signature being a perfect cube is vanishingly small.

In either of these cases, RSA e=3 is dead.  Obesa cantavit.

I don't yet agree with this conclusion.

  There'll always be broken standards out there that require e=3 (I know of
at least one that uses e=2, and another that uses raw, unpadded RSA, and
another that... well you get the idea), but the only quick, sure fix is to
kill e=3, not to try and anticipate every potential way of trying to use it,
because you'll never be secure that way.

I just have to mention that e=2 is Rabin signatures, and they have different and very stringent requirements for signatures. Maybe the same problem exists, maybe it doesn't, I don't know.


The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Reply via email to