From: frantz@netcom.com (Bill Frantz)
Date: Tue, 21 Nov 1995 04:09:53 +0800
To: cypherpunks@toad.com
Subject: Virus attacks on PGP
Message-ID: <199511201945.LAA27486@netcom10.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


PGP can be vulnerable to virus attacks.  (Similar attacks can be made on
other cipher systems.) These virus attacks can either be "Get the Key", or
"Subvert the System" attacks.  Schneier's "Rubber Hose" attack and a class
of attack which I will call "Black Bag" attacks are get the key attacks. 
With a black bag attack, victims do not know their keys have been stolen,
and so continue to use them.  (According to "The Puzzle Palace", NSA got
the FBI to perform black bag attacks on embassies in Washington DC.)  I
don't think subvert the system attacks have any parallel in classical
cryptography.


Get the Key Attacks

PGP has three keys: the secret key ring pass phrase, the secret RSA key,
and the IDEA key.  Getting any of them would constitute a successful
attack.

A virus that collects secret key rings and sends their contents somewhere,
either via UDP like messages or by dialing the modem late at night doesn't
seem to much harder to build than one that erases your hard disk.  If it
runs only once per machine, its chances of getting caught are fairly low. 
The standard IP error handling of "throw away the packet" means that it
probably won't be caught by firewalls.  It seems more likely that someone
will catch their computer making an unauthorized 800 number call.  This
attack would allow an opponent to use a brute force attack on the pass
phrase.

Getting the pass phrase or the IDEA key requires that the virus infect
something in the PGP environment.  The infection could be to PGP itself, or
to the operating system in which it runs.  (N.B. Since Mac and PC systems
have only one protection domain, all programs running in them are part of
the operating system for the sake of this analysis.)

Assuming PGP is infected, although similar arguments apply to the operating
system, the possible mechanisms of infection are many:

  A infected PGP binary is installed
  A virus modifies disk copies of PGP
  The OS's loader is infected to modify PGP as it is loaded
  The compiler or linker is infected to modify PGP.

Any of these forms of infection could send pass phrases, secret keys, or
IDEA keys out via IP or modem.


Subvert the System Attacks

The mechanisms of infection are similar to those of the get the key
attacks, but these attacks do not require that the virus send data outside
the machine.  Instead, these attacks act by reducing the size of one of the
three key spaces, making it vulnerable to brute force attacks.  For
example, if the OS provides a "random number" service, then limiting the
randomness of the numbers constitutes an attack.  Making RSA key generation
loosely connected to the date and time constitutes an attack.


Defenses

One standard defense in classical cryptography is to frequently change the
cipher keys.  The PGP web-of-trust makes changing keys difficult, and is
perhaps the weakest part of the overall protocol.

Standard defenses against viruses can help, but if the attacker is
determined and competent, then the virus will not be detected by virus
detection programs, and will not have bugs which cause noticeable ill
effects on infected machines.

Custom changes to things like random number utilities and the PGP code
itself may increase resistance by preventing some of these attacks from
identifying the modified code as its intended target.

Auditing code, preferably object code, can detect infection.  Having ALL
the source code available is almost a requirement here.

Maintaining a file of cryptographic hashs of the IDEA keys used and
checking for duplicates can detect subvert the system attacks on IDEA key
generation at the risk that the cryptographic hash is in fact invertible
and can be used to reveal the IDEA key.

Using operating systems which run in many small protection domains can
limit the opportunity for infection.  One such system I have been involved
with for over 20 years is described at the following WEB sites:
  http://www.cis.upenn.edu/~KeyKOS/
  http://www.webcom.com/agorics/allkey.html

Bill


-----------------------------------------------------------------
Bill Frantz                   Periwinkle  --  Computer Consulting
(408)356-8506                 16345 Englewood Ave.
frantz@netcom.com             Los Gatos, CA 95032, USA