Did NSA know about Public Key before Diffie and Hellman did?

[tcmay@netcom.com (Timothy C. May)]

Did the National Security Agency and its crew of mathematicians know
about public key cryptography before Diffie, Hellman, and Merkle made
their mid-70s discovery? There have long been rumors that they did,
but others say it hit them like a ton of bricks, that is, it surprised
them.

This question came up again on sci.crypt recently, and I cautiously
offered the comments of a "source with deep ties to the public key
community." This was Whit Diffe, who told us about this at a
Cypherpunks meeting several months back, but I wasn't sure how public
the information was or if Whit wanted his name attached to this
revelation.

In any case, Steve Bellovin, who of course is on this list himself,
wrote the attached article for sci.crypt. I think it's pretty
interesting and helps to clarify the history of public key crypto, a
topic of some interest here on this list.

Enjoy!

--Tim

Newsgroups: sci.crypt
From: smb@research.att.com (Steven Bellovin)
Subject: Re: HELP! National Security Decision Directive 145
Message-ID: <1994Jan15.192102.26379@ulysses.att.com>
Date: Sat, 15 Jan 1994 19:21:02 GMT
Distribution: usa
Organization: AT&T Bell Laboratories

In article <tcmayCJKzyn.CDt@netcom.com>, tcmay@netcom.com (Timothy C. May) writes:
> Lucien Van Elsen (lucien@watson.ibm.com) wrote:
> : >>>>> Matt Blaze writes:
> : > I recently got a copy of NSAM #160, dealing with requirements for
> : > permissive action links on weapons systems, just by asking the JFK library
> : > to initiate a declassification review.
> 
> : So, does it shed any light on the rumor that came up at the ACM security
> : conference that the NSA (or some other government body) knew about public
> : key encrytion back then?
> 
> A source with deep ties to the public key community says that Gus
> Simmons, heavily involved in the creation of PALs while at Sandia
> until recently, told him that the mid-70s announcement of public key
> hit them like a ton of bricks, as something completely unexpected.

You don't need to cite anonymous sources; at the Festcolloquium in his
honor at the Fairfax conference, Simmons said it publicly.  He said
that he was on a plane to Australia, to give a talk, when he read the
famous Martin Gardener column.  He promptly tore up his slides and
wrote up a new talk.

On the other hand -- when a retiree from NSA alluded to NSAM 160,
Simmons was the one who supplied the memo number.  Both of them agreed
that it was (at the least) the forerunner of public key systems.

Did the NSA have PK in the mid-60's?  The memo doesn't indicate that,
at least in the declassified portions.  A device meeting the
requirements spelled out in the memo could have been constructed
without PK, using hardware available back then.  Envision a device
with a core memory holding a key, an input line, a set of output lines,
and some transistor and/or SSI comparator circuitry, all embedded in
epoxy.  You get exactly *one* chance to enter the right input value,
since core memory uses destructive read-out, and there would be no
reason to include writeback circuits.

This isn't a design that would have been proof against a sophisticated
enemy (let's be precise:  against the USSR), but that was not a design
goal.  It would have stopped random maniacs, deranged weapons officers,
and immediate battlefield use by enemy forces -- and those were the
threats to be guarded against.

I'm quite skeptical that -- with 1963 technology -- a high-reliabilty
PK design could have been built.  And high reliability was an explicit
design goal.

Now -- there was a portion of the memo, near the end, that wasn't released.
In the context of the memo, that section *could* have spelled out long-
term research efforts that would have led to public-key cryptography.
And frankly, given the number and caliber of mathematicians who worked
for NSA, if the right question was asked I think there's no doubt that
they would have found an answer.  According to Diffie's paper, it took
just two years from the initial conception to when RSA was developed.
Would NSA have taken much longer?  I doubt it.

As for why Simmons didn't know of it -- it does strike me as believable
that NSA regarded the technique as too sensitive to use for PALs.  After
all, I claim that a secure (enough) nuclear command and control system
could have been built without PK -- so why discuss it with someone who
(to NSA) didn't have ``need to know''.  Granted, PK would have strengthened
the guarantees -- but security is a matter of engineering against a
whole spectrum of risks, and balancing the tradeoffs; there's nothing
that says you should favor one threat over others because the solution
is sexier.  You or I might have made different choices -- but I don't
think my scenario is out of the question.

		--Steve Bellovin



-- 
..........................................................................
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**859433 | Public Key: PGP and MailSafe available.