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.