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

*To*: [email protected], Randall Farmer <[email protected]>*Subject*: Re: Encyrption Program*From*: Bill Stewart <[email protected]>*Date*: Wed, 15 Oct 1997 18:55:31 -0700*Cc*: [email protected]*In-Reply-To*: <[email protected]>*Sender*: [email protected]

At 12:58 PM 10/14/1997 PST, [email protected] 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: [email protected]", 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, [email protected] Regular Key PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639

**References**:

- Prev by Date:
**Free Sex Test Drive !** - Next by Date:
**Re: anti-GAK design principles: worked example #1** - Prev by thread:
**Re: Encyrption Program** - Next by thread:
**CDL is here!! (fwd)** - Index(es):