From: Damaged Justice <frogfarm@yakko.cs.wmich.edu>
Date: Fri, 24 Jan 1997 15:29:20 -0800 (PST)
To: frogfarm@yakko.cs.wmich.edu
Subject: (fwd) Re: PGP implementation source code
Message-ID: <199701242329.PAA11838@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


[The discussion started with Pretty Safe Mail, the recent "PGP-compatible"
Mac program, and whether or not it was safe. Source code is not available.
Some authors noted that PSM was much slower than PGP, but so far lives up
to its promise of user-friendliness. A Win95 version is in the works.]

>From: Ian_Miller@bifroest.demon.co.uk (Ian Miller)
Newsgroups: comp.security.pgp.discuss,comp.security.pgp.resources
Subject: Re: PGP implementation source code (was "Imminent Death of PGP?" revisited)
Date: Fri, 24 Jan 1997 19:55:46 +0000
Lines: 66
Message-ID: <AF0EC44296683DACD@bifroest.demon.co.uk>

In article <5c2kap$1tu@topcat.uk.gdscorp.com>,
Steve Gilham <steveg@uk.gdscorp.com> wrote:

>PGP defines, but, IIRC does not inspect, a comment packet type.  This
>packet type could be added to a .pgp file and contain anything the
>implementor  wished (your plaintext secret key if it has been used in
>this instance of the program, any IDEA key used, your passphrase, if
>given) without any standard PGP implementation being aware of it 

The IDEA initialisation vector could also be used as a subliminal channel,
it is only 8 bytes but it could (for example) leak a random 60 bits of one
prime in your secret key with the remain 4 bits saying which set of 60
bits. 

Worse is the possibility that the program could put a back door into RSA
key generation to make the modulus trivially factorisable by someone in the
know.  There are a number of mechanisms for this of varying detectability
up to detectable only by reverse-engineering.
Here are some of the (endless) possibilities in order of increasing
sophistication:-
1) Make one of the primes a constant.  Factorise by dividing by this
number.  Detectable by inspection of public keys alone.  (For more details,
see my article "There are no common factors in the Public keyring", 13th
Jan in comp.security.pgp.announce.)

2) Select the first prime P at random but make second prime Q the smallest
prime larger than PK where K is a constant.  Factorise by searching from
root(N/K).  Probably detectable by suitable inspection of several secret
keys generated by the product, but (I think) undetectable from public keys
alone.

3) Select a random seed and using a good PRNG, make the rest of generation
process deterministic based on the seed.  Use the "deadbeef" technique to
select a modulus that has this seed as its least significant bytes. 
Factorise by extracting the seed from the modulus and repeating the
deterministic key generation.  This is detectable only by reverse
engineering.

4) Select a random seed and use a short key PKE key exchange system (e.g.
Elliptic curve) to generate a session key and a key exchange cyphertext. 
Use a key generation similar to (3) except that you seed the PRNG with the
session key and deadbeef to make a key ending in the key exchange
cyphertext.  
Factorise by extracting and decrypting the session key (requires a secret
key), and repeating the key generation.  Again this is only detectable by
reverse engineering, but even after executing the reverse engineering you
still cannot factor the keys generated because the program only contains
the public key not the secret key.

Method (4) is an interesting example of a "locked back-door".  There is
often an unstated assumption that back-doors have to be open.  i.e. If you
can find them you can get in.  It isn't always true.  Whereas it seems
intuitively unlikely, it is not inconceivable that there is a way of
putting a locked back-door into some forms of Feistel ciphers.  The NSA
would have been reluctant to put an open back-door into DES, but they would
not have hesitated to put in a locked back-door.  In my opinion the only
safe assumption is that they could and they did.

In cryptography you shouldn't trust your intuition, code with source or
unexplained algorithm components.

Ian

Ian_Miller@bifroest.demon.co.uk    FAI-D10204
PGP key 1024/FCE97719 FP: 2A 20 46 10 E5 96 27 40  91 B1 95 BA CA D3 BC 14
Antworten auf Deutsch waeren mir angenehm.

-- 
http://yakko.cs.wmich.edu/~frogfarm  ...for the best in unapproved information
Tell your friends 'n neighbors you read this on the evil pornographic Internet
"Where one burns books, one will also burn people eventually." -Heinrich Heine
People and books aren't for burning. No more Alexandrias, Auschwitzs or Wacos.