Slashdot Mirror

← Back to Stories (view on slashdot.org)

IBM Warns Quantum Computing Will Break Encryption (zdnet.com)

Posted by EditorDavid on from the no-more-secrets dept.

Long-time Slashdot reader CrtxReavr shares a report from ZDNet: Quantum computers will be able to instantly break the encryption of sensitive data protected by today's strongest security, warns the head of IBM Research. This could happen in a little more than five years because of advances in quantum computer technologies. "Anyone that wants to make sure that their data is protected for longer than 10 years should move to alternate forms of encryption now," said Arvind Krishna, director of IBM Research... Quantum computers can solve some types of problems near-instantaneously compared with billions of years of processing using conventional computers... Advances in novel materials and in low-temperature physics have led to many breakthroughs in the quantum computing field in recent years, and large commercial quantum computer systems will soon be viable and available within five years...

In addition to solving tough computing problems, quantum computers could save huge amounts of energy, as server farms proliferate and applications such as bitcoin grow in their compute needs. Each computation takes just a few watts, yet it could take several server farms to accomplish if it were run on conventional systems.
The original submission raises another possibility. "What I wonder is, if encryption can be 'instantly broken,' does this also mean that remaining crypto-coins can be instantly discovered?"

27 of 197 comments (clear)

  1. crypto-coins? by DogDude · · Score: 5, Insightful

    What I wonder is, if encryption can be 'instantly broken,' does this also mean that remaining crypto-coins can be instantly discovered?

    This could theoretically be the biggest breakthrough in computing since transistors, and this person is wondering about how it's going to affect Monopoly money? Jesus.

    --
    I don't respond to AC's.
    1. Re:crypto-coins? by FrankSchwab · · Score: 2, Insightful

      You have no idea what you're talking about, do you?

      You've got all the right words there, but completely the wrong concepts behind them. You do realize that ALL of the data shipped around via HTTPS is encrypted with symmetric algorithms, right? And that asymmetric algorithms are used to create and agree on the symmetric keys to be used for communications, right?

      --
      And the worms ate into his brain.
    2. Re:crypto-coins? by Joce640k · · Score: 4, Informative

      To be clearer: Quantum computers break things based on number factoring, eg. certificate signing.

      It doesn't break block ciphers like AES.

      It might break blockchain, yes, but, like, who cares?

      --
      No sig today...
    3. Re:crypto-coins? by glenebob · · Score: 3, Interesting

      What a strange and verbose way of saying "you're right, quantum computing will break HTTPS".

    4. Re:crypto-coins? by ledow · · Score: 5, Interesting

      Hashes are actually one of the best ways to stay QC-safe.

      At the moment, we use our existing encryption algorithms to generate hashes. Instead, most of the quantum-safe encryption algorithms use hashes to build themselves.

      The reason is quite simple if I can use an analogy. It's not 100% accurate, but good enough to make most people understand.

      First - a hash.
      You take an input, you generate a "mini-mash" of it - you jumble it up and cut bits out in a predictable manner until you get something that is absolutely tiny but built from that original input.

      The same input will give the same hash every time, because you do the same thing every time. Yet millions of different inputs might give you that same mini-mash (because they are much fewer hashes than there are data-sets, so by chance they overlap sometimes - a hash collision) but that hardly matters in real life because the chances of those other inputs being valid Microsoft Word files, or containing the same secrets as your files are infinitesimally small.

      Quantum-computers attacking conventional encryption works like this:
      - you "build a circuit" that performs the same encryption that was used (e.g. AES, ECC, etc.).
      - you plug in the ANSWER (the encrypted text) into the end of it.
      - by some magic of physics, it instantaneously determines the only possible inputs that could have ever formed that answer. Thus, it works out the SECRET INPUT (i.e. the keys) that was originally used to encrypt it - all in one "tick".

      As such, QC defeats traditional encryption entirely. Every encrypted text/web session is one tick away from compromise with zero effort required and only tiny amounts of time expended.

      But when you apply that technique to hashes, there may not be only one possible input. In fact there may be an infinity of inputs that give the same hash (because the input can be any size, right? So the mini-mash of a entire novel could the same as the mini-mash of "123" or the same as the mini-mash of a dataset as large as the universe).

      As such, the QC can't determine the answer - it gets all the answers and doesn't know which one's right. To know which one was right, you'd have to check them all... and you're now back from "working out the answer instantaneously" to "checking all the possible combinations one at a time".

      So instead you can build QC-safe encryption by using hashes upon hashes upon hashes upon hashes. Now any possible inputs a quantum computer may determine is lost in an infinity of other inputs... and it's no longer as simple as "just give us the only input that looks like a Word file" - you have to check them all.

      As such, hashes are the basis of much more security, based on their "unknown but potentially infinite amount of data" turned into "a small set of characters" property.
        Crypto-currencies use hashes a lot (Bitcoin is/was basically built upon "keep hashing different things on the end of this string until you get a hash of 0 out of it") and so may be the last thing to fall to QC.

      In the same way that QC turns cryptanalysis on its head, to solve the problem of QC we turn hashes and encryption on their heads.

    5. Re:crypto-coins? by Joce640k · · Score: 3, Insightful

      You have no idea what you're talking about, do you?

      You've got all the right words there, but completely the wrong concepts behind them. You do realize that ALL of the data shipped around via HTTPS is encrypted with symmetric algorithms, right?

      It's almost as if you don't know that HTTPS relies on signed certificates for authentication...

      --
      No sig today...
    6. Re:crypto-coins? by Anonymous Coward · · Score: 2, Insightful

      You do realize that ALL of the data shipped around via HTTPS is encrypted with symmetric algorithms, right? And that asymmetric algorithms are used to create and agree on the symmetric keys to be used for communications, right?

      Except for the keys when not using Diffie-Hellman, which lets you break the whole thing. An the trust validation is done based on RSA/ECC signatures, so you could just crack the root cert and use it to sign whatever keys you want, letting you break the whole thing. If you want to try to sound smart, you should probably know what you're talking about first.

    7. Re:crypto-coins? by sjames · · Score: 2

      Or, you generate the block you want which produces a partial hash. Now, you have a partial hash, a desired complete hash, and an empty field to make it happen.

      The blockchain doesn't care which possible solution goes in that field, just that one of them does.

    8. Re:crypto-coins? by ZorinLynx · · Score: 5, Insightful

      With the rate that crypto-currency mining is wasting energy, breaking blockchain might be a very good thing for our future.

    9. Re:crypto-coins? by lhunath · · Score: 2

      Please update your response. QC does not break encryption. It breaks factoring performance. That means, all it breaks is private key discovery from a public key. It does not break the encryption performed with those keys (though obviously, discovering a private key trivially is a problem), and it does NOT BREAK SYMMETRIC ENCRYPTION, which is by far the most common and most robust encryption in use today. It's vital we stop the spread of misinformation. Start with yourself.

      --
      ``OK, so ten out of ten for style, but minus several million for good thinking, yeah?''
    10. Re:crypto-coins? by swillden · · Score: 4, Informative

      To be clearer: Quantum computers break things based on number factoring, eg. certificate signing.

      It doesn't break block ciphers like AES.

      It might break blockchain, yes, but, like, who cares?

      Quantum computing does weaken both symmetric ciphers like AES and hashing algorithms which are the basis of blockchains (though many blockchains also make use of asymmetric digital signatures which are more deeply affected). Specifically, Grover's Algorith is a quantum algorithm that can find the input that provides a given output for any algorithm with at most sqrt(N) applications of the algorithm. This means that with sufficiently-good quantum computers, you can find a 128-bit AES key for a known plaintext/ciphertest pair in 2^64 steps, which just might be feasible. Similarly, given a 160-bit hash, like SHA-1, you can find a pre-image for a given hash value in 2^80 steps.

      Of course, if you use AES-256, Gover's algorithm will find you an answer in 2^128th steps, which is almost certainly forever out of reach Similarly for SHA-2 256. This assumes that Grover's algorithm is the best way to attack these sorts of primitives with a quantum computer, of course. We may discover other approaches that are less general, but better.

      --
      Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
    11. Re:crypto-coins? by swillden · · Score: 2

      Quantum-computers attacking conventional encryption works like this: - you "build a circuit" that performs the same encryption that was used (e.g. AES, ECC, etc.)... As such, QC defeats traditional encryption entirely.

      This is incorrect. Shor's algorithm promises one-step breaks of asymmetric algorithms (RSA, ECC), but it does not work on symmetric ciphers like AES or (as you correctly say) hash functions. However, Grover's algorithm, does work on symmetric ciphers and hash functions. Not as well; given an N-bit search space, Grover's algorithm requires sqrt(N) steps. Still that puts AES-128 at risk of sufficiently large and efficient quantum computers. AES-256 is pretty safe, though, barring some other quantum algorithm that is more effective.

      --
      Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
    12. Re:crypto-coins? by Joce640k · · Score: 2

      Quantum computers can potentially reduce the amount of operations by the square root of the search space. So if you have a 64 bit key, it's now a 32 bit keyspace you have to search through.

      Only for known-plaintext attacks.

      --
      No sig today...
    13. Re:crypto-coins? by thegarbz · · Score: 5, Insightful

      It might break blockchain, yes, but, like, who cares?

      I care. The sooner we can break blockchain the sooner we can stop the insane amount of wasted energy we are pouring into this retarded tulip and go back to reducing the world's energy consumption like we were doing before this stupidity infected us.

  2. Kinda like fusion.... by jythie · · Score: 4, Insightful

    I am thinking back to the saying 'AI, like fusion, has been 10 years away for 30 years now'. I think that quote was from the 60s or 70s, so add a few decades. The earth shattering predictions for quantum computers have been around for a while and they are always 'just about to be realized', but even today it is cheaper to emulate quantum computers on traditional machines than to actually build and use them. It is questionable, given advances in traditional semi-conductors, if it will EVER be cheaper to use quantum computing, even for the tasks it is best suited for.

  3. Elliptic Curve Cryptography? by Dwedit · · Score: 3, Interesting

    Wasn't elliptic curve cryptography supposed to be resistant to quantum computers?

  4. Both by dilvish_the_damned · · Score: 5, Funny

    The original submission raises another possibility. "What I wonder is, if encryption can be 'instantly broken,' does this also mean that remaining crypto-coins can be instantly discovered?"

    Yes and No.

    --
    I think you underestimate just how much I just dont care.
  5. Regarding crypto coins by Anonymous Coward · · Score: 2, Interesting

    Yes, quantum computers will eventually allow people to crack the private keys for most cryptocurrency wallets. However, some projects are already working to address this. The best example is Quantum Resistant Ledger (QRL), which is redesigned from the ground up to use quantum proof crypto algorithms. Look it up, they have a lot of info on exactly HOW quantum computers will affect cryptocurrencies, and other related data.

  6. Alt encryption owned by IBM by DalM · · Score: 4, Insightful

    Of course the alternate encryption like that which IBM recommend happens to be owned by IBM. Better buy in now!

  7. Answer: lattice-based crypto around since 80's... by Idisagree · · Score: 3, Informative

    Article is very light on evidence of any new form of successful attack so it's a bit premature to advise the sky is falling just yet!

    Better encryption methods are always being worked on and we will phase out the old encryption methods when they become stale and move onto more resistant types.

    As it so happens there are already some constructions (and they have been around for some time) that can be used such as Ring-LWE and NTRU which have been shown to hold up against classic and Quantum based attacks.

    I'm going back to my bowl of cereal now.

  8. Re:IBM salesbros and hindu slackers are not going by vtcodger · · Score: 4, Interesting

    Probably wrong on the details

    But that's slightly different than dead wrong.

    It does emphasize what we all sort of know. Encryption that is good enough today will probably be not good enough in a few -- five, ten, fifteen -- years. Which suggests that all your email and metadata that you and others have stashed in encrypted stores may be decodable if you (and they) keep the stores around too long.

    And it doesn't matter what technology makes the data readable. Quantum computing, brute force, some clever algorithm, some flaw in common encryption algorithms or the software implementing them. Your secrets may not remain secret.

    That's probably not a good thing.

    --
    You can't see ANYTHING from a car, You've got to get out of the goddamned contraption and walk...Edward Abbey
  9. The solution is easy, folks .. by CaptainDork · · Score: 2

    ... when quantum computing is capable of breaking current encryption, that same computer will be providing unbreakable encryption.For example:

    . A. Ekert, “Quantum cryptography based on Bell’s theorem,” Phys. Rev. Lett.0031-9007 https://doi.org/10.1103/PhysRe... 67, 661–663 (1991). Google ScholarCrossref, CAS

    --
    It little behooves the best of us to comment on the rest of us.
  10. No news by manu0601 · · Score: 2

    It has been known for years that quantum computers will break RSA using the Shor algorithm.

    The interesting question, which is not answered in TFA, is: what algorithms are resistant to quantum computers? Do we have some available in TLSv1.3?

  11. IBM is known as by zaphirplane · · Score: 4, Insightful

    The company that sheds jobs, non stop revenue door and off shoring jobs
    Their insights are marketing equivalent of click bait

  12. Ideal quantum computer factors in polynomial time by raymorris · · Score: 4, Interesting

    More accurate would be be "if an ideal (perfect) quantum computer existed, with enough cubits, it could break some types of encryption in a reasonable time".

    Ideal quantum computers don't exist, and never will. An open question how near actual, physical quantum computers will get to this theoretical perfect machine. It's kinda like doing physics approximations and starting with "ignoring air resistance and friction ...". Well yes, if there were no friction we could build machines that do a lot of things which can't actually be done, because in the real world there is friction.

    In a universe that only exists in textbooks, a universe of ideal machines, ideal quantum computers could factor numbers in polynomial time. Not instantly, but it wouldn't take a billion years like it would with classical computers.

    Some of the cryptographic algorithms we use today get their strength from the difficulty of factoring certain types of large numbers. Those algorithms would need to be replaced if quantum computers developed sufficiently.

    Already, we deprecate cryptographic algorithms every couple of years. Part of my job is checking https, ipsec, and other systems to see that they are configured to use strong algorithms. I have to update our list of currently accepted algorithms a couple times per year. The designers of these protocols were smart in that the designed the protocols to support any algorithm you want. For example, TLS defines that "key exchange" messages should be exchanged, but doesn't define what type of key exchange. It could be RSA key exchange, it could be Diffie-Hellman, it could be elliptic curve Diffie-Hellman, or supersingular elliptic curve Diffie-Hellman. TLS (aka SSL) doesn't know or care. Classical Diffie-Hellman can be replaced with supersingular DH without changing anything about TLS.

  13. Warning: Consultants at Work by cormandy · · Score: 2

    "Anyone that wants to make sure that their data is protected for longer than 10 years should move to alternate forms of encryption now," Please contact IBM Professional Services for further assistance in this matter.

  14. Lol! My brain does that by raymorris · · Score: 2

    If the quantum computer is 300 cubits in length, 50 cubits in width and 30 cubits in height - well then it's Noah's ark.

    Qubits, of course. My brain does that - I spell well and all, but I tend to write homophones, words that sound identical, because I think audibly.