(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 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

On Fri, 27 May 1994, Eli Brandt wrote:

> > 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 
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'

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

> 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