ClickySkip to main content
Need help with a cyber incident now?
Call 24/7: +31 88-2747800

The threat of the quantum computer

By 24 August 2023 Blog
dreiging van de quantumcomputer

It is like a race against an invisible opponent. You know he can overtake you. But you do not know when. How can you still win?

Host Lex Borger speaks with Pasqualle Verwoerdt and Tim Weenink this time. They work at Compumatica, a Dutch company that specializes in cryptography at the highest level, certified for restricted use by, among others, the EU and NATO. Together, they take a look at the danger of the quantum computer for cybersecurity.

“If a quantum computer comes along that can break the RSA algorithm, we all are in big trouble”, Pasqualle says. “The chances as of yet are small, but the impact would be enormous. Because the vast majority of everything used for encryption in IT is based on RSA.”

“So you cannot ignore the risk”, he concludes. “And the threat is even bigger: the elliptic curve is also under threat. Virtually all asymmetrical cryptography, is seen as not (post-)quantum-proof. This realization is slowly beginning to dawn on the CIOs and CISOs of the Netherlands.”

Shor and Grover

“Why is it that cryptography is so vulnerable to the quantum computer?” Lex asks. Tim explains: “The danger has been known since the ‘90s. Back then, Peter Shor invented a quantum algorithm that could efficiently solve problems that were very difficult for classical computers. E.g. factoring numbers into prime numbers, or calculating discrete logarithms in an efficient way.”

Lex: “And that is what the big asymmetrical encryption algorithms such as RSA depend on?”

Tim: “Exactly. These are calculations that the classical computers could take years or centuries to complete. But they could soon, with the quantum computer, suddenly be solved very easily.”

“When it comes to symmetrical encryption, the problem lies with Grover’s Algorithm, which can perform brute force attacks in an efficient manner. Because of that, a 128 bits key can soon be guessed as quickly as a 64 bits key right now.”

Lex concludes: “So logarithmically, you can break in more quickly. While we currently assume that adding 1 bit makes the key twice as strong.” Tim: “Right. That’s why the key for symmetrical encryption is often doubled nowadays, just to be sure, from 128 to 256 bits.”

Lex: “So symmetrical encryption has the most resistance against quantum computing’s progress?” Tim: “Yes, that is pretty much how it is viewed everywhere: it seems resistant to everything.”

China

“How strong does my quantum computer need to be then, to really pose a threat to current crypto?“ Lex asks. A good question, according to Pasqualle. “The big challenge is to keep enough quantum bits stable simultaneously. For decryption, some are thinking in the hundreds of thousands qubits, but it will probably be closer to a million.”

That is being worked on. “Europe is putting an enormous amount of money towards the quantum computer’s development, but America even more so. IBM is now right around four thousands qubits, or so. However, I have read that China, through its government, is investing ten times the amount of America in quantum computing.”

“How far the Chinese are? We don’t know. What we do know, is that such a development always progresses exponentially. It can suddenly go real fast. Maybe they can already break RSA-2048 in two or three years.”

Vulnerable data

Whether we are safe until then, Lex wants to know now. That isn’t really the case, according to Pasqualle. “All kinds of long-living data are already being intercepted and stored right now, among others by China. Think of personal information, intellectual property, state secrets, and so on.”

“The motto is ‘store now, decrypt later’. When they have appropriate quantum hardware later on, they can calmly take a look at everything.”

Postquantum-crypto

“But of course, the industry hasn’t stood still”, Lex argues, “because ‘post-quantum crypto algorithms’ are being developed, which, even with quantum computers, can’t be cracked. Isn’t NIST working on that: the American organization for technological standards? Just like at the time with the development of AES?”

Pasqualle: “Yes, NIST has been running a competition for a while now. That has yielded four finalists. But another year, maybe two, will pass before they have the final winners, which can actually be used. Next, you’ve got several years in which the various vendors have to implement those algorithms in their products without any teething problems.”

“And then companies still have to put them to use! Phasing out SHA-1 at a bank takes approximately twelve years. At regular companies that will maybe take between five and ten years.”

“So, with everything added – the competition, product adjustment and your own migration – you are far past 2030.”

AIVD (General Intelligence and Security Service)

Not a happy thought. But, there is a solution, Pasqualle explains. “The AIVD (General Intelligence and Security Service) just released a publication on the migration to post-quantum cryptography (PQC). For the short term, it is strongly advised to strengthen the asymmetrical encryption of your most important long-living data and critical connections with a layer of symmetrical encryption.”

“They consider that hybrid method very secure. And it is a solution that Compumatica has been able to provide for decades. And a solution that we, if necessary, could implement as soon as tomorrow.”

Lex hesitates: “There is of course a reason why asymmetrical encryption got so popular. The symmetrical approach requires you to declare a joint key together with each of your connections. If you really want that to be safe, everything needs to be done individually and must be checked. That is undoable.”

Pasqualle: “You’re right. Our solution therefore focuses on symmetrical encryption within and surrounding company networks. So everywhere you’ve got network connections, within your organization and to fixed locations outside of it, such as datacenters and partners. So encryption of data in transit. Transparently within a network, with no impact on performance.”

He continues: “At the same time, you still need asymmetrical encryption. We still use that daily for so many things … Think of authentication, or PKI. I don’t think we’ll ever lose that.”

Impact analysis

Choices will have to be made, says Pasqualle. “As a CISO, you usually begin with data classification and business impact analysis: what data do I have and how important is it? But subsequently you also must look at where it’s at and where it’s going. And last but not least: which algorithms do you use for encryption?”

“Once you have that all figured out, you can see what’s the most critical. From there it’s about the combination of the algorithm with the risk of the data and the connection.”

Cracked piece by piece

How does this story continue? With large uncertainties, Pasqualle says. “Various candidates in the NIST competition were eliminated because they were broken – sometimes as quick as in half a day. Despite experts believing in the solution. What are we going to do if the now remaining algorithms drop off one by one?”

Lex: “That’s a tough one. What we do know, from the past, is that twenty years ago there were very many crypto algorithms. One by one they were cracked. Often, improved versions then appeared. We’ve learned a lot from that. The effect is that you kind of end up with a ‘best of breed’.”

Pasqualle: “That’s what NIST has organized with that competition: it’s where some of the weaker brothers have fallen. But what guarantee do we have that the finalists don’t fail because of a new technology or something like that?”

That is something Lex can imagine. “Think of MD5 and SHA-1: they were seen as particularly strong. But then a smart Chinese researcher appeared who looked at the algorithms in a different way. Suddenly they turned out to be very vulnerable.”

Crypto-agile

What to do? Compumatica, of course, follows developments closely, Pasqualle declares. “We research these kinds of algorithms, so that we can shift quickly when time has come. And in time, of course, you want to be crypto-agile, thus being able to adjust your crypto based on enhanced insights.”

Conclusion

For now, we only seem to be sure of one thing: symmetrical encryption with a long key cannot be cracked. But not all symmetric solutions are really symmetrical: sharing the keys often takes place beforehand through an asymmetrical protocol.

For Compumatica, that risk is unacceptable, Tim states. “Therefore we always exchange the keys physically. Doing so, there is no communication over the internet between the end users.”

Pasqualle: “But we do make sure that the keys can regularly be renewed remotely. That’s how we stay post-quantum-crypto proof!”

Want to know more? For example, how Compumatica securely renews the keys? Listen to Tesorion Podcast 55

And do you want to stay up-to-date on the topics of quantum and crypto? Sign up at the new Quantum Gateway Foundation. Besides Compumatica, ABN Amro, Capgemini and the University of Amsterdam (UvA) are also involved in QGF. Visit https://quantumgateway.foundation