From: aba@dcs.exeter.ac.uk
Date: Tue, 12 Sep 95 10:33:50 PDT
To: gjeffers@socketis.net
Subject: Re: Returned mail: User unknown
In-Reply-To: <199509121728.SAA16313@hermes>
Message-ID: <26561.9509121731@exe.dcs.exeter.ac.uk>
MIME-Version: 1.0
Content-Type: text/plain



[whoops mispelled cpunks on cc line 1st time, sorry for 2 copies]

Perry Metzger <perry@piermont.com> wrote:
> Gary Jeffers <gjeffers@socketis.net> writes:
> >    Well, I just used MIT's PGP 2.6.2 with 3 different users' public
> > keys to encrypt 3 different files. In all 3 files, the first 3
> > characters were the same (an umlauted A, then an i with an up arrow
> > over it, and then a heart). This beginning 3 character string is
> > apparently the infamous PGP RSA signature. The signature that says
> > to spooks' programmed encryption sniffers - "HEY! I'M PGP -  GIVE ME
> > A LOOK!."
> 
> As if they couldn't figure it out anyway. It isn't an "RSA signature"
> by the way. Read format.doc sometime.

Yeah, that's what stealth does, removes the boiler plate stuff saying,
various things, such as pgp version number, rsa encrypted message,
conventional idea block, and as Perry says, it's all in pgformat.doc
in the PGP docs directory.

> >    When are the PGP designers and coders going to get serious and de-
> > velope STEALTH PGP inside PGP itself!?
> 
> Never, I hope. It would dramatically lower the utility of the
> system. Can you imagine how disgusting it would be to try decrypting
> something if you have a dozen keys outstanding? Not to mention how
> hard it would be to deal with figuring out that you should even try to
> decrypt things in the first place.

I reckon it would be a very nice utility, built into pgp as an
*option*, some countries it isn't legal to use PGP, and it hasn't been
ruled out that the US may not be the next to join the list, all this
GAK stuff, son of Clipper, it is a distinct possibility that the law
enforcement lot might outlaw other crypto wiht mandatory GAK.  Then
stealth features for PGP become important for incorporating into
stego, of course you can argue that well stealth should be part of the
stego app then.  It shouldn't be a problem unless it was enforced, as
an option I see no problem with it, and lots of possible future
advantages even.

I'm trying to work on stealth2.1, modifing Henry Hastur's stealth util
to added Hal Finney's algorithm for improving the stealthiness (it's
not enough to just strip the headers as stealth1.x does, the fact that
the RSA encrypted header is always < N, the rsa modulus gives the game
away with a few messages to analyse for statistical purposes, ie if
you see a lot messages < N, where N is by definition not an even power
of 2, and possibly even N is known, or suspected from keyservers).

I've been delaying releasing it because I was worrying about ran no
generators being good enough, but I think I might have convinced
myself that it is not even necessary to use ran no generators, I'd
appreciate it if some folks with a bit of crypto expertise could cast
their eye over the description below.

> >   So what, -that "only a few companies" will be discovered to be using PGP
> > through the RSA signature!? Those few companies are the seeds for the
> > vast numbers of companies that would follow them in using PGP over the
> > Internet. The RSA signature is the flag that allows the spooks to easily
> > net the bold first companies. The RSA signature is greatly impeding the
> > spread of PGP use over the Internet. PGP MUST BE STEALTHED!!
> 
> It isn't an RSA signature. Its a bunch of magic numbers.
> 
> Look, get real already. If someone sees a bunch of random numbers in
> mail sent by me, its going to be pretty obvious what the hell is
> inside anyway.

Yeah, but you wouldn't do it that way.  I reckon this is what you'd do:

% pgp -es duress
% pgp -es msg
% stealth < msg.pgp > msg.stl
% cat msg.stl >> duress.pgp
% pgp +makerandom=1234 noise
% cat noise >> duress.pgp
% pgp -a duress.pgp
% mail someone < duress.asc

The pgp +makerandom=<size> <file> is an undocumented feature of pgp >
2.6 (not sure exactly when it got added, Colin Plumb pointed it out
when I asked him about ran nos for stealth).

So what this means is that you are using PGP it's self to hide a
stegoed message.  This would be good for the guy from FACTnet
(forgotten his name) who just got hit by the CoS, he could hold out
for a while, then give up his key, the duress message would appear,
and the real message would be explained by having a script to do this
on his HD, and having long since burned the disk with a script to do
the above on it:

% pgp -es msg
% pgp +makerandom=4567 noise
% cat noise >> msg.pgp
% pgp -a msg.pgp
% mail someone < msg.asc

ie the idea is that you pad your message to a fixed size for the
express purpose of hampering traffic analysis (of the type of my,
Alice did have a lot to say to Bob that day).  It would be even better
cover if the thing had gotten sent through a remailer, as this kind of
thing is expected of type I remailer traffic (before mixmaster which
does the packetizing for you).

So the duress message really looks like this:

+---------+---------------------------+--------------------+--------+
| pgp hdr | IDEA encrypted duress msg | stealthed real msg | noise  |
+---------+---------------------------+--------------------+--------+

the IDEA block has a length field, but you can increase the length
without damage to include the following stealthed stuff as the
underlying stuff which is IDEA encrypted will know it's length on
decryption, and the following junk will just be discarded.

So, Alice and her secret key ring (encrypted) gets nabbed by the
Charlie (CoS?), and coerced into divuling her passphrase.

And if and when it is noticed that the message was longer than it
ought to be (CoS that smart? substitute the NSA and they'd notice for
sure), Alice explains away the junk on the end by pointing them to the
fact that all of her messages where exactly (say) 16k long, and that
she was using a the noise only script, and that the message really is
this:

+---------+---------------------------+-----------------------------+
| pgp hdr | IDEA encrypted duress msg | noise                       |
+---------+---------------------------+-----------------------------+

Now we come to arguments about why you might want this built-in to
PGP.  Well it provides plausible deniablity as you have no extra
software which might look incriminating unless you managed to dispose
of it first, if it comes as stock.

Also the 2nd reason for built-in at least for stealth is if it needs
good random number source, but as I said, I'm not sure it needs a
random no generator.  So comments please, this has been around a few
times already, but here's the algorithm for manipulating x which is
the RSA encrypted component of the header of an RSA+IDEA encrytped PGP
message:

(this is a description of my implementation of Hal's algorithm as
described on his www page: http://www.portal.com/~hfinney/):

consider random no x, RSA modulus N

	1 < x < N

(that used to say 0 <= x < N, but 0, and 1 being RSA fixed points, 0,
1, and N won't be generated by PGP presumably?  I think this shouldn't
matter as the keyspace of N is so large that the probability of a 0 or
a 1 specifically is nothing to worry about I think.)

Hal's algorithm was to convert x to being in the range:

	0 <= x' < lim

where lim which is the next power of 2 above N * 2^surety, and surety
is 64, 64 seems big enough?

The recover operation is:

	x = x' mod N

and the create operation is:

1) scale = int( (lim-1) / N ) + 1

2) scale2 = 2^int( log2( scale ) + 1) 

	ie scale2 = next power of two over scale

3) r = MD5( 0, x ) 

	ie MD5 digest of x, as x is an RSA encrypted random session
	key misc other info, and more random padding to bring up to
	be close to N in size.  It strikes me that we already have 
	a random number, and that provided MD5 can not be inverted
	(which it is not possible, as it is compressing, and looses
	info, and the brute force to find which of all the possible
	y's (0 < y < N) MD5 digests come out to be x.

	I would have thought it likely that this would be evenly
	distributed, and that the cost would be enormous?

4) r = MD5( r, rand() )

	it will fail some of the time, so in this
	case repeat with another random number, Istirred it in first
	but perhaps you would only do it if it failed.  Or perhaps it
	is enough to MD5( r, r ) ie stir r into itself to generate
	another ran no?  So long as there are no rare cycles?
	Presumably either impossible or infinitessimally small
	probability.


5) r = r mod scale2
	
6) if (r > scale) goto 4)

	4),5) & 6) are designed to generate an evenly distributed
	random number in the range:

		0 <= r <= scale

7) x' = N * r + x

8) if (x' > lim) goto 4)



an example, with small numbers, and surety set to 8, x = 7, and
manufactoring the ran nos manually:

lim = 2^( int( log2(N) + 1 ) + surety )
    = 2^( 4 + 8 ) = 4096

1) scale = int( 4096 / 13 ) + 1 = 316

2) scale2 = 2^( int( log2( scale ) ) +1 ) = 2^(8 + 1) = 512
          
3) say MD5( x ) = 0x00000000000000000000000000001234

4) say MD5( x, rand ) = 0x00000000000000000000000000001235 = 4661 (base 10)

5) r = 4661 mod scale2 = 4661 % 512 = 53

6) if ( 53 > 315 ) - it's not

7) x' = N * r + x = 13 * 53 + 7 = 696

8) if (696 > 4096) - it's not)

so x' = 696

reversing:

x = x' mod N = 696 mod 13 = 7


when 6) is true, ie r > scale which will happen half the time on avg
with the first ran no, and so on like a coin flip, the chances of many
coins flipping the wrong way diminishes rapidly with number of flips.

when 8) is true, ie x' > lim, x' can only be > than lim when x = N - 1, 
and given that x = N - 1, the probability is less of x being in 

	N * scale <= x < lim

but this will only occur with probability:

       1         1
    -------- < -----
    2^surety   scale

I think.  So you'd have to collect one mess of messages to even catch
one sample, let alone enough messages to have a statistical proof of
steganography being present.


Pls check the maths a bit, the above describes the software
implementation of Hal's algorithm which he has on-line, on his page:

	http://www.portal.com/~hfinney/

But the main question I'd like to get verification on is if it is safe
to use the MD5 of the RSA encrypted message to perform the operation.

I'm essentially doing:

	x' = N * f(MD5(x)) + x

where f(y) is a function which converts from range 0 <= y < 2^128 to a
range 0 <= f(y) < scale.

Is that safe?

x is random, and will be different even for a repeat encryption of the
same file, as PGP is using a random IDEA session key.

So are there any brute force attacks on that which would be cheaper
than attacking 128 bit IDEA?  PGP's random number generator also makes
extensive use of MD5, so I'm taking the use of MD5 as secure as a
given.

If it is thought to be dangerous for some reason (it is after all some
kind of signature on it's self, presume that you know N, and x' but
not x, the question is can the equation be brute force reversed in a
less than 128 bit brute force attack.  I'm neglecting to consider the
rand() calls, which I'm not expecting to add security, but are just a
mechanism to stir the value with to get more random nos, as
occasionally the alogrithm needs more than one, if the first fails,
etc.

If people reckon it's insecure, then it would be ideal to include the
stealth functionality into PGP, so that integral use of PGPs ran no
routines can be made.  I was previously using an MD5 digest of PGPs
randseed.bin for this, but you can't stir it (well you could but that
would considered a security risk diddling with PGPs files), and not
stirring means you have no improvement over the above, in the event
that that your system is captured with the known plaintext.  If you
stirred it there would be no proof of that being the message in the
file.  Even unstirred, if the N * f(MD5(x)) + x is no good, the
inclusion of a digest of the randseed.bin would be a big improvement.

It seems rather messy to have all of the keyboard sampling stuff, for
PGP keys duplicated for this.  Hope the x' = N * f(MD5(x)) + x
construct is secure as this will avoid the issue.

Adam