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]
