NSA's Key Role in Major Developments in Computer Science [pdf] | Hacker News Reader

NSA's Key Role in Major Developments in Computer Science [pdf]

media.defense.gov

111 pointsgraderjs21 comments

In modern cryptography...

The NSA improved the DES cipher but declined to explain how it works. https://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA's... . The successor, AES / Rijndael, was selected in an open competition.

They designed SHA-0 but quietly revised it to become SHA-1, which was in widespread use for over a decade; SHA-256 and SHA-512 which are in widespread use today. Again, the successor, SHA-3 / Keccak, was selected in an open competition.

They designed the notorious Dual EC DRBG (Elliptic Curve Deterministic Random Bit Generator) which performs poorly and is widely believed to have a backdoor. https://en.wikipedia.org/wiki/Dual_EC_DRBG

> is widely believed to have a backdoor.

I would like to stress that it isn't just "widely believed" that Dual EC DRBG has a backdoor. It has been shown beyond any reasonable doubt, with plenty of research papers going into the details of how this was exploited.

hey now dont forget Speck, the cipher so dang great they not only refused any real discussion with cryptographers and linux kernel developers but insisted it be included on a litany of "its classifed" and "we cant tell you" boilerplate.

https://en.wikipedia.org/wiki/Speck_%28cipher%29

turns out in 2013 kernel hackers decided to tell the NSA to go pound sand into a rathole while they focused on things like ED25519 because as Bruce Schneier himself publically stated:

"I no longer trust the constants. I believe the NSA has manipulated them through their relationships with industry."

https://en.wikipedia.org/wiki/Curve25519

The thing about Speck is a shame if it turns out that it's a good cipher. Speck is trivial to implement, has decent performance and doesn't rely on S-Boxes. It's basically all anyone could ever ask for and a design I can very much appreciate. As a block cipher, it has different trade-offs than the djb ARX ChaCha20, which is a stream cipher.

Bernstein later designed Gimli to address that alternate set of tradeoffs.

Bitcoin is a bounty designed to force the government to reveal which algorithms are secure: https://news.ycombinator.com/item?id=28860239

A bunch of unsupported conjecture does not a conspiracy make.

This Schneier "constants" quote is kind of infamous. Notably, he's referring to elliptic curve writ large (the context is a comment on his blog where someone asks why he promotes FFDH over ECDLP-based crypto). He's not saying he no longer trusts the Dual EC constants (he never did, but he also once suggested it was somewhat unlikely to be a backdoor), or even the P-curve constants (which, for the record, I don't think anyone plausibly claims are themselves backdoored). No, he's saying we should all stay in the 1990s with FFDH, which, ironically, involves even more magic parameters.

It would be better if people avoided citing Schneier on curve cryptography, since he spent his career sort of publicly and vocally avoiding elliptic curves. Cryptography is a big discipline; it's not the case that someone with good ideas on, say, block ciphers necessarily has a lot of insight into elliptic curve or lattice cryptography or isogenies or pairings.

There's been a whole bunch of research and some controversy about SIMON and SPECK, the NSA small-footprint ciphers. The problem with backdooring something as simple as SPECK is twofold: you don't have many degrees of freedom, because block ciphers are so simple, and whatever backdoor you come up with has to be "NOBUS" to be practical --- meaning: your backdoor has to work for the NSA, but not for the GRU.

There was a cool paper last year that proposed a NOBUS-like backdoor mechanism for block cipher designs that embedded a susceptibility to linear cryptanalysis into S-boxes (that paper is also notable for a shout-out to yours truly, for writing an HN comment dumb enough to motivate a whole academic paper to refute it) --- this is Tomer Ashur and Raluca Posteuca's thing. So it's been shown that you can introduce a vulnerability --- nowhere nearly as useful as Dual EC, since linear cryptanalysis is annoying to carry out --- but it's still up in the air whether you can really make them NOBUS, because the backdooring work has to survive its own cryptanalysis to prove that up.

At any rate: I kind of doubt there's really anything sketchy about SIMON or SPECK, but it doesn't matter, because nobody is going to use it (having said this on Hacker News we can now be sure that there's a PR to introduce it to Juniper VPN devices, but I stand by it!) and because there are lots of simple low-footprint cipher designs to choose from now.

To be fair, that just puts it in the company of:

"Information wants to be free."

"I'm not my brother's keeper."

"Those who give up essetial liberty to purchase temporary safety deserve neither and will soon lose both."

as aphorisms that are correct as commonly used despite their original coinage having been in service of bullshit.

> No, he's saying we should all stay in the 1990s with FFDH, which, ironically, involves even more magic parameters.

Which magic parameters are you referring to? Like the choice of groups in RFCs 2409 and 3526?

Yep. I'm just suggesting that it's tricky to evaluate FFDH groups for different applications (for instance, with SRP), and there's less clear guidance about which to use, while with curves the popular curve choices are pretty intensely studied and argued about.

I think it's fair to say that they've helped create more secure computers but that's different from improving computer SCIENCE. Why? Because science is about our shared understanding of how the world works. The NSA rarely shares many fundamental truths. They may help debug some crypto algorithms, but they rarely explain how and why they do it. So we're just as much in the dark before and after their help.

If they want credit for improving science itself, they need to share much, much more.

Other interesting articles are available at this page of categorized FOIA releases of NSA Internal Periodicals and Publications: https://www.nsa.gov/Helpful-Links/NSA-FOIA/Declassification-...

"It wasn't all magic" by "Colin B. Burke" is a very interesting read and details early efforts starting with MIT's Vannevar Bush in the 1930's and going to a bit past WWII. Developing a punch that wouldn't wear out was a major engineering challenge, just one of many interesting problems they had to overcome.

An interesting link exists between Richard Feynman and "Thinking Machines Corporation". There are some good videos of Feynman explaining basic computer science ideas in his own special way. The connection makes me wonder what other secret projects Feynman worked on that we don't know about yet.

There's work that Feynman did on the Manhattan Project that is still classified. I believe it was an unpublished formula to determine the yield of the atom bombs.

Some videos of Danny Hillis talking about Richard Feynman and Thinking Machines:

https://www.youtube.com/results?search_query=danny+hillis+ri...

Also listed this:

https://www.youtube.com/watch?v=cNaEI70hT-o

Danny Hillis article on Feynman (if you prefer reading):

https://longnow.org/essays/richard-feynman-and-connection-ma...

Feynman computer science videos:

https://www.youtube.com/results?search_query=richard+feynman...

Only scanned the paper, but I didn't see mention of the POPCOUNT instruction.

A post about POPCOUNT: https://news.ycombinator.com/item?id=20914479

There are others, but that one has the most comments.

I just found that there is a standard way to access it in C/C++

https://en.cppreference.com/w/cpp/numeric/popcount

That's C++, not C. two different languages. Further, that was introduced in C++ '20, which means it's relatively recent and thus not as widely supported as some of the older compiler extensions to implement a popcount intrinsic.

Unfortunately, if you compile with MSVC, or with Gcc or Clang but don't specify a more-recent-than-2003 target (e.g. "-mavx" or "-march=native"), you won't get a POPCNT instruction. Likewise, for the conforming extension __builtin_popcount.

On MSVC, _popcount gets you POPCNT regardless of target. But its std::bitset and std::popcount still won't use it.

C does not, in fact, offer any Standard way to get a popcount instruction. Gcc's and Clang's optimizers recognize certain naive counting loops and can substitute a POPCNT instruction if told that the target supports it.

On RISC-V, you don't get a POPC under any circumstances, nohow. I have been told that the RVA-22 target (supposed to be used in desk machines) will have it, but cannot find any confirmation online. I expect it to be tricky to get compilers for RISC-V to emit it, into the indefinite future, regardless of support on particular machines.

Reply on news.ycombinator.com