Security equivalent and key length

Different key material lengths are often used when using cryptography, yet it is claimed that they have the same resistance. Aren't we counting apples and pears together?

Why is the security equivalent important? Is the key length a correct rating?

Cryptographic protection is based on encryption, and some key material is always needed for encryption. However, for symmetric ciphers, the key is very short and for asymmetric ciphers, the key is very long, apart from which the algorithm differs from the algorithm. So does it make sense to work with the key length at all? And how does the security of the algorithm be determined? For a start, before we go any further, it is necessary to quickly stop at the term key, because everyone understands something different under it.

Password and key

In a very simplified way, the password is input from the user, but the key is generated by the system. Generally based on user input. Unfortunately, a password like a user input is often predictable and not random enough. That's why reasonable programs have methods for distilling sufficiently random and unpredictable key material from a password. These functions are called the key derivation function (KDF). If your software doesn't use it or doesn't know it, stay alert and get your money back. In this article, we'll deal with the key material and its properties, and the password itself doesn't interest us all that much.

Key material for asymmetric ciphers

Asymmetrical ciphers have the biggest differences in key length. Asymmetrical, because the key is used asymmetrically. For example, a private key is designed for signing a document, and a public key (which is derived from a private key) allows all of its holders to verify the authenticity of the signature. But how come the RSA algorithm with a 3072b key and the ECDSA algorithm with a 256b key have the same security? I guess the question is whether there's some kind of betrayal. But there really isn't. Security can be compared quite simply, using the so-called security equivalent. And according to the said equivalent, all is well. The length of the keys, on the other hand, is used as a recommendation to avoid mistakes. Especially if someone doesn't know the security equivalent. So, how is it possible to calculate this equivalent?

What is the security equivalent

If I have a task, I can fairly accurately express its complexity. Whether I will need a thousand, a million, a billion operations or more. Since we are talking about the world of computers, I can express complexity as a power, for example, 2^20, 2^64, 2^128. So how many operations do I need to successfully solve the problem. And here's the important figure. The security equivalent of 128b means that I need 2^128 operations. And the number 2^128 can be expressed as a 128b number. So it's not appropriate to calculate the length of the key, but the complexity. And complexity is nothing else than the difficulty of solving the problem. At the same time, such a statement of complexity can be used as a universal translation of the ability to protect symmetric and asymmetric algorithms, hashes and, under certain conditions, passwords. The truth is that in the case of passwords, this is already an extreme interpretation of the security equivalent.

Security equivalent for RSA algorithm

The RSA algorithm is currently (2024) still used for the purposes of digital signature and key agreement. Its security provides the difficulty of factoring large numbers. In translation, this means a way to find two primes whose mutual multiplication produces this large number. Currently, the most effective method on classical computers is the so-called General Number Field Sieve (GNFS), on quantum computers the Shorr algorithm (based on QFT - Quantum Fourier Transformation). In the case of GNFS, our ability to attack this algorithm is very limited. Another disadvantage of the RSA algorithm is its sub-exponential complexity. In translation, this means that its resistance to attacks grows more slowly than the size of the key. Thanks to this, we can easily encounter technical limitations e.g. in popular protocols SSL/TLS, SSH, IPSec and others. For an idea of these dependencies, it is possible to provide a table for conversion to and from the security equivalent, which looks like this. An explanation of the impacts of quantum computers on asymmetric algorithms will be in another article.

Security equivalent for algorithms: Diffie-Hellman, ElGamal, Schnorr signature and DSA

These algorithms use the discrete logarithm problem in a body for protection. In this case, under a numerical body, we mean additive (i.e. single numbers are increased by a certain number each time, usually by 1 or 2, resulting in the remainder after division by a prime number) or multiplicative (single numbers are multiplied by a certain number, resulting in the remainder after division by a prime number) group. In simple terms, it's easy to raise some numbers in such a body, but practically impossible to square those numbers. To give you an idea, if we use modular multiplication (i.e. multiply by two numbers, multiply by divide by the chosen prime number, resulting in the remainder), we can easily write 5*8 mod 13 = 1. In this case, it's challenging, but still possible, to find which number multiplied by 5. But even if we have 5^8 mod 13, the situation is much worse. We're not able to figure out if it was 8, 10, 92 ... or maybe it was another number? In any case, it is still a primary school curriculum. To derive complexity, it is possible to use the so-called. Pollard's algorithm, which allows classical computers to attack this structure, on quantum computers it is again a modified Shore algorithm algorithm (uses QFT - Quantum Fourier Transformation). Interestingly, although the complexity of attacking these algorithms is significantly higher, is a key of similar size to RSA. However, this is due to the design of the key. It contains both a body definition and a generator (i.e. from what point starts with the calculation), so the public key. Because the information is quite large, a similar situation arises with the size of the resulting keys like the RSA. Therefore, for simplicity, the key size corresponding to the previous table is given. In reality, however, the width of secret key is important. An explanation of the impacts of quantum computers on asymmetric algorithms will be in another article.

Note: Because of other data that are part of the key, the resulting size of the key file is approximately equivalent to the size of the keys in RSA and therefore resistance is considered in a similar way.

Security equivalent for algorithms based on elite curves: ECDH, ECDSA, EdDSA

Algorithms based on elliptic curves use a similar principle as the algorithms Diffie-Hellman, ElGamal, Schnorr signature and DSA. Unlike them, however, they do not use general bodies, but bodies above elliptic curves. These add an additional layer of complexity. In fact, this is again an elementary school curriculum, only the mentioned body arises above an equation, usually a quadratic one. The other parts of the procedure are the same, i.e. again a division with the rest is used, a kind of "size limiter" of the body. In terms of the complexity of the attack, it is again possible to use the Pollard algorithm on a digital computer, the modified Shor algorithm on a quantum computer (it uses two QFTs - Quantum Fourier Transformation). Explanation of the effects of quantum computers on asymmetric algorithms will be in another article. Dependence on security is more complicated here, therefore only a simplified explanation is given. The key file is at the moment corresponding to the size of the key bit width, therefore the key file is significantly smaller.

Security equivalent of symmetric encryption algorithms

For symmetric encryption algorithms, the bit width of the key is used as the security equivalent. However, new attacks are emerging and each of these methods may result in weakening of existing resistance. An example of such weakening is the RC-4 algorithm, which, although it may have a 128b key, is breakable in a matter of seconds. And there are more examples.

Security equivalent of hash functions

For hash functions, the security equivalent is based on the birthday paradox, i.e. the probability of two identical texts with similar output. In simple terms, therefore, it can be argued that the security equivalent is roughly half the output width of the hash function, i.e. length/2. For quantum computers, this is a similar value, which should be length/3

Note: Explanation of the Birthday Paradox

Mathematicians are special people, able to entertain themselves at celebrations by calculating probabilities. For example, how many people could have the same birthday, hence the birthday paradox. But a mathematician is not looking for a specific example where someone will have the same birthday as the birthday boy, he is looking for a general case. This means that anyone at a celebration can have the same birthday as someone else. Surprisingly, only 23 people are needed for a 50% probability. These can be calculated using the following procedure.
Probability = (1 − variation (365, participants) / variation with repetition (365, participants))

Conclusion

Whatever cryptography is involved, it is advisable to deploy approximately the same security equivalent. Otherwise, the weakest algorithm may compromise the security of the more heavily protected, i.e. algorithms with a higher security equivalent. As for the stronger algorithms, on the other hand, they unnecessarily burn machine time on tasks that are unnecessarily demanding. At such a moment, computing can only become an overpriced direct-fuel. Currently, the corresponding security equivalent is 128b, but due to the risks posed by quantum computers, there are significant changes, for symmetric algorithms the requirement of a key width of 192b to 256b is being considered. Classical asymmetric algorithms are no longer sufficient and their substitution is being addressed.

Appendix:

List of problems of classical asymmetric cryptography and their explanation, taken from prof. Bill Buchannan asecurity [1]

Autor článku:

Jan Dušátko

Jan Dušátko has been working with computers and computer security for almost a quarter of a century. In the field of cryptography, he has cooperated with leading experts such as Vlastimil Klíma or Tomáš Rosa. Currently he works as a security consultant, his main focus is on topics related to cryptography, security, e-mail communication and Linux systems.