Exponent 3 damage spreads...

[Greg Rose]

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.

Greg.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com