Re: Encyrption Program

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.

    Thank you for your interest and criticisms. They have been 
helpful.

--Dylan

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'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.

> you can download both the compiled version *and* the source
Providing source is important - thanks; at least there's some chance that
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

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

> 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 

The way I understand this is that only one character is chosen and this
same character is XORed with all plaintext for that session. Therefore,
given that there are 8 bits in an unsigned char (which I am assuming you
are using based on your choice of the word "character"), meaning that 
there are only 2^8 (256) possible 8 bit characters, hence only 256
different possible outcomes. Such a short keyspace is linearly searchable
in a very small amount of time, making the encryption scheme particularly
weak.

If I am writing this based on a false understanding of your scheme, would
you mind clarifying exactly the points in which I am in error, so that I
might analyse with that information taken into account.

Yours Sincerely,

Benjamin Grosman