Exponent 3 damage spreads...

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:

0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFF003021300906052B0E03021A050004140000000000000000000000000
000000000000000

and

0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFF003021300906052B0E03021A05000414FFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFF

But actually the nearest cube root is:

0x1428A2F98D728AE223DDAB715BE250D0C288F10291631FBC061800CC36
FA2DD3A60B7D03DA26F0840F25C

Cubing this gives:

0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFC66E7388AFD22947A600FB19230A3162AB
4A53B003B80F979B8E97D7DB74891A5769312C88639E645DD3DB79E32561
BD7FF661977573AF888EF025ED0608245DE7048210C94AC32731DD6B19B2
F25722E951F41C0

and cubing the next higher value gives:

0x2000000000000000000000000000000000000000000000000000000000
0000000000000000000000000012A06F78681CDECFB70DC81AEE9F1B2FF7
CBB6140D9A07D97209E81A4A2D957560CB04CF8F504EF90797FEBD799E9A
64841F1168C13EC938E0D109610B8CC43EF3FDA8B374E3AD57AF2A0E084B
15E8BB328384C05

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 majordomometzdowd.com