11 ms·

NSA Brute-Force Keysearch Machine

61 points by remx 9y ago

jhallenworld 9y ago
I wonder how programmable it is... Assuming it's not programmable would be an argument not to use standard encryption algorithms.
- sp332 9y ago
  ASICs are not reprogrammable. And they're expensive to build, but the NSA apparently has the resources to build new ones at semi-regular intervals, so I don't know if switching algorithms would really slow them down that much.
  - robert_foss 9y ago
    Considering that it takes 1-2 years to spin custom silicon I would say that it is a viable approach.
    - mcshicks 9y ago
      I think they could probably do significantly faster than that since these would presumably be a relatively low volume, single customer application, and wouldn't need the extensive testing cycle required for mass production ASICs. Which is to say it doesn't take a year from delivering a mask set to a fab to getting packaged parts.
    - jokr004 9y ago
      That's not true at all. Were you paying attention to the development of bitcoin asics? Those things popped up fast once the idea spread.
    - kevin_thibedeau 9y ago
      Gate arrays can be pumped out in weeks to days if you control the fab.
  - cavanasm 9y ago
    I think grandparent was suggesting custom encryption algorithm (potentially less secure) to prevent use of a brute force approach that's custom made for a specific algorithm.
    - schoen 9y ago
      I thought I heard some presentation about superencipherment with AES + some cipher (maybe derived from AES) with per-session randomized S-boxes. You would include the S-boxes in the message as a sort of salt. The goal of this is that if there is a cryptanalytic attack that gives brute force a 2⁴⁰ speedup and hence attackers build custom hardware to implement it, their hardware is still not effective against the other cipher and they have to do something different (maybe hard to characterize how difficult the different thing would be anticipated to be).
      - tptacek 9y ago
        Don't ever do this. The interaction of different crypto algorithms can be counterintuitive (in the sense that you won't gain what you think you're gaining), it's extraordinarily expensive in ways unbalanced against defenders, and it introduces new implementation errors that can weaken the whole system. If you're paranoid about AES, use Chapoly (or just use Chapoly because it's in many ways more convenient to use than AES). Don't build elaborate cascades (all cascades qualify), and don't randomize S-boxes. It is hard enough getting these systems right when you're playing exactly by the book. If you're designing a cryptosystem and you're not a professional cryptographer, the list of things you should be worried about getting wrong is very long and very scary.
        schoen 9y ago
        By "don't build elaborate cascades (all cascades qualify)", do you mean "no cascade construction is preferable to any other", or "every cascade is too elaborate to be worthwhile"? (The second implies the first, but the first doesn't imply the second.)
        9y ago
- mikeash 9y ago
  It's probably easier to use a standard algorithm in a way that can't be attacked by this machine (e.g. use AES-256 with a properly random key) than it is to create a non-standard algorithm that doesn't have vulnerabilities.
  - tptacek 9y ago
    Without some secret algorithmic defect, the existence of which would moot the machine and would throw any encryption algorithm into question, no amount of compute that can be assembled under the physical limits of conventional, non-quantum computing can break a 128 bit key. AES-128 is the norm. No NSA supercomputer should convince you to use AES-256.
    - deleted 9y ago
      [deleted]
- tptacek 9y ago
  No, it would not be. If you're using algorithms or constructions that are physically within the reach of a conventional computer assembled for any amount of money obtainable from the treasuries of all the Five Eyes governments, you're doing something wrong. Don't use RSA-1024; don't use 1024 bit multiplicative group Diffie-Hellman, don't use RC4, and then stop worrying about NSA supercomputers.
  - schoen 9y ago
    Per our previous discussion, you should probably add hash and KDF issues to this list. I also find supercomputers relevant to PRNGs, both on the overall PRNG security front and on the inadequate seeding front. Since CSPRNGs are not designed to be slow to calculate, supercomputers can be used to attack key generation from inadequate seeding, given some useful model of what the effective space of seeds could have been. For instance, there are probably still many embedded systems that are initializing without anything that is reasonably called "environmental noise", and their state space is dangerously small, yet maybe still challenging for most organizations to search, depending on exactly what they initialized it with.
    - tptacek 9y ago
      The embedded systems cold start entropy problem is a good point I hadn't thought about before. Of course (not that you disagree), if you have this problem, you have it with or without NSA supercomputers! I don't think CryptGenRandom or urandom on general-purpose computers is a viable target for this, though, regardless of how "fast" the CSPRNG is.
wand3r 9y ago
Schneier often has great insight but this blog post was pretty much the opposite of that. I think I recall reading the original post from the guy who found that NYU info; and I def. read the Intercept piece. Schneier's post quotes the original article and says unfortunately we don't know more. Literally over 50% of it is a quote from another article which he derides for it's lack of substance. Not sure what the point is.
- tptacek 9y ago
  For better or worse --- I think, often, it's for the worse ---- Schneier has an audience that wants his reaction on all the crypto news of the day. This is his reaction to the Intercept story. In this case, by the way, I think he's dead on. We all need to resist the urge to judge pages linked from HN in the context of "worthy of the front page of Hacker News". Sometimes authors are writing explicitly to that kind of audience, but often, as in this case, they're not. In the context of the service Schneier is trying to provide, this is a solid and useful post.
alex_duf 9y ago
> Whatever the details, this is exactly the sort of thing the NSA should be spending their money. Breaking the cryptography used by other nations is squarely in the NSA's mission. I can't tell if it's sarcasm. (it's a serious question)
- tptacek 9y ago
  It's obviously not sarcasm.
yeukhon 9y ago
"Unfortunately, the Intercept decided not to publish most of the document, so all of those people with "a Ph.D. in a related field" can't read and understand WindsorGreen's capabilities. What sorts of key lengths can the machine brute force? Is it optimized for symmetric or asymmetric cryptanalysis? Random brute force or dictionary attacks? We have no idea." When I was reading the news article, I thought to myself, should they really be publishing classified information? The dumb leak was one thing, but publishing it more broadly is a whole different thing. If this was a government contract, I would assume these are classified documents (which they are). Obviously we tax payers should have the right to know, but logically, wouldn't that consider a crime just like leaking to Wiki Leaks?
- nyolfen 9y ago
  > When I was reading the news article, I thought to myself, should they really be publishing classified information? are you not familiar with the intercept? it was initally created mainly to publish snowden documents > wouldn't that consider a crime just like leaking to Wiki Leaks? we have freedom of the press in america
  - yeukhon 9y ago
    Freedom of press does not mean you can just report on classified information without consequences. You can't just go into Google office and start leaking an NDA project. In this circumstances, sure, the document was available publicly. But since it has been hidden, wouldn't further distribution considered illegal?
    - tptacek 9y ago
      Unlawful, in the NDA case. It's not illegal to break a contract.
    - pvg 9y ago
      Freedom of press does not mean you can just report on classified information without consequences. In the US, you effectively can, assuming you are actually the press and have the means of defending yourself. While there are laws on the books that supposedly limit this in various ways, they are generally not invoked - notice the government typically asks papers to delay publishing classified information they may have received.

61 points by remx 9y ago

I wonder how programmable it is... Assuming it's not programmable would be an argument not to use standard encryption algorithms.

sp332 9y ago
ASICs are not reprogrammable. And they're expensive to build, but the NSA apparently has the resources to build new ones at semi-regular intervals, so I don't know if switching algorithms would really slow them down that much.
- robert_foss 9y ago
  Considering that it takes 1-2 years to spin custom silicon I would say that it is a viable approach.
  - mcshicks 9y ago
    I think they could probably do significantly faster than that since these would presumably be a relatively low volume, single customer application, and wouldn't need the extensive testing cycle required for mass production ASICs. Which is to say it doesn't take a year from delivering a mask set to a fab to getting packaged parts.
  - jokr004 9y ago
    That's not true at all. Were you paying attention to the development of bitcoin asics? Those things popped up fast once the idea spread.
  - kevin_thibedeau 9y ago
    Gate arrays can be pumped out in weeks to days if you control the fab.
- cavanasm 9y ago
  I think grandparent was suggesting custom encryption algorithm (potentially less secure) to prevent use of a brute force approach that's custom made for a specific algorithm.
  - schoen 9y ago
    I thought I heard some presentation about superencipherment with AES + some cipher (maybe derived from AES) with per-session randomized S-boxes. You would include the S-boxes in the message as a sort of salt. The goal of this is that if there is a cryptanalytic attack that gives brute force a 2⁴⁰ speedup and hence attackers build custom hardware to implement it, their hardware is still not effective against the other cipher and they have to do something different (maybe hard to characterize how difficult the different thing would be anticipated to be).
    - tptacek 9y ago
      Don't ever do this. The interaction of different crypto algorithms can be counterintuitive (in the sense that you won't gain what you think you're gaining), it's extraordinarily expensive in ways unbalanced against defenders, and it introduces new implementation errors that can weaken the whole system. If you're paranoid about AES, use Chapoly (or just use Chapoly because it's in many ways more convenient to use than AES). Don't build elaborate cascades (all cascades qualify), and don't randomize S-boxes. It is hard enough getting these systems right when you're playing exactly by the book. If you're designing a cryptosystem and you're not a professional cryptographer, the list of things you should be worried about getting wrong is very long and very scary.
      - schoen 9y ago
        By "don't build elaborate cascades (all cascades qualify)", do you mean "no cascade construction is preferable to any other", or "every cascade is too elaborate to be worthwhile"? (The second implies the first, but the first doesn't imply the second.)
        9y ago
mikeash 9y ago
It's probably easier to use a standard algorithm in a way that can't be attacked by this machine (e.g. use AES-256 with a properly random key) than it is to create a non-standard algorithm that doesn't have vulnerabilities.
- tptacek 9y ago
  Without some secret algorithmic defect, the existence of which would moot the machine and would throw any encryption algorithm into question, no amount of compute that can be assembled under the physical limits of conventional, non-quantum computing can break a 128 bit key. AES-128 is the norm. No NSA supercomputer should convince you to use AES-256.
  - deleted 9y ago
    [deleted]
tptacek 9y ago
No, it would not be. If you're using algorithms or constructions that are physically within the reach of a conventional computer assembled for any amount of money obtainable from the treasuries of all the Five Eyes governments, you're doing something wrong. Don't use RSA-1024; don't use 1024 bit multiplicative group Diffie-Hellman, don't use RC4, and then stop worrying about NSA supercomputers.
- schoen 9y ago
  Per our previous discussion, you should probably add hash and KDF issues to this list. I also find supercomputers relevant to PRNGs, both on the overall PRNG security front and on the inadequate seeding front. Since CSPRNGs are not designed to be slow to calculate, supercomputers can be used to attack key generation from inadequate seeding, given some useful model of what the effective space of seeds could have been. For instance, there are probably still many embedded systems that are initializing without anything that is reasonably called "environmental noise", and their state space is dangerously small, yet maybe still challenging for most organizations to search, depending on exactly what they initialized it with.
  - tptacek 9y ago
    The embedded systems cold start entropy problem is a good point I hadn't thought about before. Of course (not that you disagree), if you have this problem, you have it with or without NSA supercomputers! I don't think CryptGenRandom or urandom on general-purpose computers is a viable target for this, though, regardless of how "fast" the CSPRNG is.

wand3r 9y ago

Schneier often has great insight but this blog post was pretty much the opposite of that. I think I recall reading the original post from the guy who found that NYU info; and I def. read the Intercept piece. Schneier's post quotes the original article and says unfortunately we don't know more. Literally over 50% of it is a quote from another article which he derides for it's lack of substance. Not sure what the point is.

tptacek 9y ago
For better or worse --- I think, often, it's for the worse ---- Schneier has an audience that wants his reaction on all the crypto news of the day. This is his reaction to the Intercept story. In this case, by the way, I think he's dead on. We all need to resist the urge to judge pages linked from HN in the context of "worthy of the front page of Hacker News". Sometimes authors are writing explicitly to that kind of audience, but often, as in this case, they're not. In the context of the service Schneier is trying to provide, this is a solid and useful post.

alex_duf 9y ago

> Whatever the details, this is exactly the sort of thing the NSA should be spending their money. Breaking the cryptography used by other nations is squarely in the NSA's mission. I can't tell if it's sarcasm. (it's a serious question)

tptacek 9y ago
It's obviously not sarcasm.

yeukhon 9y ago

"Unfortunately, the Intercept decided not to publish most of the document, so all of those people with "a Ph.D. in a related field" can't read and understand WindsorGreen's capabilities. What sorts of key lengths can the machine brute force? Is it optimized for symmetric or asymmetric cryptanalysis? Random brute force or dictionary attacks? We have no idea." When I was reading the news article, I thought to myself, should they really be publishing classified information? The dumb leak was one thing, but publishing it more broadly is a whole different thing. If this was a government contract, I would assume these are classified documents (which they are). Obviously we tax payers should have the right to know, but logically, wouldn't that consider a crime just like leaking to Wiki Leaks?

nyolfen 9y ago
> When I was reading the news article, I thought to myself, should they really be publishing classified information? are you not familiar with the intercept? it was initally created mainly to publish snowden documents > wouldn't that consider a crime just like leaking to Wiki Leaks? we have freedom of the press in america
- yeukhon 9y ago
  Freedom of press does not mean you can just report on classified information without consequences. You can't just go into Google office and start leaking an NDA project. In this circumstances, sure, the document was available publicly. But since it has been hidden, wouldn't further distribution considered illegal?
  - tptacek 9y ago
    Unlawful, in the NDA case. It's not illegal to break a contract.
  - pvg 9y ago
    Freedom of press does not mean you can just report on classified information without consequences. In the US, you effectively can, assuming you are actually the press and have the means of defending yourself. While there are laws on the books that supposedly limit this in various ways, they are generally not invoked - notice the government typically asks papers to delay publishing classified information they may have received.