[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected]*Subject*: Truly Stealthy PGP (algorithm)*From*: [email protected] (Eric Hughes)*Date*: Mon, 7 Mar 94 08:34:04 -0800*In-Reply-To*: Hal's message of Sun, 6 Mar 1994 11:22:17 -0800 <[email protected]>*Sender*: [email protected]

>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

**References**:**Truly Stealthy PGP (algorithm)***From:*Hal <[email protected]>

- Prev by Date:
**Re: Where'd pgptools go?** - Next by Date:
**Re: Format of PGP ciphered message** - Prev by thread:
**Truly Stealthy PGP (algorithm)** - Next by thread:
**PGP (surprise, surprise..)** - Index(es):