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