Slashdot Mirror
John Nash's Declassified 1955 Letter To the NSA
An anonymous reader writes "In 1955, John Nash sent an amazing letter (PDF) to the NSA in order to support an encryption design that he suggested. In it, he anticipates computational complexity theory as well as modern cryptography. He also proposes that the security of encryption can be based on computational hardness and makes the distinction between polynomial time and exponential time: 'So a logical way to classify enciphering processes is by the way in which the computation length for the computation of the key increases with increasing length of the key. This is at best exponential and at worst probably at most a relatively small power of r, ar^2 or ar^3, as in substitution ciphers.'"
Hereâ(TM)s some linkys to the actual NSA website pages that talk about this:
http://www.nsa.gov/public_info/press_room/2012/nash_exhibit.shtml
http://www.nsa.gov/public_info/_files/nash_letters/nash_letters1.pdf
If you want news from today, you have to come back tomorrow.
I think overtly creative people get to be that way partly because they are not "normal". It is their gift or mindset to be able to see, conjecture and analyze what others can not fathom.
Yet we tend to shy away from anyone who is "not normal". I am glad Mr. Nash has been able to proceed in his career in spite of his problems. I hope his story gives others with problems some inspiration.
John Nash is one of my favorite things ever and definitely the best thing Don Johnson has done in a long time. I really like the girl who plays his daughter on the show (isn't it his daughter in real life?). Plus, Cheech Marin is great comic relief.
Reading Nash's letters makes me realize how much better presentation medium powerpoint is.
And also how much junk is made to sound nice, just with a nice presentation.
A schizogram?
I hear Big Daddy Cool wrote a classified letter to the WWF in 1995.
Memorable quotes for
Looker (1981)
http://www.imdb.com/title/tt0082677/quotes [imdb.com]
âoeJohn Reston: Television can control public opinion more effectively than armies of secret police, because television is entirely voluntary. The American government forces our children to attend school, but nobody forces them to watch T.V. Americans of all ages *submit* to television. Television is the American ideal. Persuasion without coercion. Nobody makes us watch. Who could have predicted that a *free* people would voluntarily spend one fifth of their lives sitting in front of a *box* with pictures? Fifteen years sitting in prison is punishment. But 15 years sitting in front of a television set is entertainment. And the average American now spends more than one and a half years of his life just watching television commercials. Fifty minutes, every day of his life, watching commercials. Now, thatâ(TM)s power. â
âoeThe United States has itâ(TM)s own propaganda, but itâ(TM)s very effective because people donâ(TM)t realize that itâ(TM)s propaganda. And itâ(TM)s subtle, but itâ(TM)s actually a much stronger propaganda machine than the Nazis had but itâ(TM)s funded in a different way. With the Nazis it was funded by the government, but in the United States, itâ(TM)s funded by corporations and corporations they only want things to happen that will make people want to buy stuff. So whatever that is, then that is considered okay and good, but that doesnâ(TM)t necessarily mean it really serves peopleâ(TM)s thinking â" it can stupify and make not very good things happen.â
â" Crispin Glover: http://www.imdb.com/name/nm0000417/bio [imdb.com]
âoeWeâ(TM)ll know our disinformation program is complete when everything the American public believes is false.â â" William Casey, CIA Director
âoeItâ(TM)s only logical to assume that conspiracies are everywhere, because thatâ(TM)s what people do. They conspire. If you canâ(TM)t get the message, get the man.â â" Mel Gibson
[1967] Jim Garrison Interview âoeIn a very real and terrifying sense, our Government is the CIA and the Pentagon, with Congress reduced to a debating society. Of course, you canâ(TM)t spot this trend to fascism by casually looking around. You canâ(TM)t look for such familiar signs as the swastika, because they wonâ(TM)t be there. We wonâ(TM)t build Dachaus and Auschwitzes; the clever manipulation of the mass media is creating a concentration camp of the mind that promises to be far more effective in keeping the populace in line. Weâ(TM)re not going to wake up one morning and suddenly find ourselves in gray uniforms goose-stepping off to work. But this isnâ(TM)t the test. The test is: What happens to the individual who dissents? In Nazi Germany, he was physically destroyed; here, the process is more subtle, but the end results can be the same. Iâ(TM)ve learned enough about the machinations of the CIA in the past year to know that this is no longer the dreamworld America I once believed in. The imperatives of the population explosion, which almost inevitably will lessen our belief in the sanctity of the individual human life, combined with the awesome power of the CIA and the defense establishment, seem destined to seal the fate of the America I knew as a child and bring us into a new Orwellian world where the citizen exists for the state and where raw power justifies any and every immoral act. Iâ(TM)ve always had a kind of knee-jerk trust in my Governmentâ(TM)s basic integrity, whatever political blunders it may make. But Iâ(TM)ve come to realize that in Washington, deceiving and manipulating the public are viewed by some as the natural prerogatives of office. Huey Long once said, âoeFascism will come to America in the name of anti-fascism.â Iâ(TM)m afraid, based on my own experience, that fascism will come to America in the name of national security.â
After Nash invents modern cryptography, explains it quite eloquently in a few pages of hand written notes, and designs and builds an electronic machine that automatically encrypts / decrypts the messages. He is then sent form letter rejection by the government: "It has been found that cryptographic principles involved in your system, although ingenous, do not meet the necessary requirements for official application."
There's a glowing radioactive strip in my arm I'm sure is pregnant with meaning; I hope this newly revealed information will allow me to decode it.
They hint that they have found a weakness in it, but for some reason they don't disclose it. It might be the case that the NSA wanted to keep it secret, just like the British did.
Or, they simply wanted to butter him up and keep him quiet because the presiding industrial defence complex entities at the time (Westinghouse, GE, Hughes, Bell Telephone (or later, AT&T), etc.) already had inferior, but completed cryptographic solutions ready to go. How many times has the Fed been handed elegant solutions to problems only to pass them by for fixes given to them by men from the old boy's network?
Python: 'And then suddenly you have a language which says "we're all stuck with whatever the whiniest coder wants".'
You're right, I can't imagine why they'd work with a vendor with a three-decade track record of on time deliveries and at-cost wartime contracting, when an academic and known schizophrenic with no manufacturing or operational experience was available.
Don't blame me, I voted for Baltar.
You're completely glossing over my point; how many times has the government spent millions on massive, bloated, unworkable solutions after they get handed an elegant solution? I suspect the cases are in the thousands. Thanks for being so cavalier with MY money.
Python: 'And then suddenly you have a language which says "we're all stuck with whatever the whiniest coder wants".'
Did he invent modern cryptography? I just skimmed the machine description but how much different is it from the Engima (built 10-20 years before 1950)?
He did get to the crux of his letter eloquently. I wonder what he would have come up with if he worked with another genius on it. Is it ironic that around this time the UK was injecting Turing with hormones?
As I read the correspondence I tried to put myself in the position of Dr. Campaigne, and tried to figure out whether what Nash was saying made any sense. I confess that Nash's presentational style made me feel as though I was reading what Nash himself referred to as "a crank or circle-squarer". The core of Nash's invention is a squiggly, messy node graph of colored lines demonstrating a manually obfuscated binary function. But the importance of his communication is the importance of P vs. NP functions, which Nash communicated very very obliquely. Nash's Unabomber handwritten font didn't help him either.
I feel bad that I would have made the same mistake that Campaigne did. But I think nearly anyone would have.
I suspect the cases are in the thousands.
Ah, well. As long as you have hard numbers, then.
Thanks for being so cavalier with MY money.
You would, of course, be saying the exact same damn thing if the government were spending millions of dollars on elegant-sounding but ultimately impractical or unworkable solutions offered by academic geniuses with no experience in government or project management.
~Idarubicin
The moral of the story is, if you ever develop some new scheme that will be of interest to the government, and particularly its secret agencies, send full details to anyone and everyone else.
Particularly in these times of the Western Autumn.
Actually I was surprised by how much interest the NSA showed. Here was a young (~27) assistant professor of math writing to the government largely out of the blue. Nash himself was relatively insecure in his reputation, at least to this audience:
"I hope my handwriting, etc. do not give the impression I am just a crank or circle-squarer. My position here is Assist. Prof. of math. My best known work is in game theory (reprint sent separately)."
Even though he's insecure, he still chose to hand-write his letters sloppily with relatively poor penmanship and words crossed out. Still, the NSA dutifully corresponded with him and analyzed his machine, concluding
"[it] has many of the desirable features of a good auto-key system; but it affords only limited security, and requires a comparatively large amount of equipment. The principle would not be used alone in its present form and suitable modification or extension is considered unlikely, unless it could be used in conjunction with other good auto-key principles."
The letters certainly don't give me the impression of someone who is serious about making a working cypher machine. He's pretty clearly just dabbling in cryptography because it's a nice mental game for him to play. That doesn't necessarily mean his ideas should be ignored, and (somewhat surprisingly) the NSA didn't ignore them.
Ah, well. As long as you have hard numbers, then.
You've never heard the reports of government waste in the media? I find that difficult to believe.
You would, of course, be saying the exact same damn thing if the government were spending millions of dollars on elegant-sounding but ultimately impractical or unworkable solutions offered by academic geniuses with no experience in government or project management.
I find that many government geniuses have no experience in government or project management. Glad you seem to have gotten so lucky.
Python: 'And then suddenly you have a language which says "we're all stuck with whatever the whiniest coder wants".'
dude, they are payed to be secretive. they are the big brother of the CIA. hell they probably used to spy on the CIA.
they probably took his theories and used them (if they didnt already have people who had come to similar conclusions working for them already).
Your first mistake: you misunderstood 1950s formal pleasantry with insecurity.
"My best known work is in game theory." roughly translates to "I'm a well-known badass in this other field, so you'd be an idiot to ignore me."
What about the "crank or circle-squarer" bit? He was afraid of getting put in a crank file. See this article for a fascinating discussion of mathematical cranks, among them angle trisectors and circle-squarers:
"Many mathematics departments do not bother with crank work, throwing it out or putting it in a file labeled 'nuts' or 'crackpots.'"
That he was at all afraid of that outcome implies his insecurity, regardless of his work in game theory (which is of course distinct from cryptography) or his own opinion of it. By the way, Nash hadn't won any major awards by 1955 (as far as I can tell). His Nobel came in the 90's, for instance. He used MIT math department stationary, probably for convenience and also as proof that he was at least somewhat respectable. Conversely, he wasn't not respectable either; his mental problems didn't develop until around 1959. He was just afraid of getting ignored.
It may have been handwritten for secrecy reasons, given the national security implications Nash thought the work had. He might not have wanted to send it through the MIT typing staff. That was the era before computers and TeX, remember. ~~~~
Hmm, and totally unrelated, nobody's using Hash127 either ...
- Michael T. Babcock (Yes, I blog)
What Nash seems to be describing is a feedback shift register. This has potential as a cryptosystem, but isn't a very good one. As the NSA pointed out, it "affords only limited security".
When Nash wrote this, Friedman had already developed the theory that allowed general cryptanalysis of rotor-type machines. But that was still highly classified. Friedman, of course, was responsible for breaking the Japanese "Purple" cypher, plus many others. Before Friedman, cryptanalysis was about guessing. After Friedman, it was about number crunching.
Friedman was the head cryptanalyst at NSA at the time. Within NSA, it would have been known that a linear feedback shift register was a weak key generator. So this idea was, properly, rejected. At least NSA looked at it. Friedman's hard line on that subject was "No new encryption system is worth looking at unless it comes from someone who has already broken a very hard one."
The fact that a problem is NP-hard isn't enough to make it a good key generator. The Merkle-Hellman knapsack cryptosystem, the first public-key cryptosystem published, is based on an NP-hard problem. But, like many NP-hard problems, it's only NP-hard in the worst case. The average case is only P-hard. (Linear programming problems, and problems which can be converted to a linear programming problem, are like that.) So that public-key system was cracked.
We still don't have cryptosystems which are provably NP-hard for all cases. Factoring and elliptic curves are as good as it gets, and there's still the possibility that a breakthrough could make factoring easy.
Yup, and in fact I did think of that when I wrote the post above. My main complaint was his sloppy writing style. He could certainly have done a more professional job of writing his letters by hand. Using the ones we have as drafts and copying their corrected contents carefully to new paper would have made a big difference, for instance. Of course these are minor points; I was just pleasantly surprised the NSA gave him the attention he seems to have deserved in spite of his stylistic flaws.
I wonder if he could type--or, more generally, if academics and particularly mathematicians generally had that skill in the mid 50's.
(I don't think TeX would have been much more helpful than a standard word processor to him since there were so few equations, and typesetting them would be extremely simple. I'd use some other program like OmniGraffle to generate the diagrams.)
So... this new letter shows that Nash had what amounts to a new set of tactics for picking up girls at a bar, right?
Wow. You really don't understand how academic politeness works? Yes, he was rightfully worried that his letter would be ignored, because he knew that a handwritten letter without an up-front defense would be ignored automatically.
What he wrote is simply the polite way of saying "do not mistake me for a crank; here are my credentials". The fact that he covered his bases is not evidence that he was insecure; instead, it's evidence that he understood how the letter would be received and wrote the necessary defense in polite terms. That defense worked, and it wasn't ignored.
You say fear and insecurity. I say realism and politeness. He was confident in his ideas, but he knew he had not yet earned "stop everything; we just received a letter from the esteemed Dr. Nash" status with the NSA, so he offered proof that he deserved to be heard. If you think that's fear and insecurity, then you've got a thing or two to learn about approaching three letter agencies.
Parts of Nash's dissertation was also handwritten, so I don't t think that should be any indication of a lack of thoughtfulness.
I've read the documents and i believe that i understand them but perhaps not. It appears that Nash has forgotten a + or - on one of the permutation rules. No that big of a deal as one should be able to deduce it's value from the other rules. But both values produce an infinite loop. Perhaps a mistake was made else where. It appears that the mechanics are there and are sound (insofar as its level of encryption).
It would have been fun to work through it and perhaps implement it via simple JavaScript or something, but my attention span is too short tonight to determine where the mistake is, perhaps in the morning. . .
I think we actually agree. By "insecure", I meant he was not secure in his reputation with the NSA. He seemed quite confident about the correctness and worth of the ideas he presented. I suppose he may or may not have literally felt fear about getting ignored. Perhaps it's not standard, but to me the phrase "X was afraid of Y" is an idiom that doesn't necessarily imply X feels fear. For instance, take "I'm afraid you'll have to leave" or "He's afraid the door will be locked and he'll have to go around back in the cold."
To be clear, I understand your "translation" of his "1950's politeness". It's so obvious that I didn't feel the need to explicitly agree with you. I only bring it up now since you repeated your translation in different words as if I didn't understand the first version (or the original text).
I don't know why you keep obliquely insulting me ("Your first mistake was..." [you never got to my second mistake, by the way; did you have one?]; "Wow. You really don't understand how academic politeness works?"). It's distracting.
I agree that just because they were handwritten doesn't necessarily indicate a lack of thoughtfulness. He probably wanted to avoid having a secretary type them up to keep them secret. That they're sloppily handwritten does indicate a lack of thoughtfulness, though not necessarily about the key ideas: mostly, his presentation could have been better. Beyond the stylistic issues I mentioned above, there is for instance this sentence:
"Recently a conversation with Prof. Huffman here indicated that he has recently been working on a machine with similar objectives."
A more thoughtful presentation might replace the second "recently" with "lately" or similar. His description of his exponential conjecture could also have used a second draft. As an example, he says "n is the maximum span of the 'memory' of the process" when in fact he (probably accidentally) put n+1 x_k's in his function, so the 'memory' would be n+1, not n.
(Just so I don't give the wrong idea, I found the letters fascinating. That I found flaws in them is not terribly important.)
Did he invent modern cryptography?
No. His "machine" (the letters don't imply it was ever built) certainly wasn't the only one of its kind. If anything, the letters might give him some vague claim on the beginnings of computability and/or computational complexity theory, though his "exponential conjecture" isn't really developed enough to earn him much credit for either, IMO.
Is it ironic that around this time the UK was injecting Turing with hormones?
It's certainly coincidental. There are some rumors that Nash was bisexual (inasmuch as he had some sort of maybe-sexual relationship with some men, or was attracted to some men), though he allowed his wife to deny it in a 60 Minutes interview. There's some discussion of the issue in the book A Beautiful Mind was based on.
While it's a bit off topic, I hope for a day where society doesn't care about a person's sexuality, and where I stop keeping a mental list of the non-heterosexual celebrities I know of. Until that day comes, thank you Anderson Cooper, Ellen Degeneres, Wanda Sykes, Alan Turing, ....
Beyond English department embroidery, there's little to fault with Nash's composition. His argument develops logically, his sentences parse correctly, he sticks to the primary points, and he's clear both about the potential significance and the nature of the mechanics involved.
This particular English department suggestion made me laugh out loud. How is it that adjectives became spin one-half particles? There are two distinct recent events in his sentence (the work and the discussion about the work). You suggest his presentation is weak because the cognitive Boson (recentness) wasn't recast as Fermionic when appending the -ly affix. When writing to the NSA, which is notorious for using seven levels of Fraktur script to distinguish algebraic levels, one presumes they can't keep two verb instances straight in a simple English sentence.
In high school I was given a composition exercise to write a paragraph on camera assembly. We were given the steps as a mishmash. It was an exercise in achieved logical order.
My solution: ...
The A goes into the B.
The B goes into the C.
The C goes into the D.
QED.
I varied the "goes into" part appropriately. In fact, I wrote very nice sentences. What I did not vary was beginning every sentence with "The". My English teacher was so annoyed with my stylistic uniformity he docked me severely. I could only raise my eyebrows and file his feedback in my Twilight Zone folder. We weren't given any objective function on the benefits of faux variation of form upon correct assembly, yet we were expected to engage in the art of embroidery nevertheless.
Nash made a pretty good start there. If he had received a one sentence answer (with or without confounding word repetitions) explaining that the class of LFSR ciphers (or whatever refined class is most suitable) are known to have a weak of the following nature, expressed perhaps with a supplemental equation or three, it would have been very interesting to read Nash's next response.
The next NSA response (if they were willing to engage in such a dialog) would likely have been "you're still on the right track, but the bar is higher yet".
One needs to realize that Nash is precisely the person the NSA doesn't wish to encourage to clear any bars for which they do not yet know the solution, as he was not of the right temperament to nurture in house, and not in any way predictable out-of-house.
Pedantic interjection: Oh look, I did something terrible and inconsistent with my compound adverbial prepositions in my previous sentence. Here I'm using my hyphens as instruction prefetch markers to the front-end sentence parser ("in house" hardly needs a hint as situated).
If I were in the NSA, however, I would use a regular hyphen where it appears as a prefetch hint, and a Fractur hyphen when used in a capacity that maps into the semantic parse tree. That place is packed with pedants. If you don't keep your levels straight, conversation degenerates and no ciphers are broken.
Shortly after pressing submit, I realized that I made light of the difference between adjectives and adverbs when I first commented on the adenoidal Fermions. Like the difference between ovaries and testicles, people tend to insist upon the distinction even when it isn't terribly germane. Either type leads to adenoidal behaviour patterns.
Hah, that was hilarious, thank you.
While I don't quite agree with you about the quality of his exposition, I also don't see the point of discussing it further since it's such a minor issue. I will if you wish, though.
I'm not sure where "[Nash was] not in any way predictable out-of-house" came from. I'm no Nash expert, but his mental disturbances didn't start until 1959, several years after these letters were written. From the letters, the impression I got was that his ideas simply weren't advanced enough to merit him further time, rather than him being unsuitable for being in-or-out-of-house with the NSA.
Another comment talked about people with self-diagnosed Aspergergers sysndrome.
It appears I have it as I write software for a living and like listening to techno which is HIGHLY repetitive music (even if FABULOUSLY composed/performed).
Anyway the post mention John Nash and Richard Feynman -- an introvert and an extrovert who were both geniuses but had two diametrically opposed 'methods' for interacting with other people.
In my case, I pretty much have NO patience for 'socializing'. I see it pretty much as a waste of time...like push-based advertising.
Just give me specs and $$$ so I can churn out the code you want, thank you very much, full stop!
Interacting with other people in this manner makes me a 'black box' which I don't mind.
Until that day comes, thank you Anderson Cooper, Ellen Degeneres, Wanda Sykes, Alan Turing, ....
Niel Patrick Harris
I've made a full transcript of the declassified PDF: http://www.gwern.net/docs/1955-nash