Cryptographic Parameters and Bits of Security: Classical and Quantum

Did you ever wonder how the parameter size of cryptographic algorithms relates to their security strength? Or how the security strength changes with quantum computers? Or do you keep forgetting when the bits-of-security are equal to the parameter size, and when they are halved?

You’re in luck! Here are the tables:

Table 1: Taken from NIST’s “Recommendation for Key Management” (SP 800-57 Part 1, Section 5.6.1.1). You can find similar tables on keylength.com.

Table 2: Assembled by me.

My motivation for collecting this information and writing this post is two-fold:

1. To answer the “why”: Where do these numbers come from? You can find the NIST table quoted a lot around the internet. But I always missed a concise summary of why the parameter sizes and the security strengths relate in this way.
2. To cover quantum: All tables I found only contained the security strengths in the classical case.

Point 2 is already solved by Table 2 above. For the remainder of this post I will address point 1 and give an explanation of the “why”. That is, I will explain why Table 2 has these values.

This post is not meant to explain all areas in depth. Rather, it is intended as a quick, summarising overview that pulls all the concepts together in one place. It assumes prior knowledge, refreshing only the points that are important in this context.

THIS POST DOES NOT CONSTITUTE CRYPTOGRAPHIC ADVICE. DO NOT TRUST A RANDOM PERSON ON THE INTERNET. YOU SHOULD SEEK PROPER CRYPTOGRAPHIC COUNSEL INSTEAD.

Preliminaries

Let’s start with some background. We will need this when we discuss for each type of algorithm how its parameter sizes relate to its classical and quantum strength.

Representing Numbers

We represent integers \( \leq 2^n = N \) as bit strings of length \( n \). We use capital \( N \) for integers, and lower case \( n \) for bit string lengths.

Note that \( \frac{2^n}{2} = 2^{n-1} = \mathcal{O}(2^n) \). Also note that \( \sqrt{2^n} = 2^{n/2} \).

Parameter Size

The “parameter size” is what we can tune about an algorithm to achieve different security strengths.

In most cases the parameter size is the key size. But not always! For example, for unkeyed hash functions (such as SHA-256) the parameter size is the size of the output.

Security Strength: Bits of Security

We measure the “strength” of an algorithm in “bits of security”, or short “bits”. An algorithm has “\( n \) bits of security” if it takes \( \mathcal{O}(2^n) \) operations to break it.

Usually, an “operation” is equal to one algorithm invocation and one comparison. For example, one invocation of SHA-256 and one comparison of the output against a target value.

Ideally, an algorithm can only be “broken” by brute-forcing, i.e. by trying all possible values. For keys of length \( n \) there are \( 2^n \) many possible keys, so an average brute-force search succeeds after \( \frac{2^n}{2} \) attempts. But as noted above, this is still \( \mathcal{O}(2^n) \). So instead of “127 bits” we say “128 bits”. Thus you can read all the bit-of-security values in the tables above with a big-\( \mathcal{O} \) in mind.

Classical: Discrete Logarithm

The Discrete Logarithm Problem is that given two numbers \( a, b \), find a number \( x \) such that \( b^x = a \). That is, find \( x = \log_b a \). We work in a cyclic group \( G \) of order \( N \) (i.e. there are \( N \) group elements). For cryptography \( N \) is usually prime.

There exist classical algorithms such as Pollard’s rho that solve the DLP in time \( \mathcal{O}(\sqrt{N}) = \mathcal{O}(2^{n/2}) \).

Hence classically, for parameter size \( n \) bits we only get \( n/2 \) bits of security.

Quantum: Integer Factorisation and Discrete Logarithms – Shor’s Algorithm

Shor’s period finding algorithm can be adapted to solve both the Discrete Logarithm Problem and Integer Factorisation Problem. It is “efficient”, meaning that it runs in polynomial time.

Hence for quantum, for parameter size \( n \) bits we get \( \approx 0 \) bits of security.

Quantum: Brute-Force Search – Grover’s Algorithm

Grover’s algorithm speeds up unstructured search from \( \mathcal{O}(N) \) classically to \( \mathcal{O}(\sqrt{N}) \).

Hence for quantum, for parameter size \( n \) bits we only get \( n/2 \) bits of security.

Hashing: Pre-images, Collisions, and the Birthday Attack

For pre-image resistance, the problem is that given an output \( y \) to find an input \( x \) such that \( x = h(y) \). Both classically and quantum the best known approach is brute-force search.

For collision resistance, the problem is to find two arbitrary inputs \( x_1, x_2 \) such that \( h(x_1) = h(x_2) \). Classically, this can be solved with a birthday attack in time \( \mathcal{O}(\sqrt{N}) = \mathcal{O}(2^{n/2}) \). For quantum, there is a paper claiming to be able to find collisions in time \( \mathcal{O}(\sqrt[3]{N}) = \mathcal{O}(2^{n/3}) \). However, Daniel Bernstein vigorously disagrees, concluding that the best practical collision attack even with quantum is still in time \( \mathcal{O}(2^{n/2}) \).

Tying It All Together

With the above in mind, we obtain the following relations that describe how the security strength \( S \) varies with the parameter size \( n \).

• Symmetric crypto (AES, HMAC):
  • Random symmetric key, breakable by brute force search.
  • \( S = n \) classically.
  • \( S = n/2 \) quantum (Grover’s).
• Asymmetric crypto (RSA, DH, ECC):
  • Discrete Logarithm and Integer Factorisation.
  • \( S = n/2 \) classically (Pollard’s rho and others).
  • \( S \approx 0 \) quantum (Shor’s).
• Hashing:
  • Pre-image resistance:
    • \( S = n \) classically.
    • \( S = n/2 \) quantum (Grover’s).
  • Collision-resistance:
    • \( S = n/2 \) classically (Birthday attack).
    • \( S = n/2 \) OR \( S = n/3 \) quantum (Bernstein OR Brassard, Høyer, and Tapp).

Note that just like the value “128” in the security strength is an approximation, the \( = \) is also an approximation.

Also note that these relations and the values in Table 2 are upper bounds. They only represent the security strength under generic attacks. There can be algorithm-specific attacks. For example, SHA-1 has an output size of 160 bit, which would imply 80 bit security against generic collision attacks. However, the SHAttered attack estimates that it only needs \( \approx 2^{64} \) operations.

What Security Strength Should You Target?

For a long time, 128 bit was commonly recommended. However, the NSA’s latest guidance in its Commercial National Security Algorithm Suite is at least 192 bit (except for RSA-3072, which is 128 bit).

Conclusion

We started this post with concrete values: a table of common cryptographic algorithms, their parameter size, and their security strength in both the classical and the quantum setting.

We ended this post with the formal relations that relate the parameter size to the security strength.

Inbetween, we refreshed our knowledge to understand the why. We explained where these relations come from.

I hope this helps as a quick reference to look up the values, the relations, and the derivation of the relations.