Viewing a single comment thread. View all comments

mrlazyboy t1_j1nhdg4 wrote

Reply to comment by itdood in An IBM Quantum Computer Will Soon Pass the 1,000-Qubit Mark by giuliomagnifico

“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

18

jared555 t1_j1of2w6 wrote

Technically then AES is "broken" using conventional means but only barely.

2

mrlazyboy t1_j1ohtkh wrote

Which mode of operation?

2

jared555 t1_j1ombmi wrote

https://en.m.wikipedia.org/wiki/Biclique_attack

1

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

1

jared555 t1_j1srlsr wrote

Isn't any attack that we don't have the computational power to test going to be theoretical?

1

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.

1

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.

1

wthulhu t1_j1ojprp wrote

For reference; the earth is about 2^92 grams.

1