(fwd) Re: NSA Helped Yeltsin Foil 1991 Coup
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. If true, a serious compromise of NSA's listening capabilities. Also note the reference to how the coup plotters should've been using PGP. (Prediction: something along these lines will be added to the list of reasons why PGP is bad and Clipper is good..."We need to have Escrowed Coup Plotter Encryption so that we can examine the messages of coup plotters.") --Tim May From: guym@gamma1 (Guy MacArthur) Newsgroups: alt.cyberpunk Subject: Re: NSA Helped Yeltsin Foil 1991 Coup Date: 20 May 1994 01:45:54 GMT Organization: University of Arizona, CCIT Lines: 47 Distribution: world Message-ID: <2rh4oi$p2s@news.CCIT.Arizona.EDU> ben@il.us.swissbank.com (Ben Galewsky) writes: : There is an article on the front page of today's "Independent", a British : daily newspaper. The headline is "US Agents Helped Yeltsin Break Coup". : : It describes how Bush passed on transcripts of encrypted conversations : between the leaders of 1991's failed Soviet coup to Boris Yeltsin. : Apparently the NSA was not too happy that Bush broke their cover and : acknowledged that they could read all of the Soviet military's codes. : : The article reads: : "As soon as the coup started on 18 August, 1991, the NSA, : America's largest intelligence organization was able to decrypt : conversations between the coup's two leaders, Vladimir Kryuchkov, : chairman of the KGB, and Dmitri Yazov, the Defense minister, : taking place over a supposedly secure landline." : : It continues: : "The NSA's ability to decrypt what Soviet military commanders : -- and their successors -- said over their communications system : is probably the most significant intelligence achievement since : Britain broke Germany's Enigma codes during the second world : war." : : Bush decided to pass this info on to Yeltsin. It enabled him to know who : in the military supported the coup and who was against it. : : It finishes by saying that as a result of letting the russians know their : code has been broken "the US intelligence community may no longer be in a : position to have advance warning of momentous events inside Russia -- as : it had months before the coup that brought Yeltsin to power". : : This information came from Seymour Hersh. It will appear in a forthcoming : issue of "Atlantic Monthly" : : I guess the KGB should have been using something secure, like PGP, since : the NSA can't possibly break that ;-) : : At least we can be comforted that the NSA is not allowed to monitor the : domestic traffic. ;-) ;-) : : : Ben Galewsky : ----------------------------------------------------------- : My employer doesn't know I read this group. : They do know I'm posting, though. "Hi Neil!" : ----------------------------------------------------------- :
Timothy C. May says:
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.
If true, a serious compromise of NSA's listening capabilities.
If true, it is seriously disturbing. The KGB is presumably the only entity on earth with cryptography expertise in the range of the NSAs. The notion that in spite of the advances of the last twenty years it is still possible for a few years technical lead to make that much of a difference likely means that what we don't know about conventional cryptosystems is likely still extremely important. I had been running on the assumption for a while that the NSA was slowly losing its capacity to break codes as ones with inherently better and better theoretical underpinnings arrived. If the story is true, it means that the NSA can break some classes of conventional cryptosystems very fast -- fast enough to be of use in this case, for instance. We are all very dependent on things like MD5 and IDEA, which may or may not actually be secure. We should bear this in mind. Perry
Date: Fri, 27 May 1994 14:21:28 -0400 From: "Perry E. Metzger" <perry@imsi.com> We are all very dependent on things like MD5 and IDEA, which may or may not actually be secure. We should bear this in mind. If you suspect that some of the non DOD/NSA cyphers might be broken, but you are not ready to employ one-time-pads, then you should threshold you mesages into N parts so that all N are needed to recover the original. Then encrypt each part under a different cypher. Perhaps IDEA, and 3DES would be apropriate. This will not increase the size of your messages very much since you compress before encrypting -- don't you? j'
Jay Prime Positive writes:
[...] If you suspect that some of the non DOD/NSA cyphers might be broken, but you are not ready to employ one-time-pads, then you should threshold you mesages into N parts so that all N are needed to recover the original. Then encrypt each part under a different cypher.
Perhaps IDEA, and 3DES would be apropriate. This will not increase the size of your messages very much since you compress before encrypting -- don't you?
Most compression programs add a characteristic signature to the beginning of the compressed output file. If a cryptanalyst guesses that you may be compressing before encrypting, wouldn't this make his job easier? To me, this sounds as though you're adding a known bit of "plaintext" to the start of each message. If you're encrypting files that you wish to store securely you could just clip off the signature, I suppose. But this would be unsuitable for sending messages, because your compression program is now incompatible with everyone else's. Or am I missing something? -- Martin Janzen janzen@idacom.hp.com
From: Martin Janzen <janzen@idacom.hp.com> Date: Fri, 27 May 94 14:43:02 MDT Most compression programs add a characteristic signature to the beginning of the compressed output file. If a cryptanalyst guesses that you may be compressing before encrypting, wouldn't this make his job easier? To me, this sounds as though you're adding a known bit of "plaintext" to the start of each message. In short, you are right, compression algorithms often _do_ include a magic number at the begining. However, compression algorithms intended for cryptographic applications don't have to include a magic number. This is especialy true if the crypto system is never used without the compression algorithm. And if magic numbers are unavoidable, then they can be put at the end, and the system run in CFB or CBC modes. Alternatively, a random block can be prepended to the plaintext, and then exored with each of the folowing plaintext blocks (thus creating a garanteed flat distribution for the first bytes of the plain text). Finaly, the state of the art in cryptanalysis (as far as I know), sugests that modern crypto systems aren't as vulnerable to known plaintext as past systems. The best attacks I know of (differential, and linear cryptanalysis) require masive (about 2^30 blocks for DES) amounts of known, or chosen, plaintext -- though miniscule relative to the key size (2^56 again for DES). j'
Jay Prime Positive writes:
From: Martin Janzen <janzen@idacom.hp.com> Date: Fri, 27 May 94 14:43:02 MDT
Most compression programs add a characteristic signature to the beginning of the compressed output file. If a cryptanalyst guesses that you may be compressing before encrypting, wouldn't this make his job easier? To me, this sounds as though you're adding a known bit of "plaintext" to the start of each message.
In short, you are right, compression algorithms often _do_ include a magic number at the begining.
However, compression algorithms intended for cryptographic applications don't have to include a magic number. This is especialy true if the crypto system is never used without the compression algorithm. [...]
OK; so ideally this is something that would be built in to one's encryption/decryption program. I was thinking of UNIX compress, gzip, and the like.
Finaly, the state of the art in cryptanalysis (as far as I know), sugests that modern crypto systems aren't as vulnerable to known plaintext as past systems. The best attacks I know of (differential, and linear cryptanalysis) require masive (about 2^30 blocks for DES) amounts of known, or chosen, plaintext -- though miniscule relative to the key size (2^56 again for DES).
That's good to know! Thanks for the explanation, Jay. -- Martin Janzen janzen@idacom.hp.com Pegasus Systems Group c/o Hewlett-Packard, IDACOM Telecom Operation
Jay Prime Positive says:
Date: Fri, 27 May 1994 14:21:28 -0400 From: "Perry E. Metzger" <perry@imsi.com>
We are all very dependent on things like MD5 and IDEA, which may or may not actually be secure. We should bear this in mind.
If you suspect that some of the non DOD/NSA cyphers might be broken, but you are not ready to employ one-time-pads, then you should threshold you mesages into N parts so that all N are needed to recover the original. Then encrypt each part under a different cypher.
Its far simpler to encrypt your message with multiple systems, one after another, than to break it up in the manner you suggest, and the security is in fact better that way than in the manner you suggest. Perry
From: "Perry E. Metzger" <perry@imsi.com>
If you suspect that some of the non DOD/NSA cyphers might be broken, but you are not ready to employ one-time-pads, then you should threshold you mesages into N parts so that all N are needed to recover the original. Then encrypt each part under a different cypher.
Its far simpler to encrypt your message with multiple systems, one after another, than to break it up in the manner you suggest, and the security is in fact better that way than in the manner you suggest.
Why? If you XOR-split the message and encrypt each mask differently, you are /guaranteed/ that all of the encryption methods must be broken to retrieve the original. If you use repeated encryption, this is much harder to prove, and not always true. There's a result that if you choose the first cipher unwisely, you're hosed no matter what you do on top of it. Eli ebrandt@hmc.edu
From: "Perry E. Metzger" <perry@imsi.com>
If you suspect that some of the non DOD/NSA cyphers might be broken, but you are not ready to employ one-time-pads, then you should threshold you mesages into N parts so that all N are needed to recover the original. Then encrypt each part under a different cypher.
Its far simpler to encrypt your message with multiple systems, one after another, than to break it up in the manner you suggest, and the security is in fact better that way than in the manner you suggest.
Why? If you XOR-split the message and encrypt each mask differently, you are /guaranteed/ that all of the encryption methods must be broken to retrieve the original. If you use repeated encryption, this is much harder to prove, and not always true. There's a result that if you choose the first cipher unwisely, you're hosed no matter what you do on top of it.
Eli ebrandt@hmc.edu I think the second poster assumed what I did - that the message would be split into say 5 parts, each to be encrypted differently. How to X-or split the message isn't obvious to me - pnrg? If you use some bytes conveniently hanging around you may as well use a OTP, since both ends need the same bitstream. Unless I'm missing something, which is usually
On Fri, 27 May 1994, Eli Brandt wrote: the case. David isdmill@gatekeeper.ddp.state.me.us
Eli Brandt says:
Its far simpler to encrypt your message with multiple systems, one after another, than to break it up in the manner you suggest, and the security is in fact better that way than in the manner you suggest.
Why? If you XOR-split the message and encrypt each mask differently, you are /guaranteed/ that all of the encryption methods must be broken to retrieve the original. If you use repeated encryption, this is much harder to prove, and not always true.
You are correct that in extremely weird cases you are screwed. Such cases are nearly IMPOSSIBLE to produce in practice. Anyone out there want to claim that DES and IDEA are inverses? I'll bet a lot that they aren't. Although in THEORY you are correct, in PRACTICE superencipherment wins.
There's a result that if you choose the first cipher unwisely, you're hosed no matter what you do on top of it.
Again, you have to do something startling stupid. Ordinary use won't let this happen. Perry
You are correct that in extremely weird cases you are screwed. Such cases are nearly IMPOSSIBLE to produce in practice. Anyone out there want to claim that DES and IDEA are inverses? I'll bet a lot that they aren't. Although in THEORY you are correct, in PRACTICE superencipherment wins.
It's pretty easy to screw up subtly and not know it. Given that we're discussing how to get encryption more secure than the KGB's best, I think assuming that DES and IDEA's strengths combine additively, or necessarily combine at all, is a mistake. (They don't have to be inverses (they clearly aren't) to be weak -- meet-in-the-middle?) Unless there is some theory to this effect, or at least some dramatic hand-waving... In any event, XOR-splitting is no less secure, and is much more tractable theoretically. It does require a higher-rate random source than is needed just for key generation. (Though if you're willing to wager that the NSA can't factor fast, you could use the BBS PRNG) And it requires linear ciphertext expansion. Just to make it explicit what I'm talking about: take your message A. let A1=A generate a random string X1, with |X1|=|A|. let A1 = X1 xor A1; let A2 = X1 generate another random string, X2 let A2 = A2 xor X2; let A3 = X2 etc. Then send (E1(A1), E2(A2), ... , En(An)), where the Ei's are distinct. Recipient decrypts to get A1, ... An, and calculates A1 xor A2 xor ... xor An = (A xor X1) xor (X1 xor X2) xor ... xor (Xn-2 xor Xn-1) xor (Xn-1) telescoping, = A Eli ebrandt@hmc.edu
The problem with forming product cyphers is the birthday paradox. The problem with threshold cyphers is bandwidth. Concider for example e1( e2( e3( x ))), and the permutations it generates. Let E1 represent the number of permutations generated by e1 under all the different keys, and similarly E2 and E3 the number generated by e2 and e3 respectively. E1, E2, and E3 are all nearly the same as the number of keys for the respective cryptosystems. But there is no garantee that the number of permutation that the composition of e1, e2, adn e3 is equal to the product of the number of keys (E1*E2*E3). Infact, the birthday paradox just about garantees that the number is less than E1*E2*E3. So some of the additional keybits are lost. On the other hand, the number of permutations that the system Eli and I describe *is* garanteed to increase with the addition of cyphers. Concider the same three encryption functions as in the previous case. If the number of permutations generated by e1, e2, and e3 is E1, E2, and E3 respectively, then the number of permutations in ej{e1,e2,e3}(xi) == <e1(xi xor ri), e2(ri)> and ri is a cryptographic random number generated by e3, is exactly E1 * E2 * E3. The problem with thresholding is the linear increase in cyphertext with linear increase in number of keybits. So if you are a bit too paranoid to rely on a single non DOD/NSA cypher, but not willing to use a one time pad, then concider thresholding. If you don't have the communication bandwidth to support it, then certainly fall back to the simpler scheme Perry describes. (Note that Eli and My scheme is only slightly slower to compute than Perry's. It requires computing one extra xor per block. Also note that the actual increase in bandwidth for a three cypher system threshold in a practical encryption package like PGP would not be 2 to 1 since it likely compresses before encryption.) j'
Jay said:
It requires computing one extra xor per block.
Plus a truckload of good random numbers. To do it right, a hardware RNG is in order. A PRNG really makes no sense, because if you have a PRNG that strong, why not just use it as a stream cipher?
that the actual increase in bandwidth for a three cypher system threshold in a practical encryption package like PGP would not be 2 to 1 since it likely compresses before encryption.)
To be fair, you need to compare compressed-and-split with compressed-only. This *is* going to be a factor-of-3 size hit. Eli ebrandt@hmc.edu
Date: Fri, 27 May 94 22:44:29 PDT From: Eli Brandt <ebrandt@jarthur.cs.hmc.edu>
Jay said:
It requires computing one extra xor per block.
Plus a truckload of good random numbers. To do it right, a hardware RNG is in order. A PRNG really makes no sense, because if you have a PRNG that strong, why not just use it as a stream cipher?
I don't see why. I assume the PRNG is cryptographic, and concider its key (and iv) as part of the key to the system. And I don't see why the PRNG needs to be so tremendously strong. Hmmm. Now I think I get it. If the PRNG is the weak link, then the atacker can solve the easy PRNG crypto system and the hard e1 crypo system. On the other hand if it is the strongest crypto system, the atacker will solve the weaker e1 and e2 crypto systems instead. Hmmm. Yeah, you are right. Although the PRNG threshold scheme has E1*E2*E3 permutations, it is really only as hard as either E1*E2, or E1*E3. Yet another example of 'key size is not proportional to strength'. So my new criteria is if you have bandwidth, and strong random numbers, use the threshold scheme. If not, use the product cypher. But perhaps the fenced DES stratagy is better than either. For comparison purposes we would need to know how the fence permutation(s) are keyed.
that the actual increase in bandwidth for a three cypher system threshold in a practical encryption package like PGP would not be 2 to 1 since it likely compresses before encryption.)
To be fair, you need to compare compressed-and-split with compressed-only. This *is* going to be a factor-of-3 size hit.
Yeah, your are right. The Cthr/Cpro will be about 2 to 1. (2 cause I used one key for the PRNG, the other two for encrypting the thresholded pieces.) But Cthr/Plain will not be nearly 2 to 1. I think this is interesting. If you, Eli, think it is interesting enough for the general list, feel free to forward this. j'
From: "Perry E. Metzger" <perry@imsi.com> If the story is true, it means that the NSA can break some classes of conventional cryptosystems very fast -- fast enough to be of use in this case, for instance.
It's also possible that they're not doing a direct cryptanalytic attack. They might be using technical or human means to compromise the key distribution, for example, or they might just have bugged somebody's phone. But, yeah, the bottom line is that they were able to read Russian military communications, which is a substantial achievement.
We are all very dependent on things like MD5 and IDEA, which may or may not actually be secure. We should bear this in mind.
The lack of decent theoretical underpinnings for most cryptosystems is rather worrisome. Eli ebrandt@hmc.edu
participants (7)
-
David Miller -
Eli Brandt -
Jay Prime Positive -
jpp＠jpplap.markv.com
-
Martin Janzen -
Perry E. Metzger -
tcmay＠netcom.com