At 11:53 PM 9/27/2003 +0100, Paul Walker wrote:
Talking to a friend the other day, he was telling me about a potential
loophole with SHA-1 hashes protected by an RSA signature. Basically, he
seemed to think that with an SHA hash of a suitable length (say, 2^20), the
hash could be cubed and still not 'fail', since it was below the key
modulus. If you change the hash length, this problem doesn't occur.
I'm unconvinced for a number of reasons - this sounds very strange to me.
Not least because, even if cubing the hash does work (why cubing?), since
it's infeasible to create a binary which produces a given hash it still
doesn't help.
I think your friend has a very limited understanding of what's going on;
he's right in some small sense, but wrong in practice.
Cubing is coming from the assumption that the public exponent is 3, which
is possible for RSA but rare in practice; 17 or 2^16+1 are much more common
values. It also relies on using some rawly implemented RSA, so that all
that is in the RSA payload is the hash, and nothing else. This violates all
the standards that specify that the payload should be padded with stuff
that, among other things, guarantees that even with an exponent of three,
the answer will have exceeded the modulus and been subject to modular
reduction. So he's talking through his hat.
Could someone help shed some light on this? Either pointing me at a paper
documenting the hole, or confirming that it's gibberish (at which point I'll
go back to work and ask him for more details :).
So, here's the attack. Suppose you have a 160-bit SHA-1 hash of some
document, and it just happens to be a perfect cube (integer-speaking). Then
the cube root of that hash is a valid signature independent of the modulus,
so long as the public exponent is 3. Adding (and checking) correct padding
(eg. OAEP or PSS, see the PKCS standards) makes it extremely unlikely that
there will be a cube root for the attack to work on.
Others may want to correct me or elaborate further, but I think that's correct.
regards,
Greg.
Greg Rose INTERNET: [EMAIL PROTECTED]
Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199
Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/
Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
