From: Raph Levien <raph@c2.org>
Date: Tue, 2 Apr 1996 20:07:02 +0800
To: mail2news@utopia.hacktic.nl
Subject: "Dead beef" attack against PGP's key management
Message-ID: <199604011958.LAA19153@infinity.c2.org>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

   This post is signed by a forged key for Phil Zimmermann. I forged
the key this morning. The key has the same user id and visible key id
as an old key for Phil Zimmermann, which he has since revoked.

   I should stress that this attack does not in any way weaken the
security of PGP's message formats. However, it does expose a problem
in the user interface of its key management. Namely, it is fairly easy
to forge a key that looks very similar to an existing key. In fact,
the only way to distinguish between real and forged keys in general is
by the fingerprint and keysize together.

   My purpose in posting this is to demonstrate that such forgeries
are possible. The lesson is: please do not use the key id alone to
identify keys.

   Another reason for the public posting of this forgery is to goad
the PGP development team into improving the user interface in PGP 3.0,
so as to make the detection of such a forgery much easier, if not
routine. Derek Atkins has assured me that PGP 3.0 will include a
cryptographic hash of the key, for use as a key id. If implemented
properly, such a facility would address this attack.

   I am not the first to propose this attack. According to Derek
Atkins, Paul Leyland first proposed the attack two years ago. Also,
Greg Rose successfully mounted a similar attack six months ago,
creating a key with user id 0xDEADBEEF, thereby giving rise to the
name.

   The pseudocode for the attack is as follows:

      choose random 512 bit prime p
      choose random 480 odd x
      q = x * ((0xdeadbeef * (p * x) ^ -1) mod 2^32)
      do {q += 2^32} while q composite

   The above bit of pseudocode replaces the original selection of p
and q, which are normally just random 512 bit primes. Without having
done detailed analysis, I believe that the resulting forged keys are
just as good as ordinary PGP keys. Further, the modified key
generation is almost as fast as ordinary PGP key generation, and I
think I could speed it up a bit more.

   The attack took me a few hours to design and code. Any good
programmer familiar with PGP could duplicate it easily.

   One practical application of this attack is to implement a certain
degree of "stealth." Since PGP includes the key id in encrypted
messages, it is in most cases possible to identify the recipients of
encrypted messages. However, if a lot of people generated keys with
the same key id, then it would not be possible to tell from the
encrypted message which one was the intended recipient.

   Here's the public key I forged, which can be used to check the
signature of this message:

Key for user ID: Philip R. Zimmermann <prz@acm.org>
1024-bit key, Key ID FF67F70B, created 1992/07/22
Also known as: Philip R. Zimmermann <prz@sage.cgd.ucar.edu>
- -----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.6.2

mQCNAyptNMAAAAEEALRhS3ZCFKLPNF/fZeluh/rNfpgZ5a0ddTBtxJ+1yLIkVurb
HWFFBsrmnA4hU4MhlA8DS/f2gnS0v3zyQ78JOY1SBIJrLdaIPIrh0ZTAZXWoQWDe
Qknm1ZgyLkIRJlt5aDLp+iLJ5sc+LSO5N/DtrL+Htc5MF0AVAWtzPhz/Z/cLAAUR
tCJQaGlsaXAgUi4gWmltbWVybWFubiA8cHJ6QGFjbS5vcmc+iQCVAwUQMWAremtz
Phz/Z/cLAQE//AP/bg9gMOuiBYkFCiyarJ/DIARWDf7e4bWFJloXAyPeBXCITDIw
tuHRJ41yFqnlLmdcuVhXQf/xrH248JyWpHqqED6eOU/PnBHo9IR6H0Fts+O3I+vk
tOYRjuTJy+6JV0s/8VN/Sgh8y6Jm2FGhhzhCp6KHNcTHpUud6iGScaEs/CG0LFBo
aWxpcCBSLiBaaW1tZXJtYW5uIDxwcnpAc2FnZS5jZ2QudWNhci5lZHU+
=Z1mf
- -----END PGP PUBLIC KEY BLOCK-----

Raph Levien

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBMWA2pGtzPhz/Z/cLAQELEQP/fam4tHS8TlMy7SFoUZvC0C4q0ID9Ze5W
rY2D++df4UtAFDITGs4lQqzeq6YCqk51oT8gZAACK6D6UlFgr5roIbgwa74Fxso1
B5mquC9axlOlxZJI1PuK+NflBJqCokuQGtG95ER6vbm4n4RACW43In9SAatIvduN
JfBSLYrAr14=
=V5U6
-----END PGP SIGNATURE-----