From: tcmay@netcom.com (Timothy C. May)
Date: Tue, 23 Nov 93 11:23:00 PST
To: cypherpunks@toad.com
Subject: Comments on NSA (was: "Pyrrhus Cracks RSA?")
In-Reply-To: <6E4CCAA7E0204AD3@sleepy.egr.msu.edu>
Message-ID: <199311231920.LAA06189@mail.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


Michael Marotta writes an intruiging political essay, though I have
some corrections/disagreements.

I'll also talk about NSA employment of mathematicians, from the 1950s
on, the founding and funding of Engineering Research Associates, Cray
Research, the Institute for Defense Analysis, and the ultra-secretive
Jasons Group.


> CAN THE GOVERNMENT BUILD AN ATOMIC BOMB?  
> by mercury@well.sf.ca.us <Michael E. Marotta> 

> Cypherpunks know that centralized systems are inefficient, yet 
> they fear the NSA.  Cypherpunks know that government employees 
> are slugabeds, yet they fear the NSA.  Cypherpunks know that 
> qinnovation and enterprise are the antithesis of socialism, yet 
> they fear the NSA.  They don't fear that the NSA will kick in 
> their doors and shoot them in a cybernetic Kristallnacht or burn 
> t(their homes the way the Romans and Mongols did to Carthage and 
> Samarkand.  (Waco comes to mind, here.)  No, the Cypherpunk is 
> afraid that the government has "powerful computers" capable of a 
> "brute force attack" on their algorithms. 

Some Cypherpunks (me, at least) are not afraid of the NSA's powerful
computers. We understand that the mathematics of today's algorithms
means the race is always won by the encryptor, not the cryptbreaker.
If a dozen Crays at the Fort can--somehow--factor a 150-digit number,
and thus break a 512-bit RSA key (more or less), then the encryptor
can trivially move to a 1024-bit key....safe for many generations,
even with 10,000 Crays munching away.

Crypto is economics, as Eric Hughes likes to point out (but he's just
one of my many tentacles, so I can freely quote him), and the public
key math favors the encryptor over the would-be cypher breaker to an
incredible extent, with the advantage growing ever-greater as key
lengths increase.

(Work out the math yourself...the advantage lies with the user of
one-way functions...barring unforeseen breakthroughs in factoring, of
which there is no evidence, or the reported proof that P = NP from
Kryptogorodok, the secret city of Russian cryptographers in the Urals.)

As Phil Karn and several others have noted, the weak link is physical
security. Black bag jobs, viruses, etc. For example, my Macs have
"keyboard capture" buffers, as Unix systems often do, that capture and
stores _all_ keyboard entry in files, as an aid to recovering text
entered. Great for writers, but a terrible security hole. (Watch out
for this on Macs or Unix systems you may use!)

These are the real weaknesses. Floppy disks laying around or "lost"
that have one's secret key on them, combined with keyboard capture of
the PGP passphrase. I expect at least some people have already had
their PGP privacy turned into Pretty Crummy Privacy. And not by
brute-force cracking.

...
> pumps which came from fire trucks.)  Ask "anyone" and they will 
> tell you that World War Two brought us nuclear power, spaceships, 
> radar, television, the transistor, the computer, canned food, and 
> recycling.  In fact, it brought none of these.  They already 

Well, some of these things existed in some form prior to WW II, but
many key innovations reached fruition during the war: radar, rocketry,
gyroscopes, etc. Some things were clearly invented _during_ the war:
nuclear reactors, nuclear bombs, computers, etc. And the transistor,
by the way, came after the war (the ordinary Shockley et. al.
transistor at Bell Labs....the 1930s German work on
metal-insulator-semiconductor devices, by Lillienfeld (as I dimly
recall), was not really a precursor--the significance was not
appreciated until decades later).

> unpacked Diffie's knapsack.  What is most probable, is that these 
> ciphers will stand for some unforeseeable time until someone who 
> may not be born yet comes along and breaks them all as an idle 
> {exercise on her way to greatness in another field. 

Maybe. But if factoring is shown to be NP-complete (it hasn't been so
far, though most suspect it), then this future Gauss will truly be a
giant.

> But the NSA?  No way, Jose.  They might be nerds who hacked some 
> code at 3 am.  But you put them on a salary and benefits in a 
> pyramid, then tell them not to talk about their work, and you 
> thwart whatever creativity they had.  The NSA can kill you.  But 
> t({they can never out-think you. 

For many years the NSA hired as consultants some of the brightest
mathemeticians in the world, including Claude Shannon (information
theory), Andrew Gleason (math), E. Berlenkamp (algebraic coding
theory), David Huffman (Huffman codes), Richard Garwin (physics), Luis
Alvarez (physics, later known for the dinosaur extinction work--the
idea that a giant meteor hit the NSA and killed it...just kidding),
John R. Pierce (communications), Hendrik Bode (Bode plots), and so
on.The NSA also funded Seymour Cray at Engineering Research Associates
in the 1950s and even--many people claim--funded Cray Research in the
early 1970s. NSA also was centrally involved in formation of Mitre
Corp., The Institute for Defense Analysis (IDA), and it built and paid
for the "Communications Research Division" building at Princeton
University...linked to what is now the John von Neumann Supercomputer
Center (I may have the exact title wrong).

(Source: Bamford's "The Puzzle Palace," 1982, and discussions with
Brian Snow of the NSA at the 1988 Crypto Conference.)

Yes, the NSA has long had many "tentacles" into academia. What was
probably so shocking to them about the mid-70s breakthroughs in public
key, by Diffie, Hellman, and Merkle, was that (presumably) this was
work done outside their usual network of contract mathematicians. (NSA
has been making noises about how they'd already discovered public key
crypto years before Diffie and Hellman did. This could be face-saving
bragadoccio. Time will tell. Any NSA readers out there are free to
post anonymously to this group or to alt.whistleblowers, or to "sell"
your memoirs on BlackNet.)

Mathematicians have to seek funding from somewhere. For many years,
NSA was a prime source--and may still be. The "SCAMP" program ("Summer
Campus, Advanced Mathematics Program") meets in a special building on
the UCLA campus to discuss items of interest to the Agency, and to
fund mathematicians who attend. Much like the ultra-secret "Jasons"
and their summer work on La Jolla, California.

A fascinating topic. I sure do wish someone would write another book
on the Agency.

--Tim May


-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^756839 | Public Key: PGP and MailSafe available.
Note: I put time and money into writing this posting. I hope you enjoy it.