deadbeef attack was choose low order RSA bits (Re: Key Pair Agreement?)

[Adam Back]

On Mon, Jan 20, 2003 at 09:08:31PM -0500, Radia Perlman 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.

One cheap way the low order 64 bits can be set is to set the low order
bits of p to the target bitset and the low order bits of q to ...00001
(63 0s and one 1 in binary), and then to increase the stride of
candidate values in the prime sieve to be eg 2^64.

This was the method used in the deadbeef attack on pgp 2.x keyids.
pgp 2.x uses the least significant 64 bits as a keyid, and being able
to easily generate keys with the same keyids can be a nuisance for
keyservers and databases and could possibly confuse a user who
incorrectly though they unique.

(The intended unique id value is the pgp fingerprint, but in 2.x this
had problems, see:

http://216.239.53.100/search?q=cache:BcFAtn404nAC:cypherpunks.venona.com/date/1997/06/msg00523.html+dead+fingerprint+%22adam+back%22&hl=en&ie=UTF-8

).

Adam

> As for Jack Lloyd's solution...I was also thinking
> of something based on Diffie-Hellman, and was going
> to suggest that Scott supply the prime p. I'd have
> had Scott generate p (as with PDM). If Alice also
> needs assurance that p isn't funny somehow, then she
> could specify the high order bits of p to Scott, or
> Scott could provide the seed to Alice from which he
> generated p. But that would force Alice to do a lot
> of work. I sort of like making it cheap for Alice,
> and making Scott, who is making Alice jump
> through hoops for no discernible reason, do a lot
> of work.
> 
> Radia
> 
> 
> "David Wagner" <daw at mozart.cs.berkeley.edu> wrote:
> >Jeroen C. van Gelderen wrote:
> >>Here is a scenario: Scott wants Alice to generate a key pair after 
> >>which he will receive Alice's public key. At the same time, Scott wants 
> >>to make sure that this key pair is newly generated (has not been used 
> >>before).
> >
> >You might be able to have Scott specify a 64-bit string, and then ask
> >Alice to come up with a RSA public key that has this string as its low
> >64 bits.  I believe it is straightforward to modify the RSA key generation
> >algorithm to generate keypairs of the desired form.
> >
> >If you're worried about the security of allowing Scott to choose the
> >low bits of Alice's public key, you could have Scott and Alice perform
> >a joint coin-flipping protocol to select a random 64-bit string that
> >neither can control, then proceed as before.
> >
> >I haven't worked out all the details, but something like this might
> >be workable.
> >
> >In practice, you might also want to confirm that Alice knows her private
> >key (i.e., has ability to decrypt messages encrypted under her public
> >key).
> >
> >---------------------------------------------------------------------
> >The Cryptography Mailing List
> >Unsubscribe by sending "unsubscribe cryptography" to
> >majordomo at wasabisystems.com
> 
> 
> 
> ---------------------------------------------------------------------
> The Cryptography Mailing List
> Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com