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 [EMAIL PROTECTED]