Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

words.filippo.io

Post reply on HN
Print view View original

61–70 of 116 posts

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#61

Post by f33d5173 »

cortesoft wrote: post #51
f33d5173 wrote: post #39

Earlier quoted context omitted.

You don't need to keep shrinking features. Brute forcing is highly parallel; to break a key within a certain time frame all you need is a large enough quantity of chips. While it's in the realm of science fiction today, in a few centuries we might have nanorobots that can tile the entire surface of mars with processors. That would get you enough orders of magnitude of additional compute to break a 128 bit key. 256 bi…

The power and heat are the issues for that, though. Think about how much energy and heat are used/generated in the chips we have now. If we tiled out those chips to be 20 orders of magnitude larger… where is the heat going to go, and where is the energy coming from?

In my example I had imagined that your nanobots would also create solar panels and radiators for the chips you were tiling the surface of mars with. This is why it needs to be done on the surface instead of underground somewhere.

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#62

Post by SahAssar »

bob1029 wrote: post #17
glitchc wrote: post #11

Earlier quoted context omitted.

You're clearly not using these keys in certificates, which would need to be signed by a root or interim CA on every update.

Correct. The keys are only used for signing JWTs. Trust was established with the vendor out of band from this wire protocol (the URL they scan for public keys).

I'm not sure I understand, but haven't you just moved the problem to the out of band layer? And is that layer not secured using the same normal (somewhat) long-lived TLS as most sites?

I don't think I understand the threat model you are using here?

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#63

Post by SAI_Peregrinus »

amluto wrote: post #56
staticassertion wrote: post #54

Is there any reason to believe that Grover's is as good as it gets? I'm on board here, and I think the article caveats that it's a matter of cost, priority, and assumptions. Cool, cool, I'm already using xaes-256-gcm. But I'm just curious if quantum could have new applications for algorithmic analysis, or take advantage of other weaknesses?

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…

Nitpick: AES isn't a Feistel network, it's based on a substitution-permutation network.

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#64

Post by upofadown »

rugina wrote: post #20

On 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?

The idea seems to be that there will some sort of cascading effect if we can somehow create physical qubits with sufficient noise performance. It's this "threshold" we keep hearing about. Once we exceed threshold there is a possibility that we can use error correction to expand everything without limit.

This assumes that there will not be other problems that arise. I suspect that "error correcting" thousands of qubits entangled with one another will be one of those problems.

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#65

Post by rolph »

gucci-on-fleek wrote: post #60
rolph wrote: post #14

encryption is not ever to be considered impossible to break. every encryption scheme has at least one way to be decrypted. fidelity of information is one use of encryption, if you apply the solution and get garbage, something is wrong, somewhere. occultation of information is another use, that is commonly abused by extending undue trust. under the proviso that encryption will eventually be broken, you cant trust encr…

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

if you have high stakes, your message in the clear, should only be useful for a limited time, at the point that it is no longer actionable.

im very familiar with one time pads random, and keyed.

they are a little simple, you can use a triaxial scheme, or a tensor like scheme, for more leg room and more complexity.

depending on what you are doing it may be necessary, to not carry any pads, but to have access at some point, to agreed upon keys, in order to generate a pad on the spot. or even work in your head, if you have skill. e.g. jackdwlovemybigsphnxfqurtz as a weak example.

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#66

Post by eru »

cwillu wrote: post #59
staticassertion wrote: post #54

Is there any reason to believe that Grover's is as good as it gets? I'm on board here, and I think the article caveats that it's a matter of cost, priority, and assumptions. Cool, cool, I'm already using xaes-256-gcm. But I'm just curious if quantum could have new applications for algorithmic analysis, or take advantage of other weaknesses?

Fun fact: Grover's algorithm is a rare example of an algorithm that was proven optimal before it was invented.

If you like this kind of thing: there's a deterministic algorithm for finding minimum spanning trees in a graph that's proven optimal, but no one knows its exact runtime.

Basically, the best they've proven is something like O(n * inverse_ackermann(n)), but it seems likely the algorithm actually runs in O(n). We also already have a randomised algorithm for this problem that runs in O(n) expected time on worst case input. The expectation is over the random choices.

https://en.wikipedia.org/wiki/Expected_linear_time_MST_algor...

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#68

Post by gucci-on-fleek »

rolph wrote: post #65
gucci-on-fleek wrote: post #60

Earlier 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…

> not trying to be obtuse, but there is at least one solution, the one used to decrypt

Right, which is why I didn't quote that part :)

> you can use a frequency analysis to identify vowels.

That will help in many cases, but not against a properly-used one-time-pad.

> but to have access at some point, to agreed upon keys, in order to generate a pad on the spot

That's not really a one-time pad then, that's just a stream cipher. Which do work better than one-time pads in the vast majority of cases, aside from not being "perfectly" secure.

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#69

Post by fred_is_fred »

He mentions "non-existing AES-512" but why not? Why not AES-1024 or AES-4096? Is it too much processing power needed to encrypt and decrypt? I am guessing perhaps also the algo needs work - you can't just take AES-128 and add bits, if you could it would have been done?

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#70

Post by amluto »

SAI_Peregrinus wrote: post #63
amluto wrote: post #56

Earlier 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…

Nitpick: AES isn't a Feistel network, it's based on a substitution-permutation network.

That’s a very valid nitpick :)
Post reply on HN