Embracing the Post-Quantum Internet

Cisco researchers working on bringing post-quantum cryptography to the entire Internet

Owen Lystrup
Jun 10, 2019 · 7 min read
Image for post
Image for post

A common saying about quantum computers is they have been 10 years away since the late ‘80s.

But the delivery predictions are starting to feel closer to reality today and many believe it’s actually now more like 2024. That belief is rooted in recent news of both landmark technological innovations, and the massive investments from governments, corporations, universities, research firms, and even startups. The ability to create a viable, general-use quantum computer now seems less eventual and more inevitable.

The potential in quantum computers is hard to even measure at this point. We know they will be good at polynomial calculations and much better at factoring large prime numbers than any computer that exists today, but the practical applications could bring about advances previously considered impossible. One of the most exciting things about the space is we don’t even know all the applications for a quantum computer yet. New drug therapies, far more accurate mapping of the earth, early disease detection, more accurate self-driving cars, safer flight travel, and even room-temperature superconductors are just a few examples of anticipated use cases.

Yet as the world’s leaders in physics and computer engineering are seemingly closer than ever to grasping the promise of quantum computing, it’s widely understood that the same powerful technology will also put encryption at risk.

The risk is extremely important, because today’s Internet relies very heavily on an ability to encrypt data to conduct business, message each other securely, document our lives and so on. A quantum computer, because it can so expertly factor very large numbers much better than a classical computer, could render obsolete many of the standard cryptographic algorithms we rely on to experience the Internet with an expectation of privacy.

If cryptography underpins practically everything we do on the Internet, how then do we continue to provide the same security and privacy in a post-quantum Internet?

A small group of top engineers, security experts, and cryptographers at Cisco have been researching and developing a solution for this very dilemma over the last couple of years. They announced a major step forward in their progress at Cisco Live! in San Diego today.

A Quantum Problem on a Global Scale

In March 2017, a Cisco principal engineer named Lionel Florit caught a short article in The Economist that laid out the quantum computing landscape and the possibilities and challenges involved.

One paragraph in particular struck Florit. It discussed the concept of quantum networks and the dire need for post-quantum security. The article sparked Florit’s interest in Quantum Key Distribution (QKD) which is a way of establishing shared secrets using the physical properties of photons. It was an interesting and novel solution for a large-scale challenge. Being the world’s leader in network technology and hardware, Cisco should play a role, Florit thought.

As stated earlier, with a powerful enough quantum computer, a bad actor or perhaps a nation-state attacker could break many of the standard encryption models behind practically all traffic on the Internet. Secure session keys could be particularly vulnerable.

Today’s key-exchange algorithms, like RSA, Diffie-Hellman, and others, rely very difficult mathematical problems such as prime factorization for their security. An encrypted message sent across the Internet today — an e-mail, a bank transaction, username and password login, etc. — is kept private by transmitting it in an encrypted form to its recipient who then decrypts the message or data using a public key. If we use the case of RSA as an example, to defeat the encryption, an attacker needs to solve the hard mathematical problem, factoring a very large number. It’s a lengthy “trial-and-error process,” even for the most powerful computers.

A powerful enough quantum computer, however, could shorten the factoring process enough to make it viable for a bad actor to create a matching cryptography key and decrypt practically any “secure” communication or transaction on the Internet. What would take a normal computer thousands of years to break, would take a quantum computer a handful of hours at most. This is true even if the transaction or record is captured in an encrypted state, and then decrypted at a later date — like an estimated 10 to 15 years from now when a powerful enough quantum computer becomes available.

Understanding this challenge, Florit decided to present the problem to his colleagues at Cisco and see if there was a viable market play that could use Cisco’s expertise. He was asked to put together a project to explore the possibilities, and Florit — whose background is in building networks and protocols for IoT devices, not security or cryptography — knew he would need help.

David McGrew then joined the project, along with cryptography expert Scott Fluhrer and engineering lead Amjad Inamdar, to provide cryptographic, security, and implementation expertise. McGrew is one of only a handful of veteran engineering fellows at Cisco. In his storied past, he helped design several cryptographic standards, like GCM and Secure RTP, that are widely used today. He also co-chaired the IRTF Crypto Forum Research Group, and is co-creator of a Cisco technology called ETA or encrypted traffic analytics — a machine learning and pattern detection model used to find malware inside encrypted traffic without needing to decrypt the traffic or conduct deep-packet inspections.

Florit’s original proposal was to explore Quantum Key Distribution solutions, a rather niche technology at the time. As mentioned above, QKD passes encryption keys using polarized photons and flying quantum bits (Qbits).

The Heisenberg’s Uncertainty Principle states that the mere act of observing a quantum entity, like a photon, will change its behavior. Therefore, if a bad actor were to try and spy on a secure quantum channel, it would immediately and unmistakably be detected when the encryption keys are validated. But it also comes with limitations. For example, QKD systems need a dedicated optical channel and are limited by the physical distance over which they can pass a key (usually about 50km or less).

After some exploration of the technology, McGrew and Florit wondered if there was a way to deliver quantum-safe encryption keys that could work on real network, versus short-range point-to-point connections. The eventual goal would be to scale the solution to a global Internet level. Continuing to work through the possibilities, the two came up with a novel approach.

Since the algorithms used to establish sessions keys are the most at-risk in a post-quantum world, they explored if there was a way to pass post-quantum secure encryption keys between parties, establish a post-quantum secure session, and then pass traffic along using existing algorithms that are already considered quantum-safe.

“If somebody is able to build a general-purpose quantum computer that can break RSA or elliptic cryptography, then [that somebody] could eavesdrop on every section on the Internet, because all the public key algorithms that we’re using on the Internet today are all vulnerable to a quantum computer,” McGrew said in an interview.

While we can’t fix the problem by just replacing everything that we’ve already built, he said, “a quantum computer can’t break every cryptographic algorithm. There are some that don’t need to be replaced…so a good way to solve the problem is to develop a way to use a layer of indirection right where I want to be able to bring in a post quantum secure key — except I’m going to bring it in so that I can use it in one of these standard algorithms.”

The Great Quantum Cryptography Race

NIST, the institute that defined the cryptography standards that are in widespread use, is working swiftly with its community of cryptographers and security experts to develop algorithms that would be secure in the post-quantum era. NIST began with 69 cryptography candidate models submitted over two rounds and announced just last month that the number has been whittled to 26. But even once the final candidates are completely vetted, tested, and approved, it is a very long process getting the entire Internet to adopt a new standard.

To Dave McGrew, this waiting period is precious time lost. “Are we really going to wait? Because we really have no idea when these standards will be optimal relative to quantum supremacy.” In other words, McGrew would rather develop a working fix sooner than later.

Image for post
Image for post
The router has a secure connection to a colocated key provider. It reaches out over that interface to get a key and a key identifier. The router includes that key in the key derivation process of the standard key exchange protocol, using post-quantum secure algorithms. It [then] sends the key identifier to its peer, and the peer uses the identifier to ask its key provider for the same key.

What McGrew, Florit and a handful of other Cisco engineers developed — which is still at this point a research project currently called Secure Key Import Protocol or SKIP — is a method similar to BYOB, only instead bring-your-own-key. A CIO chooses the preferred product for generating post-quantum keys, the keys are used to initiate a secure connection, and data is then tunneled using algorithms that already exist and are considered post-quantum secure, like AES-256 or SHA-512.

SKIP connects the customer’s choice of key provider via API and can be implemented into already existent networking gear like ISR routers running IOS-XE, and it will work with whatever post-quantum method the customer chooses. Be it quantum key distribution (QKD) or a lattice algorithm the solution, McGrew says, will work with all of the available mechanisms and even try new ones slated to come out in the future.

The interesting thing about this approach to exchanging keys is it will allow customers to integrate new post-quantum key exchange methods into existing Cisco networking gear. No need to rip out anything already installed. By using existing equipment and standards good enough for post-quantum use, CIOs could essentially create a post-quantum connection for all traffic with minimal effort and scale it to the global Internet.

To find out more about SKIP and how it works, watch a discussion between McGrew and Cisco EVP and General Manager David Goeckeler.

Be sure to follow David Goeckeler and Owen Lystrup on Medium and Twitter. And subscribe to David Goeckeler’s YouTube channel, which will have many more interesting tech talks coming soon.

Owen Lystrup

Written by

Writer, photographer, and creative producer for Cisco's security and networking business.

Shifted

Shifted

Technology as we know it has shifted. Cisco is reengineering networking for a new era of computing. Viewpoints expressed here do not necessarily represent Cisco or its opinion on any given topic.

Owen Lystrup

Written by

Writer, photographer, and creative producer for Cisco's security and networking business.

Shifted

Shifted

Technology as we know it has shifted. Cisco is reengineering networking for a new era of computing. Viewpoints expressed here do not necessarily represent Cisco or its opinion on any given topic.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store