From: wichita@cyberstation.net Date: Sat, 30 Nov 1996 02:41:28 -0600 (CST) cc: Bill Frantz <frantz@netcom.com>, John Anonymous MacDonald <nobody@cypherpunks.ca>, cypherpunks@toad.com ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Shannon proved that you cannot prove what the plaintext is for OTPs, Let P, K, and C represent bit strings of equal length. Given a ciphertext C, for every plaintext P there exists a key K such that P XOR K = C. This is true (K=P XOR C). or for the system we have developed either. False. Let P and C represent byte strings of equal (arbitrary) length and K represent the key string of fixed length. The IPG algorithm can be summarized C = P XOR PRNG(K) where PRNG(K) is the output of the pseudo-random number generator with seed K. The details of the PRNG are unimportant for this argument. For every ciphertext C longer than K, there exists a plaintext P such that no K will satisfy C = P XOR PRNG(K). Proof: There are 256^length(K) possible keys (roughly 10^34322). There are therefore at most this many possible decryotions of the given plaintext. Since length(C) > length(K), there are more possible plaintexts than possible decryptions. Shannon's proof of the security of the OTP therefore doesn't apply to IPG's cipher. Assume that the PRNG is resistant to analysis. Given the size of the keyspace, it is not feasible to search the whole keyspace hoping something like a plaintext pops out. However, it is easy to take a key obtained through some other means and verify that the plaintext makes sense. Since the PRNG is assumed resistant to analysis, this constitutes proof that the plaintext is correct (since it's infeasible to find a key that decrypts the ciphertext to another plausible plaintext). Of course, all encryption algorithms short of the OTP allow an attacker to prove a key correct, but most cryptographers don't claim their algorithms to be as secure as OTPs.