Quantum PC secure encryption

Discussion in 'Serious Discussion' started by CHEF-KOCH, Apr 10, 2016.

  1. CHEF-KOCH

    CHEF-KOCH MDL Addicted

    Jan 7, 2008
    941
    885
    30
    #1 CHEF-KOCH, Apr 10, 2016
    Last edited by a moderator: Apr 20, 2017
    Hello security friends :icecream:.


    Today I open a little topic which explains what is theoretically quantum pc secure, I say theoretically because Googles D-Wave and other QP's [Quantum Pc's] still have huge problems [see attachments/papers] and it might take several years to really stabilizing them. There are not only hardware problems to solve also several software problems because you really need to re-write own stuff from the ground.


    This topic is not really for beginners and requires a little bit own background knowledge but I try to keep them as easy as possible for you.




    First things first - What are Quantum Computers?
    Quantum computers are going to be the next huge development in computing for processing data, with an ability to perform calculations thousands of times faster than today’s modern supercomputers.

    [video=youtube_share;JhHMJCUmq28]https://youtu.be/JhHMJCUmq28[/video]
    [video=youtube_share;CMdHDHEuOUE]https://youtu.be/CMdHDHEuOUE[/video]



    Quantum computing is not well suited for tasks such as word processing and email, but it is ideal for tasks such as cryptography, modeling and indexing enormous databases.
    A quantum computer can compute in minutes or hours what a conventional computer would take years or much longer to do the same action.


    Which encryption is known as weak?

    • Symmetric encryption is in general weak. A quantum computer can search through a space of size 2n in time 2n/2. This means that a 128-bit AES key would be demoted back to the strength of a 64-bit key - however, note that these are 264 "quantum-computing-operations" You cannot apply figures from studies with FPGA and GPU and blindly assume that if a quantum computer can be built at all, it can be built and operated cheaply.
    • RSA (with limitations see my example)
    • DSA
    • ELGamal (DSA, Diffie-Hellman)
    • Diffie-Hellman Key Exchabge
    • ECC
    • The real problem is not only which algo was used, a lot of implementation mistakes can leak your privacy data, an example is e.g. the Tox Ip leakage problem, same like the WebRTC ip leakage. In fact the 'new' protocols promising you a lot of things but none or less was really audited, or created by experts. To create something new and to think just because you implemented end-to-end encryption, makes you not more secure. You should not believe the hype and consider using known techniques which really are tested over years. Another great example is Telegram, which also uses false sense of security in the past.
    • A quantum computer can implement Shor's algorithm which can quickly perform prime factorization. Encryption systems are build on the assumption that large primes can not be factored in a reasonable amount of time on a classical computer.


    Quantum computing will make mostly dramatic impact on asymmetric encryption, but symmetric algorithms are considered safe with a large enough key size (256 bits) [x509/SSL]. Same like 1-time pad which is de-facto uncrackable.


    Which one is secure and not attackable (directly)?

    • ECDSA (with high key length e.g. described in NIST FIPS 186-4)
    • One-time pad (the mentioned problems are useless in this article due the fact that data how we it use today was not present in the past and there not exist much encryption experts like today + implementation problems)
    • 264 bit enc. + 512 hash ... (unconfirmed, needs test because theoretically it's enough - theoretically also SHA2/3 + AES based on diffusion and confusion)
    • Microsoft has already took an initiative, and is working with chip maker NXP and Queensland University of Technology (QUT), to build a new protocol of key exchange model that is suitable for use in SSL/TLS and can’t be cracked easily by Quantum computers.
    • NTRUEncrypt (Based on Lattice based cryptography)
    • RSA (theoretically - it's depending)
    • McEliece (code-based cryptography)
    • Multivariate cryptography like Hidden Fields Equations
    • AES (theoretically if a long key was chosen)
    • The implications of applying multiple layers of encryption can be quite complex and in the worst case reduce the individual layers' security - take for example XOR'ing the entire message twice - you end up with the original message! And even if you use two different keys, it's still equivalent to XOR'ing with one entirely different key. It's of course more complex with AES, but you'd really do yourself a favor by increasing the key size instead as explained above or in given research links/papers.


    Are the higher key length the answer?
    No it's not really necessary, there exists protocols which are uncrackable and if I say uncrackable I really mean that e.g. axolotl due the fact that if you want to MITM or otherwise want to hack/crack it it simply entirely breaks. This is an security mechanism which blocks then the entire communication.


    What we can do?

    That's an good question, because why they need to crack something if they just can fool us with other tricks, like social engineering, fake updates or compromised certificates?


    • You should consider to use alternatives
    • Don't believe every hype, just because someone promises you it's secure it does't mean anything. Same goes to VPN providers, I not talk about paranoia I talk about that you should have a distrust in such promises and ask as much as possible to get the information you really need to come to an conclusion. If possible wait until there are same reviews and statements or audits from crypo-experts. If you see that an software/app not regularly get's maintained this is mostly a bad signal - some goes if it get's too often updates.
    • Knowledge and information is still together with your mind the biggest weapon, if you keep yourself motivated and interested in such topics you have almost won because people which may not get informed more get's a target or are unable to protect themselves.
    • Since we know that NSA and CO. is spying on us, just ensure you simply not send plain-text into the network, critical documents should be taken offline and have nothing much to do in the cloud. Snowden said that xyu cloud is maybe more secure, I say it's bull, the better logic is to simply (if possible) not send it into the cloud if it's not necessary which reduce the attack surface by 100%. Always ask yourself why you need to upload everything in the cloud, the conclusion is because you can + it's easier in some situation, and exactly because of this it's also easier to hack you since most not care about additional protection mechanism. If you really want to go into the cloud, ensure you use in-top of it tools like boxcrypter or cryptomator.
    • Security not starts with the tools you use, it should start with the protocols you prefer, you could use sftp instead of the insecure ftp as an example if you not game or need really Windows apps you tried Linux already - why not? Even if you are forced to use Windows, did you tried to harden the Windows settings? Mostly this is so easy everyone could understand it and it lowers several attack scenarios.
    • There exist hardware based solutions. China also also comes with an solution /which may can be adopt into other systems)
    • Be careful about mixed mixed algorithms.



    Source/Research:

    * http://arxiv.org/abs/1507.08852
    * https://en.wikipedia.org/wiki/Post-quantum_cryptography
    * http://www.theguardian.com/world/2013/sep/05/nsa-how-to-remain-secure-surveillance
    * http://www.washingtonpost.com/world...ff297e-7195-11e3-8def-a33011492df2_story.html
    * https://en.wikipedia.org/wiki/Lattice-based_cryptography
    * https://en.wikipedia.org/wiki/Category:Code-based_cryptography
    * https://www.fredericjacobs.com/blog/2016/04/07/qc-axolotl/?1=0
    * https://en.wikipedia.org/wiki/Multivariate_cryptography
    * http://www.springer.com/us/book/9783540887010
    * https://www.quantamagazine.org/20150908-quantum-safe-encryption/
    * http://www.pcworld.com/article/3041...mputer could make today's encryption obsolete
    * https://crypto.stackexchange.com/qu...ave-been-out-for-a-while-has-rsa-been-cracked
    * https://en.wikipedia.org/wiki/Double_ratchet
    * http://codexgalactic.com/2014/01/27/axolotl-protocol-for-cryptographically-secure-messaging/
    * https://github.com/WhisperSystems/Signal-Android/wiki/Publicity-material
    * http://techcrunch.com/2015/06/22/pq-solutions/
    * http://www-03.ibm.com/press/us/en/pressrelease/965.wss
    * http://tbuktu.github.io/ntru/
    * http://tools.ietf.org/id/draft-ietf-pkix-pkalgs-supp-01.txt
    * http://pqcrypto.org/
    * http://arxiv.org/pdf/quant-ph/0310130
    * http://www.princeton.edu/main/news/archive/S26/53/89C28/index.xml?section=newsreleases
    * https://imgur.com/a/zWIoY (Pictures)
    * http://emergentchaos.com/archives/2008/03/quantum-progress.html
    * https://www.sans.org/reading-room/whitepapers/vpns/quantum-encryption-means-perfect-security-986
    * https://www.federalregister.gov/doc...lic-key-post-quantum-cryptographic-algorithms
    * https://www.nist.gov/news-events/ne...blic-help-future-proof-electronic-information


    Problems:

    * http://arxiv.org/pdf/1512.02206v1.pdf
    * http://arxiv.org/abs/1304.4595
    * http://www.scottaaronson.com/blog/?p=2555
    * http://www.sciencemag.org/content/early/2014/06/18/science.1252319
    * http://www.nature.com/nature/journal/v473/n7346/full/nature10012.html
    * http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf
    * https://www.techdirt.com/articles/2...cking-computers-hacking-entire-industry.shtml



    Official Papers/Talk by NIST:
    * http://csrc.nist.gov/publications/drafts/nistir-8105/nistir_8105_draft.pdf
    * https://cryptologie.net/article/334/nist-and-quantum-computers/
    * http://pqcrypto.eu.org/docs/initial-recommendations.pdf




    What we have learned from this?
    * RSA systems are e.g. based on two prime numbers and their multiplication -> p1,p2,.. are huge primes p1xp2=N modulus. RSA systems is like that choose a prime number, smaller as factor E (public key), which stands for (p1-1)*(p2-1)=R find a D number that makes E*D=1 mod(R) we are sharing (E,N) data as public key publicly we are securely saving (D,N) as private. Solving this is possible if we find the prime factors of N. As an example: The entire mass of the (visible) Universe is closer to 10^53 kg* electron mass is 9.10938291 × 10^-31 kilograms if we divide universe to electrons we can create 10^84 electrons. electrons has slower speeds than light. its move frequency can be 10^26 if anybody produces electron size parallel rsa prime factor finders from all universe mass. all universe can handle (10^84)*(10^26)= 10^110 numbers/per second. RSA has limitless bits of alternative prime numbers. maybe 4096 bits 4096 bit rsa has 10^600 possible prime numbers to brute force. So our universe mass quantum solver need to make tests during 10^500 years. -- Theoretically this is still good to go.
    * QP's are far away from been perfect, they are currently by time or writing this not faster as a normal PC/Supercomputer.
    * The hype and the fear is present but not anything we can work with.
    * Implementation problems, missing knowledge/audits makes it almost impossible to say which is secure and which not, just because it's closed source not means it contains mistakes/backdoors failures, and just because it's open source it not means a lot of people will understand and audit it (e.g. see entire OpenSSL story).



    Verdict:
    * Costs 10 ~ 15 mio (e.g. Googles D-Wave) and the price will not lower much, due several factors, so only agencies or rich people/organisations can buy this.
    * Runtime problems / slowdowns
    * Slowdown the calculation process have a huge impact on 'cracking' encryption
    * The entire building around the ONE SINGLE CPU is easy detectable, just mention this because if someone not like that, he could easily (more or less) start attacks ... Building something deep in the mountain is semi optional because this is visible via satellites (remember NSA new Headquarter was also spotted by this).
    * The CPU needs to be cooled down all the time, every single °C has an negative impact on it and it's performance.
    * It's unclear how the real output (power) of a QP is. We are here on more or less theoretically ground and no one from us can check against a running QP (not saw yet one on ebay) so the question is if we give them too much credits or will it really work at the end?! - Who considers it unbreakable even with quantum computers?
    * As Mentioned as long side-channel attacks are possible, it's critical, an solution is to keep e.g. the key not on the same device.


    Please excuse my math examples, the board software not allows latex/math, which could be help with picture of it but's pure pain and we not have any plugin to fix that


    If there is more interest with mathematically facts I could give via pm a link for a free download of my book (but's in .ru lang).
     
  2. Yen

    Yen Admin
    Staff Member

    May 6, 2007
    11,087
    10,744
    340
    #2 Yen, Apr 22, 2016
    Last edited: Apr 22, 2016
    One should consider that if that tech should be realized quantum cryptography to encrypt should be also realised.
    This tech is not an impact on the security side by decryption only (except the tech is only available to a few)!

    AFAIK quantum key distribution has been already successfully realized over a distance of around 20 kilometres.
    Carrier of communication were photons (to share keys), the clue is that if one 'grabs' and releases those they get modified either way. Receiver and sender detect changes by comparing a part of it (can be public) and a new key can be created in time before the attacker can even use a quantum computer to try to decrypt.

    To get familiar with it I'd suggest to get info about entanglement, superposition and decoherence.
    I personally am very sceptical about a realisation anytime soon.

    @chef
    Grover iteration reduces probability from N/2 to square root of N attempts and belongs besides of Shor to a favourable quantum algo.
     
    Stop hovering to collapse... Click to collapse... Hover to expand... Click to expand...
  3. CHEF-KOCH

    CHEF-KOCH MDL Addicted

    Jan 7, 2008
    941
    885
    30
    Chrome get's quantum secure encryption. It's already mentioned over here what is quantum pc secure encryption. Now people will saying there is a backdoor because Google, MS, IBM and Intel working together to realize that, but it' wrong, because such project needs a lot of time, money, research and people which can code such things. CECPQ1 seems a promising project, from what I know tor also already adopted Elliptic Curve 25519, I only can hope that we see more TLS with it. You can get a deeper look how it works over here and here. The source will be open once it's final.
     
  4. CHEF-KOCH

    CHEF-KOCH MDL Addicted

    Jan 7, 2008
    941
    885
    30
    Since there is no progress (exactly what I've expected) there is maybe now finally a new 'hope'. This article is very complex and you need to understand the basics of 'Qubits'.

    I'll try to summarize it :Albert: :
    * On Ions based devices which want to address more than 10 - 14 Qbits it was (is) problematically to stabilize them, since they acting on this small line as normal Bits, which means they then only use 0/1 - then there would be no benefit of using it since they acting like traditional Bits we already know.
    * Now several University and Google claim to have an solution for this.
    * Overall they want to force a specific behavior with a magnet field (direct on a silicon-die). It simply blocks/prevent the Qubit to act like an normal Bit.

    All of this is more in a beta test right now, there was one single sample which worked but the question is still to fully get it stabilized. Ms works (since 2006) btw already on a different (and imho better way) they working on a topological Qubit (they call it 'Station Q'). The benefit here is that this 'version' is much more resistant against environmental influences. Both 'solutions' are anyway based on Ions.


    I would say they finally did it but it's another step forward.