[12331] in cryptography@c2.net mail archive
Re: Key Pair Agreement?
daemon@ATHENA.MIT.EDU (Greg Rose)
Tue Jan 21 18:16:05 2003
X-Original-To: cryptography@wasabisystems.com
X-Original-To: cryptography@wasabisystems.com
Date: Wed, 22 Jan 2003 07:47:34 +1100
To: <radia.perlman@sun.com>
From: Greg Rose <ggr@qualcomm.com>
Cc: "David Wagner" <daw@mozart.cs.berkeley.edu>,
<cryptography@wasabisystems.com>
In-Reply-To: <200301210208.h0L28Mj02804@sydney.East.Sun.COM>
At 09:08 PM 1/20/2003 -0500, Radia Perlman - Boston Center for Networking
wrote:
>I was going to suggest something similar to what
>David Wagner suggested, but with Scott telling Alice
>the modulus size and the *high* order 64 bits (with the
>top bit constrained to be 1). I can see how Alice
>can easily generate two primes whose product will have
>that *high* order part, but it seems hard to
>generate an RSA modulus with a specific *low* order
>64 bits.
This is the essence of the "DEADBEEF" attack on PGP. PGP used the least
significant bits of the modulus as the key ID. If you want to create a key
with a particular key ID, you just hack the code so that it checks for
primes that end in things which will multiply together to yeild the desired
answer; the easy case, of course, is 0x00000001 and 0xDEADBEEF, which is
what was done to create the Prime Rib Lovers' key as a proof of concept[*].
There does not appear to be any significant erosion of security, although
I'm not sure if anyone's thought too seriously about that specific case either.
regards,
Greg.
[*] I note that there are three keys on the us.pgp.net server with
0xDEADBEEF as their key ID (including the one mentioned above), and one of
them is even a DSA key! I can only assume this was brute forced through the
hash function.
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@wasabisystems.com
