# Why are asymmetric cryptography keys more vulnerable to brute force attack than symmetric ones?

I came across this paper which says that

Asymmetric keys must be many times longer than keys in secret-cryptography in order to boast equivalent security. Keys in asymmetric cryptography are also more vulnerable to brute force attacks than in secret-key cryptography. There exist algorithms for public-key cryptography that allow attackers to crack private keys faster than a brute force method would require.

I would like to know:

1. What makes Asymmetric Cryptography keys more vulnerable to brute force attacks?
2. In which cases should Asymmetric Cryptography usage be avoided?
• Thank you all for the wonderful answers. IMHO, Cryptography exchange is the best stackexchange site. – Jay Oct 11 '16 at 12:24

For your first question: The main point here (at least that comes to mind) is that of how the key is made, used, and subsequently how it is attacked. Good symmetric ciphers are designed so that the best possible attack is brute force, i.e. simply trying with each possible key, which are typically random (or as good as). With a 128-bit key you have $2^{128}$ possible keys. Trying all of these takes a lot of time.

With an asymmetric cipher however, the private and public keys have a mathematical relation between them, and asymmetric ciphers are based on problems that are computationally hard to solve. An example of this is RSA, where the keys are based on two large (and secret) prime numbers, $p$ and $q$, then multiplied to create an even larger number, $n$. The result is then used for encryption and decryption (i will not go into further details of RSA here). To crack this system the most straight forward way is to find $p$ and $q$ by factoring $n$ (which is not secret).

Checking $2^{128}$ (or $2^{127}$ on average) symmetric keys with todays computational power is simply not possible within any conceivable time-frame. Factoring a 128-bit number however, takes about a second (depending on hardware and optimization). Thus, one needs larger keys for RSA than symmetric ciphers, e.g. 128-bit symmetric keys are typically approximated to equal 2048-bit RSA keys.

For your second question: Encryption and (even more so) decryption with asymmetric ciphers are often a lot more computationally intensive than a symmetric cipher (if i remember correctly is RSA typically about 1000 times slower than AES). This makes asymmetric ciphers impractical for encrypting large chunks of data. Subsequently, for encrypting e.g. internet traffic: asymmetric ciphers are typically used for securely exchanging keys that are used to encrypt/decrypt using a symmetric cipher.

EDIT: As rightly pointed out by @fgrieu the statement "128 to 256-bit symmetric keys are typically approximated to equal 2048 to 4196-bit asymmetric keys." is not correct, and comes from a writing-mistake on my part. The correct statement was supposed to be that 128-bit symmetric keys are typically approximated to equal 2048-bit RSA keys.

• @jay: The statement "128 to 256-bit symmetric keys are typically approximated to equal 2048 to 4196-bit asymmetric keys" in this answer is quite incorrect. No similar approximation applies for asymmetric cryptography in general. Example: for Ed25519, an increasingly used asymmetric scheme, 128-bit symmetric key security is believed obtained for 128-bit prIvate key and 256-bit public key. We can say that 128 to 256-bit symmetric keys are typically approximated to equal 2048 to 15360-bit RSA or DSA public key size in security. – fgrieu Oct 11 '16 at 6:45
• @jay I apologize for the slip-up! This was a typo resulting from writing and rewriting. I initially intended to say that 128-bit symmetric keys are approximated to equal 2048-bit RSA , with the typical recommendations for these being 128 to 256-bit for symmetric and 2048 to 4196-bit RSA. I will edit my answer to reflect this. And as fgrieu rightly say: ECC and the like operate with much smaller keys than the "classical" asymmetric schemes, which is one of the qualities making them desired in many use-cases over e.g. RSA. – henrheid Oct 11 '16 at 11:57

Putting this paper into context, it was "the culmination of the research efforts of nine dedicated undergraduate students in the Computing Research Topics course at Villanova University" and this particular paper was the only one related to cryptography (link). The welcome message states, the students spent four months in scientific research. This paper looks like a homework paper rather than a peer-reviewed scientific publication at a conference.

I just skipped over it, but the paper covers too much material in 6 pages. The content ranges over the topics of a full semester's class, which leads to many unconnected statements and lack of proper reasoning.

Question 1: This one has a correct statement in the homework, but you misunderstood: For asymmetric cryptography, more efficient attacks exist compared to brute force. Examples: Pohlig-Hellman and index calculus for discrete log in $$\mathbb{Z}_p$$, general number field sieve for factoring. That is why the keys have to be larger, so that the actual effort for an attack is somewhat comparable with symmetric ciphers. For any symmetric cipher, it is considered broken if there is an attack more efficient than brute force.

Question 2: As a rule of thumb, symmetric and asymmetric encryption serve different purposes, and you cannot use both interchangeably. You could not avoid using asymmetric cryptography if you need it. However, you can reduce the asymmetric crypto part and use symmetric encryption in addition. that's when you want to encrypt a large amount of data and encrypt it with the public key of someone. In that case, hybrid encryption is used, where you use the symmetric encryption for the actual data with a randomly chosen key, and then just encrypt that random key with the public key.

• For question 1 i think it is wrong to say that the "homework" is correct. It states that asymmetric keys are more vulnerable to brute force attacks than in secret-key cryptography. This statement is nonsense. The "homework" however correctly states There exist algorithms for public-key cryptography that allow attackers to crack private keys faster than a brute force method would require. – Guut Boy Oct 11 '16 at 8:09
• @GuutBoy you're right, I edited it. Besides that, the entire point of view on both symmetric and asymmetric crypto is quite flawed. – tylo Oct 11 '16 at 10:05
1. Asymmetric cryptography keys are NOT necessarily more vulnerable to brute force attack than their secret-key cryptography counterparts. Some asymmetric algorithms have short private keys (256-bit for Ed25519, targeting 128-bit security). Private key size for asymmetric crypto only needs to be at least as wide as secret key of symmetric crypto for equivalent security. For Ed25519 we could replace the private key by the SHA-256 of a 128-bit secret and public user ID; and every asymmetric algorithm (e.g. RSA) can have it's private key reduced down to the security level, by replacing the random source of the key pair generator by a PRNG seeded by the short key and user ID.
We however can state that:
• All known asymmetric cryptosystems have a public key significantly longer than the (secret) key of a symmetric cryptosystem of comparable security. But that's an apples-to-oranges comparison: in symmetric cryptosystems there is no equivalent to the public key (known to all including the adversary in asymmetric cryptography).
• When considering RSA (one asymmetric cryptosystem among many), indeed the public key is much longer than the key for symmetric crypto of comparable strength: we need like a 2048 to 3072-bit public modulus for a 128-bit symmetric security level; and while we can reduce the public key size by a factor of 2 or 3 compared to the public modulus (depending on if we want a security argument, or a lack of insecurity argument; see this), the ratio of sizes remains large, and growing with size. This is related to the fact that the security of RSA is no better than that of factoring the public modulus, and good factoring algorithms like GNFS have cost sub-exponential w.r.t. the size of the integer to factor.
• For other asymmetric cryptosystems, including the aforementioned Ed25519, the public key can be as little as twice as long as the key for symmetric crypto of comparable strength. In the case of Ed25519, the ratio 2 is related to the fact that the best algorithms to solve $$g^x=a$$ for integer $$x$$ in a general multiplicative group have cost growing about as $$x^{1/2}$$. I don't know any asymmetric cryptosystem beating that ratio, nor any strong argument that it can't be beaten.
2. Asymmetric cryptography is more complex and resource-hungry than good symmetric cryptography. Therefore asymmetric cryptography is best used together with symmetric cryptography, or avoided when not required.
• Asymmetric cryptography is required so that any of the following can be:
• some party can encrypt data without the secret allowing decryption;
• some party can verify authenticity of data without the secret allowing to sign that data as authentic;
• two parties (at least) can securely agree on a secret key for later use using symmetric cryptography, without a previous shared secret.
• Asymmetric cryptography is neither required nor useful when:
• asymmetric cryptography has just been used to agree on a secret key (see above);
• all communication is, by design, to a central trusted party that holds (or can recompute) all other party's secret keys, without this being deemed a drawback.
• This is a very good answer. Although I have 'Accepted' the first answer as I got what I wanted, fgrieu's answer explained lot of things very clearly. Somehow I felt it did not get the upvotes it deserved. Thank you. – Jay Oct 14 '16 at 15:37
• Substantive difference between the ‘128-bit security level’ of Ed25519 vs. the ‘128-bit security level’ of AES-128: On any of $n$ targets, best known attack costs expected ${\sim}2^{128}$ bit operations before breaking the first Ed25519 target, but ${\sim}2^{128}/n$ bit operations before breaking the first AES-128 target. I.e., ‘128-bit security level’ of Ed25519 is qualitatively different—and quantitatively stronger than that of AES-128. – Squeamish Ossifrage May 4 '18 at 6:09
• "•All known asymmetric cryptosystems have a public key significantly longer than the (secret) key of a symmetric cryptosystem of comparable security."; recent counterexamples (which postdate fgrieu's answer); GravitySphincs, Picnic (which are both signature algorithms based on symmetric operations) – poncho Nov 1 '19 at 15:14
• @poncho: per the paper's abstract: "Gravity-SPHINCS has shorter keys (32 and 64 bytes)". Seems to be a 256-bit public key for 128-bit security level, same as EdDSA. How is that a counterexample to my statement? I'm still scratching my head on Picnic, wondering if it's a signature algorithm or a proof o knowledge protocol. Also, the idea that the public key could be essentially the result of a hash bothers me. I need to get back to that old question of proving knowledge of a preimage of a SHA(-1/-2) hash without revealing it, which I never quite got. – fgrieu Nov 1 '19 at 15:52
• @fgrieu: Gravity-Sphincs is essentially the same as a hash; perhaps that's not the best example. I still think that the Picnic citation works... – poncho Nov 1 '19 at 18:03