What does the NSA think of academic cryptographers? Recently-declassified document provides clues
Brighten Godfrey was one of my officemates when we were grad students at Berkeley. He’s now a highly-successful computer networking professor at the University of Illinois Urbana-Champaign, where he studies the wonderful question of how we could get the latency of the Internet down to the physical limit imposed by the finiteness of the speed of light. (Right now, we’re away from that limit by a factor of about 50.)
Last week, Brighten brought to my attention a remarkable document: a 1994 issue of CryptoLog, an NSA internal newsletter, which was recently declassified with a few redactions. The most interesting thing in the newsletter is a trip report (pages 12-19 in the newsletter, 15-22 in the PDF file) by an unnamed NSA cryptographer, who attended the 1992 EuroCrypt conference, and who details his opinions on just about every talk. If you’re interested in crypto, you really need to read this thing all the way through, but here’s a small sampling of the zingers:
- Three of the last four sessions were of no value whatever, and indeed there was almost nothing at Eurocrypt to interest us (this is good news!). The scholarship was actually extremely good; it’s just that the directions which external cryptologic researchers have taken are remarkably far from our own lines of interest.
- There were no proposals of cryptosystems, no novel cryptanalysis of old designs, even very little on hardware design. I really don’t see how things could have been any better for our purposes. We can hope that the absentee cryptologists stayed away because they had no new ideas, or even that they’ve taken an interest in other areas of research.
- Alfredo DeSantis … spoke on “Graph decompositions and secret-sharing schemes,” a silly topic which brings joy to combinatorists and yawns to everyone else.
- Perhaps it is beneficial to be attacked, for you can easily augment your publication list by offering a modification.
- This result has no cryptanalytic application, but it serves to answer a question which someone with nothing else to think about might have asked.
- I think I have hammered home my point often enough that I shall regard it as proved (by emphatic enunciation): the tendency at IACR meetings is for academic scientists (mathematicians, computer scientists, engineers, and philosophers masquerading as theoretical computer scientists) to present commendable research papers (in their own areas) which might affect cryptology at some future time or (more likely) in some other world. Naturally this is not anathema to us.
- The next four sessions were given over to philosophical matters. Complexity theorists are quite happy to define concepts and then to discuss them even though they have no examples of them.
- Don Beaver (Penn State), in another era, would have been a spellbinding charismatic preacher; young, dashing (he still wears a pony-tail), self-confident and glib, he has captured from Silvio Micali the leadership of the philosophic wing of the U.S. East Coast cryptanalytic community.
- Those of you who know my prejudice against the “zero-knowledge” wing of the philosophical camp will be surprised to hear that I enjoyed the three talks of the session better than any of that ilk that I had previously endured. The reason is simple: I took along some interesting reading material and ignored the speakers. That technique served to advantage again for three more snoozers, Thursday’s “digital signature and electronic cash” session, but the final session, also on complexity theory, provided some sensible listening.
- But it is refreshing to find a complexity theory talk which actually addresses an important problem!
- The other two talks again avoided anything of substance. [The authors of one paper] thought it worthwhile, in dealing [with] the general discrete logarithm problem, to prove that the problem is contained in the complexity classes NP and co-AM, but is unlikely to be in co-NP.
- And Ueli Maurer, again dazzling us with his brilliance, felt compelled, in “Factoring with an Oracle” to arm himself with an Oracle (essentially an Omniscient Being that complexity theorists like to turn to when they can’t solve a problem) while factoring. He’s calculating the time it would take him (and his Friend) to factor, and would like also to demonstrate his independence by consulting his Partner as seldom as possible. The next time you find yourself similarly equipped, you will perhaps want to refer to his paper.
- The conference again offered an interesting view into the thought processes of the world’s leading “cryptologists.” It is indeed remarkable how far the Agency has strayed from the True Path.
Of course, it would be wise not to read too much into this: it’s not some official NSA policy statement, but the griping of a single, opinionated individual somewhere within the NSA, who was probably bored and trying to amuse his colleagues. All the same, it’s a fascinating document, not only for its zingers about people who are still very much active on the cryptographic scene, but also for its candid insights into what the NSA cares about and why, and for its look into the subculture within cryptography that would lead, years later, to Neal Koblitz’s widely-discussed anti-provable-security manifestos.
Reading this document drove home for me that the “provable security wars” are a very simple matter of the collision of two communities with different intellectual goals, not of one being right and the other being wrong. Here’s a fun exercise: try reading this trip report while remembering that, in the 1980s—i.e., the decade immediately preceding the maligned EuroCrypt conference—the “philosophic wing” of cryptography that the writer lampoons actually succeeded in introducing revolutionary concepts (interactive proofs, zero-knowledge, cryptographic pseudorandomness, etc.) that transformed the field, concepts that have now been recognized with no fewer than three Turing Awards (to Yao, Goldwasser, and Micali). On the other hand, it’s undoubtedly true that this progress was of no immediate interest to the NSA. On the third hand, the “philosophers” might reply that helping the NSA wasn’t their goal. The best interests of the NSA don’t necessarily coincide with the best interests of scientific advancement (not to mention the best interests of humanity—but that’s a separate debate).
Follow
Comment #1 November 16th, 2014 at 1:17 pm
Maybe the report should be read given the context that the last couple of years leading up to EuroCrypt92 had seen the (re)discovery of differential cryptanalysis by Biham and Shamir. Biham had a string of papers in EuroCrypt{91,93,94}.
I’ve never heard theoretical crypto researchers being described as philosophers, but it makes sense – and I don’t think that it’s something to be ashamed of either, for that matter. I left TCS after writing my thesis, which probably wouldn’t have impressed the guy from NSA, and my work now is algorithmic but with immediate applications (solving users’ problems here and now). Sometimes I feel that parts of TCS feel like creating problems just to solve them, but then again I also see lots of results for which I don’t feel that way. But I do hope that the subject keeps its connections with problems and algorithms in the real (non-oracle) world.
Comment #2 November 16th, 2014 at 3:34 pm
How do we know the extent to which Koblitz’s thinking is representative of the NSA?
Comment #3 November 16th, 2014 at 4:18 pm
anon #2: You’re right; we don’t. I just thought there were some obvious points of convergence between the views of this particular person at NSA, and the views Koblitz would later express in his writings.
Comment #4 November 16th, 2014 at 5:27 pm
Gunnar #1: “Sometimes I feel that parts of TCS feel like creating problems just to solve them”
Maybe.. But I think that in most cases the purpose is to create abstract problems, each one which being equivalent to N concrete problems, and to to solve them (thus helping to solve the concrete ones).
Comment #5 November 16th, 2014 at 5:29 pm
Wow, this redaction is less than perfect: the author was at this Balatonfüred conference with her Hungarian-American wife called Donna. What are the rules, is he fair game?
Comment #6 November 16th, 2014 at 5:42 pm
Anon #4: Yeah, I noticed that too! It’s surely enough information to figure out who the writer was, if one cared and had enough time to dig (I don’t and don’t).
Comment #7 November 16th, 2014 at 8:11 pm
FWIW, it bears pointing out that there are nowadays plenty of serious research cryptographers (mostly outside the US, or in the US but outside academia) who similarly think that Crypto/Eurocrypt and theoretical cryptography can sometimes become self-parody. Note that theoretical cryptography is a subset of provable security, not equal to it — there are lots of people who find value in provable security but don’t enjoy papers on concurrent quantum non-malleable zero-knowledge proofs with O(log n) rounds based on regular one-way functions (apologies in advance if there is a paper with that title!)…
Comment #8 November 16th, 2014 at 8:15 pm
Anon #4, Scott #5: Presumably the author also has initials “REK”, from the comment on one-way functions at the top of page 19.
Comment #9 November 16th, 2014 at 8:48 pm
Maybe it was disinformation. As Salvatore “Big Pussy” Bonpensiero said (in “The Sopranos”, “That disinformation – it’s the nuts!” (Or something like that.)
Comment #10 November 16th, 2014 at 11:39 pm
The converse of this is that the NSA must just *hate* djb.
All the same, was a little cocky to (seemingly) draw broad conclusions from the lack of practical-crypto progress at one academic conference. I mean, we got AES, designed by a couple smart non-Americans no less, widely deployed in hardware, and lots of little advances in how cheaply you could deploy crypto that add up to something substantial.
And Internet corporations finally got behind working harder on practical security; it took the (unplanned) release of rather more than that newsletter to make it happen, but it’s happening.
I suppose all this happened later than it might have had crypto academics had a different focus, and in that sense the Crypto-Log writer had a point. But a too-slowly-arriving future does arrive in the end anyway.
Comment #11 November 17th, 2014 at 1:54 am
Hat tip to George Porter from whom I learned of this.
Comment #12 November 17th, 2014 at 2:41 am
I just was so very delighted to read at the very start of this post about what your friend is working on! We sorely need more smart people working exactly on this sort of stuff. And we need more journalists, TED talks, and popular science coverage on this sort of not-so-glamorous (IMO), perhaps incrementally progressing work.
Unfortunately, the science media seems to obsess about is the exotic & sensational. String theory, multiverses, et cetra.
Comment #13 November 17th, 2014 at 3:35 am
I just loved the document. It’s so refreshing to get the rare chance to hear the true, frank opinions of a knowledgeable, intelligent (presumably) man. Or woman.
How often at the typical conference or seminar do I get to hear that “these sessions were of no value whatever” or “that was a silly talk” or something like that.
It’s not that silly talks don’t exist, it is just that we have become too diplomatic & nicety nice to call them out. Perhaps if we were forthright & told people more often that what he was presenting was BS the quality of overall work might improve?
Comment #14 November 17th, 2014 at 4:47 am
Rahul: OK then, my frank opinion is that your comments are tiresome and wrongheaded. 😉
1. I referred to the writer as “he” not because I’m sexist, but rather because (as mentioned in comment #4) he talks, unredactedly, about his Hungarian-American wife Donna, and I don’t believe there were lesbian marriages in 1992.
2. How many academic conferences have you gone to? If you hang out at coffee breaks, I guarantee you can hear plenty of sentiments of the form “these sessions were of no value whatever” or “that was a silly talk.” Of course, if a piece of research is merely forgettable—rather than wrong, massively overhyped, unfair in allocating credit, etc.—then there’s no particular reason to broadcast those sentiments through a megaphone, rather than sharing them in private. People who do it anyway are known as “assholes.”
3. Related to 2, once a piece of research has cleared the bars of being correct and original, whether it’s “of value” is an inherently subjective question—as the writer of this trip report, to his credit, clearly understands. The same talk could be worthless to someone who needs to know what the NSA should be worried about right now, and highly worthwhile to someone who wants a deep understanding of how much of cryptography can be based solely on the assumption that one-way functions exist. Or vice versa.
4. It’s also important not to conflate “truth” with “frankness,” as many people do. That someone is frank in sharing their feelings about a talk is a good first step, but it doesn’t imply that those feelings are right, or (for example) are shared by other intelligent listeners.
5. I agree that Brighten’s research is awesome! But as usual, you seem miscalibrated to me. Yes, plenty of science journalism is cringe-inducing (particularly when it involves the multiverse), and yes, people ought to have a better understanding of the backbone of the Internet, how it could change, and how it affects their lives. But neither of these problems is reducible to “too much science journalism” or “not enough technology journalism.” There’s lots of good discussion about the future of the Internet—whether in the technology sections of New York Times or almost any other newspaper (the NYT is unusual only in also having a science section), or Slashdot, tech blogs, etc. Though of course, if you like getting enraged by too much attention paid to far-out speculation and theory, then it’s a good idea to continue visiting blogs written by theorists. 🙂
Comment #15 November 17th, 2014 at 6:01 am
Scott #13:
Arggh. Sorry.
I wasn’t trying to insinuate that you were being sexist. Not at all. I was just being defensive & using a “he-she” hedge to be on the safer side. Lest someone ask how I knew he was a he.
I hadn’t read the bit about the Hungarian wife yet.
Comment #16 November 17th, 2014 at 1:33 pm
Interesting, given the discrete log and Ueli Maurer references, is this pointer from Wikipedia: Ueli Maurer: Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms. In: Advances in Cryptology – Crypto ’94. Springer-Verlag, 1994, S. 271−281
Comment #17 November 17th, 2014 at 2:01 pm
Not to sound paranoid or anything.(but I’m gonna sound paranoid)
Could NSF be more amenable to funding less practical avenues of crypto research? If you control the funding(and the USFG does control much of it) you gradually pull the field astray.
Comment #18 November 17th, 2014 at 4:15 pm
Theory sometimes (often?) works on problems that are easy to state and may have nice solutions rather than problems that people in the outside world care about. However, there are now many theorists who DO work with the outsiders and DO work on problems that matter.
But in Crypto it might be worse since the NSA might not tell us what they care about!
Comment #19 November 17th, 2014 at 4:22 pm
Now, it’s been a while since I’ve been to a Math Event, but this sounds pretty much like 1.5-sigma arrogance and benign sociopathy for that population.
Comment #20 November 17th, 2014 at 5:21 pm
As to whether this was representative of NSA opinion, see here:
He goes on to note a different failure of redaction of the author’s name, his initials in a parenthetical at the top of page 19. I had assumed that those were added by an editor, not the original author, but it is in the middle of a quotation, so it’s plausible.
Comment #21 November 18th, 2014 at 3:08 am
Indeed. Though the rest of the world is probably implicitly telling us what it cares about i.e. not letting NSA succeed.
Comment #22 November 18th, 2014 at 4:33 am
Question by almost surely everyone out there: Do 99.9% of professors do anything more than work for tenure, get paychecks, go home and sleep?
Comment #23 November 18th, 2014 at 7:25 am
a #22: Yes, surely >0.1% of them also write blogs.
Comment #24 November 18th, 2014 at 10:55 am
a: Who has time for sleep? I’ve worked 27 hours already this week and it’s only Tuesday night.
Comment #25 November 18th, 2014 at 2:38 pm
1. Oh we are philosophers? Cool, now I know why there is a Ph next to the D. I used to find that confusing.
2. Isn’t the NSA guy’s terminology odd? There is something old-fashioned about the sound of “cryptology” as opposed to “cryptography”. And I don’t think Silvio Micali’s research is really cryptanalysis, so how was he the leader of any wing of the East Coast cryptanalytic community?
3. Given recent-ish revelations about the NSA, I am relieved we have been useless to them.
Comment #26 November 18th, 2014 at 7:25 pm
What the heck is the difference between cryptography and cryptology? I understand -ography vs -ology, but what’s the difference when it comes to the modern usage of the words? I think I remember reading in Simon Sing’s The Code Book that cryptology is cryptography together with cryptanalysis, but I’ve seen other explanations too, and Shaso’s comment about cryptology sounding old-fashioned is making me wonder.
Comment #27 November 18th, 2014 at 7:26 pm
Err, that’s Simon Singh, not Sing.
Comment #28 November 18th, 2014 at 7:39 pm
Sour grapes?
Comment #29 November 18th, 2014 at 8:40 pm
Cryptology, Sasho, is defined as the scientific or mathematical study of cryptography and cryptanalysis, therefore it is not the same as cryptography per se, because cryptography is defined as the discipline concerned with communication security, which is broader than the scientific or mathematical study of itself subset of itself. Cryptography, for example, would logically include things like jurisprudential concerns related to the matter of communication security, while cryptology would not. Wouldn’t the valid question then be whether or not the guy was using the term “cryptology” correctly, rather than whether or not it sounds old-fashioned to your ear? Or is the argument I’m missing that the Journal of Cryptology actually is old-fashioned?
Comment #30 November 18th, 2014 at 9:01 pm
[…] follow Schneier’s Security Blog. Today, he alerted his readers to this post about an NSA member’s take on the cryptography session of a mathematics conference. The whole […]
Comment #31 November 19th, 2014 at 1:52 am
Beyond the admittedly entertaining zingers, I think this article says more about its author than about academic cryptography.
I hope this is not representative of the NSA since the article is extremely narrow-minded, starting with the premise that the less relevant cryptographic research is to practice, the better it is for the NSA. This only makes sense if one views NSA’s mission as trying to access as much of the world’s communication as possible, as opposed to trying to make the U.S. more secure.
Some of these academic “cryptologists” (scare-quotes in original) such as Adi Shamir and Ron Rivest have done a great deal to secure the Internet, and hence U.S. interests as well.
BTW one of the most interesting passages to me was the discussion on MD-5 on page 14. We often wonder whether the NSA is ahead of open research in factoring algorithms etc.. but one area where it seems that they should have far outpaced open researchers is cryptanalysis of symmetric algorithms including MD4, MD5, SHA-0, SHA-1 etc.. Indeed it seems likely that they have far many more people working on this than academic researchers in this area. But at least from this passage it doesn’t seem that they were aware in 1994 of the attacks that would come only few years later.
Comment #32 November 19th, 2014 at 11:56 am
Although the material was an interesting read, I have to say that the comments have been even more entertaining! 🙂
Comment #33 November 19th, 2014 at 5:46 pm
There is a difference between the US and Europe regarding areas of cryptography/cryptoanalysis that are funded. Cryptoanalysis of specific cryptographic systems (say those of cell-phones or car-keys) seems more popular/fundable in Europe. (Of course, there is also a difference between Euro-CS-theory and US-CS-theory but here there might be a specific non-funding policy.)
Comment #34 November 20th, 2014 at 5:08 am
Gil Kalay #33: What is the difference between Euro-CS-theory and US-CS-theory?
Comment #35 November 20th, 2014 at 5:13 am
It seems the guy that wrote this just doesn’t have a clue. Either this post is from some clueless lower-ranking employee or it is a display of extreme arrogance on the part of the NSA (which bodes well for public crypto since arrogance doesn’t tend to create much progress).
I wouldn’t think/hope it is representative of any of the undoubtly brilliant cryptographers NSA has at its disposal. Just take his description of Oracles “essentially an Omniscient Being that complexity theorists like to turn to when they can’t solve a problem” raises the question if this guy knew anything about what he was talking about.
Comment #36 November 20th, 2014 at 2:11 pm
Vitruvius #29: Thanks, this was very informative. Please don’t read anything into my comment, I am sure it shows my ignorance more than anything else.
Comment #37 November 21st, 2014 at 8:54 am
The point of oracles is not to reflect the real world, but to advance in knowledge thanks to a thought experiment. The same guy could have bashed Einstein when he said “imagine you are standing on a photon, what would you see?”, but we are now thankful for relativity theory thanks to these abstract considerations.
Comment #38 November 21st, 2014 at 9:07 am
Denis #37: That’s very well-put.
Comment #39 November 23rd, 2014 at 4:57 pm
Hey Scott, this is a far off topic comment, but since its been some time when you said you would do it (and I am still waiting!), Im just checking again and see how long should I wait…
Where is your MOOC course (On Edx or whatever place you like)???
Come on, stop procrastination 🙂
Oh, btw, when you start, do like 2 or 3 in roll 🙂
Cheers.
Julio Cesar
Comment #40 November 23rd, 2014 at 6:01 pm
Julio #39: Sorry, but while I’ve toyed with the idea of a MOOC, I have no plans to do one in the foreseeable future. Right now, between research, the baby, “ordinary” teaching, the blog, the Speaking Truth to Parallelism book, and several other things, I have time to take on about -3 additional responsibilities.
Comment #41 November 25th, 2014 at 6:50 am
Hi Scott, thanks for replying.
Im just thinking here that everyone would benefit from your recording classes.. you wouldn’t have to put any “extra” effort. Just record your “ordinary teaching” just as Open courseware does and post it! Erik Demaine has done himself.
Just as a thought, I would say the same about your lectures, what David Mermin said about Feynman’s Teaching: “I would drop everything to hear him lecture on the municipal drainage system”.
Thanks
Julio
Comment #42 November 26th, 2014 at 7:05 pm
Every field that does theory that is potentially but not directly relevant to practice gets this sort of feedback, sometimes deservedly, sometimes not. I’ve seen central bankers and macroeconomic policy makers complain about academic macro. I’ve seen executives complain about management research. I’ve seen medicinal chemists at drug companies complain about academic chemistry and biochemistry. For all I know, some guy who uses particle beams to zap tumors is bitching about how airy-fairy they are at CERN.
Comment #43 December 15th, 2014 at 7:54 am
Scott’s post made it to Bruce Schneier’s widely-read, monthly security newsletter Crypogram!
Quoting Schneier:
https://www.schneier.com/crypto-gram-1412.html
Comment #44 December 17th, 2014 at 4:28 am
I think the trip report should be an eye-opener for European researchers. With the amount of tax money poured into research, I feel European citizens should be able to expect better security, technical leadership and real alternatives to US and Asian products and services in the fields of computing. Yes, the UK is a giant US backdoor but they can be worked around or frozen out completely from European research initiatives. Maybe it is time to climb out of the Ivory towers and get your collective hands dirty in the trenches.
Comment #45 January 23rd, 2015 at 12:13 pm
[…] 1. Shtetl-Optimized » Blog Archive » What does the NSA think of academic cryptographers? Recently-dec… […]