Originally published at: https://www.whonix.org/blog/most-encryption-will-be-broken

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

Maybe add OTP’s ?

http://users.telenet.be/d.rijmenants/en/onetimepad.htm

AFAIK One-Time Pads cant be broken by QC ?

Please correct me if I’m wrong

Good day,

OTP doesn’t work in a digital environment, as it’s based on pre-agreed knowledge which key is used. That doesn’t work when your partner is sitting across the globe and can’t be told which key should be used to decode a message safely. Adding to that, the QC problem extends from encryption of plain text, to any implementation of for example AES, including SSL and the encryption of hard drives and alternative solutions seem even more necessary. Luckily, as far as I can tell, a few guys over at the Debian team seem to have found a solution for this problem already, which is currently being rolled out.

Have a nice day,

Ego

I’m using OTP’s for some of my Peers and its not that big of a deal to exchange pads in person or by other trustworthy peers.

One example : http://red-bean.com/onetime/

True , but that wasnt my point.[quote=“Ego, post:3, topic:2419”]

Luckily, as far as I can tell, a few guys over at the Debian team seem to have found a solution for this problem already, which is currently being rolled out.

[/quote]

A few good News in a bad Time…

How can someone prove that this solution is QC safe when officially there are no QC’s yet?

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

Thanks @goldstein for the tip:

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

Thanks for the link and the adding of OneTime to the Docs.

@Ego

Thanks for the explanation

I read a interesting discussion some time ago about QC’s and D.J.Bernstein Monopole Role at the cypherpunks mailing list (trying to find it atm , going to post the link later)

Furthermore, allegedly the so called “adiabatic quantum computation” used in the famous D-Wave QC’s is capable of circumventing this problem

Just FYI D-Wave is not a general purpose quantum computer and therefore cannot run Shor’s algorithm or its variants.

Quantum computing works in strange ways:

https://www.schneier.com/blog/archives/2015/08/nsa_plans_for_a.html

EDITED TO ADD: The computation that factored 143 also accidentally “factored much larger numbers such as 3599, 11663, and 56153, without the awareness of the authors of that work,” which shows how weird this all is.

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://www.eetimes.com/document.asp?doc_id=1279619

https://blog.agilebits.com/2013/03/09/guess-why-were-moving-to-256-bit-aes-keys/

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

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

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.

Good day,

Well, at the moment, AES-256 is safe, as mentioned before. However, this may change in the not so distant future.

Has quite a lot of advantages over “older curves”, mainly because it wasn’t co-created with the NSA, which is also the main reason its used as the base for many advanced encryption implementations including GPG and some of the encryption used for Tor.

However, any elliptic curve can be broken by Shor’s algorithm or alternatively the D-Wave method mentioned before. Curve25519 is after all based on a “slightly” longer prime number, namely 2^255-19 (that’s also how these curves are named, simplied take the exponent, remove any operators and call it a curve). So even with it, a very strong and efficient quatum computing based system could become quite efficient at “cracking” this curve.

Like I’ve said, the latter technique gets us to numbers as high as 200099 at the moment, so we maybe shouldn’t panic quite yet.

However, keeping in mind the fact that the NSA has just recently built a massive serverfarm capable of saving somwhere between Exa- and Yottabyte’s of data (sources are unsure about the exact number, though the lowest estimate would still give them 500mb per human (!), while the highest about 100tb per human), it might not be unreasonable to assume that the NSA uses this space to store currently encrypted communication to decrypt it at a later date once the technology “is there”. If the higher estimates are true, they could hypothetically make constant snapshots of the Tor network for “investigation purposes”.

What that datacenter is really used for remains a mystery though, at least for now. Some also speculate that it’d have enough computational power to crack standards like AES, though this is pure speculation not based on any verified information.

Have a nice day,

Ego

wow quite interesting indeed,and I had no idea Tor used Curve25519 and that GPG used that, atleast Quantum computers would be too expensive for most users to have, except people such as the NSA though,hopefully Quantum cryptography will be our future solution.

oh forgot to ask so what method of cracking do Quantum Computers use? Brute force?or some type of new complex attack?

If there using Brute force im assuming Quantum computers are faster than all the super computers in the world put together? a billion super computers could check about 2^75 keys per year.If we assume they can look at 2^50 keys per second.i’m just wondering how fast quantum computers are thats all not saying your wrong or anything.

also if their using the brute force method perhaps Brute Force Detection software can help such as this? https://www.rfxn.com/projects/brute-force-detection/ let me know what you think

Good day,

Explained that above, quote:

It just, like a “normal” brute force looks true a list of possibilities, however in just the square root of time you’d normally need.

Like I’ve said, the square root of the time an equivalent “normal” machine would need.

Such a thing only works if

a.) the system is noticing such an attack fast enough and

b.) the encryption isn’t done locally in a datacenter where this kind of information can simply be ignored.

Such software only helps if you own for example a server and want to keep a look on whether someone tries to access it, not for securing communication and encryption in general.

Have a nice day,

Ego

thanks for the reply and info given