Comparison among algorithm based on key length

Question

Some months ago I found in some paper that we cannot compare symmetric algorithm with asymmetric algorithm based on the key length and more important we cannot compare asymmetric algorithm using only the key length, while a comparison of only symmetric algorithm in this term is reasonable... I explained it basing on the fact that:

in symmetric encryption algorithm the key length identifies the number of attempts necessary to decrypt the communication in both way, while in asymmetric encryption we are not sure that for a key of n bits, we will use all the possible numbers, so using ONLY the key length as a term of comparison is not sufficient, we could have key of 300 billion of bits but available only 2...

My question so is: is it true that all the possible symmetric algorithm uses all the possible numbers of n bits as possible keys or among these there are some of that not usable?

Thanks

Answer 1

Usually we only consider those keys, we can actually use. There is no restriction about the bits in a symmetric key, you can use all of them. For asymmetric encryption schemes, both keys need to fulfill some constraints to actually work. For example:

In RSA, $e$ has to be chosen coprime to $\phi(n)$, and you need $ed=1 $ mod $\phi(n)$0. What does it mean? Yes, there are certain values of $e$ (and $d$) which do not work.

edit: Even numbers never work, because $\phi(n)= (p-1)(q-1)$ is always divisible by 4. Other than that, the fastest way is to pick a random odd number for $e$, and check if it is coprime to $\phi(n)$.

What the reason is, that we can not blindly compare bit sizes of keys, is that attacks on symmetric and asymmetric encryption schemes are fundamentally different. It is a bit like comparing apples and oranges. So a 200 bit symmetric key is just something different than a 200 bit asymmetric key.

However, there are heuristics (not proven) to compare the strengths of these keys. For example NIST provides information about that here.

A very good read is Universal security; from bits and mips to pools, lakes -- and beyond, which tries to accommodate the the irritating scale of bits in a humorous way.

Answer 2

A symmetric key is basically a random blob, the whole 2^n space is valid and thus has to be searched.

Answer 3

Tylo is correct that the keyspace size is not necessarily dictated by the number of bits in the key for an asymmetric algorithm. RSA is a prime example (pun intended).

However, the problem is more fundamental: the best-known algorithm for breaking symmetric cryptography is usually brute-force, or at least, something with a negligible speedup over it; for asymmetric algorithms, though, the nature of the one-way function usually permits algorithms with significant speedups over brute-force.

Take ECC for example. For an n-bit key, the keyspace will be n bits large, but the Pollard-Rho algorithm allows searching it in O(2^(n/2)), giving an effective security of n/2 bits.

Answer 4

As already answered there are mathematical reasons why public-key (aysmmetric) algorithms must have strength less than their key size, often dramatically so: RSA or (non-EC) DSA/DH requires about 3000 bits size for 128 bit strength. For secret-key (symmetric) algorithms we can have strength equal to the key size, or colloquially "use all the bits", and usually do, but it isn't required.

An important counterexample is DES or to be pedantic DEA. Back in the 1970s when it was designed ciphers were implemented in hardware mostly as discrete electronic circuits, where it was quite possible for one bit to fail without affecting others, and additional circuits to check for such faults were needed when you wanted consistent results, which you certainly do for practical cryptography. Thus the DES designers chose a key format with 56 bits actually used as the key plus 8 parity bits to check for faults, stored or transmitted together as 64 bits. In addition the design of DEA produces a "complementation" property which reduces a bruteforce attack by one bit.

Original DES/DEA is now obsolete, because advances in hardware have made it brute-forceable since about 2000, but triple-DES (again pedantically triple-DEA or TDEA) is still used. It has a key conventionally (generated and) stored as 192 bits, of which it uses only 168 -- but because of the generic meet-in-the-middle attack it has strength of only 112. See

• Why is triple-DES using three different keys vulnerable to a meet-in-the-middle-attack?
• Why is Triple DES not vulnerable to meet in the middle attacks? (answer: it is)