From: firstname.lastname@example.org (David Koontz )
Message Hash: 3dc981efd88eb1e42e37957ffb2823e5504fe6c04170f0cc3fb9406521408d4f
Message ID: <9406011531.AA16098@io.lrcs.loral.com>
Reply To: N/A
UTC Datetime: 1994-06-01 17:23:51 UTC
Raw Date: Wed, 1 Jun 94 10:23:51 PDT
From: email@example.com (David Koontz ) Date: Wed, 1 Jun 94 10:23:51 PDT To: firstname.lastname@example.org 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: email@example.com > >firstname.lastname@example.org: >> 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.