From: hughes@ah.com (Eric Hughes)
Date: Thu, 14 Apr 94 10:25:01 PDT
To: hh@xcf.Berkeley.EDU
Subject: fake pgp messages
In-Reply-To: <9404140957.AA18212@xcf.Berkeley.EDU>
Message-ID: <9404141714.AA24963@ah.com>
MIME-Version: 1.0
Content-Type: text/plain


>in the process of doing stuff to fight traffic analysis, i need to generate
>a bunch of fake pgp messages.  it is possible to asciiarmor random
>bits, but this is pretty easy to spot.  

You'll have to write a simulator for PGP messages.  This is
straightforward, since the outer part of a PGP doesn't contain much
information.  There's the destination ID (those naughty bits), an
encrypted session key, and an encrypted body.

I recommend that the next PGP release come with just such a simulator.
Fake messages are a useful primitive for certain tasks and their use
should be supported.  For similar reasons, a simulator for faking
cleartext signatures should also be distributed.

The destination ID should be chosen at random from a list of known
ID's, maybe with some randomly generated ones added to the list.
These shouldn't be flatly distributed because destination ID's are not
flatly distributed.  Download a big ol' public keyring and use that.

[There's a small opening here.  If the opponent were to seed the
public keyring with keys known not to be in use, they could detect
some of the messages as fakes, and certainly the presence of fakery.
On the other hand, if _none_ of the messages used known moduli, that
would be equally suspect.]

The encrypted session key should be less than the RSA modulus for the
given destination ID.  For arbitrary ones added to your list, make a
data structure which contains an upper limit, a substitute for the
modulus.

The encrypted body is just the output of your favorite PRNG.  Since
this is a simulation of encrypted text, you don't need the really
strong characteristics of a good PRNG.  Here's my recommendation.
Take a cryptostrong PRNG and generate a seed of sufficient length
(like 128 bits).  Take this seed and seed a PRNG of lesser quality and
(much) greater speed; a linear congruential generator would be fine.
For each block of output, take a secure hash, like MD5.

[crypto-strong PRNG]
[slow seed 128 bits]
	|
	v
[crypto-weak PRNG] 
[block 1] -->	[block 2] -->	[block 3] --> 
	|		|		|
	v		v		v
	[MD5]		[MD5]		[MD5]		...
	|		|		|
	v		v		v
	[output 1]	[output 2]	[output 3]

If the strong seed is too small, you could simply generate all
messages and do an exhaustive search.  If the space of the weak
generator is too small, that's where to do the search.  The reason for
the one-way hash is to prevent detection that a random generator is
behind it all.

Eric