Security (Evaluation Criteria)

Call for Proposals

4.A      Security

The security provided by a cryptographic scheme is the most important factor in the evaluation. Schemes will be judged on the following factors:

4.A.1 Applications of Public-Key Cryptography NIST intends to standardize post-quantum alternatives to its existing standards for digital signatures (FIPS 186) and key establishment (SP 800-56A, SP 800-56B). These standards are used in a wide variety of Internet protocols, such as TLS, SSH, IKE, IPsec, and DNSSEC. Schemes will be evaluated by the security they provide in these applications, and in additional applications that may be brought up by NIST or the public during the evaluation process. Claimed applications will be evaluated for their practical importance if this evaluation is necessary for deciding which algorithms to standardize.

4.A.2 Security Definition for Encryption/Key-Establishment
NIST intends to standardize one or more schemes that enable “semantically secure” encryption or key encapsulation with respect to adaptive chosen ciphertext attack, for general use. This property is generally denoted IND-CCA2 security in academic literature.

The above security definition should be taken as a statement of what NIST will consider to be a relevant attack. Submitted KEM and encryption schemes will be evaluated based on how well they appear to provide this property, when used as specified by the submitter. Submitters are not required to provide a proof of security, although such proofs will be considered if they are available.

For the purpose of estimating security strengths, it may be assumed that the attacker has access to the decryptions of no more than 2⁶⁴ chosen ciphertexts; however, attacks involving more ciphertexts may also be considered. Additionally, it should be noted that NIST is primarily concerned with attacks that use classical (rather than quantum) queries to the decryption oracle or other private-key functionality. 

4.A.3 Security Definition for Ephemeral-Only Encryption/Key-Establishment   While chosen ciphertext security is necessary for many existing applications (for example, nominally ephemeral key exchange protocols that allow key caching), it is possible to implement a purely ephemeral key exchange protocol in such a way that only passive security is required from the encryption or KEM primitive.

For these applications, NIST will consider standardizing an encryption or KEM scheme which provides semantic security with respect to chosen plaintext attack. This property is generally denoted IND-CPA security in academic literature.

The above security definition should be taken as a statement of what NIST will consider to be a relevant attack. Submitted KEM and encryption schemes will be evaluated based on how well they appear to provide this property, when used as specified by the submitter. Submitters are not required to provide a proof of security, although such proofs will be considered if they are available. Any security vulnerabilities that result from re-using a key should be fully explained.

4.A.4 Security Definition for Digital Signatures NIST intends to standardize one or more schemes that enable existentially unforgeable digital signatures with respect to an adaptive chosen message attack. (This property is generally denoted EUF-CMA security in academic literature.)

The above security definition should be taken as a statement of what NIST will consider to be a relevant attack. Submitted algorithms for digital signatures will be evaluated based on how well they appear to provide this property when used as specified by the submitter. Submitters are not required to provide a proof of security, although such proofs will be considered if they are available.

For the purpose of estimating security strengths, it may be assumed that the attacker has access to signatures for no more than 2⁶⁴ chosen messages; however, attacks involving more messages may also be considered. Additionally, it should be noted that NIST is primarily concerned with attacks that use classical (rather than quantum) queries to the signing oracle. 

4.A.5 Security Strength Categories NIST anticipates that there will be significant uncertainties in estimating the security strengths of these post-quantum cryptosystems. These uncertainties come from two sources: first, the possibility that new quantum algorithms will be discovered, leading to new cryptanalytic attacks; and second, our limited ability to predict the performance characteristics of future quantum computers, such as their cost, speed and memory size.

In order to address these uncertainties, NIST proposes the following approach. Instead of defining the strength of a submitted algorithm using precise estimates of the number of “bits of security,” NIST will define a collection of broad security strength categories. Each category will be defined by a comparatively easy-to-analyze reference primitive, whose security will serve as a floor for a wide variety of metrics that NIST deems potentially relevant to practical security. A given cryptosystem may be instantiated using different parameter sets in order to fit into different categories. The goals of this classification are:

1. To facilitate meaningful performance comparisons between the submitted algorithms, by ensuring, insofar as possible, that the parameter sets being compared provide comparable security.
2. To allow NIST to make prudent future decisions regarding when to transition to longer keys.
3. To help submitters make consistent and sensible choices regarding what symmetric primitives to use in padding mechanisms or other components of their schemes requiring symmetric cryptography.
4. To better understand the security/performance tradeoffs involved in a given design approach.

In accordance with the second and third goals above, NIST will base its classification on the range of security strengths offered by the existing NIST standards in symmetric cryptography, which NIST expects to offer significant resistance to quantum cryptanalysis. In particular, NIST will define a separate category for each of the following security requirements (listed in order of increasing strength²):

1. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 128-bit key (e.g. AES128)
2. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for collision search on a 256-bit hash function (e.g. SHA256/ SHA3-256)
3. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 192-bit key (e.g. AES192)
4. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for collision search on a 384-bit hash function (e.g. SHA384/ SHA3-384)
5. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 256-bit key (e.g. AES 256)

Here, computational resources may be measured using a variety of different metrics (e.g., number of classical elementary operations, quantum circuit size, etc.). In order for a cryptosystem to satisfy one of the above security requirements, any attack must require computational resources comparable to or greater than the stated threshold, with respect to all metrics that NIST deems to be potentially relevant to practical security.

NIST intends to consider a variety of possible metrics, reflecting different predictions about the future development of quantum and classical computing technology. NIST will also consider input from the cryptographic community regarding this question.

As preliminary guidance to submitters, NIST suggests an approach where quantum attacks are restricted to a fixed running time, or circuit depth. Call this parameter MAXDEPTH. This restriction is motivated by the difficulty of running extremely long serial computations. Plausible values for MAXDEPTH range from 2⁴⁰ logical gates (the approximate number of gates that presently envisioned quantum computing architectures are expected to serially perform in a year³) through 2⁶⁴ logical gates (the approximate number of gates that current classical computing architectures can perform serially in a decade), to no more than 2⁹⁶ logical gates (the approximate number of gates that atomic scale qubits with speed of light propagation times could perform in a millennium).

The complexity of quantum attacks can then be measured in terms of circuit size. These numbers can be compared to the resources required to break AES and SHA3. At the present time, NIST would give the following estimates for the classical and quantum gate counts for the optimal key recovery and collision attacks on AES and SHA3, respectively, where circuit depth is limited to MAXDEPTH^{4, 5}:

It is worth noting that the security categories based on these reference primitives provide substantially more quantum security than a naïve analysis might suggest. For example, categories 1, 3 and 5 are defined in terms of block ciphers, which can be broken using Grover’s algorithm, with a quadratic quantum speedup. But Grover’s algorithm requires a long-running serial computation, which is difficult to implement in practice. In a realistic attack, one has to run many smaller instances of the algorithm in parallel, which makes the quantum speedup less dramati.⁶

Finally, for attacks that use a combination of classical and quantum computation, one may use a cost metric that rates logical quantum gates as being several orders of magnitude more expensive than classical gates. Presently envisioned quantum computing architectures typically indicate that the cost per quantum gate could be billions or trillions of times the cost per classical gate. However, especially when considering algorithms claiming a high security strength (e.g. equivalent to AES256 or SHA384), it is likely prudent to consider the possibility that this disparity will narrow significantly or even be eliminated.

NIST asks submitters to provide a preliminary classification, according to the above categories, for all parameter sets that they intend to be considered for standardization. All submitters are advised to be somewhat conservative in their preliminary classifications, but submitters of algorithms where the complexity of the best known attack has recently decreased significantly, or is otherwise poorly understood, should be especially conservative.

NIST will not require submitters to provide distinct parameter sets for all five security-strength categories. Submitted parameter sets meeting the requirements of a higher category will be automatically considered to meet the requirements of all lower categories. Submitters may also provide more than one parameter set in the same category, in order to demonstrate how parameters can be tuned to offer better performance or higher security margins.

NIST recommends that submitters primarily focus on parameters meeting the requirements for categories 1, 2 and/or 3, since these are likely to provide sufficient security for the foreseeable future. To hedge against future breakthroughs in cryptanalysis or computing technology, NIST also recommends that submitters provide at least one parameter set that provides a substantially higher level of security, above category 3. Submitters can try to meet the requirements of categories 4 or 5, or they can specify some other level of security that demonstrates the ability of their cryptosystem to scale up beyond category 3.

4.A.6 Additional Security Properties While the previously listed security definitions cover many of the attack scenarios that will be used in the evaluation of the submitted algorithms, there are several other properties that would be desirable:

One such property is perfect forward secrecy⁷. While this property can be obtained through the use of standard encryption and signature functionalities, the cost of doing so may be prohibitive in some cases. In particular, public-key encryption schemes with a slow key generation algorithm, such as RSA, are typically considered unsuitable for perfect forward secrecy. This is a case where there is significant interaction between the cost, and the practical security, of an algorithm.

Another case where security and performance interact is resistance to side-channel attacks. Schemes that can be made resistant to side-channel attack at minimal cost are more desirable than those whose performance is severely hampered by any attempt to resist side-channel attacks.  We further note that optimized implementations that address side-channel attacks (e.g., constant-time implementations) are more meaningful than those which do not.

A third desirable property is resistance to multi-key attacks. Ideally an attacker should not gain an advantage by attacking multiple keys at once, whether the attacker’s goal is to compromise a single key pair, or to compromise a large number of keys.

A final desirable, although ill-defined, property is resistance to misuse. Schemes should ideally not fail catastrophically due to isolated coding errors, random number generator malfunctions, nonce reuse, keypair reuse (for ephemeral-only encryption/key establishment) etc.

4.A.7 Other Consideration Factors As public-key cryptography tends to contain subtle mathematical structure, it is very important that the mathematical structure be well understood in order to have confidence in the security of a cryptosystem. To assess this, NIST will consider a variety of factors. All other things being equal, simple schemes tend to be better understood than complex ones. Likewise, schemes whose design principles can be related to an established body of relevant research tend to be better understood than schemes that are completely new, or schemes that were designed by repeatedly patching older schemes that were shown vulnerable to cryptanalysis.

NIST will also consider the clarity of the documentation of the scheme and the quality of the analysis provided by the submitter. Clear and thorough analysis will help to develop the quality and maturity of analysis by the wider community. NIST will also consider any security arguments or proofs provided by the submitter. While security proofs are generally based on unproven assumptions, they can often rule out common classes of attacks or relate the security of a new scheme to an older and better studied computational problem.

In addition to NIST’s own expectations for the scheme’s long-term security, NIST will also consider the judgment and opinions of the broader cryptographic community.

²Note that, barring some truly surprising technological development during the standardization process, NIST will assume that the five security strengths are correctly ordered in terms of practical security. (E.g., NIST will assume that a brute-force collision attack on SHA256 will be technologically feasible before a brute-force key search attack on AES192.)

³See [N. C. Jones, R. Van Meter, A. G. Fowler, P. L. McMahon, J. Kim, T. D. Ladd, and Y. Yamamoto, Layered Architecture for Quantum Computing, Phys. Rev. X 2, 031007 (2012)]  and [M. Mariantoni, Building a Superconducting Quantum Computer, Invited Talk PQCrypto 2014, October 2014 Waterloo, Canada. https://www.youtube.com/watch?v=wWHAs--HA1c (accessed 10/24/2016)]

⁴Quantum circuit sizes are based on the work in [M. Grassl, B. Langenberg, M. Roetteler, and R. Steinwandt, Applying Grover’s algorithm to AES: quantum resource estimates, in T. Takagi, editor, Post-Quantum Cryptography, Lect. Notes in Comput. Sci. vol. 9606, Springer, pp. 9–43 (2016)].

⁵NIST believes the above estimates are accurate for the majority of values of MAXDEPTH that are relevant to its security analysis, but the above estimates may understate the security of SHA for very small values of MAXDEPTH, and may understate the quantum security of AES for very large values of MAXDEPTH.

⁶See [C. Zalka, Grover’s quantum searching algorithm is optimal, Phys. Rev. A 60, 2746 (1999)]

⁷The term perfect forward secrecy is commonly used to denote a feature of key agreement protocols which gives assurances that past session keys will not be compromised even if the private key of the server is compromised.