Truly Stealthy PGP

Eric points out the difficulty of making a "stealth PGP" which is 100%
indistinguishable from a string of random bits.  The problem is that we
have to encode the RSA encrypted number, m, which is less than n, the
RSA modulus.

PGP first puts out two bytes of bit length, then m.  This obviously won't
do, since the bit length is generally much less than 2^16 and so these
two bytes are a dead giveaway.  However, we could leave these two bytes
off and just output m as raw bits, padded to the length of n.  The
recipient knows n so he would be able to extract m.

The problem here, as Eric points out, is that m is less than n, so the
high bits of m will look non-random.  If the high two bytes of n are,
say, 0x0C12, then m's high two bytes will never be bigger than this.  This
will allow the opponent to do much better than 50% on guessing which files
have embedded messages.

This was discussed some time back on the pgp developers' list, and at that
time the suggestion was made to add a multiple of n to m so that it covered
a fuller range of values.  The recipient would then just take the exponent
mod n and try that.

Mathematically, call L the next multiple of 256 above n.  (0x10000... in the
example above.)  We want to choose k so that M = m + k*n is randomly distributed
between 0 and L-1 if m is randomly distributed between 0 and n-1.  This may
not be possible in this form.  Perhaps there is another deterministic and
reversible transformation would accomplish it, though.  In that case we
would have M = f(m,n) such that f can be reversed given M and n (we can
recover m).

As a trivial example of this problem, given n=2 and L=3, try to come up with
a way to turn a random 0/1 value into a random 0/1/2 value which is both
reversible and produces each of 0/1/2 with 33% probability.  Seems pretty
tough!

Hal

>This was discussed some time back on the pgp developers' list, and at that
>time the suggestion was made to add a multiple of n to m so that it covered
>a fuller range of values.  The recipient would then just take the exponent
>mod n and try that.

What I suggest is making the exponent (the encrypted session key)
completely random over the length assigned to it, since that's
visible, and just live with a slightly non-flat distribution of
exponents mod n.  It turns out that this can be made to work just
fine.

>Mathematically, call L the next multiple of 256 above n.

n is the modulus.  Divide L by n to get L = t * n + s, s in [0,n).
Assume x is random in [0,L).  The entropy of x mod n is

   E = - s (t+1)/L log (t+1)/L - (N-s) t/L log t/L

Rearranging, we get:  (get out some paper, do the algebra)

   E = log L/t - s(t+1)/L log( 1 + 1/t )

This makes sense, since if s is zero, E = log n, which is just the
entropy of the random distribution of [0,n).

What is the smallest value of E?  In other words, what's the upper
bound of the randomness we can lose?  It happens when when t = 1 and
when n = L/2+1.  This maximize the expression in t and maximizes s at
n-2.  This minimum value of E is

   E_min = log L - ( ln 2 - 2/L ln 2 )

In other words, the most entropy we can lose is two bits.  That's
right, only two bits.  Since the entropy of the session key is the
length of the modulus, for a 1000 bit key the entropy loss is
negligible.

Therefore, my recommendation is that the session key representation be
chosen randomly over [0,2^k) and to use as an actual session key this
value mod n.  The effective entropy loss is small enough not to worry
about.

Eric

Scratch that.  I made an algebra error.  I'll repost with the right
answer.

Eric

>Scratch that.  I made an algebra error.  I'll repost with the right
>answer.

Scratch the scratch.  I thought I'd made an error in my entropy
expression, but I hadn't.  More confusion to follow, no doubt.  I hope
it just won't be mine.

I kept thinking that the location of the minimum entropy was wrong.
I worked out some examples with real numbers to prove to myself that
my intuition about the location of the minimum entropy was incorrect.
Intuition about entropy is difficult to develop, and I still don't
completely have all of it.  A word to the wise.

Eric