Exponent 3 damage spreads...

[Hal Finney]

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:

0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF003021300906052B0E03021A050004140000000000000000000000000000000000000000

and

0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF003021300906052B0E03021A05000414FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

But actually the nearest cube root is:

0x1428A2F98D728AE223DDAB715BE250D0C288F10291631FBC061800CC36FA2DD3A60B7D03DA26F0840F25C

Cubing this gives:

0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC66E7388AFD22947A600FB19230A3162AB4A53B003B80F979B8E97D7DB74891A5769312C88639E645DD3DB79E32561BD7FF661977573AF888EF025ED0608245DE7048210C94AC32731DD6B19B2F25722E951F41C0

and cubing the next higher value gives:

0x20000000000000000000000000000000000000000000000000000000000000000000000000000000000012A06F78681CDECFB70DC81AEE9F1B2FF7CBB6140D9A07D97209E81A4A2D957560CB04CF8F504EF90797FEBD799E9A64841F1168C13EC938E0D109610B8CC43EF3FDA8B374E3AD57AF2A0E084B15E8BB328384C05

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 majordomo at metzdowd.com