Re: Internet Privacy Guaranteed ad (POTP Jr.)
I find less and less disagreeement with your comments - with one major exception - for a given message length - say 10 to the 500th power, a OTP seeded algorithm, a better term would be to call it an OTP driven algorithm, can produce the exact same effect as an OTP of that length - that is, the encrypted text can be any possible message of that length, and it is not possible to predict in way what the RNG generated stream is - We can prove that to your or anyone eleses satisfaction - It obviously fails to do that somewhat short of infinity, but not short of what is needed to prove system integrity for practical limits. If all the paricles in the Universe, 10 to the 80th, were Cray T3Es, and they had been calculating since the big bang, according to my rough calculations, it would still take over 10 to the 370th power years to just generate the message possibilities -for a 10 to the 500th power message length possibilities - we assert that if it can do that, and it can, it functions like a OTP of that length - and is unbreakable We also have a light, but only a slight disagreement, about whether the the key is truly symmetrical - we assert that because of the aprticlaur data feedback system employed it is not symmetrical, but that is entirely beside the point, we believe 10 to the 500th, or whatever should be sufficient Appreciatively, Ralph
-----BEGIN PGP SIGNED MESSAGE-----
"IPG" == IPG Sales <ipgsales@cyberstation.net> writes:
IPG> I find less and less disagreeement with your comments - with IPG> one major exception - for a given message length - say 10 to IPG> the 500th power, a OTP seeded algorithm, a better term would IPG> be to call it an OTP driven algorithm, can produce the exact IPG> same effect as an OTP of that length - that is, the encrypted IPG> text can be any possible message of that length, and it is IPG> not possible to predict in way what the RNG generated stream IPG> is - First, what you describe is commonly called a keyed RNG. Such a system is provably less secure than an OTP, because the number of possible plaintexts from any given ciphertext is limited by the number of possible keys. This makes an exhaustive search of all keys possible, because it is very unlikely that a given ciphertext decrypts to multiple plaintexts that make sense. In contrast, with a OTP there are as many keys as there are possible plaintexts, so any given plaintext can be reached, making it impossible to recognize the correct plaintext. Of course, searching the whole keyspace might be impossible if the number of possible keys is large enough. But there are other ways of attacking a croyptosystem besides trying all possible keys. Your cryptosystem seems to be based on what is called a linear congruential generator in combination whith an RC4-like 8*8 S-box, although somewhat simpler. I don't want to make any claim about the security of the algorithm, but linear congruential generators can't be considered secure for any cryptographic use. Your only chance is that the security of that algorithm does not depend on the generator, but I doubt that. For further reference, go out and buy "Applied Cryptography" by Bruce Schneier. The pseodo-code snipped describing your algorithm, for other people's reference: IPG> Bi=(Bi+Ci MOD Di) Mod 256 Large prime numbers IPG> ENCRYPTEXTi=OTP[Bi] XOR PLAINTEXTi Encryption IPG> OTP[Bi]=ENCRYPTEXTi Makes the OTP Dynamic Andreas -----BEGIN PGP SIGNATURE----- Version: 2.6.2 Comment: Processed by Mailcrypt 3.4, an Emacs/PGP interface iQCVAgUBMSu6OEyjTSyISdw9AQGKIQP+MqE5Scq99kGfLT8CdN3h9abJZNhj9qzm rUFGsnXfdAvyRzfLz6v8FsfLHgnkgu10MG++NABFBz0I+U0iGFi8Zivkd3Ae9/6J qOHqbGjiS4r3QN8IOLDwAW6eO6pF4Z0A/+FqLVR+zB+OZF/7TzUmgWpa8+cLWQkH Hndr5tAVekw= =bY+f -----END PGP SIGNATURE-----
IPG Sales writes:
I find less and less disagreeement with your comments - with one major exception - for a given message length - say 10 to the 500th power, a OTP seeded algorithm, a better term would be to call it an OTP driven algorithm, can produce the exact same effect as an OTP of that length - that is, the encrypted text can be any possible message of that length, and it is not possible to predict in way what the RNG generated stream is -
That is manifestly untrue. Read any information theory text. There is only so much entropy in your stream of random numbers, period. No amount of prayer, tantric meditation, or anything else will generate more. It is not the "exact same effect" no matter how much you might like it to be. What you are flogging here is a pseudo-random number generator. You are using this to produce what is properly called a stream cipher, NOT a one time pad. We in the crypto community have been working with this sort of thing for years. If you start with 100 bits of entropy, your stream will have only 100 bits of entropy. If you start with 1024 bits, you will have a kilobit of entropy, and so forth. This may seem like a lot, but it really isn't. Its easy to calculate the unicity distance of a given key. The unicity distance is most easily explained as the amount of ciphertext after which only one possible decoding is possible and in theory brute force will extract the key. The unicity distance is the information content of the key (which is the log base two of the number of possible keys, or in this case the equivalent, the number of bits of key) divided by the redundancy of the language in question. The rate of english text is somewhere around 1.3 bits per letter, so the redundancy of ASCII is somewhere around 6.7 bits. For a 1024 bit key the unicity distance will be, at best, around 150 characters. For a 5000 bit key, the unicity distance would be around 746 characters. That means that there is one, and only one, probable decoding of the ciphertext stream resulting from your system after a fairly short period of time, and one, and only one, possible key. Now, finding that key is hard. Done right, it can be VERY HARD. However, it is indeed possible given enough time. There is a big difference between something that is hard or very hard and something that is information theoretically impossible. Breaking a PRNG is always possible given enough compute cycles. Breaking a one time pad is not. That is the difference. Your phrase "can produce the exact same results as a one time pad" are, in short, bogus. Claude Shannon proved this fourty years ago. Perry
Perry E. Metzger writes:
If you start with 100 bits of entropy, your stream will have only 100 bits of entropy. If you start with 1024 bits, you will have a kilobit of entropy, and so forth.
This may seem like a lot, but it really isn't.
...and note that IPG does us the favor of ensuring the keys conform to this elaborate battery of statistical tests. Thus, there are bunches of keys that "aren't random enough" and thus not among the set to be considered when trying to break one. ______c_____________________________________________________________________ Mike M Nally * Tiv^H^H^H IBM * Austin TX * I want more, I want more, m5@tivoli.com * m101@io.com * I want more, I want more ... <URL:http://www.io.com/~m101> *_______________________________
...and note that IPG does us the favor of ensuring the keys conform to this elaborate battery of statistical tests. Thus, there are bunches of keys that "aren't random enough" and thus not among the set to be considered when trying to break one.
I wouldn't fault them on that. For example, let's say they have a sample of 1000 bits. They count the number of 1 bits, and discard any samples that have less than 450 or more than 550. They have thrown away a number of bits of entropy here. Somewhere between 10 and 100 at a guess -- my combinatorics is nonexistant. So what? There are plenty of bits there still. If they really are using 5600 bit keys, they can afford to lose some and still be invulnerable to brute-force attacks. What they have gained is the knowledge that their random number source isn't broken. If your RNG started spewing 0 bits by the thousand would you say "This stream is just as likely as any other stream that I can imagine so there is no problem", or "My RNG is broken". Of course, in nice mathematical abstractions your RNG never breaks, but we live in a nasty world of thermal failiures and cold solder joints.
On Thu, 22 Feb 1996 11:08:37 -0500, SINCLAIR DOUGLAS N <sinclai@ecf.toronto.edu> wrote:
What they have gained is the knowledge that their random number source isn't broken. If your RNG started spewing 0 bits by the thousand would you say "This stream is just as likely as any other stream that I can imagine so there is no problem", or "My RNG is broken". Of course, in nice mathematical abstractions your RNG never breaks, but we live in a nasty world of thermal failiures and cold solder joints.
No, they really haven't. Their initial post indicated that they are throwing away some 50% of their generated sets of "random" data. This indicates either their random number generator is seriously broken, or their analysis of the numbers produced is seriously broken. Either way, they have a significant problem which they are NOT addressing. In any truly random data stream, you would expect a certain percentage of blocks to have statistics outside whatever you decide is the "typical" range. If their generator is producing significantly more or less than the expected number of "atypical" blocks, it is broken. If is producing about the expected number of such blocks, it is likely working as designed, and such blocks are still TRULY random. In any case, throwing away some selected portion of its output is NOT an appropriate cure for a broken random number generator. The proper cure is fixing the generator. As a separate issue, if your cryptosystem has a set of "weak keys" it may make sense to screen your random numbers to prevent use of such weak keys. This, however, appears not to be what IPG is doing.
participants (6)
-
andreas＠artcom.de -
IPG Sales -
lull＠acm.org -
m5＠dev.tivoli.com -
Perry E. Metzger -
SINCLAIR DOUGLAS N