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

Patrick started developing Whonix, the Anonymous Operating System in 2012, when quickly others joined efforts. He collected experiences working pseudonymous on Whonix for two years, enjoys collaboratively working on privacy preserving software.

Posted in Whonix Important News, Whonix Misc News, Whonix Wiki Updates

Notable Replies

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

  2. Ego says:

    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

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

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

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

  5. Ego says:

    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

Continue the discussion forums.whonix.org

10 more replies

Participants