Article 36772 of alt.security:
Path: ix.netcom.com!ix.netcom.com!ix.netcom.com!ixnews1.ix.netcom.com!howland.reston.ans.net!spool.mu.edu!usenet.eel.ufl.edu!bofh.dot!newsfeed.internetmci.com!news.msfc.nasa.gov!sol.ctr.columbia.edu!news.cs.columbia.edu!news.cs.columbia.edu!news-not-for-mail
From: ayoung@news.cs.columbia.edu (Adam L. Young)
Newsgroups: talk.politics.crypto
Subject: Backdoor in RSA Discovered
Date: 28 May 1996 16:15:45 -0400
Organization: Columbia University Department of Computer Science
Message-ID: <4ofmth$lft@ground.cs.columbia.edu>
NNTP-Posting-Host: ground.cs.columbia.edu





In CRYPTO '96 Dr. Moti Yung and I (Adam Young) will be
presenting the following paper:

A. Young, M. Yung, "The Dark Side of Black-Box Cryptography -or-
Should We Trust Capstone?", CRYPTO '96, Springer-Verlag.

In this paper we present a mechanism that can quite easily be
added to PGP that allows the person who modifies PGP to learn
the private keys of those who use it to generate keys. Furthermore
the keys are leaked securely and subliminally, i.e. even if you
analyze the source code you cannot determine previously generated
keys or future keys, only the attacker can. The only way to detect the
presence of the mechanism itself is by looking over the source code, or
the compiled code. The attack has the effect of turning a database of
public keys into a database of public/private key pairs with respect to
the attacker *exclusively*.

We are posting this article to forewarn people of these new
attacks. It is now imperative to have trust in those who install PGP for
other users, since a SETUP can easily be added, and is only identifiable
in source by those knowledgeable in programming and in Cryptography.
Recovering a users private key amounts to simply looking up the users 
public key, and so, an attacker (or employee) can compromise security
with little risk of getting caught. We are particularly concerned
for corporations that may have PGP installed on a large scale by a
small handful of individuals.

We discovered SETUP attacks soon after we discovered cryptovirological
attacks over a year ago. A cryptovirus encrypts user data using the
authors public key. This can be used for extortion, since only the virus
writer knows the private key. Similarly, a cryptotrojan is a trojan
horse containing the authors public key. Adding a SETUP to PGP amounts to
adding a cryptotrojan to PGP. Cryptotrojans and cryptoviruses are
defined in:

A. Young, M. Yung, "Cryptovirology: Extortion-Based Security Threats and
Countermeasures", Proceedings of the 1996 IEEE Symposium on Security and
Privacy, pp. 129-140, May 6-8, IEEE Computer Society Press, 1996.

And were first mentioned in:

A. Young, "Cryptovirology and the Dark Side of Black-Box Cryptography",
Masters Thesis, Comp. Sci. S6902, Columbia University Dept. of Computer
Science, Summer '95. Advisor: Moti Yung. 

The SETUP attacks were also described in the Masters Thesis. The 
two conference papers are currently available in .ps form at:

http://www.cs.columbia.edu/~ayoung

adam