Peter Gutmann writes:
> 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 don't think this works. I tried with a 1024 bit key.  We want a cube root of
something between:




But actually the nearest cube root is:


Cubing this gives:


and cubing the next higher value gives:


So no variation on the hash value will produce something that is a
perfect cube.  Now, this is specific to 1024 bit keys, but larger keys
should be even more unfavorable.  As a general rule we can only force
the top 1/3 of the bits to be 1s as required, and the chances of getting
lucky will be worse for larger keys.

We could start adding in multiples of the modulus and look for perfect
cubes again, but basically the odds against are 1 in N^(2/3) so there
is no point.

Hal Finney
PGP Corporation

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

Reply via email to