7 ms·

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

111 points by graderjs 5y ago

dboreham 5y ago
Only scanned the paper, but I didn't see mention of the POPCOUNT instruction.
- WalterGR 5y ago
  A post about POPCOUNT: https://news.ycombinator.com/item?id=20914479 https://news.ycombinator.com/item?id=20914479 There are others, but that one has the most comments.
  - ape4 5y ago
    I just found that there is a standard way to access it in C/C++ https://en.cppreference.com/w/cpp/numeric/popcount https://en.cppreference.com/w/cpp/numeric/popcount
    - junon 5y ago
      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.
    - ncmncm 5y ago
      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.
greenail 5y ago
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.
- wantoncl 5y ago
  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+richard+feynman https://www.youtube.com/results?search_query=danny+hillis+ri... Also listed this: https://www.youtube.com/watch?v=cNaEI70hT-o 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-machine/ https://longnow.org/essays/richard-feynman-and-connection-ma... Feynman computer science videos: https://www.youtube.com/results?search_query=richard+feynman+computer+heuristics+lecture https://www.youtube.com/results?search_query=richard+feynman...
nayuki 5y ago
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_involvement_in_the_design 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 https://en.wikipedia.org/wiki/Dual_EC_DRBG
- hannob 5y ago
  > 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.
- nimbius 5y ago
  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 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 https://en.wikipedia.org/wiki/Curve25519
  - westcort 5y ago
    Bitcoin is a bounty designed to force the government to reveal which algorithms are secure: https://news.ycombinator.com/item?id=28860239 https://news.ycombinator.com/item?id=28860239
deleted 5y ago
[deleted]
echopurity 5y ago
Who do y'all think invented cryptocurrency? Did you think Uncle Scam was gonna let the eCNY take over?
graderjs 5y ago
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-Transparency-Initiatives/Internal-Periodicals-Publications/ https://www.nsa.gov/Helpful-Links/NSA-FOIA/Declassification-...
xhkkffbf 5y ago
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.
greenail 5y ago
"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.

111 points by graderjs 5y ago

dboreham 5y ago

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

WalterGR 5y ago
A post about POPCOUNT: https://news.ycombinator.com/item?id=20914479 https://news.ycombinator.com/item?id=20914479 There are others, but that one has the most comments.
- ape4 5y ago
  I just found that there is a standard way to access it in C/C++ https://en.cppreference.com/w/cpp/numeric/popcount https://en.cppreference.com/w/cpp/numeric/popcount
  - junon 5y ago
    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.
  - ncmncm 5y ago
    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.

greenail 5y ago

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.

wantoncl 5y ago
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+richard+feynman https://www.youtube.com/results?search_query=danny+hillis+ri... Also listed this: https://www.youtube.com/watch?v=cNaEI70hT-o 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-machine/ https://longnow.org/essays/richard-feynman-and-connection-ma... Feynman computer science videos: https://www.youtube.com/results?search_query=richard+feynman+computer+heuristics+lecture https://www.youtube.com/results?search_query=richard+feynman...

nayuki 5y ago

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_involvement_in_the_design 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 https://en.wikipedia.org/wiki/Dual_EC_DRBG

hannob 5y ago
> 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.
nimbius 5y ago
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 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 https://en.wikipedia.org/wiki/Curve25519
- westcort 5y ago
  Bitcoin is a bounty designed to force the government to reveal which algorithms are secure: https://news.ycombinator.com/item?id=28860239 https://news.ycombinator.com/item?id=28860239

deleted 5y ago

[deleted]

echopurity 5y ago

Who do y'all think invented cryptocurrency? Did you think Uncle Scam was gonna let the eCNY take over?

graderjs 5y ago

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-Transparency-Initiatives/Internal-Periodicals-Publications/ https://www.nsa.gov/Helpful-Links/NSA-FOIA/Declassification-...

xhkkffbf 5y ago

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.

greenail 5y ago

"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.