(No Ratings Yet)

Loading...

• Facebook
• Twitter
• LinkedIn
• Mail

October 19, 2016 1

Google Prepares For Quantum Computing Risks

in Industry Lowdown

And How You Can Try Post-Quantum Cryptography Today.

Quantum computers are still a long way from being used outside of the laboratory, it was only this year that researchers figured out how to make it possible to run one at room temperature instead of just above absolute zero.

But while it is likely decades before quantum computers are used in any real sense, the risk they pose to certain technologies designed for the “classical” computers we use every day is very real, even if it is a distant one.

The underlying problem is that quantum computers can “solve certain sorts of problems dramatically faster than conventional computers can.” For certain technologies – like the encryption methods that are commonly used in SSL/TLS – quantum computers threaten to nullify any protections they were designed to provide.

So Google’s engineers have been working on a way to test a new encryption algorithm, one that could be used with today’s SSL/TLS protocol and provide security against classical and quantum computers.

Google is calling this “post-quantum cryptography” and in July they launched an experiment in their Chrome browser to get real world data. The algorithm is based on a protocol named “New Hope,” which was designed by an outside group of researchers.

This new algorithm, known as CECPQ1 (Combined Elliptic Curve + Post-Quantum 1), fuses New Hope with the widely-used and accepted X25519 Elliptic Curve, in order to ensure connections encrypted with this experimental algorithm remain secure even if New Hope turns out to have vulnerabilities.

The algorithm is only available to a randomly selected group of Chrome Canary clients and the test will be run for up to two years.[1] After that it will disappear, hopefully “replacing it with something better,” wrote Google’s Matt Braithwaite.

While you may never use CECPQ1, this experiment is extremely important for the future of cyber security and cryptography and will be significant for new research in the field of quantum computing.

What is Quantum Computing? And Why Do Cryptographers Care About It?

Quantum computing is a big deal for cryptographers, who have spent years of effort designing algorithms and mechanisms that are secure for use with classical digital computers.

If you aren’t at all familiar with quantum computing, it is a fundamentally different type of computer that uses quantum physics and mechanics. It is incredibly complicated – good explanations are a few pages long – but you only need to understand a tiny sliver for our purposes here.

IEEE.org has a good summary of the difference between classical computers and quantum computers:

“Quantum computers, however, have a leg up over traditional computers when it comes to factoring. A classical computer uses bits of information, 1s and 0s. A quantum computer uses what are called qubits, which can be a mix of both 1 and 0 simultaneously and which exist in a delicate quantum state called superposition.”[2]

These qubits, and their superpositions, make it possible for quantum computers to factor numbers very quickly.

For classical computers, factoring numbers is difficult work. RSA, one of the most widely-used encryption algorithms, is based on “the practical difficulty of factoring the product of two large prime numbers.” [3]

A quantum computer that could easily factor said numbers would be a major threat to the security of the RSA algorithm. If someone – a nation-state would likely be the first to do so – deployed a fully operational and sufficiently powerful quantum computer, it could potentially decrypt every bit of information secured with RSA.

The Quantum Threat

So, are quantum computer close to posing a real threat to modern-day cryptography in use with protocols like SSL/TLS?

In 2014, researchers made a breakthrough in quantum factorization. They showed how a quantum computer could factor the number 56,153, smashing the previous record which was a factorization of 143. They used some tricks to achieve the feat, but for these purposes, we will say this is the record.

Today, most SSL certificates use RSA keys to generate secure connections. These connections can be ‘broken’ and made unsecure if someone had a copy of your key or could guess the key by factoring it.

To keep users safe, industry regulations mandate that RSA keys must be at least 2048-bits to provide adequate protection from classical computers, which are capable of factoring large numbers given enough time (years).

That private key is created from two prime numbers, which are normally half the length of the key – so 1024-bits each in this case. These are binary numbers – 0s and 1s. A 1024-bit binary number is a 309 digit number in decimal notation – which is the form we use in everyday life to count money or express measurements.

A 309 digit number is quite large. To put it into context, a billion is just ten decimal digits. Classic computers would need tens of years to factor a number this size, and we do not know of any successes in breaking RSA-2048 this way.

So, back to that largest number ever factored by a quantum computer: 56,153. In binary, this would be expressed as “1101101101011001.” That makes it a 16-bit binary number.

That is just 1/64th of 1024. Now, I am not an expert in quantum computing – so it is hard to say exactly how significant that gap is. But, back in 1995, the first version of SSL required a minimum of a 64-bit key, which would use 32-bit primes. So today’s quantum computers couldn’t even crack SSL security from two decades ago.[4]

Matthew Green, a cryptographer and professor at John Hopkins, said any real risk is “from 15 to 30 years away,” in an interview with IEEE.org earlier this year.[5]

So, there is certainly no immediate threat posed by quantum computing, but it can’t hurt to be prepared early.

Try Post-Quantum Crypto Now:

Not everyone will be able to use this cipher. Chrome only enables the CECPQ1 cipher on a certain subset of clients. So even if you follow these directions, you may just not be lucky enough to have been “selected” (the specific criteria is unknown, but is likely created to collect a wide range of data without collecting too many observations ). One of my PCs at home has CECPQ1 support, and another does not.

First, you will need to download Chrome Canary. This is a developer version of Chrome that acts as a test bed. It is usually 2-3 releases ahead of the “stable” version that you usually use. If you already have Canary installed, make sure it’s updated to the latest version by visiting the About page.

Then, open Developer Tools (Ctrl + Shift + I on Windows/Linux, Cmd + Opt + I on Mac) and select the “Security” tab. This will show you information on the TLS configuration of the site you are on.

Go to https://play.google.com. In the Security pane, you should see a section titled “Secure Connection,” which will tell you about the TLS connection. If it says you are using “a strong key exchange (CECPQ1_ECDSA)” then you are using quantum-resistant cryptography!

You can also see CECPQ1 in use alongside RSA at https://mjos.fi/, the personal website of Dr. Markku-Juhani O. Saarinen, a security researcher and cryptographer.

If instead, it lists “ECDHE_ECDSA” as your key exchange, then unfortunately your Chrome client does not have support and you will have to live vicariously through the screenshots in this post.

---

[1] https://twitter.com/agl__/status/785166356500971520

[2] http://spectrum.ieee.org/tech-talk/computing/hardware/encryptionbusting-quantum-computer-practices-factoring-in-scalable-fiveatom-experiment

[3] https://en.wikipedia.org/wiki/RSA_(cryptosystem)

[4] https://twitter.com/KristoferA/status/788232099228708865

[5] http://spectrum.ieee.org/tech-talk/computing/hardware/encryptionbusting-quantum-computer-practices-factoring-in-scalable-fiveatom-experiment

• #Google
• #Post-Quantum Cryptography
• #Quantum Computers
• #Quantum Computing
• #SSL
• #TLS