On 10/10/2007, Martin Klingensmith <martin@nnytech.net> wrote:
> Only if you know the scheme, seed, and samples of the resulting stream
> of data. There's no way you can catalog all the data to match the
> pattern, so you have to know the starting point. So while it's not
> random, it's not easy to figure out what the next value is going to be.
> If you want to be pedantic, I did NOT say that it was random.

Berlekamp-Massey decodes the seed for any given sequence of a known
LFSR (which is a basic structure with arbitrary linear modifications)
given twice the length of bits and the length of bits. If you can
guess 64 bits of an output stream (which isn't awfully hard, given
that most of them start with whitespace or XML-ish starts) you can
decode any 32-bit LFSR.

> I'm sure there are theoretical attacks on large LFSRs. You could hash
> the output with a good hashing algorithm. Or you could use some sort of
> hybrid s-box feedback instead of a XOR. It wouldn't be linear like an XOR.

These are the practical attacks. Theoretical attacks imply that you
must include a non-LFSR source to prevent this or hide them very well,
which hasn't had much analysis yet. S-boxes don't do much good for the
output but permute the order of the repetitions and make it less
likely that you find a polynomial that gives a full result.
-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist