In ~10 years Quantum Computers will break todays common asymmetric public-key cryptography algorithms used for web encryption (https), e-mail encryption (gnupg…), ssh and others. See Post-Quantum Cryptography (PQCrypto).

# most encryption will be broken

## Notable Replies

### Continue the discussion forums.whonix.org

10 more replies

HulaHoopsays:Can you post a link?

It is possible to simulate some quantum operations with classical computing: https://cr.yp.to/talks/2015.04.03/slides-djb-20150403-a4.pdf

Egosays:Good day,

Sorry, messed up on that part, heard a while ago that someone was working on implementing Niederreiter and didn't fact check it. Seems to not be the case after all. Allegedly, with some sort of error correction was used to prevent the reconstruction of private keys which usually taunts McEliece and its implementations.

@goldstein Regarding how we can tell, whether an encryption is safe against QC, it's actually quite easy and doesn't need any sort of simulation.

You see, the QC operation we are most concerned about at the moment is called "Shor's algorithm", which is a quite advanced system for the integer factorization of large numbers. In regards to the technology of QC, it just has a few limitations. One of them is the fact that for a QC to use this method to factor a number, the resulting numbers must be lower than the amount of Qubits the used QC has. At the moment, for Shor's algorithm, the official record lies at 21 using a seven qubit system which factored the numbers 3 and 7 out of it (3*7=21). With this, we can do a small thought experiment.

Think of two numbers with the following properties:

1.) They are both prime numbers.

2.) At least one of them is bigger than seven.

Now multiply them. You have created a simple encryption solution which at the moment can't be attacked by Shor's algorithm, whose main job it is to factor (i.e. guess back) the two prime numbers your result is made out of.

What this means is that, at least for Shor's algorithm, because of these mathematical limitations imposed on such a system, there are actually multiple things we can do to protect against QC based attacks. For one, looking for new, longer prime numbers is a good start. That's the reason the EFF pays anyone up to 250,000$ who finds new, long prime numbers. Regarding McEliece and other "postqantum encryption candidates", as far as I can tell, what they do is use far more complex mathematical systems over simple factorization and other solutions, though I'm not sure, I wasn't able to follow this document detailing it in it's entirety: http://tuvalu.santafe.edu/~moore/mceliece-waterloo.pdf

Furthermore, allegedly the so called "adiabatic quantum computation" used in the famous D-Wave QC's is capable of circumventing this problem which, if true, could be a massive problem as it would allow to crack encryption much faster then initially predicted. It has been said that this algorithm has factored numbers as high as 200099, though evidence is supporting this is rare.

Have a nice day,

Ego

Joshuasays:I had no idea Quantum Computers were that fast! Patrick.

Thought it would take an unreasonable amount of time to brute force AES-256 and though research i've heard it would take breaking a 128-bit key would require the storage of 2^81 bits of data (about 38 trillion terabytes).

A 256bit encryption is the mathematical equivalent of 2^256 key possibilities. To put that into perspective, 2^32 is about 4.3 billion, and it keeps growing exponentially after that. What does this mean though? Well simply put, let’s say hypothetically all the super computers in the world (the ultimate brute force attack) decided to group up and tasked themselves to decrypt your AES-256 key so they could access your data. Assume they could look at 2^50 keys per second (which is approximately one quadrillion keys/second – a very generous assumption). A year is approximately 31,557,600 seconds. This means that by using the one billion super computers required to do this, they could check about 2^75 keys per year. At this rate it would take these computers 2^34 years (the age of our universe) to look at less than .01% of the entire key possibilities.

also heres another stunning bit of info i found

If you assume:

Every person on the planet owns 10 computers.

There are 7 billion people on the planet.

Each of these computers can test 1 billion key combinations per second.

On average, you can crack the key after testing 50% of the possibilities.

Then the earth's population can crack one encryption key in 77,000,000,000,000,000,000,000,000 years!

http://canadiancloudbackup.com/safe-safe-aes-256-encryption-data/

http://www.eetimes.com/document.asp?doc_id=1279619

blog.agilebits.com

## Guess why we're moving to 256-bit AES keys

1Password is moving to using 256-bit AES keys instead of 128-bit keys. We already started this within the browser extensions in the summer of 2011, and the new Cloud Keychain Format also uses 256-bit keys. Why do you think we are making this move? If your answer is because AES 256 is stronger than

http://blog.smartbear.com/security/learn-aes256-on-your-lunch-break/

Egosays:Good day,

That's the reason why quantum computing is so attractive at the moment.

For "cracking" AES, factorization is not really going to get us anywhere, so the algorithm most suitable as far as I'm concerned would be one capable of looking through a limited number of entries in a database which hasn't been organized, as this would be the best "way" to imitate a brute-force attack without having to go into much detail. Something in the ball park of amplitude amplification should do the trick here. What this would allow us to do, is to do a search for the wanted entry in a square root of operations based on the number of possible enquiries. Or to put it more simply, if there are X possibilities, we'd need √X operations with the logarithm of X being the needed amount of memory. The advantage of such a system is obviously the much smaller number of necessary operations as for a normal computer the amount of operations would always equal X. With this, AES-128 could be broken quite easily, though that is not really necessary, as AES-128 has been rendered both insecure and obsolete decade(s) ago. Now, for AES-192 and AES-256, at the current point in time there seems to be no concern as even with the squared speed compared to normal super-computers it'd still take a long time, as your generous estimate showed. Just take the square root of your results and you may see how immense the positive impact on work speed provided by this solution would be, however at the same time, how immensely long it'd still take.

Have a nice day,

Ego

Joshuasays:yea quite intesrestings stuff but far over my head,Quantum cryptography might be the solution were seeking as the old saying goes "fight fire with fire"

really thought AES-256 was unbeatable, techology keeps surprising me the more it evolves i'm quite impressed with these Quantum computers very advanced indeed but troublesome if someone with the wrong hands gets a hold of them

Whats your opinion on elliptic curve cryptography which uses Curve25519?

This elliptic curve follows all of the standard IEEE P1363 security criteria. It also follows new recommendations that achieve "side-channel immunity" and "twist security" while improving speed. What this means is that secure implementations of Curve25519 are considerably simpler and faster than secure implementations of (e.g.) NIST P-256; there are fewer opportunities for implementors to make mistakes that compromise security, and mistakes are more easily caught by reviewers.

An attacker who spends a billion dollars on special-purpose chips to attack Curve25519, using the best attacks available today, has about 1 chance in 1000000000000000000000000000 of breaking Curve25519 after a year of computation. One could achieve similar levels of security with 3000-bit RSA, but encryption and authentication with 3000-bit RSA are not nearly fast enough to handle modern DNS loads and would require much more space in DNS packets.

http://dnscurve.org/crypto.html