From: koontzd@lrcs.loral.com (David Koontz )
Date: Wed, 1 Jun 94 10:23:51 PDT
To: cypherpunks@toad.com
Subject: RE: NSA breaks Russian PRNGs with neural networks??
Message-ID: <9406011531.AA16098@io.lrcs.loral.com>
MIME-Version: 1.0
Content-Type: text/plain



>From: rishab@dxm.ernet.in
>
>tcmay@netcom.com:
>> An interesting article by Seymour Hersh is cited below. It says that
>> NSA had transcripts of the 1991 coup plotters (and presumably other
>> Russian leaders) and that Bush passed these on to Yeltsin to warn him.
>
>A recent article from the Daily Telegraph, another British paper, went on abou
>the possible encryption techniques used by the Russians. It described how
>reused one-time pads led to the unmasking of Fuchs, the Rosenbergs, Philby
>et al. Then it suggested that the method the NSA broke was based on (presumabl
>weak) PRNGs, a stream cipher. It suggested that the NSA might have developed
>techniques to find patterns in PRNG outputs through neural networks, or geneti
>algorithms!!
>
>While the latter sounds like crap to me, even though I've worked with and
>believe in the power of neural networks for amazing pattern recognition, unles
>the PRNGs were _really_ weak, I'm skeptical. I don't think the Russians are
>fools, and in these times one doesn't rely on secret weak algorithms for
>crypto, not when there are publicly well known strong ones. Humint? Maybe.

I can recall having seen keylists for Soviet crypto, similar (but larger)
than those used for shift register based U.S. tactical crypto from the
Korean War era.  We used to monitor send/receive ciphertext for U.S.
crypto during key changes.  One handy tool was a meter, which would integrate
(low pass) the data stream.  We could easily determine that the key had been
changed by watching the meter.  This was done with idle circuits operating
under traffic flow security (meaning the line was active, data equal to a
constant mark, the encrypted constant mark showing on the data stream).
The distribution of average voltage values (MIL STD 188) and how fast
and furious it would change, hop, skip and jump were generally distinct
between successive keys.

DES S Box outputs have the identical symbol distribution for key and key_not
(E(Rn) xor KSn, input to the S Boxes).  For a given round key (and its
inverse), there are between 0 and 65,536 symbols missing from the domain
of the P permutation (32 bit symbols).  Which symbols and how many that
don't show up are dependant on the key.  Some keys have no missing symbols,
while others have lots.  This is a function of the E permutation and R bit
sharing between adjacent S Boxes.  Someone appears to have been quite
aware of this weakness, the second XOR operation found in a DES round
( (E(Rn) xor KSn) xor Ln )goes a long way towards masking the fact that
some symbols can be missing.

Were DES not to perform the second XOR, you could determine the key
simply by monitoring missing symbols from the output of the S boxes
(P permutation).  Each new symbol found would eliminate certain patterns
from the scheduled key (KSn), a 48 bit value.  It would go a long way
to reducing the number of unknown key bits to the range of easy brute
force attacks.

Now imagine that shift register based crypto generally doesn't mix key and
data as well.  DES  operates on each bit 16 times, more than the typical
shift register based crypto.  Each bit of the output block of DES depends
on all the input bits and all the key bits input to the key scheduler.  A
shift register based crypto with a shift register of a size comparable to
the block size of DES would typically have a lot fewer variables contributing
to each key bit, making brute force attacks on a known crypto system
with known plaintext (including idle data values) much easier.  Now, imagine
that there is statistical significance to the output distribution of 1's
and 0's based on weaker mixing.  This sounds right up the alley for neural
nets.

Anyway, I think it really depends on the age of the crypto gear in use.
Older gear tends to be less secure based on shift register size, and
key/data mixing.  There are also rules used to specify tap to input
selections, which eliminate weak keys (the sort of rules enforced by
key card readers).  Attacking a cryptosystem operated with keys provided
from a centralized generation/distribution system would further reduce the
key search domain to strong keys.

Having worked on crypto gear built the year I was born (1954) through the
late '70s, I have no problem believing that Russia is using antiquated (and
thus more vulnerable) crypto today.  Based on replacement cost, the only thing
that would drive comsec gear out of service would be demonstrable weakness
(such as Bush giving Yeltsin intercepts, personnel insecurity with respect
to key handling, etc.), or prohibitive maintenance/operating costs.   After
all, some protection is better than none.