Key Pair Agreement?

[Greg Rose]

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 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 wasabisystems.com