Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!princeton!allegra!ulysses!faline!karn
From: karn@faline.UUCP
Newsgroups: rec.ham-radio.packet,sci.crypt
Subject: Re: passwd security
Message-ID: <581@faline.bellcore.com>
Date: Thu, 14-May-87 18:28:23 EDT
Article-I.D.: faline.581
Posted: Thu May 14 18:28:23 1987
Date-Received: Sun, 17-May-87 01:06:55 EDT
References: <1012@chinet.UUCP> <1615@Umunhum.STANFORD.EDU>
Organization: Bell Communications Research, Inc
Lines: 43
Xref: utgpu rec.ham-radio.packet:303 sci.crypt:368
Summary: LFSRs are NOT encryption systems

In article <1615@Umunhum.STANFORD.EDU>, paulf@Umunhum.UUCP writes:
> 4) Design a piplined serial encryptor / decriptor pair using LFSR's.
> 	This is probably stretching part 97 a bit.
> 
> A STA for LFSR encryptors would be nice for those who want closed systems;
> 	the situation is similar to PL - type access on a closed repeater.

I wish you hadn't brought this up. Linear Feedback Shift Registers
(LFSRs) are already in use in the K9NG and WA4DSY amateur packet radio
modems as data randomizers. They're called "scramblers" in the
commercial world, but this word has bad connotations in the amateur
world. The purpose of a scrambler or randomizer is NOT to hide the data
being sent, but rather to change its statistics to improve the modem's
performance and to reduce co-channel interference.  In particular,
scrambling gets rid of the DC component in a long flag stream, and it
guarantees plenty of data transitions for clock recovery in the event
you're not running HDLC and you're sending long strings of 1's or 0's.
In part 97 wording, the purpose here is to facilitate communications,
not hide the meaning.

You need to know the polynomial (the taps on the shift register) being
used in order to decode a randomized data stream. Steve and Dale have
published their polynomials, so as far as I'm concerned they aren't
encrypting. However, this wouldn't be much of an encryption system even
if they tried to keep their polynomial secret. All you need is 2N bits
of the pseudo-random sequence generated by the LFSR (where N is the
number of stages in the shift register) and you can obtain the
polynomial by solving a simple linear system of equations.

Shift register feedback systems intended for encryption must use NON-linear
feedback.  The effect of this is to simulate a LFSR with an extremely long
register, so long that the attack just mentioned isn't practical.

Based on the available public information about the secret NSA
algorithms now being recommended for the replacement of DES I think it's a
good bet that they're based on nonlinear feedback shift registers. I say
this because they're stream ciphers and they run much faster than DES in
hardware. NSA also claims that you have to get your keys from them in
order to guarantee security (!) because constructing a "good" key
requires special knowledge of the algorithm. All this is consistent with
the nature of non-linear feedback shift register algorithms.

Phil