Submitted by giuliomagnifico t3_zuxy0d in technology
itdood t1_j1mp2la wrote
It's estimated that 6600 q-bits are required to break 256b AES. Given the road map this could happen in the next 4-6 years.
mrlazyboy t1_j1nhdg4 wrote
“Breaking” a crypto system usually means that you can decrypt a message faster than simply brute forcing the key. An example is DES which had a key space of 2^64, but only required 2^56 brute force attempts.
If I’m remembering my crypto correctly, quantum computers can break AES256 with 2^128 guesses, which is still effectively infinite from a practical perspective
jared555 t1_j1of2w6 wrote
Technically then AES is "broken" using conventional means but only barely.
mrlazyboy t1_j1ohtkh wrote
Which mode of operation?
jared555 t1_j1ombmi wrote
mrlazyboy t1_j1ov2cl wrote
That’s a theoretical attack (not practical) and it looks like it’s only applicable to ECB mode, not something like CBC or GCM
jared555 t1_j1srlsr wrote
Isn't any attack that we don't have the computational power to test going to be theoretical?
mrlazyboy t1_j1su83d wrote
Not necessarily, but it depends.
Anything worth securing is using AES256 with GCM so this attack in particular has a computational complexity of 2^254 which is effectively infinity. The computational complexity of this problem is probably greater than the number of atoms in the universe.
Even using a quantum computer, the computational complexity using this attack would be equivalent to AES128 which is still a number you don't have the ability to even conceptualize.
If you want practical attacks against this type of thing, you should check out the BEAST, Lucky13, and CRIME attacks. Those are practical attacks against SSL and TLS.
Practical attacks are those you can actually execute in the wild. I think CRIME (a chosen plaintext attack that takes advantage of compression) only requires about 20,000 messages which is relatively small.
maqp2 t1_j1tmlug wrote
Yeah, the 1.6-bit improvement is roughly 3.03x improvement. It's interesting we haven't yet seen snake oil claims like "AES 66% broken". In layman's terms, it's kind of like having to eat a cake that's 1/3rd the size of our galaxy. Sure, you got rid of 2/3rds of the cake size but your stomach will only fit so much.
wthulhu t1_j1ojprp wrote
For reference; the earth is about 2^92 grams.
nicuramar t1_j1nvznu wrote
AES isn't really susceptible to quantum attacks except with Grover's algorithm, which isn't effective because it can't parallelise very well. So I don't know where that 6600 number comes from.
Also, note that that would be error corrected qubits, which these chips don't have.
sumguysr t1_j1n9e5c wrote
Source please? My understanding was quantum computing only halves the difficulty of breaking symmetric encryption like AES but completely breaks current asymmetric encryption like RSA
nagareteku t1_j1njxg2 wrote
Grover's algorithm more than "halves" the difficulty of AES, it square roots it.
For a brute-force attack, 128-bit AES will now take 2^(64) rather than 2^(128) operations, and 256-bit AES will now take 2^(128) rather than 2^(256) operations.
To visualise the difference, 2^(128) is 18,446,744,073,709,551,616 times larger than 2^(64) and 2^(256) is that amount squared times larger than 2^(128).
Given a rate of a billion guesses per second, a single 6600-qubit quantum chip can crack AES-128 in 585 years. If we run a million cores of quantum chips in parallel, then in about 5 hours AES-128 is broken even when using a naive brute force attack. A well funded state actor could cuild such a machine, and easily decrypt anything encrypted on less than 128-bit of cipher.
256-bit AES will take a little longer, since 2^(128) is still quite a large number (3.4*10^(28)). Fortunately (or unfortunately), there exists a quantum attack on 256-bit AES with only 2^(100) operations required, although it might take 2^(100) bits (1.268 quettabytes) of storage and still require 2^(36) times more computational power than cracking AES-128.
For now, AES-256 is safe, but AES-128 is vulnerable. AES-256 may be slower than AES-128 but do not skimp on cybersecurity!
KAMSPioneer t1_j1npnnm wrote
All completely true, but the last paragraph should probably be taken with a grain of salt. For non-PQ threat models, AES-128 is totally fine. In fact key schedule attacks against AES-256 that could bring attacks down to 2^70 time (!!) do not affect AES-128.
None of that is to say that AES-256 is broken -- it's still quite safe. But unless you have strong and imminent concerns about quantum attacks on your cryptosystem, AES-128 is almost definitely not vulnerable. Most experts agree that your time is better spent worrying about everything around the primitive than the choice of primitive itself.
I just don't want anyone alarmed by the idea that there is a nearly-practical attack on AES or something. That's a long, long way off.
nicuramar t1_j1nw5o7 wrote
> Grover's algorithm more than "halves" the difficulty of AES, it square roots it.
Yes, but unfortunately it also makes it impossible to run the algorithm in parallel, making it more or less useless in practice.
itdood t1_j1n9mik wrote
KAMSPioneer t1_j1nrm7d wrote
This source says 6600 error-corrected qubits and the source article OP posted appears (though it's not completely clear to me) to not be utilizing error correction. I suspect this dampens the usefulness of IBM's new machine in implementing Grover's.
nirad t1_j1og4dn wrote
I wouldn't be surprised if the DOD already has it.
winkler t1_j1ov5wj wrote
Noob question but if I had 7 1000q-bit QCs could I break this encryption?
maqp2 t1_j1to2vx wrote
tl;dr No.
ELI5: The goal in quantum computers is to get many qubits into into a superposition where they are sort of connected to each other. As the number of qubits inside a single quantum computer is increased linearly, the problem size they can solve grows exponentially. If you add a second quantum computer, you're only doubling the computational power. With seven computers you can parallelize breaking of e.g. 7 keys, but the number of qubits inside a single quantum computer determine the size of the encryption key you're able to break.
Finally, I hope I didn't ruin some horcrux reference here, with the seven and all.
Viewing a single comment thread. View all comments