[14326] in cryptography@c2.net mail archive
Re: A quick question...
daemon@ATHENA.MIT.EDU (Greg Rose)
Sun Sep 28 20:42:22 2003
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Mon, 29 Sep 2003 08:33:59 +1000
To: Paul Walker <paul@black-sun.demon.co.uk>
From: Greg Rose <ggr@qualcomm.com>
Cc: cryptography@metzdowd.com
In-Reply-To: <20030927225308.GC8819@black-sun.demon.co.uk>
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: ggr@qualcomm.com
Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199
Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/
Gladesville NSW 2111 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
