Truly Stealthy PGP

[Hal <hfinney@shell.portal.com>]

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