12 ms·

Don’t Rush Quantum-Proof Encryption, Warns NSA Research Director

123 points by jonbaer 7y ago

strictnein 7y ago
In 15-20 years I really hope a book comes out about the NSA's quantum computing work in this decade. I'm immensely curious to know how far they are/are not ahead of the Google/IBM/D-wave crowd. They pretty obviously haven't recreated the magical chip from Sneakers yet (I think), but are they close? Or maybe they are there, but they have to be so very careful with how they use it so not to reveal its existence? Or maybe they're far enough along to realize that's not a thing that can be built in this century?
- kadoban 7y ago
  If they do have that box, they'll still be using it in 15-20 years. If nothing else, information from it will still be of some use and they won't want to give up the game.
- randomsearch 7y ago
  Indeed. The probability of government agencies not at least seriously considering a “Manhattan project” for quantum is zero. But it’s a different situation from the 40s in many ways, consider this: quantum machines could potentially revolutionise several fields, including medicine. So by keeping an advanced machine secret (whether it has arrived or in the future) could be passing up the opportunity to save millions of lives. It’s a hell of a moral judgement call to make. I’d go so far as to say that any intelligence advantage is just not worth the trade off. You’d have to find some way to share that technology. If your hypothetical book emerged, it’d be fascinating to see how it is justified.
  - dfnoo 7y ago
    I think its cute that you think the US government would seriously consider saving millions of lives against breaking every encryption and authentication system on earth, that must be the single most naive thing I've ever heard in my life.
  - kelnos 7y ago
    I think it's entirely plausible (and likely) that the US intelligence agencies would keep life-saving technologies secret if other uses of that tech would give them an edge in intelligence-gathering.
- newguy1234 7y ago
  My guess is they aren't far ahead which explains why they are constantly telling companies to not encrypt data. The reality is they've spend billions developing a "super weapon" of mass surveillance and that entire system is heavily reliant on people not using effective encryption and companies willingly handing over data or creating backdoors.
  - DATACOMMANDER 7y ago
    I agree, this is the simplest and most likely explanation. As tempting as it is to buy into the romantic idea that they’re 100 years ahead of everyone else but can only use their powers in extreme circumstances, that just seems very unlikely.
    - Nasrudith 7y ago
      The funny thing is even if they did have that they would still be as useless for their claimed function given the sheer haystack of communication and simple opsec and signals making it impossible to decode from the context. A terrorist saying "Say hello to grandma for me." Could mean cancel/start/delay the attack or it might mean exactly what it says.
      - mike_hock 7y ago
        See you at the "fireworks" tonight. We're gonna have a "blast." Muahahahaha.
segfaultbuserr 7y ago
It was the NSA who shocked [0] the world of cryptography by announcing "elliptic curve cryptography is dead under the threat of quantum computers, we must move to Post-Quantum Cryptography ASAP and encourage its development." (common knowledge, uncontroversial), "therefore, if you are running a legacy system which had not yet upgraded from RSA to ECC, you should not bother to do so, and instead should save money for the future upgrade to post-quantum protocols." (WTF? Most people thought the threat of quantum computers is serious, but ECC should be good for another ten years, and one should should definitely upgrade to ECC, also, it's worth to revise the ECC standard to include newer curves). > In August 2015, the U.S. government’s National Security Agency (NSA) released a major policy statement on the need to develop standards for post-quantum cryptography (PQC). The NSA, like many others, believes that the time is right to make a major push to design public-key cryptographic protocols whose security depends on hard problems that can-not be solved efficiently by a quantum computer. The NSA announcement will give a tremendous boost to efforts to develop, standardize, and commercialize quantum-safe cryptography. While standards for new post-quantum algorithms are several years away, in the immediate future the NSA is encouraging vendors to add quantum-resistance to existing protocols by meansof conventional symmetric-key tools such as AES. Given the NSA’s strong interest in PQC, the demand for quantum-safe cryptographic solutions by governments and industry will likely grow dramatically in the coming years. Most of the NSA statement was unexceptionable. However, one passage was puzzling and unexpected: > <quote>For those partners and vendors that have not yet made the transition to Suite B algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition.... Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, necessitating a re-evaluation of our cryptographic strategy</quote> > The NSA seemed to be suggesting that practical quantum computers were coming so soon that people who had not yet upgraded from RSA to ECC should not bother to do so, and instead should save their money for the future upgrade to post-quantum protocols. > Shortly thereafter, the NSA released a revised version in response to numerous queries and requests for clarification. The new wording was even more explicit in its negative tone on the continuing use of ECC: “...elliptic curve cryptography is not the long term solution many once hoped it would be. Thus, we have been obligated to update our strategy.” Although other parts of the statement assured the public that ECC was still recommended during the time before the advent of practical quantum computers,the overall impression was inescapable that the NSA was distancing itself from ECC. > In addition, people at the National Institute of Standards and Technology(NIST) and elsewhere have noticed that the NSA has not been taking an active part in discussions of new curves to replace the NIST curves that were recommended for ECC in 1999. The PQC announcement suggests that the NSA has no interest in this topic because it now views ECC as only a stopgap solution. The statement in fact advises against “making a significant expenditure” to upgrade to any of the Suite B algorithms, let alone to any new ECC standards using updated curves. Even industrial and government users who are using antiquated protocols should just sit tight and wait for post-quantum standards. This caught many people by surprise,since it is widely believed that ECC will continue to be used extensively for at least another decade or two. Later, NSA ordered the NIST to start the PQC competition - which I think is good for driving further development of PQC. But now, NSA research director is telling us "don't rush"? It doesn't make sense. [0] See the exceptionally good paper by Koblitz, et al. https://eprint.iacr.org/2015/1018.pdf https://eprint.iacr.org/2015/1018.pdf
cwmma 7y ago
Don't rush to improve chicken coop, warns local fox
- ryanisnan 7y ago
  Great metaphor. I hope the right people (academics, crypto authors, etc.) don't get deterred from reviewing this in earnest, but for lay people like myself, I cannot help but feel as you do.
- PrefixKitten 7y ago
  If by fox you mean a sexy lady then hey I'll leave the door unlocked ( ͡° ͜ʖ ͡°) (just to clarify, this is intended as a serious comment meant to draw attention to the relevance of language ambiguity to computer science)
- jakemal 7y ago
  It's an intentionally misleading title to get clicks. The actual context of the quote refers to the fact that encryption methods built in too much of a rush may introduce other vulnerabilities. This article has no substance or constructive purpose.
- paulddraper 7y ago
  You've got to give them enough time to dig a tunnel underneath.
- strbean 7y ago
  I read this title as "NSA thinks they are getting close to enough qbits to mount real attacks, please don't switch to PQC before we get a return on our investment!" In other news, your totally-trustworthy not-at-all-compromised neighborhood NIST is working on new PQC algs!
  - wil421 7y ago
    If this was the case why does the NSA issue warnings about things from time to time?
staticassertion 7y ago
I think the key quote is this: > "Shor's algorithm is the attack that was developed in the absence of a quantum computer,” Frincke said. “It's hard to predict what people will actually do with one." Once QC actually manifests we may find new properties and new approaches to attacking existing algorithms, and being 'quantum hard' before that point is impractical. I'm not a cryptographer by any means, so I have no idea if this is actually the case. Perhaps we understand the fundamentals so well that we can truly say an algorithm today can hold up in a QC world - I have no idea, that certainly sounds bold, but we do already have purported 'quantum hard' algorithms.
- helen___keller 7y ago
  > Perhaps we understand the fundamentals so well that we can truly say an algorithm today can hold up in a QC world - I have no idea, that certainly sounds bold, but we do already have purported 'quantum hard' algorithms. We don't have any theoretical proof that we can even encrypt against classical computation. It's still technically an open problem if P=PSPACE (as well as P=NP). All encryption (quantum or not) would be broken if we could effectively solve PSPACE-hard problems. So really, nobody can truly say any encryption can hold up anywhere. But we still usually have a good idea of the truth of things simply based on empirical evidence - we don't think anybody is proving P=NP, much less P=PSPACE. We don't think people are going to crack our best classical encryption without brute force. There's not as much empirical evidence that our current quantum encryption will hold up, which is the point of the assertion "it's hard to predict what people will actually do [with shor]"
- twotwotwo 7y ago
  I feel like 1) that is the key quote, 2) it's true, 3) it's also setting the bar too high for current efforts. The first go at a post-quantum public-key crypto standard may in effect be (a public-key analog of) the DES that'll need be replaced with an AES someday. But provided we can get something that isn't a step backwards in classical security (so, well-studied problem) and doesn't fall to Shor's algorithm or any other thing we can find in a few years, that's way ahead of where we are now. We may be feeling around in the dark because we don't know much about quantum computing, but we may also have to do that if we want reasonable security when the first big quantum computers show up.
JasonFruit 7y ago
I have a hard time reading this with an open mind, because I mistrust the NSA so much. That being said, the processes described in the article sound like they will arrive at a fairly transparent (in a good sense), publicly-vetted algorithm --- or at least one where it's easy to perceive if it's not trustworthy. I'm not sure, based on my conversations with people in the field, that I put so much stock in the "20 years 'til Shor" prediction. Most seem to be of the opinion that the best currently available encryption should be okay until we're very old.
- kick 7y ago
  NSA put (effective) backdoor in Dual_EC_DRBG: https://www.schneier.com/blog/archives/2007/11/the_strange_sto.html https://www.schneier.com/blog/archives/2007/11/the_strange_s... Thread by someone directly involved on why the ISO rejected NSA ciphers in the past (hint: they refused to justify design decisions, lied, and attacked the credibility of people who had put out actually-secure crypto): https://twitter.com/TomerAshur/status/988696306674630656 https://twitter.com/TomerAshur/status/988696306674630656 Either they're too incompetent to be trusted or are bad actors and should be treated as such.
  - burfog 7y ago
    NSA fixed the S boxes in DES, protecting users from a type of attack that wasn't yet public knowledge. Many people wrongly assumed that the NSA was trying to weaken DES, but they strengthened it.
  - mrandish 7y ago
    > Either they're too incompetent to be trusted or are bad actors I agree but am curious about one thing. If they aren't stupid won't they realize it's a terrible idea to embed weaknesses in standards destined to become so pervasive your own economy will rely on them (as well as your own military/intel)? Also, history virtually guarantees that your most secret secrets are reasonably likely to become known to your adversaries and used against you with catastrophic consequences? Even if they could entirely subvert the standards process to plant their own backdoor that ends up everywhere, game theory dictates they might be creating their own greatest future weakness.
NatoshiSakimoto 7y ago
There's never been a perfectly secure lock in all of history, thousands of years of it. What makes modern day humans think that one can exist in digital form? I think there is a direct connection to the laws of physics somewhere.
- JasonFruit 7y ago
  Math, mostly.
  - NatoshiSakimoto 7y ago
    copied from Reddit No, when properly implemented, it can not be broken. "Properly implemented" pretty much implies a paper version where there are only two copies of any pad page, and both are immediately destroyed after use. Computerized versions share the same vulnerabilities as the computer it is on. It can't be "cracked", per se, but there are side-channel attacks that can be effective. Here is a paper by Dirk Rijmenants which explains it in the context of Cuban spy communications: http://users.telenet.be/d.rijmenants/papers/cuban_agent_communications.pdf http://users.telenet.be/d.rijmenants/papers/cuban_agent_comm... I've experimented with generating them manually, using 10-sided dice to generate the code groups and an old manual typewriter (not electric!) with a very used cloth ribbon and 2 part carbonless forms. Works pretty well, and once you get into a rhythm you can make a considerable amount of key material. I just grabbed some random 10-sided die at the local gaming store, but if you were serious about it, I'd get Game Science 10-sided die: http://www.gamesciencedice.com/Gamescience-White--d10--Ten-sided-die--Plain-_p_53.html http://www.gamesciencedice.com/Gamescience-White--d10--Ten-s...
- strangecasts 7y ago
  > What makes modern day humans think that one can exist in digital form? ...Shannon's[1] work showing that the one-time pad maintains perfect secrecy? [1] https://ieeexplore.ieee.org/document/6769090 https://ieeexplore.ieee.org/document/6769090
  - NatoshiSakimoto 7y ago
Havoc 7y ago
Hey NSA. You still on top of those backups you were making for me? Might need some of that data back soon...duplicati has been spitting errors
- eternalny1 7y ago
  Send an email to the admins at the Utah Data Center. They have it. https://en.wikipedia.org/wiki/Utah_Data_Center https://en.wikipedia.org/wiki/Utah_Data_Center
kd3 7y ago
I'm a simple man. I see an algorithm backed by djb, I use it.
eternalny1 7y ago
So, the NSA, who intentionally compromised NIST with bad crypto proofs, is now warning NIST not to make better crypto, in the name of "security".
- newguy1234 7y ago
  That's exactly what they're saying.
- staticassertion 7y ago
  I don't get that sentiment from the article at all. The article is talking about the difficulty of targeting a problem space 'too early' vs 'too late'. Too early and you solve the wrong problem, too late and, well, the obvious.
- pera 7y ago
  Where did you read that? The only thing she says is to wait the competition to end (by 2022): > “It's very important that people wait for NIST to do its due diligence,” Frincke said. This is the standard process.
  - CrazyStat 7y ago
    The NSA, who have a history of feeding NIST intentionally compromised crypto algorithms, suggest we need to wait to hear what NIST recommends? How very fucking convenient.
    - pera 7y ago
      It's a totally different ball game though: this isn't about NIST recommending a shady algorithm with mysterious parameters, this is about a well-known standardization process that accept submissions from cryptographers all around the world where anyone can review the proposals and make comments. I don't care what they end up selecting as the winner (and to be honest, I'm so ridiculously paranoid that I don't trust Keccak, for instance), I just think that having a competition where everyone is spending all their energy into looking for flaws on the others candidates is a great thing. Next year China will announce a similar standardization process. Do I trust China? of course not, but I really welcome this initiative anyways.
brobinson 7y ago
Can we start a Gofundme or Kickstarter or something to get 24/7 bodyguards for DJB? We gotta keep this dude alive.
hannob 7y ago
Just a note that there's a relatively fail-safe way to avoid concerns about rushing pqcrypto too soon: Just couple it with established crypto. This is e.g. what google is doing in all their pqcrypto experiments. They use an elliptic curve key exchange combined with a post quantum key exchange. If you don't do any really big mistakes you get at lest the security of the stronger of the two. Given that elliptic curve crypto is really cheap such a combination will probably be used for most post quantum schemes for a while.
- ksaj 7y ago
  Eventually quantum computing will also be really cheap. I don't think it'll take all that much time, given the amount of money and attention. Thinking of security in layers, as you've suggested, is the way to go. Secure communications has always been about being "too expensive" to decrypt in a relevant time span. Just because there's a new kid on the block, we need to keep our old friends around.
Perseids 7y ago
The whole premise of the article is broken: 1. Every respectable cryptographic protocol designer would hedge their bets by combining a post-quantum cryptography (PQC) algorithm with a classical one, preferable elliptic curve cryptography (ECC), such that you first have to break ECC in order to attack the post-quantum cryptography. ECC is great in that it is both fast, secure, its signatures, ciphertexts and keys are small. Every post-quantum algorithm fails in at least one of the categories, but as ECC excels everywhere, the overhead is basically bound by a factor of two. 2. Our focus can't be on choosing one PQC algorithm now (and keep it forever), as it is a very young field comparably (as the article agrees). Instead, we need to built up algorithm agility in our protocols and software, as we are probably going to change PQC algorithms at least once, when the cryptographic community has gained experience in PQC design/cryptanalysis and we switch to the second wave PQC algorithms. In practice that means: Never assume keys, ciphertext, signatures are small. Investigate whether it is possible for keys to have state (see Lamport signature). And the only way to show these properties about protocols and software is to try out some PQC algorithms now. (Why the urgency? Because software and protocol turnaround time is bonkers in commercial applications. Heck, parts of the payment industry still use single DES in 2019...) Given that the NSA knows both of this, the question is whether the author was clueless or the NSA spokesperson is malicious.
- morelisp 7y ago
  Algorithm agility has been a hilarious disaster for designing secure systems. In reality even protocols like TLS that are nominally agile advance primarily by versioning, not agility - and TLS is somewhat of a best case here compared to e.g. the mess of JOSE.
  - tptacek 7y ago
    You're more right than the parent comment --- algorithm agility is, I believe, an increasingly discredited idea among cryptography engineers --- but there's truth to the idea that a serious PQC scheme is going to be paired with a conventional key exchange, so that a new lattice crypto attack won't break the whole handshake. That's not "agility" --- the schemes will almost certainly be hermetically sealed, one PQC KEX and one curve KEX --- but it does mean you can deploy PQC now without compromising your whole cryptosystem. The big issue here is that this observation doesn't break the premise of the article. It remains true that we don't know enough about how real-world quantum computers, if they ever exist at scales useful to attack cryptography, will work.
bitwize 7y ago
The NSA: Don't rush building quantum proof encryption guys. Might want to take your time, make sure you really get it right. Could take years to prove it out. Maybe decades. (Psst, Joe, when will the quantum brute-force crackers be ready? How soon can you get them online?)
- andymockli 7y ago
  Joe: 2009.
mleonhard 7y ago
The only guaranteed safe post-quantum crypto is the one time pad.
aplacelikethis 7y ago
"Don't depend on bleeding-edge software exclusively."
voldacar 7y ago
Hahahahah of course the NSA research director doesn't want people to start using quantum-resistant algos. What this says about their quantum capability is left as an exercise to the reader ;)
JackRabbitSlim 7y ago
I realize this is just the broken clock being right twice a day but the fact that we give the NSA any credibility of any kind is truly mind boggling. Would you use YubiKey ever again after they got caught putting keyloggers into one model? That's what the entire security community does every time they so much as entertain anything the NSA says.
- thephyber 7y ago
  > That's what the entire security community does every time they so much as entertain anything the NSA says. [Morpheus Meme] What if it doesn't matter what the NSA publicly says, but what it quietly does and which universities+researchers it funds?
alexnewman 7y ago
I to this day think quantum proofing of encryption will greatly weaken whatever upstream its use
ksaj 7y ago
Of course NSA would have this opinion. They depend on you believing it so they don't have to buy the newest D-wave or whatever. If we adopted properly encrypted communications back in the 90's (when others were also trying to pretty much illegalize it), nobody would be complaining about speed today. The problem is, everyone ignored encryption ("I've got nothing to hide!") and now that they're learning that they actually do need it, they're not willing to accept the drop in speed it would entail. Everything up to now has been sold based on how much faster it is. Security is still hindsight, and the perception of even slightly slower bandwidth infuriates people for no real reason besides. NSA is up to its same old predictable game. They rely on public laziness and fixation on shiny new things.
gautamcgoel 7y ago
"The cybersecurity community is already hedging its bets against a future when digital secrets are knowable to anyone with the right hacking chops and a couple dozen qubits." What a bunch of journalistic bunk. All QC researchers I know say it will take at least thousands of logical qubits to break RSA. Given the large number of physical qubits required to produce one logical qubit using quantum error correction, this might entail millions of physical qubits, well beyond our current technology - and way more than "a couple dozen qubits".
blaser-waffle 7y ago
"We already have it, and we don't want you to compete with us" -NSA, probably

123 points by jonbaer 7y ago

In 15-20 years I really hope a book comes out about the NSA's quantum computing work in this decade. I'm immensely curious to know how far they are/are not ahead of the Google/IBM/D-wave crowd. They pretty obviously haven't recreated the magical chip from Sneakers yet (I think), but are they close? Or maybe they are there, but they have to be so very careful with how they use it so not to reveal its existence? Or maybe they're far enough along to realize that's not a thing that can be built in this century?

kadoban 7y ago
If they do have that box, they'll still be using it in 15-20 years. If nothing else, information from it will still be of some use and they won't want to give up the game.
randomsearch 7y ago
Indeed. The probability of government agencies not at least seriously considering a “Manhattan project” for quantum is zero. But it’s a different situation from the 40s in many ways, consider this: quantum machines could potentially revolutionise several fields, including medicine. So by keeping an advanced machine secret (whether it has arrived or in the future) could be passing up the opportunity to save millions of lives. It’s a hell of a moral judgement call to make. I’d go so far as to say that any intelligence advantage is just not worth the trade off. You’d have to find some way to share that technology. If your hypothetical book emerged, it’d be fascinating to see how it is justified.
- dfnoo 7y ago
  I think its cute that you think the US government would seriously consider saving millions of lives against breaking every encryption and authentication system on earth, that must be the single most naive thing I've ever heard in my life.
- kelnos 7y ago
  I think it's entirely plausible (and likely) that the US intelligence agencies would keep life-saving technologies secret if other uses of that tech would give them an edge in intelligence-gathering.
newguy1234 7y ago
My guess is they aren't far ahead which explains why they are constantly telling companies to not encrypt data. The reality is they've spend billions developing a "super weapon" of mass surveillance and that entire system is heavily reliant on people not using effective encryption and companies willingly handing over data or creating backdoors.
- DATACOMMANDER 7y ago
  I agree, this is the simplest and most likely explanation. As tempting as it is to buy into the romantic idea that they’re 100 years ahead of everyone else but can only use their powers in extreme circumstances, that just seems very unlikely.
  - Nasrudith 7y ago
    The funny thing is even if they did have that they would still be as useless for their claimed function given the sheer haystack of communication and simple opsec and signals making it impossible to decode from the context. A terrorist saying "Say hello to grandma for me." Could mean cancel/start/delay the attack or it might mean exactly what it says.
    - mike_hock 7y ago
      See you at the "fireworks" tonight. We're gonna have a "blast." Muahahahaha.

segfaultbuserr 7y ago

It was the NSA who shocked [0] the world of cryptography by announcing "elliptic curve cryptography is dead under the threat of quantum computers, we must move to Post-Quantum Cryptography ASAP and encourage its development." (common knowledge, uncontroversial), "therefore, if you are running a legacy system which had not yet upgraded from RSA to ECC, you should not bother to do so, and instead should save money for the future upgrade to post-quantum protocols." (WTF? Most people thought the threat of quantum computers is serious, but ECC should be good for another ten years, and one should should definitely upgrade to ECC, also, it's worth to revise the ECC standard to include newer curves). > In August 2015, the U.S. government’s National Security Agency (NSA) released a major policy statement on the need to develop standards for post-quantum cryptography (PQC). The NSA, like many others, believes that the time is right to make a major push to design public-key cryptographic protocols whose security depends on hard problems that can-not be solved efficiently by a quantum computer. The NSA announcement will give a tremendous boost to efforts to develop, standardize, and commercialize quantum-safe cryptography. While standards for new post-quantum algorithms are several years away, in the immediate future the NSA is encouraging vendors to add quantum-resistance to existing protocols by meansof conventional symmetric-key tools such as AES. Given the NSA’s strong interest in PQC, the demand for quantum-safe cryptographic solutions by governments and industry will likely grow dramatically in the coming years. Most of the NSA statement was unexceptionable. However, one passage was puzzling and unexpected: > <quote>For those partners and vendors that have not yet made the transition to Suite B algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition.... Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, necessitating a re-evaluation of our cryptographic strategy</quote> > The NSA seemed to be suggesting that practical quantum computers were coming so soon that people who had not yet upgraded from RSA to ECC should not bother to do so, and instead should save their money for the future upgrade to post-quantum protocols. > Shortly thereafter, the NSA released a revised version in response to numerous queries and requests for clarification. The new wording was even more explicit in its negative tone on the continuing use of ECC: “...elliptic curve cryptography is not the long term solution many once hoped it would be. Thus, we have been obligated to update our strategy.” Although other parts of the statement assured the public that ECC was still recommended during the time before the advent of practical quantum computers,the overall impression was inescapable that the NSA was distancing itself from ECC. > In addition, people at the National Institute of Standards and Technology(NIST) and elsewhere have noticed that the NSA has not been taking an active part in discussions of new curves to replace the NIST curves that were recommended for ECC in 1999. The PQC announcement suggests that the NSA has no interest in this topic because it now views ECC as only a stopgap solution. The statement in fact advises against “making a significant expenditure” to upgrade to any of the Suite B algorithms, let alone to any new ECC standards using updated curves. Even industrial and government users who are using antiquated protocols should just sit tight and wait for post-quantum standards. This caught many people by surprise,since it is widely believed that ECC will continue to be used extensively for at least another decade or two. Later, NSA ordered the NIST to start the PQC competition - which I think is good for driving further development of PQC. But now, NSA research director is telling us "don't rush"? It doesn't make sense. [0] See the exceptionally good paper by Koblitz, et al. https://eprint.iacr.org/2015/1018.pdf https://eprint.iacr.org/2015/1018.pdf

cwmma 7y ago

Don't rush to improve chicken coop, warns local fox

ryanisnan 7y ago
Great metaphor. I hope the right people (academics, crypto authors, etc.) don't get deterred from reviewing this in earnest, but for lay people like myself, I cannot help but feel as you do.
PrefixKitten 7y ago
If by fox you mean a sexy lady then hey I'll leave the door unlocked ( ͡° ͜ʖ ͡°) (just to clarify, this is intended as a serious comment meant to draw attention to the relevance of language ambiguity to computer science)
jakemal 7y ago
It's an intentionally misleading title to get clicks. The actual context of the quote refers to the fact that encryption methods built in too much of a rush may introduce other vulnerabilities. This article has no substance or constructive purpose.
paulddraper 7y ago
You've got to give them enough time to dig a tunnel underneath.
strbean 7y ago
I read this title as "NSA thinks they are getting close to enough qbits to mount real attacks, please don't switch to PQC before we get a return on our investment!" In other news, your totally-trustworthy not-at-all-compromised neighborhood NIST is working on new PQC algs!
- wil421 7y ago
  If this was the case why does the NSA issue warnings about things from time to time?

staticassertion 7y ago

I think the key quote is this: > "Shor's algorithm is the attack that was developed in the absence of a quantum computer,” Frincke said. “It's hard to predict what people will actually do with one." Once QC actually manifests we may find new properties and new approaches to attacking existing algorithms, and being 'quantum hard' before that point is impractical. I'm not a cryptographer by any means, so I have no idea if this is actually the case. Perhaps we understand the fundamentals so well that we can truly say an algorithm today can hold up in a QC world - I have no idea, that certainly sounds bold, but we do already have purported 'quantum hard' algorithms.

helen___keller 7y ago
> Perhaps we understand the fundamentals so well that we can truly say an algorithm today can hold up in a QC world - I have no idea, that certainly sounds bold, but we do already have purported 'quantum hard' algorithms. We don't have any theoretical proof that we can even encrypt against classical computation. It's still technically an open problem if P=PSPACE (as well as P=NP). All encryption (quantum or not) would be broken if we could effectively solve PSPACE-hard problems. So really, nobody can truly say any encryption can hold up anywhere. But we still usually have a good idea of the truth of things simply based on empirical evidence - we don't think anybody is proving P=NP, much less P=PSPACE. We don't think people are going to crack our best classical encryption without brute force. There's not as much empirical evidence that our current quantum encryption will hold up, which is the point of the assertion "it's hard to predict what people will actually do [with shor]"
twotwotwo 7y ago
I feel like 1) that is the key quote, 2) it's true, 3) it's also setting the bar too high for current efforts. The first go at a post-quantum public-key crypto standard may in effect be (a public-key analog of) the DES that'll need be replaced with an AES someday. But provided we can get something that isn't a step backwards in classical security (so, well-studied problem) and doesn't fall to Shor's algorithm or any other thing we can find in a few years, that's way ahead of where we are now. We may be feeling around in the dark because we don't know much about quantum computing, but we may also have to do that if we want reasonable security when the first big quantum computers show up.

JasonFruit 7y ago

I have a hard time reading this with an open mind, because I mistrust the NSA so much. That being said, the processes described in the article sound like they will arrive at a fairly transparent (in a good sense), publicly-vetted algorithm --- or at least one where it's easy to perceive if it's not trustworthy. I'm not sure, based on my conversations with people in the field, that I put so much stock in the "20 years 'til Shor" prediction. Most seem to be of the opinion that the best currently available encryption should be okay until we're very old.

kick 7y ago
NSA put (effective) backdoor in Dual_EC_DRBG: https://www.schneier.com/blog/archives/2007/11/the_strange_sto.html https://www.schneier.com/blog/archives/2007/11/the_strange_s... Thread by someone directly involved on why the ISO rejected NSA ciphers in the past (hint: they refused to justify design decisions, lied, and attacked the credibility of people who had put out actually-secure crypto): https://twitter.com/TomerAshur/status/988696306674630656 https://twitter.com/TomerAshur/status/988696306674630656 Either they're too incompetent to be trusted or are bad actors and should be treated as such.
- burfog 7y ago
  NSA fixed the S boxes in DES, protecting users from a type of attack that wasn't yet public knowledge. Many people wrongly assumed that the NSA was trying to weaken DES, but they strengthened it.
- mrandish 7y ago
  > Either they're too incompetent to be trusted or are bad actors I agree but am curious about one thing. If they aren't stupid won't they realize it's a terrible idea to embed weaknesses in standards destined to become so pervasive your own economy will rely on them (as well as your own military/intel)? Also, history virtually guarantees that your most secret secrets are reasonably likely to become known to your adversaries and used against you with catastrophic consequences? Even if they could entirely subvert the standards process to plant their own backdoor that ends up everywhere, game theory dictates they might be creating their own greatest future weakness.

NatoshiSakimoto 7y ago

There's never been a perfectly secure lock in all of history, thousands of years of it. What makes modern day humans think that one can exist in digital form? I think there is a direct connection to the laws of physics somewhere.

JasonFruit 7y ago
Math, mostly.
- NatoshiSakimoto 7y ago
  copied from Reddit No, when properly implemented, it can not be broken. "Properly implemented" pretty much implies a paper version where there are only two copies of any pad page, and both are immediately destroyed after use. Computerized versions share the same vulnerabilities as the computer it is on. It can't be "cracked", per se, but there are side-channel attacks that can be effective. Here is a paper by Dirk Rijmenants which explains it in the context of Cuban spy communications: http://users.telenet.be/d.rijmenants/papers/cuban_agent_communications.pdf http://users.telenet.be/d.rijmenants/papers/cuban_agent_comm... I've experimented with generating them manually, using 10-sided dice to generate the code groups and an old manual typewriter (not electric!) with a very used cloth ribbon and 2 part carbonless forms. Works pretty well, and once you get into a rhythm you can make a considerable amount of key material. I just grabbed some random 10-sided die at the local gaming store, but if you were serious about it, I'd get Game Science 10-sided die: http://www.gamesciencedice.com/Gamescience-White--d10--Ten-sided-die--Plain-_p_53.html http://www.gamesciencedice.com/Gamescience-White--d10--Ten-s...
strangecasts 7y ago
> What makes modern day humans think that one can exist in digital form? ...Shannon's[1] work showing that the one-time pad maintains perfect secrecy? [1] https://ieeexplore.ieee.org/document/6769090 https://ieeexplore.ieee.org/document/6769090
- NatoshiSakimoto 7y ago

Havoc 7y ago

Hey NSA. You still on top of those backups you were making for me? Might need some of that data back soon...duplicati has been spitting errors

eternalny1 7y ago
Send an email to the admins at the Utah Data Center. They have it. https://en.wikipedia.org/wiki/Utah_Data_Center https://en.wikipedia.org/wiki/Utah_Data_Center

kd3 7y ago

I'm a simple man. I see an algorithm backed by djb, I use it.

eternalny1 7y ago

So, the NSA, who intentionally compromised NIST with bad crypto proofs, is now warning NIST not to make better crypto, in the name of "security".

newguy1234 7y ago
That's exactly what they're saying.
staticassertion 7y ago
I don't get that sentiment from the article at all. The article is talking about the difficulty of targeting a problem space 'too early' vs 'too late'. Too early and you solve the wrong problem, too late and, well, the obvious.
pera 7y ago
Where did you read that? The only thing she says is to wait the competition to end (by 2022): > “It's very important that people wait for NIST to do its due diligence,” Frincke said. This is the standard process.
- CrazyStat 7y ago
  The NSA, who have a history of feeding NIST intentionally compromised crypto algorithms, suggest we need to wait to hear what NIST recommends? How very fucking convenient.
  - pera 7y ago
    It's a totally different ball game though: this isn't about NIST recommending a shady algorithm with mysterious parameters, this is about a well-known standardization process that accept submissions from cryptographers all around the world where anyone can review the proposals and make comments. I don't care what they end up selecting as the winner (and to be honest, I'm so ridiculously paranoid that I don't trust Keccak, for instance), I just think that having a competition where everyone is spending all their energy into looking for flaws on the others candidates is a great thing. Next year China will announce a similar standardization process. Do I trust China? of course not, but I really welcome this initiative anyways.

brobinson 7y ago

Can we start a Gofundme or Kickstarter or something to get 24/7 bodyguards for DJB? We gotta keep this dude alive.

hannob 7y ago

Just a note that there's a relatively fail-safe way to avoid concerns about rushing pqcrypto too soon: Just couple it with established crypto. This is e.g. what google is doing in all their pqcrypto experiments. They use an elliptic curve key exchange combined with a post quantum key exchange. If you don't do any really big mistakes you get at lest the security of the stronger of the two. Given that elliptic curve crypto is really cheap such a combination will probably be used for most post quantum schemes for a while.

ksaj 7y ago
Eventually quantum computing will also be really cheap. I don't think it'll take all that much time, given the amount of money and attention. Thinking of security in layers, as you've suggested, is the way to go. Secure communications has always been about being "too expensive" to decrypt in a relevant time span. Just because there's a new kid on the block, we need to keep our old friends around.

Perseids 7y ago

The whole premise of the article is broken: 1. Every respectable cryptographic protocol designer would hedge their bets by combining a post-quantum cryptography (PQC) algorithm with a classical one, preferable elliptic curve cryptography (ECC), such that you first have to break ECC in order to attack the post-quantum cryptography. ECC is great in that it is both fast, secure, its signatures, ciphertexts and keys are small. Every post-quantum algorithm fails in at least one of the categories, but as ECC excels everywhere, the overhead is basically bound by a factor of two. 2. Our focus can't be on choosing one PQC algorithm now (and keep it forever), as it is a very young field comparably (as the article agrees). Instead, we need to built up algorithm agility in our protocols and software, as we are probably going to change PQC algorithms at least once, when the cryptographic community has gained experience in PQC design/cryptanalysis and we switch to the second wave PQC algorithms. In practice that means: Never assume keys, ciphertext, signatures are small. Investigate whether it is possible for keys to have state (see Lamport signature). And the only way to show these properties about protocols and software is to try out some PQC algorithms now. (Why the urgency? Because software and protocol turnaround time is bonkers in commercial applications. Heck, parts of the payment industry still use single DES in 2019...) Given that the NSA knows both of this, the question is whether the author was clueless or the NSA spokesperson is malicious.

morelisp 7y ago
Algorithm agility has been a hilarious disaster for designing secure systems. In reality even protocols like TLS that are nominally agile advance primarily by versioning, not agility - and TLS is somewhat of a best case here compared to e.g. the mess of JOSE.
- tptacek 7y ago
  You're more right than the parent comment --- algorithm agility is, I believe, an increasingly discredited idea among cryptography engineers --- but there's truth to the idea that a serious PQC scheme is going to be paired with a conventional key exchange, so that a new lattice crypto attack won't break the whole handshake. That's not "agility" --- the schemes will almost certainly be hermetically sealed, one PQC KEX and one curve KEX --- but it does mean you can deploy PQC now without compromising your whole cryptosystem. The big issue here is that this observation doesn't break the premise of the article. It remains true that we don't know enough about how real-world quantum computers, if they ever exist at scales useful to attack cryptography, will work.

bitwize 7y ago

The NSA: Don't rush building quantum proof encryption guys. Might want to take your time, make sure you really get it right. Could take years to prove it out. Maybe decades. (Psst, Joe, when will the quantum brute-force crackers be ready? How soon can you get them online?)

andymockli 7y ago
Joe: 2009.

mleonhard 7y ago

The only guaranteed safe post-quantum crypto is the one time pad.

aplacelikethis 7y ago

"Don't depend on bleeding-edge software exclusively."

voldacar 7y ago

Hahahahah of course the NSA research director doesn't want people to start using quantum-resistant algos. What this says about their quantum capability is left as an exercise to the reader ;)

JackRabbitSlim 7y ago

I realize this is just the broken clock being right twice a day but the fact that we give the NSA any credibility of any kind is truly mind boggling. Would you use YubiKey ever again after they got caught putting keyloggers into one model? That's what the entire security community does every time they so much as entertain anything the NSA says.

thephyber 7y ago
> That's what the entire security community does every time they so much as entertain anything the NSA says. [Morpheus Meme] What if it doesn't matter what the NSA publicly says, but what it quietly does and which universities+researchers it funds?

alexnewman 7y ago

I to this day think quantum proofing of encryption will greatly weaken whatever upstream its use

ksaj 7y ago

Of course NSA would have this opinion. They depend on you believing it so they don't have to buy the newest D-wave or whatever. If we adopted properly encrypted communications back in the 90's (when others were also trying to pretty much illegalize it), nobody would be complaining about speed today. The problem is, everyone ignored encryption ("I've got nothing to hide!") and now that they're learning that they actually do need it, they're not willing to accept the drop in speed it would entail. Everything up to now has been sold based on how much faster it is. Security is still hindsight, and the perception of even slightly slower bandwidth infuriates people for no real reason besides. NSA is up to its same old predictable game. They rely on public laziness and fixation on shiny new things.

gautamcgoel 7y ago

"The cybersecurity community is already hedging its bets against a future when digital secrets are knowable to anyone with the right hacking chops and a couple dozen qubits." What a bunch of journalistic bunk. All QC researchers I know say it will take at least thousands of logical qubits to break RSA. Given the large number of physical qubits required to produce one logical qubit using quantum error correction, this might entail millions of physical qubits, well beyond our current technology - and way more than "a couple dozen qubits".

blaser-waffle 7y ago

"We already have it, and we don't want you to compete with us" -NSA, probably