Security Level

From Crypto++ Wiki
Jump to navigation Jump to search

Cryptographic algorithms provide different 'strengths' of security, depending on the algorithm and the key size used. Security Levels are a formalization of 'strengths' of security, and are used to estimate a cipher's ability to protect data based upon an adversary's [estimated] potential capabilities over time. Put another way, a security level allows one to quantify "how strong" in statements such as "cryptographically strong algorithm". Maintaining security levels ensures a component meets minimum security requirements, and helps achieve the overall system security.

An algorithm's security level is based on the best known attack on the algorithm. It is the motivation for the "cryptographic arms race" metaphore: as attacks advance, so does the algorithm or its key. The best known attack against integer factorization (ie, RSA moduli) is number field sieveing, while the best known attack on AES is paramount to guessing (some hand waiving and not considering reduced round attacks). Attacks against a DSA signature have two instance problems: the first is logarithms in the multiplicative group [math]\displaystyle{ Z_p }[/math], for which the index-calculus method applies. The second is due to Schorr and is the discrete logarithm problem in the cyclic subgroup [math]\displaystyle{ q }[/math], where current methods run in square root time.

NIST's official recommendations can be found in SP800-57, Part 1, Recommendation for Key Management, Section 5.6.1. SP800-131, Recommendation for the Transitioning of Cryptographic Algorithms and Key Lengths summarizes the information found in SP800-56 and SP800-57. Finally, ECRYPT2 Yearly Report on Algorithms and Keysizes (2010) might also be of interest.

Security levels do not change when using Multiple Encryption, or encrypting the output of the first cipher with a second cipher.

Comparable Algorithm Strengths

The table below was taken from SP800-57, Recommendation for Key Management, Section 5.6.1. In the table below, 2TDEA is 2-key triple-DES; and 3TDEA is 3-key triple-DES and sometimes referred to as just triple DES. Triple DES is specified in SP800-67, Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher. The yellow and green highlights are explained in the NIST Recommendations section.

In the table below, FF is finite field, IF is integer factorization, EC is elliptic curve. 112-bits is shaded because NIST allows 112-bits of security, but many cryptographers and organizations recommend 128-bits of security.

Security Bits Symmetric Key FF IF EC
Table 1: Comparable Algorithm Strengths
80 2TDEA† L=1024, N=160 k=1024 f=160-223
112 3TDEA† L=2048, N=224 k=2048 f=224-255
128 AES L=3072, N=256 k=3072 f=256-383
192 AES L=7680, N=384 k=7680 f=384-511
256 AES L=15360, N=511 k=15360 f=512+

† DES was deprecated in 2003

Security Bits

Security Bits estimate the computational steps or operations (not machine instructions) required to find a solution to the problem in the problem's domain (FF, IF, or EC). For example, if someone says, 'My system uses 1024 Diffie Hellman", they are really stating their system has a security level of 80 bits (and because its Diffie Hellman, the problem domain is finite field). It will take a computer, on average, approximately 280 operations to find a solution (think Big-Oh notation). To break Diffie-Hellman via classical discrete logarithms, a number of methods could be employed: Index calculus, modified Pollard's rho, or Baby-step giant-step to name a few.

Symmetric Key

Symmetric Key is a block cipher algorithm that offers an equivalent strength. Though DES and AES are listed, any non-wounded or non-broken block cipher can be used. For example, European and international users might want to use Cameilla rather than AES since Cameilla is NESSIE and ISO approved. Note that an appropriate mode (block cipher mode of operation) must also be chosen.

Finite Field

FF is finite field cryptography, sometimes referred to as the discrete log problem (DLP), and examples include Diffie-Hellman, ElGamal, and DSA (one of the three signature schemes specified in the Digital Signature Standard (DSS)). L is the size of the field, N is the size of the subgroup.

Integer Factorization

IF is integer factorization and is the underlying problem of RSA and Rabin-Williams.

Elliptic Curves

EC is elliptical curve cryptography.

Security Level Selection

When selecting a security level, the basic assumption is that there exists some data that must be protected for X years. After X years, the data is no longer valuable and can be deleted, stored in the plain text, or even suffer a brute force recovery by the adversary.

Computing power is an estimate of computer's ability to process data. It is often estimated in MIPS-years and states the number of instructions that can be performed in one years. In the late 1990s, the estimate to factor a RSA-512 modulus was 3 x 104 MIPS years.

Given that we know current computing power, we must estimate the change in computing power from now until X years have elapsed. This is not too difficult as the trend tends to follow Moore's law (processing power doubles every 18 months).

The final adversarial number (which we probably don't know) is the size of the adversary's computation farm. The size of the farm times the expected computing power in X years provides us with an estimate of the MIPS years available to the attacker.

Finally, we need to determine the cost of a single operation or iteration in the attack algorithm (the single operation will be repeated many times). Some are suprised to learn that addition of two points over an elliptic curve is computationally more expensive than encrypting a block of data using a symmentric ciher. Each operation or iteration consumes a small bit of the MIPS years available to the attacker.

Theoretical Process

The selection process is fairly straight forward and detailed below. Once we estimate the adversary's capabilities, add a margin of safety, and then select an algorithm which exceeds the estimate. For a dated academic analysis applied to RSA moduli, see Security Estimates for 512-bit RSA by M. J. B. Robshaw.

When selecting numbers, be conservative, which means err on the high side. For example, assume that the adversary is a well funded government or corporation, the NSA, or a network based exercise in distributed computing. Keep in mind that algorithmic improvements can come at anytime, and could cause significant reductions in security.

  • Estimate the adversary's capabilities
    • Big number, MIPS years
  • Calculate the cost of an opeartion required for the attack algorithm
    • Small number, operations per second
  • Divide Capabilities by Operations/sec
  • Add a margin of safety
    • Algorithmic improvements
  • Select components that meet or exceed the calculated requirement

As a concrete (but but contrived) example, suppose that the computing power available in the adversary's farm is [estimated at] 260. Further, suppose we want to protect our data for 5 years. We also want a safety of 15 bits for possible algorithmic improvements. At this point, we need at least 75 bits of security. If we over state Moore's law such that computing power doubles every year (rather than 18 months), we have a 32 (25) fold increase in five years. So we need algorithms which provides about 80 bits of security.

In this example, all components would need to provide a minimum security level of 80 bits. Since its 2011 (or beyond), 80 bits is no longer recommended - we would need at least 112 bits of security. So we could use 3-key DES, 2048 bit Diffie Hellman for key exchange, SHA-224, etc. DES has been deprecated (even though 3DES is still viable) and AES-128 is readily available, so AES-128 and SHA-256 would be used.

If you are the type of person who wants both socks to match, then we are not finished. Since we are now using AES-128, which has an approximate security level of 128 bits, we need to use an equally secure Diffie Hellman field. If we don't use an equally secure DH field, the attacker can gain access to the AES-128 key by breaking the weaker key exchange subsystem. That means DH-1024 is out, and DH-3072 is in.

With AES-128 and DH-3072, components have a consistent security level such that an attacker cannot gain a foot hold through a weak component.

Applied Process

In the real world, the sales team makes promises that the engineering team must fulfill. If the suite's sales literature states AES-256, all components must meet or exceed a security level of 256 bits.

NIST Recommendations

Though in draft status, NIST recommended security levels can be found in SP800-131, Recommendation for the Transitioning of Cryptographic Algorithms and Key Lengths. Fortunately, SP800-131 refers to other applicable documents:

The appropriate security strength to be used depends on the sensitivity of the data being protected, and needs to be determined by the owner of that data (e.g., a person or an organization). For the Federal government, a minimum security strength of 80 bits is recommended in 2010; a minimum security strength of 112 bits is strongly recommended, beginning in 2011 (see [SP800-57]). However, with the acceptance of a certain amount of risk, the minimum of 80 bits of security strength may be used until the end of 2013. Based on the latest understanding of the state-of-the-art for breaking the cryptographic algorithms, given particular key lengths, the transition to the 112-bit security strength shall be accomplished by 2014, except where specifically indicated. See Appendix A for an explanation...

Dissenting Opinions

Not everyone agrees with the NSA/NIST assessment of security levels. For example, Lenstra, et.al. claim a 1024 bit RSA modulus is sufficient (with a small amount of risk) until 2014; and a 160 bit ECC curve will provide adequate protection until 2020. See On the Security of 1024-bit RSA and 160-bit Elliptic Curve Cryptography. Also see Cryptographic Numerology - our number is up at Financial Cryptography and Peter Gutmann and Ian Grigg's The Curse of Cryptographic Numerology.

US Bureau of Industry and Security

While NIST recommends or requires a security level of 128 bits for federal systems, the US Bureau of Industry and Security considers key lengths above 64 bits too strong for uncontrolled export from the US (or a program residing on a server residing in the US). See Review of Mass Market Encryption Commodities and Software Employing Symmetric Keys Greater than 64-bits under ECCNs.

References

Retrieved from "https://www.cryptopp.com/w/index.php?title=Security_Level&oldid=28900"