Truly Stealthy PGP (algorithm)

[hughes@ah.com (Eric Hughes)]

>If I understand Eric's general idea, we would keep trying session keys
>under a set of rules which would lead to the desired statistical
>distribution of the encrypted key.  

I actually said nothing about how to get the particular distribution
of keys specified, since that was another issue.  I was more concerned
with just getting the one result across.

>Here is an algorithm which would work.

It does work, and I'll put down a proof sketch below.

Notation alert:
>Let L be the next power of 256 above the modulus n.  Let t be the integer
>part of L/n, so that L = n*t + s with s in [0,n).  Call the PGP IDEA session
>key SK, and the encrypted version of that m = SK^e.  Now do these steps:

>1) Pick a random SK in [0,n).

This random number in [0,n) is the wrong distribution, but that's OK,
since we'll be throwing some numbers away.

>2) RSA-encrypt it to form m = SK^e mod n.

RSA encryption is a bijection (an 1-1 map).  If it were not, there
would be two or more possible decryptions for a given ciphertext.
Therefore RSA encryption is a permutation, and a permutation of
probabilities preserves expected values of functions of the
probability, such as entropy.  Since we assume the entropy of the SK
is maximal (probabilistic entropy), therefore the entropy of the m's
is maximal.  So the m's have a flat distribution.

(As always, the above statements about bijection hold only if SK is
multiple of one of the divisors of the modulus.  But then if you do
find one of those, you've also factored the modulus and thus broken
the key.  We assume this doesn't happen, since if it does little of
this matters anyway.)

>3) Choose a random k in [0,t].
>4) Calculate the "stegged" encrypted key as M = m + k*n.  

Hal now observes that M is uniformly distributed.  This is correct,
and happens because m is in [0,n) and we are adding a multiple of n to
m.  This means that each M has a unique represenative as some pair
<m,k>.  Since both m and k are independently random (max entropy, flat
distribution), so is M.

>5) if M is not in [0,L) (i.e. if M >= L) then go back to step 1.
>The idea is that once we get M uniform in [0,(t+1)*n) we can make it
>uniform in [0,L) simply by rejecting those candidates which were too high.

What we have here is a Markov chain.  We have accepting states and
rejecting/retrying states.  Since the probabilities in the chain are
independent of each other and are also time-invariant, the
distribution of final probabilities is the same as the distribution of
normalized accepting probabilities.

In simple terms, you can just retry until you get it right.  Since the
probabilities are all the same before, they will all be the same
after, only larger to account for the fact that some possibilities
didn't work.

[re: rejection and retry]
>This will only happen if k=t and m>=s.

That's right, and that means that for m < s you have valid k in
[0,t+1) and for m >= s only for [0,t).  If you go back an look at the
entropy expression, you'll see exactly this difference in relative
probability for the two parts of [0,n).

>Now, it seems to me that the worst case for rejection is when n=L-1, in
>which case t=1, s=1, and almost one-half of all initial SK choices will
>be rejected.  

Right, but the worst case for rejection is not the same as the worst
case for entropy loss, which occurs at n=L/2+1 and s=t-1, i.e. at the
other end of the spectrum entirely.

>Following Eric's reasoning, this would be an effective loss
>of one bit of key length, from say 1024 to 1023, which is tolerable.

Actually not.  The loss of effective key length happens based on the
posterior distribution of the session keys, not on the number of
rejections that happen in the process.

>Using this algorithm with the current Stealth PGP would produce a
>"truly stealthy" version which I think would be indistinguishable from
>random bytes without access to the receiver's private key.

Indeed.  Observe, though, that as far as deployment went, this would
require modification to PGP itself for it to be anything like
widespread.

Eric