9 ms·
NSA announces plans for transitioning to quantum resistant algorithms
- cabirum 11y agoWait, do working quantum computers actually exist today? D-Wave is the one I heard about, but the wiki page says it's no faster than ordinary computers and not even sure it works as advertised.
- jackgavigan 11y agoD-Wave's hardware is customised for a particular function: http://physicsworld.com/cws/article/news/2014/jun/20/is-d-wave-quantum-computer-actually-a-quantum-computer http://physicsworld.com/cws/article/news/2014/jun/20/is-d-wa... A team at UCSB built a prototype quantum computer that successfully factored 15 a few years back: http://www.nature.com/nphys/journal/v8/n10/full/nphys2385.html http://www.nature.com/nphys/journal/v8/n10/full/nphys2385.ht...
- marcosdumay 11y agoYes, and last time I saw, they could break 11 bits long keys. There are probably better ones now, it's been a long time that they don't make the news. Anyway, they are still far from being practical, but do exist.
- krastanov 11y agoThere are indeed "quantum computers" that work on a few qubits (less than 10), but without what is called "error protection". They are useless for running factorization of practical sizes (i.e. they do break small keys, but you can break those by hand on paper as well).
- tlack 11y agoSuch an interesting subject. Anyone have any pointers to the most interesting post-quantum algorithms?
- palsecam 11y agohttp://pqcrypto.org/ http://pqcrypto.org/ Also https://speakerdeck.com/veorq/quantum-computers-vs-computers-security https://speakerdeck.com/veorq/quantum-computers-vs-computers... (slides 25-30)
- deleted 11y ago[deleted]
- Bluerise 11y agohttp://www.square-up.org/ http://www.square-up.org/
- robotkilla 11y agoI have next to zero understanding of how quantum computers are supposed to work. Does anyone have something like an intro into QC "for dummies"? I want to grasp this subject.
- Thorondor 11y agoThe paper http://arxiv.org/abs/0708.0261 http://arxiv.org/abs/0708.0261 is a reasonably good introduction with a fair amount of math. If you're looking for a non-technical overview, you might try https://uwaterloo.ca/institute-for-quantum-computing/quantum-computing-101 https://uwaterloo.ca/institute-for-quantum-computing/quantum... but I don't think English alone is precise enough to explain anything really interesting about quantum computing.
- noinsight 11y agoI liked this presentation at CCC: https://media.ccc.de/browse/congress/2014/31c3_-_6261_-_en_-_saal_2_-_201412291245_-_let_s_build_a_quantum_computer_-_andreas_dewes.html#video https://media.ccc.de/browse/congress/2014/31c3_-_6261_-_en_-...
- Taniwha 11y agoand we should trust them here why?
- scintill76 11y agoMaybe it's reverse psychology -- they've got quantum cryptanalysis, and the surest way to keep us all vulnerable is them telling us we should upgrade. ;)
- confluence 11y agoStop messing with my head.
- Spooky23 11y agoThey are equally, if not more threatened than you are by quantum computing. Advances in the field were an unexpected and unwelcome discovery for NSA.
- wfunction 11y agoProbably trying to insert backdoors before the community develops an algorithm without one.
- sobkas 11y agoThere is this one quantum resistant algorithm called rot13...
- aburan28 11y agoThis is a big development IMO. Quantum computers were theoretical only but now this update seems to indicate the feasibility of such
- jokoon 11y agoWas quite to hear snowden talk about those. Might mean NSA already has them.
- mtgx 11y agoI hope nobody here is actually considering using the proposed NSA algorithms - right? The NSA today is a very different beast from the pre-2000 one. The focus seems to have drastically changed from securing stuff to mostly introducing vulnerabilities in stuff.
- technion 11y agoI had the same initial thought. However, in reviewing the actual recommendations, if you trusted RSA 2048 before, it would be hard to argue the NSA has now backdoored RSA 3072 as a part of recommending it.
- biot 11y agoCan anyone explain what makes an encryption algorithm quantum-resistant?
- deleted 11y ago[deleted]
- lindig 11y agoPrime numbers can't be factored.
- wolfgke 11y agoFor every prime p, we have p = 1 * p (clearly a factoring of p, though a trivial one). So rather "Prime numbers can't be factored in a nontrivial way.",
- deleted 11y ago[deleted]
- noobie 11y agoI'd go with "Prime numbers can't be prime-factored".
- wolfgke 11y agoEven if we ignore units (i.e. 1, -1 in the ring Z), the prime number is a factorization of itself (one factor). Otherwise the famous theorem that any integer >= 1 can be factored uniquely (up to order of the factors) into prime numbers would not hold (it even holds for 1, since 1 is defined as the product of zero factors).
- fredgrott 11y agonot entirely true.. Prime number guesses cannot be fully determined as prime fast and easily...however WE CAN brute force guess big prime numbers easily..for example 1/4 to 15 RSA keys can be brute forced guessed..not full brute force break as you still have the session keys to brute force but you get the idea
- AlyssaRowan 11y agoYou'll note they don't actually specify any asymmetric quantum-resistant algorithms. I'd guess if they did, NTRU or a derivative would be one they'd consider first: Security Innovation were trying to sell them that at about the same time Certicom were pushing elliptic curves. (I'm not as convinced about ideal lattices, but that's an artifact of my not being as familiar with the field.) Pre-shared keys, as they suggest there, have no forward secrecy - which makes them great for those who really like stealing, say, IPsec keys… like the NSA. It may work with the kind of old military key infrastructure they and GCHQ have, that regularly distributes random keys from centralised, organisationally-trusted sources on specialised hardware; it is a terrible recommendation for civilians. Interesting that they're still married to P-384 (probably the most annoying curve to implement correctly). Properly-implemented Ed448-Goldilocks is safer, and that's what CFRG are going with for the "paranoid" level.
- eeZi 11y agoIPSec still has forward secrecy even with pre-shared keys.
- AnthonyMouse 11y agoThe way it does that is by using Diffie-Hellman or ECDH, which both rely on the hardness of the discrete logarithm problem that quantum computers would break.
- wolf550e 11y agoopenssl 1.0.2a on an old Conroe Core2 gets this: sign verify sign/s verify/s 256 bit ecdsa (nistp256) 0.0001s 0.0003s 8727.8 3493.3 384 bit ecdsa (nistp384) 0.0005s 0.0020s 2001.4 493.0 521 bit ecdsa (nistp521) 0.0010s 0.0017s 1021.3 603.0 Can P-384 (or Ed448-Goldilocks) be close to P-256 in speed?
- tveita 11y agoHere are some median times from the eBATS benchmark page for a 2013 Intel Xeon E3-1275 V3 3500MHz (http://bench.cr.yp.to/web-impl/amd64-titan0-crypto_sign.html http://bench.cr.yp.to/web-impl/amd64-titan0-crypto_sign.html) Cycles to generate a key pair: ed448goldilocks: 176924 ecdonaldp256: 290628 ecdonaldp384: 2202380 Cycles to sign 59 bytes: ed448goldilocks: 185056 ecdonaldp256: 381696 ecdonaldp384: 2367856 Cycles to verify 59 bytes: ed448goldilocks: 583900 ecdonaldp256: 913848 ecdonaldp384: 2741028 (ecdonaldp is ECDSA signatures with NIST P-256/384. The implementation used is OpenSSL, though I don't know which version) AFAIK no elliptic curve size is quantum secure, so I guess the goal is just to require slightly more qubits for an attack.
- titanomachy 11y agos/prelminary/preliminary
- tway 11y ago"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."
- givan 11y agoIf they managed to make quantum calculations does it mean that it validates the many worlds/multiverse theory?
- akvadrako 11y agono
- krastanov 11y agoTo expand a bit on this quite correct "no": There are many interpretations of quantum mechanics, like Bohm Mechanics, Multiverse, Copenhagen, but they all are mathematically equivalent and indistinguishable. They are of purely philosophical interest, not scientific (people will argue about this last sentence, but this would be an argument over semantics, not science). So please do not call it "Multiverse theory", rather "Multiverse interpretation" :)
- maaku 11y agoUh, no. MWI and Copenhagen make different predictions. It just requires a reversible quantum computer to test. It is possible to distinguish which is true but it may take a few generations of experiment.
- krastanov 11y agoCould you elaborate on that? I have hard time believing it without a reference. Edit: Probably you were referring to the need for "wavefunction collapse" in the Copenhagen theory. Practically, this can be addressed with the Master equations (or other approaches) for open quantum systems. Philosophically it might be unpleasant, but mathematically it is no different from what the Many World/Multiverse requires.
- williamjennings 11y agoIdeal lattices are a generic defense against quantum hacking. Server load balancing is a dynamic process which may actually induces vulnerabilities to distributed denial of service attacks, whether or not the maintenance occurs regularly. Especially dangerous DDoS is statistically timed to gain root access by damaging the infrastructure. Irreversible destruction of the hardware is attributed to atomic decay processes which are incited by zeta normalization of the attack timing. Any virtual machine may encapsulate a finite-dimensional p-adic space. Honing a conditional random field on that model is technically the same as training an AI to preemptively reject any possible series of attacker signals. In this way, the multiplicity of primes can be mapped in order to secure, contain, and protect any and all esoteric data.
- newsdotyc-ta 11y agoThis comment (along with many of this author's other comments) seems to take a form which strongly reminds me of the output of SCIgen[1] and I wonder if anyone more versed in quantum cryptography or any related fields of mathematics can make more sense of it than I can. I could, of course, be unfairly interpreting the unusually simple [2] grammatical structures as being computer generated rather than as an artifact of not being a native English speaker. If that is the case, I do apologize and hope that I have not caused any offence. [1] http://pdos.csail.mit.edu/scigen/ http://pdos.csail.mit.edu/scigen/ [2] Simple structures relative to the complexity of the topic(s)
- williamjennings 11y ago>This comment (along with many of this author's other comments) seems to take a form which strongly reminds me of the output of SCIgen[1] Whilst a context-free grammar is used to generate sentences; the preferred output is typically the sequence of words with the lowest entropy. That has the effect of sounding extremely concise, idiomatically as: a man of few words. I veritably assure you that you are indeed in communication with a real, live human being who has written software for Natural Language Processing; so I attribute your confusion to that point, mostly. >and I wonder if anyone more versed in quantum cryptography or any related fields of mathematics can make more sense of it than I can. Here is where you are being offensive. If you become confused by words which you cannot fathom, then you need to admit your own ignorance and ask a question directly. Otherwise, as in this case, you are engaging in fallacious excommunication or at least rude duplicity! >I could, of course, be unfairly interpreting the unusually simple [2] grammatical structures as being computer generated rather than as an artifact of not being a native English speaker. Here is where you espouse two falsehoods: that my grammatical structures are in any way simple; or that native English speakers have any specific level of complexity in their language. It is easy to show how certain grammatical constructions are indicative of a person's native language; but those are usually grammatical errors such as: run-on sentences, misplaced plurals, or redundant hyphenation. There is no homogenous measure of complexity for the English spoken by people born in England, so that topical premise is entirely wrong. >If that is the case, I do apologize and hope that I have not caused any offence. If you feel the need to apologize in advance, then you have probably written something rude; and you should revise the message before sending it. Let my wall of text be a lesson to you!