Pay No Attention to the Man

Dave Bacon mentions a possible instance of NSA chicanery, which reminds me of a story. First, I should relate a little background:

At MIT, each undergraduate has a few different “advisers” during their stay. You have a “freshman adviser” during your first year; after you declare a major, you get an adviser within your department who basically signs paperwork for you once or twice a term. If you survive a few years at the Institute, you’ll also work with a “thesis adviser,” who probably won’t be the same person as your departmental adviser. This story concerns my paperwork-signing adviser, Edward Farhi. Since Krishna Rajagopal told our entire quantum class about this incident, I figure it’s OK to repeat the tale here.

Prof. Farhi works in quantum computation, it so happens, and in the course of this work, he had cause to use some pretty hefty computer power. The details don’t matter so much, but doing the simulations he had to do required so many computrons that eventually his research hit a bottleneck.

This was the situation when he gave a presentation to a roomful of funding-agency representatives, describing his research. After his talk, a man from the NSA approached him and said, “That is very interesting work you do.”

Farhi replied, “Thank you. Of course, as I mentioned, we’re stalled at the moment, since we’ve gone as far as we can go with the computers we have. If we could use your computers. . .”

[This is where Rajagopal interpolated, “Eddie is pretty gutsy.”]

The man from the NSA stared blankly at him. “I can neither confirm nor deny,” he said, “that the National Security Agency has computers.”

6 thoughts on “Pay No Attention to the Man”

  1. Ha.

    I can confirm that at least the NSA has at least one computer, as I saw it being used at a presentation. Actually I’ve seen multiple presentations, but it could be that it was the same computer used over and over again and I wasn’t that observant as to whether it was a different laptop being used (and even then, maybe they would be disguising the computer by switching out its shell.)

  2. Clearly the Dave mistook the NSA Presentation Aid Utility for a computer. It’s just a series of candles and precisely timed mirrors. Of course, I can neither confirm or deny this claim.

  3. I saw the same essay at Schneier’s (highly-recommended) blog last night.

    An elliptic-curve-based PRNG isn’t a completely ridiculous idea, even though it’s slow. In the public world, there’s a PRNG called Blum-Blum-Shub which is provably hard to break as long as factoring is hard. Blum-Blum-Shub is slow too. Admittedly, nobody’s pushing for it as a standard.

    What’s most plausible to me is that Dual_EC_DRBG is backdoored, but the goal was not to get all the world’s crypto engineers using a weak PRNG (it’s too slow) but to get it implemented by a friendly company in some deliberately weak devices. (There’s an only somewhat kooky theory theory that NSA did that sort of thing in the past through the Swiss company Crypto AG.)

    An unrelated NSA fact I find interesting: NSA wants top secret stuff encrypted with AES keys longer than 128 bits. We outsiders can break 64-bit keys now. If the amount of computing power available continued to double every 18 months, it would take 96 years until the we could break a 128-bit block cipher key. So the reason NSA wants 192+-bit keys could be something interesting:

    1) Quantum exhaustive search would effectively halve key lengths (search n possibilities in \sqrt{n} time, thus 2^n possibilities in 2^{n/2} time). NSA could think it’s likely enough that QC will become practical within, say, 20 years that they might as well recommend longer keys.

    2) NSA might be worried that conventional computing could progress much faster than Moore’s Law suggests.

    3) Could be a mundane protocol-design consideration. There are many ways to use ciphers other than straight encryption; for example, you can use them to build hash functions. A hash function that produces a 128-bit value can have a collision found in 2^64 time. I don’t think ciphers-as-hash-functions is specifically something they’d worry about, but the bigger point is that in the context of a particular protocol you may need more than 128 bits.

    4) Least plausible but most fun: not all cryptographers are happy that AES uses ten rounds for a 128-bit key, as there are academic attacks on the 7-round version. For larger keys, AES uses 12 or 14 rounds. So it’s possible that clever attacks that weaken AES at 10 rounds are not a problem at more.

  4. Not that anyone is still reading this thread, but there are now related comments on Dave Bacon’s blog — mainly the boring story of why the other, faster DRBGs are most likely secure, making Dual_EC_DRBG’s inclusion more bizarre. (For starters, NSA itself designed the hash functions underlying one of the DRBGs.)

    Since this comment I’ve gotten less certain about whether this is actual chicanery or just some NSA number theorists championing their pet algorithm. Never attribute to malice what can be explained by bureaucracy, and all that. Crazy stuff all the same.

Comments are closed.