The World of Quantum Computing

What Are the Threats of Quantum Computing?

In the previous blogs we have briefly touched upon how resistant symmetric and asymmetric cryptography are against quantum attacks. Here we discuss the topic in more depth.

Among the various other implications of a working quantum computer, the ones that are among the most important for the cryptographic landscape are attacks based on quantum algorithms like Shor’s and Grover’s. For now, these attacks are just theoretical, first devised in 1994 and 1996. With a quantum computer they could be implemented in practice.

Shor’s attack can be applied to asymmetric codes (public key cryptography), such as RSA and ECC. What it essentially does is it factorizes a given integer N in polynomial time. For a given key of length K, Shor’s algorithm needs 2K q-bits to break RSA, and 6K q-bits to break ECC. The important part is, Shor’s algorithm can break both the RSA and ECC codes. This is the reason why various PKI infrastructures are one of the security areas the most threatened by quantum attacks.

Grover’s algorithm, on the other hand, can be applied to symmetric cryptography, and to hash functions. The good news is, it does not break them completely, it “just” provides a quadratic speedup to known attacks and thus decreases the levels of security.

The tables below, prepared by Entrust, give us a good overview.

Cryptographic Algorithms

Type

Purpose

Impact from Quantum Computer

AES-256

Symmetric Key

Encryption

Secure

SHA-256, SHA-3

-

Hash function

Secure

RSA

Public key

Signature,

Key Establishment

Not Secure

ECDSA, ECDH

Public Key

Signature,
Key Exchange

Not Secure

DSA

Public Key

Signature,
Key Exchange

Not Secure


Crypto Scheme

Key Size

Effective Key Length/Security Level (in bits)

Classical Computing

Quantum Computing

RSA-1024

1024

80

0

RSA-2048

2048

112

0

ECC-256

256

128

0

ECC-384

384

256

0

AES-128

128

128

64

AES-256

256

256

128

How are we preparing?

A number of quantum-resistant ciphers has been developed in the past decade or so that could take the place of RSA or ECC. The National Institute of Standards and Technology (NIST) is currently in the process of evaluating several candidates for post-quantum standards covering public-key encryption and key-establishment, and digital signatures. On January 30th 2019 NIST has announced 26 candidates that made it into the 2nd round of the NIST PQC (Post Quantum Cryptography) Standardization Process. The selection process is expected to end between 2022 and 2024.

It therefore seems that we will still have to wait quite a few years for PQC standards, though we can’t predict when exactly quantum attacks will become a real threat. When the first working quantum computer is built, we can safely assume that there is a high probability it won’t immediately be public knowledge. It should therefore be our goal that by the time quantum computers become a reality, the present cryptography has already been substituted by PQC.

How long will the transition to PQC take?

In order to try to answer this question, let us look at other transitions of cryptographic algorithms we have faced in the past. ECC was, for example, defined in 1984 and became a NIST standard in 1994. Around 2005 NSA was pushing for a greater adoption of ECC in the governments and banking sector, but by 2016 it has partly dropped ECC because of low adoption rates. Another example is SHA-1. The depreciation of SHA-1was recommended five years before it went into effect, yet it still took about 13 years until widespread change. So all in all, the industry’s track record on adopting new algorithms is not that great.

At the same time, it is true that now we have more incentive to move quickly because of a greater potential threat. There are many things the companies can already do right now to make the coming transition to PQC easier – understanding what types of keys your systems use, where they are stored, which algorithms will have to be changed, how to achieve crypto agility,… Additionally, certain quantum-ready products are already available on the market.


---
Source: Nastja Cepak, PhD Cryptography, and CREAplus Cybersecurity Team.

News

Blog: Coexistence of Blockchain and HSM 

heroBlog post: HSM & Blockchain - Coexistence of Blockchain and HSM 

Utimaco CP5 HSM on the EU QSCD List

Utimaco CP5 HSM on the EU QSCD ListUtimaco CP5 hardware security module (HSM) is now listed also on the EU QSCD List.

Read more ...

Online Technical Training for Utimaco HSM

Training Ljubljana 20190725 110441sml2CREAplus, authorized Utimaco training partner, successfully delivered its first online hands-on technical training for Utimaco HSM, on 4 - 5 June 2020.

Read more ...