At 3:58 PM -0500 10/14/97, semprini@theschool.com wrote:

This is in response to the several posts regarding the assumed weakness in the program I wrote:

While it is true that PRNG's are not very good, because of the inherent lattice structure, I believe I found a way around that problem. To work around the lattice problem, I used a systm of cubic arrays. The program first creates sixteen cubic arrays, and fills them one space at a time with random characters. When the stream of characters to be XORed with the plaintext is generated, it picks a random cube and a random location with that cube. The resulting "random" character is then XORed with the appropriate character of the plaintext. If someone can prove to me that this method is stupid or easily breakable, I would actually be happy. So, those of you bent on proving that I'm wrong, I heartily encourage you to do so. As I mentioned before, you can download both the compiled version *and* the source at "http://www.brigadoon.com/~semprini/3dmx". If you are having trouble reaching that site, e-mail me and I will send you a copy via e-mail.

Good luck, but be aware that you won't get much free analysis. In general, algorithms that aren't published don't get looked at very carefully (mostly because there's no real upside in doing so--at least if the algorithm is published you can get a paper out of a break). You might have more luck if you posted the algorthm (not in source code, but in a mathematical description) along with a comprehensive analysis of its security against existing attacks. (There is a lot of published research on the analysis of stream ciphers, although the field is much less well-studied than block cipher analysis.) Good security arguments, proofs even, will make more people interested. Cheers, Bruce ********************************************************************** Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098 101 E Minnehaha Parkway, Minneapolis,MN 55419 Fax: 612-823-1590 http://www.counterpane.com

At 12:58 PM 10/14/1997 PST, semprini@theschool.com wrote:

This is in response to the several posts regarding the assumed weakness in the program I wrote: While it is true that PRNG's are not very good, because of the

There are lots of kinds of random number generators. Many of them are good for simulations and totally useless for crypto, and not even very good for the intermediate problem of gambling. It's worth getting a copy of PGP and reading the section in the user documentation about Snake Oil - Phil Zimmermann describes how he invented a cool new cryptosystem using PRNGs and was surprised to find breaking it as a textbook exercise. He's gotten better since then :-) By far the most commonly used is the Linear Congruential Generator; x[n] = ( a * x[n-1] + c ) mod m They're popular because they're fast, simple, and for well-chosen values of a, c, and m, they produce reasonable-quality random numbers. Another very popular class of random number generators is Linear Feedback Shift Registers, which look roughly like b[n] = a[0] + a[1]*b[n-1] + .... + a[k]*b[n-k] where the a[] and b[] variables are bits and it's all modulo 2. The definitions of "random" used here imply that the value of x[n] is statistically well-distributed even if you know x[n-1], x[n-2] .... x[0]. That doesn't mean that _you_ can't easily calculate them, nor does it mean that you can't easily calculate x[n-k], x[n-k-1], ... x[0] given x[n] ... x[n-k+1]. For both LCG and LFSR, there's a lot of mathematical theory about how to do this, and especially LCGs are pretty useless. Among other things, if anybody knows the first N bits of your message, for instance they know some plaintext -- knowing the first two characters is enough for a known LCG using 16-bit integers, such as the "Fr" in "From: alice@acme.com", or the magic number in the first 2-4 bytes of a file that indicates it's a GIF or EXE or a.out or whatever. If you don't know which 16-bit LCG it is, having the first 4 bytes helps a lot. And if you don't know, there are only 65536 possibilities, so just try them all and look for text. Even if you're using 32-bit LCG random numbers, that's not very many for a Pentium to crunch on over the weekend.

To work around the lattice problem, I used a systm of cubic arrays. The program first creates sixteen cubic arrays, and fills them one space at a time with random characters. When the stream of characters to be XORed with the plaintext is generated, it picks a random cube and a random location with that cube.

you can download both the compiled version *and* the source Providing source is important - thanks; at least there's some chance that

You're probably generating the set of random characters from the LCG, which means if you know one, you know them all (or at least, if you try it 65536 times you do, for a 16-bit LCG. This _is_ more annoying for 32-bit LCGs, but not particularly harder; maybe you need a lab-full of Pentia.) Similarly, your "random" cube and "random" location are probably chosen from the same stream. So for each starting value, we know the contents of the cubes, and which cube and byte are chosen, so we XOR them with "F", and if that works XOR them with "r", and work our way down the line. people can look at your algorithm and see if it's been done before. A good description of what the algorithm is and why it's strong are also helpful, especially for people who don't know the syntax of whichever programming language you're using very well.

"http://www.brigadoon.com/~semprini/3dmx". Only connect once every hundred years? No thanks! :-)

Also, is there any way to jump ahead in the LCG? x1 = ( a*x0 + c ) mod m x2 = ( a*a*x0 + c*x0 + c ) mod m = ( (a*a+c)*x0 + c ) mod m Is it easy to extend this to x2, x4, x8, x16, x32 ....? This would make it much faster to calculate the "random" cube and cell, and would let you only calculate the values you need in the cube instead of calculating them all, so you only do about log(16*cubevolume) calculations instead of 16*cubevolume. If that doesn't work, it still gives you a set of values a[k] such that x[k] = ( a[k]*x0 + c ) mod m which lets you calculate the coefficients for the cube _once_ (the same amount of work you needed to do to use the encryption), and then for each value of x[0], calculate x[RandomCubeNumber] and x[RandomCellNumber], then calculate the value of that cell in that cube (which takes another lookup+multiply+add+mod). That means you need to do a dozen or so operations per key, so even if you're using the 32-bit LCG, that's about 50 billion ops, which is a thousand or so Pentium-seconds. If you're using the 16-bit LCG, setting up the cubes will take about as long as cracking, which says you can crack this version of the algorithm in only 2-3 times as long as it would take to use it as a user.... LFSRs are probably harder..... somewhat.... Thanks! Bill Bill Stewart, stewarts@ix.netcom.com Regular Key PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639