From: eric@remailer.net (Eric Hughes)
-- The RSA-encrypted session key does not have a flat representation over its multiword container. This yields a statistical traffic analysis hole. (This point is irrelevant without fixing 4.) Hal and I completely solved this problem last year.
For reference, here is that old message with an algorithm that produces an encrypted session key with a flat distribution over a specified number of bytes, along with a proof that it works. The purpose of this is you could strip off the PGP header stuff and have a file which looked for all intents and purposes like totally random bytes, but if you knew the secret key then you could decrypt it just fine. (I recently took my CP archives and indexed them using Mark Zimmermann's (no relation to Phil, apparently) FreeText browser which lets me do keyword searches. Pretty nice.)
Date: Mon, 7 Mar 94 08:34:04 -0800 From: hughes@ah.com (Eric Hughes) Message-Id: <9403071634.AA10351@ah.com> To: cypherpunks@toad.com In-Reply-To: Hal's message of Sun, 6 Mar 1994 11:22:17 -0800 <199403061922.LAA26901@jobe.shell.portal.com> Subject: Truly Stealthy PGP (algorithm) Sender: owner-cypherpunks@toad.com Precedence: bulk Status: RO
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