0
$\begingroup$

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

Improve this question
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Minor correction about RSA: actually, values of $e$ (and $d$) which do not work need not be rare; for one, even values never work (because $\phi(n)$ is always even). In addition, if $\phi(n)$ is a multiple of 3 (which will happen with probability 3/4 if $p$ and $q$ were not chosen with mod 3 in mind), then any $e$ which is a multiple of 3 will also not work. If $p$ and $q$ are chosen such that $p-1$ and $q-1$ has no small odd factors, then most odd values of $e$ and $d$ will work; however we generally don't use such criteria when selecting $p$, $q$ $\endgroup$ – poncho Jan 13 '15 at 19:29
  • $\begingroup$ Ah, you're right... I'll correct that. $\endgroup$ – tylo Jan 15 '15 at 13:45
0
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.