[dead]
Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys
101–110 of 116 posts
Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys
#102> there is a concrete danger to asymmetric cryptography
I guess there is genuine cause for concern and a reason why i keep seeing these error pages telling me to update my browser.
note, firefox 78(esr) still gets a 32/32 in security on https://html5test.co/
basilisk 2025: 26/32(-6 experimental features) pale moon 33.5: 26/32(-6 exp. feat.) seamonkey 2.53.23: 24/32(-6 exp. -2 prop.)
I don't know why i experience so much hate against spidermonkey and goanna while surfing the web? it appears they are keeping up to date with security features...?
Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys
#103I wonder when the OpenSSH developers will change their stance on Ed448.
What does ed448 mitigate against vs ed25519?
The simplified answer is, larger keys that demand a far larger effort to break, in a way similar to RSA-4096 vs RSA-2048.
The predicted timelines for quantum computer advances (and the requirements for practical applications) have shrunk dramatically in the past 15 years. What used to be a no-later-than-2035 recommendation for getting off e.g. RSA-2048 in good time, is today no-later-than-2030. The admission of 256-bit curves for ECDSA/ECDH has been supplanted by 384-bit curves already years ago.
In the absolutely ground shaking event that a future application of quantum computation somehow manages to cut Ed448's equivalent security of ~224 bits in half, exploring even a small portion of a 112-bit space will still cost more electrical energy than we can possibly provide.
Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys
#104On one hand I hear that quantum computers will crack factorisation and discrete logarithms, on the other that the max number factorised is 15 and that 21 might not even be feasible. What is going on?
1) It takes a long time to change cryptography standards, and cryptography also generally needs to provide some forward secrecy: i.e. you would like that something you encrypt today is safe for some time afterwards. This means the timelines cryptographers care about when advocating for a change are long, often more than a decade.
2) By most accounts, quantum computing scaling is limited by various physical effects causing noise in the circuits that prevent making larger circuits from the smaller ones that exist. If this was the end of it, then you would expect scaling to be very slow and probably infeasible. But there is also a process of quantum error correction, which means that once you can build a large enough and reliable circuit to implement it, you can scale very easily. This makes quantum computing scaling very nonlinear: it is expected that scaling will suddenly become a lot easier once this threshold is reached, and it sounds like the state of the art is getting close to that threshold (you can of course find people who are skeptical of this claim: from believing that the timelines are optimistic to doubt that the physics works at all).
3) cryptographers are also likely to err on the side of caution: the effects of widely-used encryption being broken are very bad, so it's best to assume that QC will accelerate quickly and that adoption of post-QC cryptography will be slow.
Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys
#105Earlier quoted context omitted.
Yes and no. Grover's algorithm is provably optimal [0]. No quantum algorithm will ever find an n-bit key by queries to any reasonable sort of oracle faster than Grover's algorithm, and Grover's algorithm is way too slow to be a serious problem. But symmetric ciphers are not black boxes. They're mostly built on some variant of a Feistel network, which is a very nice construction for turning a messy function into an in…
About [3]: Isn't this realizable with quantum state teleportation? Entanglement networks are definitely being worked on heavily, and after entanglement distillation you just need to send a few bits to effectively have sent a quantum state. Not sure what "chosen-quantum-cyphertext" attacks are though, so maybe my idea fails one of it's assumptions? About [5]: why not? Because of information leakage, or because they on…
Re [3]: sure, if you have two quantum computers, and you’ve built an entanglement network that can get them into a controlled entangled state, and they both have useful amounts of coherent memory that lasts long enough to be interesting (days? weeks? years? depends on the application), then you can teleport qubits from one to another. This does not currently exist.
I see papers describing a “vision” for entanglement networks. Maybe something will work for real in a decade. And then maybe someone will implement AES as a quantum circuit and will send the outputs (where the input is not a classical state!) to a remote node. That would be nifty indeed.
Re [5]: The gadgets I’ve looked into use lasers to very very poorly approximate single-entangled-photon-pair sources and use detectors that are fairly poor approximations of single photon detectors to implement QKD. But the whole thing really (IMO) implements a real mess where a particular subspace of the mess resembles the secure QKD algorithms. And then people break it by sending unexpected input.
If I’m making a cryptographic system, I want to receive classical input that is definitely 0 or 1, and I want to receive quantum input that is definitely in the computational basis. No one hacks a major website by sending something that isn’t a string of bits to one of its API, but people have broken “QKD” by doing just that.
Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys
#106Earlier quoted context omitted.
Classical brute force is embarrassingly parallel, but Grover's algorithm (the quantum version) isn't. To the extent you parallelize it, you lose the quantum advantage, which means that to speed it up by a factor of N, you need N^2 processors. The article discusses this in detail, and calculates that "This means we’ll need 140 trillion quantum circuits of 724 logical qubits each operating in parallel for 10 years to b…
So then why is quantum always touted as being able to possibly beat AES ?
Is it? I've generally understood that most symmetric cryptography like AES is safe. QC only gives exponential speedups on some specific problems. The most is that naively you might want to double your keysize to get the same protection, something that the article points out is unecessary because that naive approach assumes that QC is like classical computing but with extra magic, as opposed to having its own tradeoffs.
Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys
#107Earlier quoted context omitted.
What does ed448 mitigate against vs ed25519?
The simplified answer is, larger keys that demand a far larger effort to break, in a way similar to RSA-4096 vs RSA-2048. The predicted timelines for quantum computer advances (and the requirements for practical applications) have shrunk dramatically in the past 15 years. What used to be a no-later-than-2035 recommendation for getting off e.g. RSA-2048 in good time, is today no-later-than-2030. The admission of 256-b…
The whole point is that RSA and ECDH can't be made safe against quantum computers by making the keys bigger. The speedup is exponential and so breaking a 4096-bit key is only twice as hard as a 2048-bit key. The 'cutting in keysize in half' is true in principle in general (but not in practice, as the article points out), but for some algorithms it's much worse.
Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys
#108Earlier quoted context omitted.
> encryption is not ever to be considered impossible to break One-time pads [0] are actually impossible to break, but they're pretty tricky to use: you must never ever reuse them, they must be truely random, and you need some way to share them between both parties (which isn't that easy since they need to be at least as large as all the data that you ever want to transmit). [0]: https://en.wikipedia.org/wiki/One-time…
not trying to be obtuse, but there is at least one solution, the one used to decrypt. if you know something about the content e.g. it is for russians, or americans. you can use a frequency analysis to identify vowels. that goes for a simple substitution cypher that is relying on low frequency of usage[one time use] and does not keep it brief. when you further substitute numbers for words, you gain more room for verbo…
I don't think you understand the point of the OTP and why it can't be brute forced: for any possible output, there is a corresponding one-time key. So you have no way to tell if the key you have come up with is correct, you can 'decrypt' an OTP ciphertext into a coherent sentence saying whatever you want in any language you want (the only constraint being maximum length), and bruteforcing will just give you all of them.
Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys
#109I get what he’s saying, but, doesn’t he compare classical speed up of parallelizing 64 bit key space on 2^16 cpus with parallelizing 128 bits key space on QCs? It’s true that sqrt (2^128/2^16) = 2^56 and that 56 >> 48, but in one case you are attacking a 64 bits key space and in the other a 128! If you parallelize 2^128 on 2^16 CPUs you get 128-16=112 bits of key space per cpu which is much bigger than 56! No?
Edit: I mean, I get the point is to prove that 2^128 on QC is not the same as 2^64 on CC but it’s still a lot less to search. If a paper came out with that big of a key space reduction AES would be considered broken IMO
Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys
#110Earlier quoted context omitted.
not trying to be obtuse, but there is at least one solution, the one used to decrypt. if you know something about the content e.g. it is for russians, or americans. you can use a frequency analysis to identify vowels. that goes for a simple substitution cypher that is relying on low frequency of usage[one time use] and does not keep it brief. when you further substitute numbers for words, you gain more room for verbo…
I don't think you understand the point of the OTP and why it can't be brute forced: for any possible output, there is a corresponding one-time key. So you have no way to tell if the key you have come up with is correct, you can 'decrypt' an OTP ciphertext into a coherent sentence saying whatever you want in any language you want (the only constraint being maximum length), and bruteforcing will just give you all of th…
oh i get it, the frequency of use is what allows frequency analysis.
use a pad once then rotate to a new pad. [effectively re-key the encryption]
avoid using characters in high frequency [vowels, language specific phonemes]
use alternate misspellings, intentional typos.
keep the message very brief, the longer the message the more effective frequency analysis becomes.
try to avoid corelative events.
if every time a cypher that looks like [abc] is captured, somthing, is bombed, or major troop movements occur, you have an idea what the message is about, giving a bit more leverage.
also standard OTP pads use 2 axis, a tensor matrix is a better OTP.