January 4, 2022
In this position paper, the current ANSSI views on the so-called post-quantum cryptography transition are outlined. In particular, ANSSI recalls the context of the quantum threat and introduces a provisional transition agenda to mitigate this quantum threat with a progressive increase of assurance on the new post-quantum algorithms without introducing any vulnerability. The objective of this paper is twofold: providing directions to industrials developing security products and outlining the transition agenda in terms of security visas [3].
Quantum computers are based on physical principles that are fundamentally different from those underlying classical computing. At a large scale, they would be capable of performing certain tasks much faster than today’s computers.
While prototypes of small quantum computers already exist, building large scale re-programmable ones is still at a very upstream research stage. There are many lines of research in quantum physics for the creation of such quantum computers but none of them is certain to succeed. Though their potential benefits are not fully known, they could obviously be high. Thus, the industry, governments and academia around the world are devoting significant resources to research in quantum computing. For example, in 2021, the French government announced an investment of more than 1 billion € in quantum technologies, including quantum computing [7]. A complete survey on the status of quantum computer development can be found under reference [6].
The security of the majority of digital infrastructures relies on public key cryptography (PKC), a technology that enables secure communications between entities that do not share any pre-established secret. More precisely, PKC serves two main functionalities: protected channel establishment (key establishment) and authentication (digital signatures). Today, these techniques are essentially based on two mathematical problems dimensioned to be virtually impossible to solve with our current computing resources and mathematical knowledge: the factorization of large numbers and the discrete logarithm computation. For example, the well-known RSA public key algorithm relies on the factorization of large numbers.
These two fundamental problems will no longer be unsolvable if a large scale quantum computer is built and thus the security of currently deployed public key cryptography could potentially collapse. Indeed, in 1994, P. Shor introduced a quantum algorithm [14] able to solve these problems quite efficiently. This algorithm cannot be performed on classical computers but it could be performed on large scale ones, a.k.a. Cryptographically Relevant Quantum Computers (CRQCs) as introduced in the NCSC’s whitepaper on quantum-safe cryptography [11].
The prototypes of quantum computers that exist are presently far from the required scale of CRQCs and therefore they are currently not a threat to public key cryptography. Many research challenges in physics, engineering and computer science must be overcome before scaling up to large quantum computers able to solve the factorization and discrete logarithm problems on which the current PKC is based.
However, the threat of a “store now, decrypt later” attack cannot be ruled out, at least for very sensitive information, e.g. classified information. In this attack, an adversary stores today the data exchange corresponding to a secure channel establishment and the encrypted messages over such a channel, with the purpose of eventually decrypting these messages once a CRQC becomes available. Furthermore, the long term validity (needed in certain specific scenarios) of digital signatures may be compromised by potential future quantum attacks.
Symmetric cryptography, a different and complementary family of cryptographic algorithms, could also be targeted by potential large scale quantum computers. A generic quantum algorithm introduced by Grover in 1998 [10] quadratically speeds up the exhaustive search. This can be fully mitigated by adjusting the sizes of the hash outputs and keys (using 256 bits keys instead of 128 for the AES symmetric encryption mechanism for instance). Thus, the impact is far more limited than for public key cryptography.
Because of a “store now, decrypt later” attack outlined above, the quantum threat should be taken into account before the question of whether the development of a CRQC will ever become achievable in the future is cleared up. Thus, a profound change of today’s public key cryptography towards quantum-resistant algorithms should be globally initiated to anticipate a possible collapse of our current cryptographic infrastructure.
Even though protecting our current public key cryptography against this distant threat has a cost, researching alternative cryptographic solutions can be beneficial from another perspective. Indeed, beyond the quantum threat, cryptography is never infallible; weaknesses are found from time to time, even on cryptographic mechanisms implemented in classical computers. Thus, it is not possible to totally rule out a discovery of a potential weakness impacting the security of hardware and/or software and requiring replacement of algorithms. Nowadays, the public key cryptography used worldwide is close to a mono culture and would strongly benefit from the introduction of new alternative algorithms.
Quantum Key Distribution (QKD), sometimes called quantum cryptography, is a way of enabling secure communications without being vulnerable to classical and quantum computers by using so-called quantum channels. Nevertheless, this technique does not provide a complete functional equivalent to public key cryptography and offers limited applications due to the need of a dedicated communication infrastructure and without real routing capabilities. More information on the ANSSI position can be found under reference [4]. As such, except for niche applications for providing some extra physical security on top of algorithmic cryptography, it is not considered by ANSSI as a suitable countermeasure to mitigate the quantum threat.
Post-Quantum Cryptography (PQC) is a family of cryptographic algorithms including key establishment and digital signatures that ensures a conjectured (1) security even against an attacker equipped with quantum computers. Post-quantum algorithms can be executed on classical computers with classical communication channels and thus can be deployed in existing infrastructures, unlike QKD. Besides, these algorithms are not only for use after a CRQC is built, they can be deployed in anticipation.
For ANSSI, PQC represents the most promising avenue to thwart the quantum threat.
The international research effort on post-quantum cryptography accelerated in 2015 after NSA’s release advising to “shift to quantum resistant cryptography in the near future” [8]. In 2017, the National Institute of Standards and Technologies (NIST) started a standardization campaign to define standard post-quantum public key algorithms (key establishments and signatures). At the time of writing, this process is still ongoing [12] and currently at its third round. Standards are expected to be published within the next two to five years. Contrary to other standardization campaigns where there was only one finalist, the post-quantum campaign will end up with several standards for different applications.
This standardization process has acted as a catalyst allowing a strong involvement of the international cryptography research community and focusing the analysis efforts on a restricted number of candidate algorithms while preserving the diversity of the underlying problems. This process has also broadened the analysis to various implementation use cases like embedded components.
The different families of post-quantum public key candidate algorithms are defined by the mathematical structure on which they are built. Nowadays, post-quantum public key algorithms are mostly based upon:
While the mathematical problems were introduced in the last century, the PQC algorithms are relatively recent. They offer various compromises between key size, signatures or ciphertext size, computational complexity and security assurance. A technical survey of the algorithms and the underlying mathematical problems can be found in [9].
There is a high academic interest in France for this thematic. This is why the French community is actively participating to the design and security analysis of the primitives but also to their cryptanalysis. A national group comprising academics, industrials and ANSSI has been formed, called RISQ (2), and will publish a whitepaper in 2022 [13].
As the national cybersecurity authority in France, ANSSI has followed closely the progress in post-quantum cryptography. It publishes general recommendations on the selection of cryptographic algorithms in security products and delivers security labels for products meeting general security requirements. But, ANSSI is not a standardization agency, its role is not to develop cryptographic standards.
More precisely, ANSSI has a twofold role when it comes to the use of cryptographic algorithms: advisory and regulatory. On the one hand, it promotes the use of well-studied, state-of-the-art cryptographic algorithms by publishing national guidelines on cryptography [1] and by participating to the publication of European guidelines on the selection of cryptographic algorithm [15]. On the other hand, ANSSI supervises the evaluation and delivery of security labels, e.g. Common Criteria (CC) certificates. In the French certification scheme, each evaluation comprises specific cryptographic evaluation tasks according to the evaluation level. It is important to highlight that there is no closed list of cryptographic algorithms eligible in order for a product to obtain a security label. Generally, the use of cryptographic algorithms that are fitted with a formal standard status delivered by an international standardization body (e.g. ISO, ITU, IETF, ETSI etc.) is strongly recommended. However, a cryptographic algorithm supported by a strong record of scientific publications can be potentially judged sufficient to provide an adequate security assurance level. Conversely, there is no automatic and universal recognition of all algorithms that obtained a formal standard state from such organizations.
Beyond the NIST objective to derive standards, the past three rounds of the NIST standardization campaign provide a variety of algorithms along with security analysis. Although this new post-quantum toolbox may seem handy for developers, the maturity level of the post-quantum algorithms presented to the NIST process should not be overestimated. Many aspects lack cryptanalytical hindsight or are still research topics, e.g. analysis of the difficulty of the underlying problem in the classical and quantum computation models, dimensioning, integration of schemes in protocols and more importantly the design of secure implementations. This situation will probably last some time after the publication of NIST standards.
A hybrid mechanism (key establishment or signature) combines the computations of a recognized pre-quantum public key algorithm and an additional algorithm conjectured post-quantum secure. This makes the mechanism benefit both from the strong assurance on the resistance of the first algorithm against classical attackers and from the conjectured resistance of the second algorithm against quantum attackers. Certain hybrid protocols are in standardization processes like [16] for TLS 1.3 or [17] for IKEv2. More generally, for key establishment, one can perform both a pre-quantum and a post-quantum key establishment and then combine both results, e.g. using a Key Derivation Function (KDF). Alternatively, one may use for some specific applications a KDF on a pre-shared key and a shared key obtained from a pre-quantum scheme. For signature schemes, hybrid signatures can be achieved with the concatenation of signatures issued by a pre-quantum and a post-quantum scheme and the requirement that both signatures be valid in order for the hybrid signature to be valid.
Even though hybridation is a relatively simple construction, ANSSI emphasizes that the role of hybridation in the cryptographic security is crucial and will be mandatory for phases 1 and 2 presented in the sequel. In addition, the implementation security of the hybridation technique should be also taken in consideration.
Given that most post-quantum algorithms involve message sizes much larger than the current pre-quantum schemes, the extra performance cost of an hybrid scheme remains low in comparison with the cost of the underlying post-quantum scheme.
ANSSI believes that this is a reasonable price to pay for guaranteeing an additional pre-quantum security at least equivalent to the one provided by current pre-quantum standardized algorithms.
As detailed in the sequel, the deployment of hybrid PQC is not a mandatory feature as of today. However, ANSSI will encourage the initiation of progress towards cryptoagility as much as possible for future products. More precisely, cryptoagility is an innovation that consists in adding the possibility to update the cryptographic algorithms of security products without recalling them and redeploying new ones. The quantum threat makes cryptoagility particularly relevant, and beyond this threat, classical attacks may also evolve and make cryptographic mechanisms or key lengths obsolete.
In practice, cryptoagility also means that in addition to the possibility of patching, products could include an extra surface for allowing potential updates in order to react to upcoming cryptographic recommendations and standard updates. Even though updates of the cryptographic algorithms should be much less frequent than patches, the cryptoagility feature is non-trivial to implement due to the need for retro-compatibility and the potential requirement for additional security visas if the product is certified. However, as the motivation for cryptoagility is very relevant nowadays, ANSSI believes that cryptoagility features should be taken into account during the benefit/risk analysis of future products.
To support a gradual transition, ANSSI encourages the following 3-phase roadmap (see below for a detailed description):
Phase 1: mandatory pre-quantum security, optional PQC, no claimed quantum resistance. This phase corresponds to the current situation. The post-quantum security should not be a mandatory requirement but is considered as an optional “defense-in-depth”. As the standardization campaign is still ongoing, the idea of this phase is to enable the first post-quantum deployments with flexibility while preserving the pre-quantum security with hybrid mechanisms.
The two following conditions below should be met.
This phase should last until after NIST’s first standards are announced and it is planed to last until after 2025.
Phase 2. Mandatory pre-quantum security, optional PQC with claimed quantum resistance. In this second phase, all post-quantum PKC algorithms shall continue to be systematically included inside hybrid mechanisms (except for hash-based signatures whose hybridation is optional as presented in phase 1).
For this phase, the post-quantum part will be more than an defense-in-depth: the quantum resistance could be claimed as a feature. In that case, a post-quantum security assurance should be mandatory for both public key and symmetric mechanisms as integral part of the security analysis. By then, ANSSI will have identified criteria for acceptable post-quantum PKC algorithms depending on their associated post-quantum security assurance. Such selected algorithms may not exactly match NIST standards. For this phase, ANSSI will highly recommend the post-quantum transition for products claiming long-term security. In that sense, for certain types of security products claiming long-term security, post-quantum security could become a mandatory feature.
This phase should last until at least 2030.
Phase 3: Optional standalone PQC with claimed quantum resistance. ANSSI expects that after years of analysis, the security assurance level provided by post-quantum algorithms will be as high as today’s pre-quantum assurance level. Thus, the usage of some post-quantum schemes should be possible without hybridation.
Please note that the presented recommendations will potentially evolve depending on the global advances on post-quantum cryptography and on the progress of NIST standardization campaign. The estimated timeline of the roadmap could be advanced or slowed down accordingly.
The use of PQC will also impact the delivery of security visas. ANSSI will accompany this transition and adapt its evaluation procedures according to the roadmap described above. The general procedure [2] will be updated following the three phases as follows.
Therefore, the evaluation method for security products that do not use PQC stays unchanged. For products that use post-quantum defense-in-depth, the evaluation method for a security visa will be defined as follows :
In a nutshell, security visas will attest that pre-quantum security is evaluated and that the use of post-quantum defense-in-depth mechanisms do not have any negative impact. No formal judgement will be made on the quantum security offered by PQC.
As in phase 1, evaluation procedure for products that do not use post-quantum long-term security remains unchanged. For long-term security products that follow ANSSI recommendations and use hybridation with PQC, the evaluation method will include pre-quantum security analysis, hybridation and quantum resistance analysis. For the latter, the analysis should include both symmetric and asymmetric mechanisms and should comply with the official guidelines on quantum resistance that will be updated
by then.
This final transition phase strongly depends on the advances of research in post-quantum cryptography and quantum computing. The specific details of this phase will be adapted in the next decades.
Several governments have published similar position papers recommending to prepare the post-quantum transition. ANSSI’s views are similar to the BSI’s position [5] on many issues (e.g. necessary migration, hybridation, cryptoagility).
(1) for which no efficient quantum attack exists today.
(2) “Regroupement de l’industrie française pour la sécurité post-quantique”.
(3) This is nevertheless a non-standard algorithm choice compared to the use of current PKC standards. Thus, some analysis of the algorithm may have to be performed by ANSSI as part of an evaluation, and this may lead to an increase of the certification process duration.
(4) as defined by NIST in round 3 of the campaign.
(5) While few exceptions are expected in practice, at least for mainstream cryptography, an algorithm that is not a NIST standard, but that is demonstrably stronger that a NIST standard, could constitute such an exception. For example, a developer should be able to obtain a security visa for a product implementing FrodoKEM whether NIST decides that FrodoKEM will be one of the first PQC standards or not.
[1] ANSSI. Guide des mécanismes cryptographiques.
https://www.ssi.gouv.fr/uploads/2021/03/anssi-guide-mecanismes_crypto-2.04.pdf
[2] ANSSI. Modalités pour la réalisation des analyses cryptographiques.
https://www.ssi.gouv.fr/uploads/2014/11/anssi-cc-cry-p-01-modalites-pour-la-realisation-des-analyses-cryptographiques_v4.1.pdf
[3] ANSSI. Security visas.
https://www.ssi.gouv.fr/entreprise/visa-de-securite/
[4] ANSSI. Should quantum key distribution be used for secure communications?
https://www.ssi.gouv.fr/en/publication/should-quantum-key-distribution-be-used-for-secure-communications/
[5] BSI. Migration zu post-quanten-kryptografie.
https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Krypto/Post-Quanten-Kryptografie.pdf;jsessionid=4E25811453CDCA572EE4B949296E89EB.internet472?__blob=publicationFile&v=1
[6] BSI. Status of quantum computer development.
https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikationen/Studien/Quantencomputer/P283_QC_Studie-V_1_2.pdf?__blob=publicationFile&v=1
[7] CNRS. La recherche française au cœur du plan quantique.
https://www.iledefrance-gif.cnrs.fr/fr/cnrsinfo/la-recherche-francaise-au-coeur-du-plan-quantique
[8] CNSS. CNSS advisory memorandum.
https://cryptome.org/2015/08/CNSS_Advisory_Memo_02-15.pdf, 2015
[9] ENISA. Post-quantum cryptography: Current state and quantum mitigation.
https://www.enisa.europa.eu/publications/post-quantum-cryptography-current-state-and-quantum-mitigation
[10] L. K. Grover. A framework for fast quantum mechanical algorithms. In 30th ACM STOC, pages 53–62. ACM Press, May 1998.
[11] NCSC. Preparing for quantum-safe cryptography.
https://www.ncsc.gov.uk/whitepaper/preparing-for-quantum-safe-cryptography
[12] NIST. Post-quantum cryptography (official standardization webpage).
https://csrc.nist.gov/projects/post-quantum-cryptography
[13] RISQ. To appear on risq official webpage.
https://risq.fr/
[14] P. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In 35th FOCS, pages 124–134. IEEE Computer Society Press, Nov. 1994.
[15] SOG-IS. Agreed cryptographic mechanisms.
https://www.sogis.eu/uk/supporting_doc_en.html
[16] D. Stebila, S. Fluhrer, and S. Gueron. Hybrid key exchange in tls 1.3 (draft IETF).
https://www.ietf.org/id/draft-ietf-tls-hybrid-design-03.html
[17] C. Tjhai, M. Tomlinson, G. Bartlett, S. Fluhrer, D. Van-Geest, O. Garcia-Morchon, and V. Smyslov. Multiple key exchanges in ikev2 (draft IETF).
https://datatracker.ietf.org/doc/draft-ietf-ipsecme-ikev2-multiple-ke/
180.88 Ko