Cryptography in the age of quantum computing

Codes and ciphers have been around since the time of the Greeks. As cryptography underpins much of the security behind financial systems, we examine its evolving uses, plus the possible future of the discipline in the age of quantum computing.

Cryptography in the age of quantum computing

Cryptography is all around us. Anyone withdrawing cash from an ATM or making a card purchase at point of sale has cryptography to thank for it – writes Joyrene Thomas, Payments Cards and Mobile.

Any business providing services online is indebted to some degree to developments in cryptography 40 years ago. Anyone sending an e-mail, using a mobile phone or updating their social media profile is benefiting from a revolution in telecommunications largely brought about by cryptography.

Modern-day cryptography draws on the strange, representational power of numbers. Numbers do not exist in the world, but help us make sense of and secure our world. Yet the mathematics at the heart of computer security is under threat from quantum mechanics, the study of how light particles behave at sub-atomic levels. We have never been more digitally connected or interconnected than at any time in our history. We’re wired and, as we move into the quantum realm, it’s about to get weird.

Cryptography Goes Public 

To understand the quantum and post-quantum future and the threats posed, it is necessary to review the principles of encryption, key exchange and digital signatures from cryptography past. Until the 1970s all ciphers were symmetric. They were decrypted with the same key that had been used to encrypt them in a simple reversal of the process. The whole trick of encryption was to keep the keys secure. As both the sender and recipient had to share a key, key exchange and management vulnerabilities were often easier to exploit than the encryption itself.

However two US west coast academics, Whitfield Diffie and Martin Hellman, began thinking about the problem in a different way. What if there were two keys and a message was encrypted with one and decrypted with the other? This would help overcome key distribution problems. When Hellman explained the idea to Horst Feistel at IBM, creator of the DES algorithm, the latter said it was absurd. It seemed counter-intuitive, yet this idea was the birth of asymmetric or public key cryptography.

This had wide-reaching implications for encrypting and signing messages. The sender of a message could encrypt it with the recipient’s public key. And the recipient could decrypt it with their private key, as the keys were different yet mathematically related. Similarly, to digitally sign a message as coming from them and only them, the sender could encrypt it using their private key. The recipient could decrypt it using the sender’s public key. Only this combination of private and public keys made the message readable.

The mathematics behind public key cryptography relies on modulo and prime numbers. Modulo is an operation that concerns remainders after division. A prime number is a whole number greater than one that can only be divided by one and itself. Three MIT mathematicians: Ron Rivest, Adi Shamir and Leonard Adleman used the special properties of primes in a one-way function to enable public key cryptography.

Whilst it is easy to multiply two random 100-digit prime numbers together, it is difficult to reverse the operation knowing only the product. This type of prime factorisation became better known by their initials, RSA. It is the basis for much secure electronic communication, yet it is not resistant to quantum computers. So how significant is this?

Practical Security  

Perfect secrecy can only be found with a one-time pad. As the name suggests, a fresh key is used each time to protect the message. Naturally, perfect secrecy comes with a trade-off around the key management overhead. Cryptographic systems need to balance cost, time and security as well as what is practical and feasible.

Moore’s Law is important in this context as computing power available at a given cost tends to double roughly every 18 months. A number of encryption techniques have been broken as computers have become more powerful. In 1998, 56-bit DES was cracked in 56 hours using a desktop computer. In 2008, scientists at Eindhoven University of Technology in the Netherlands cracked the McEliece encryption system in a week on a network of 200 computers.

In both cases, the security of the encryption can be increased by increasing key length. However, “it’s not just the size of the key, it’s the quality and type of algorithm as well,” explains Paul Meadowcroft, director in the cryptography function within Thales e-Security. There are also ad-hoc ways of boosting security. For example, there are only 10,000 4-digit PINs, so to increase security most card issuers limit the number of PIN tries to three.

When it comes to the security of cryptographic systems, organisations should ask themselves what they are trying to protect. And how much cover time they need. Generally, if the length of time an attacker would need for an exhaustive search of all the keys, i.e. a brute force attack, is shorter than the cover time required for the information, then the system is too weak. Cover time extends in both directions: into the future and from the future back into the past.

“There could be data that is protected with RSA public keys that has value in 50-70 years’ time. This could be collected and if sometime over that period a quantum computer does become industrialised, then it would be able to decrypt historical data,” says Meadowcroft. That is the danger of quantum computing. It is embryonic and unstable now but whoever succeeds in building the first computer could open the door to everything we know today.

From Bits To Qubits

To early 20th century physicists, ‘quantum’ came to mean the smallest indivisible piece. Quantum computing is computing with light as opposed to classical computing with electrons. At the level of the tiniest particle, intriguing things start to happen. This includes particles existing in a quantum superposition, namely being in two states simultaneously. If a classical computer is based on the idea of the bit, a quantum computer is based on the idea of the quantum bit or qubit.

“Classical computing is binary and based on 0 or 1. Every operation you go through has to be computed in either state. For a quantum computer, it can be in the state of 0 or 1 at the same time,” explains Andersen Cheng, CEO of cyber security firm Post-Quantum. “In terms of processing speed, you can do a lot of things in parallel, which can be millions of times quicker.”

Quantum computers could potentially render much contemporary cryptography defunct by brute-forcing the encryption. The current standard for symmetric key cryptography is AES which has been judged to be post-quantum secure by the National Institute of Standards and Technology (NIST). The same cannot be said for asymmetric public key cryptography, which relies on prime number factorisation — finding the two numbers that make up a product.

“This type of integer factorisation is almost what a quantum computer is designed to do — millions of tries at the same time. You don’t have to wait for one number to be recovered before you try the next. So that’s the danger,” says Cheng.

So, how can the quantum threat be countered? There are two main methods: quantum encryption and post-quantum encryption. The first relies on quantum key distribution (QKD) to enable secure communication. Because the key to encrypt and decrypt messages involves pairs of quantum-entangled particles, eavesdropping on the exchange has the effect of destroying the delicate quantum state. This flags the presence of an eavesdropper.

“You can detect the leak or the man-in-the-middle, but it will only tell you that someone is sucking your data out. It’s not going to cure it for you,” says Cheng. “A lot of people think QKD is the end of our worries. The answer is probably not.” This is where quantum-resistant encryption comes in.

Cryptography In The Post-Quantum Age

The standards-setting bodies have concluded that post-quantum solutions will probably not be as elegant as RSA, which does both the cryptographic encryption and signing. Organisations will need to compromise and adopt two schemes, depending on requirements. But how long has the industry got?

According to NIST, the question of when a large-scale quantum computer will be built is complicated and contentious. Estimates range from 10-20 years, the more bullish ones are 3-5 years. To that end and to help standardise post-quantum cryptography, NIST kicked off a public call for quantum-resistant public key cryptography algorithms, ending November 2017.

Standards will help guide the development of cryptographic systems and the certification procedures for these. They will also help with interoperability, which is critical to the functioning of large payment networks. However interoperability also has in-built inertia. It took around 15-20 years for the industry to move from a single to a triple-length DES key. Various terminals, back-end host systems and the hardware security module (HSM) infrastructure protecting this had to be upgraded. “There’s quite a lot of inertia in those systems that make it difficult to move up the key sizes and change algorithms,” says Meadowcroft.

Hence the importance of planning and preparation. “I’d advise people to do what we’re doing: keep abreast of the evolution of these new algorithms coming out of the standards bodies,” says  Meadowcroft. “And talk to their vendors to start to formulate a plan of how they are going to migrate when the time comes.”

“If you have data today that you are trying to protect with RSA-algorithms, and you need to keep it secure for many decades, then it’s not too early to start to thinking about quantum-resistant cryptography,” he advises. However the principles of practical security still apply. If an organisation wants to protect payment data for the length of time the transaction exists, namely milliseconds, then there is less need for quantum-resistant algorithms and less urgency to adopt them.

Good old-fashioned security principles also apply with regard to taking a layered approach. A lot of focus has been on the encryption itself to counter quantum computing threats. “No one tool is sufficient. This is why you need an end-to-end solution, which is made up of a cocktail of controls,” according to Cheng. These can be complementary, supplementary or even opposite controls, which act together or as fail-overs for one another.

You Ain’t Seen Nothing Yet

For as long as there have been code makers, there have been code breakers. The innovation arms race familiar in so many areas of the payments industry is also present in cryptography. Powerful computers and encryption are no longer the unique preserve of nation states and the military. And as technology is morally neutral, there is no guarantee that quantum computers will remain in the hands of the good guys. This only intensifies the pressure on standard-setters, governments, commercial entities and academics to continue their work around quantum-resistant techniques.

It is easy to think of cryptography as being about secrecy and encryption, which it is in part. Keeping information confidential is important. Yet so is ensuring its integrity and availability, plus having attribution and non-repudiation. Ensuring encryption is robust and fit-for-purpose is important. Yet so is ensuring that the implementation and key management — the generation, distribution, storage, usage, exchange and destruction of keys — is similarly robust and fit-for-purpose.

“When we were trying to raise capital a few years ago, I had one VC almost put the phone down on me, saying I was scaremongering. Everyone is keeping quiet now, because people have concluded that it is no longer a science problem, it’s an engineering problem.”  – Andersen Cheng, CEO, Post-Quantum

Although no-one knows for sure when the first quantum computer will be available, the quantum clock is ticking. It is akin to the Y2K problem but without a known deadline. As such it must be managed as any uncertainty within business: through preparation, planning and pragmatic controls.

Cryptography comes from kryptos, the Greek for ‘hidden’, but the future of the discipline will be debated increasingly openly. The public call for quantum-resistant public key algorithms and battle for encryption between law enforcement, Big Tech and civil liberties groups are just two examples of this. Cryptography sits on the overlap between information security, privacy, electronic commerce, public safety and national security. It is of our time and will be of our future.

The post Cryptography in the age of quantum computing appeared first on Payments Cards & Mobile.