A quick question...

[Greg Rose]

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