What is the performance difference of pki to symmetric encryption?

Question

We are looking to do some heavy security requirements on our project, and we need to do a lot of encryption that is highly performant.

I think that I know that PKI is much slower and more complex than symmetric encryption, but I can't find the numbers to back up my feelings.

Gainsay

Answer 1

Yes, purely asymmetric encryption is much slower than symmetric cyphers (like DES or AES), which is why real applications use hybrid cryptography: the expensive public-key operations are performed only to encrypt (and exchange) an encryption key for the symmetric algorithm that is going to be used for encrypting the real message.

The problem that public-key cryptography solves is that there is no shared secret. With a symmetric encryption you have to trust all involved parties to keep the key secret. This issue should be a much bigger concern than performance (which can be mitigated with a hybrid approach)

Shortening

Answer 2

On a Macbook running OS X 10.5.5 and a stock build of OpenSSL, "openssl speed" clocks AES-128-CBC at 46,000 1024 bit blocks per second. That same box clocks 1024 bit RSA at 169 signatures per second. AES-128-CBC is the "textbook" block encryption algorithm, and RSA 1024 is the "textbook" public key algorithm. It's apples-to-oranges, but the answer is: RSA is much, much slower.

That's not why you shouldn't be using public key encryption, however. Here's the real reasons:

1. Public key crypto operations aren't intended for raw data encryption. Algorithms like Diffie-Hellman and RSA were devised as a way of exchanging keys for block crypto algorithms. So, for instance, you'd use a secure random number generator to generate a 128 bit random key for AES, and encrypt those 16 bytes with RSA.

2. Algorithms like RSA are much less "user-friendly" than AES. With a random key, a plaintext block you feed to AES is going to come out random to anyone without the key. That is actually not the case with RSA, which is --- more so than AES --- just a math equation. So in addition to storing and managing keys properly, you have to be extremely careful with the way you format your RSA plaintext blocks, or you end up with vulnerabilities.

3. Public key doesn't work without a key management infrastructure. If you don't have a scheme to verify public keys, attackers can substitute their own keypairs for the real ones to launch "man in the middle" attacks. This is why SSL forces you to go through the rigamarole of certificates. Block crypto algorithms like AES do suffer from this problem too, but without a PKI, AES is no less safe than RSA.

4. Public key crypto operations are susceptible to more implementation vulnerabilities than AES. For example, both sides of an RSA transaction have to agree on parameters, which are numbers fed to the RSA equation. There are evil values attackers can substitute in to silently disable encryption. The same goes for Diffie Hellman and even more so for Elliptic Curve. Another example is the RSA Signature Forgery vulnerability that occurred 2 years ago in multiple high-end SSL implementations.

5. Using public key is evidence that you're doing something "out of the ordinary". Out of the ordinary is exactly what you never want to be with cryptography; beyond just the algorithms, crypto designs are audited and tested for years before they're considered safe.

To our clients who want to use cryptography in their applications, we make two recommendations:

• For "data at rest", use PGP. Really! PGP has been beat up for more than a decade and is considered safe from dumb implementation mistakes. There are open source and commercial variants of it.

• For "data in flight", use TLS/SSL. No security protocol in the world is better understood and better tested than TLS; financial institutions everywhere accept it as a secure method to move the most sensitive data.

Here's a decent writeup [matasano.com] me and Nate Lawson, a professional cryptographer, wrote up a few years back. It covers these points in more detail.

Teakettle

It appears that your link of the writeup no longer works. – Breslau

RSA 1024 doesn't provide the security of AES-128. You shouldn't be forming your own messages for the RSA primitive; find a library that does this correctly. I don't understand what you mean by parameters in the context of RSA. Can you provide a concrete example of "evil" parameters for RSA? Public key cryptography is the most ordinary cryptography today, used in every HTTPS request. Not using hybrid encryption is out of the ordinary, and when standards like CMS or TLS support it, it is usually an afterthought that receives less scrutiny and is less likely to be supported in implementations. – Jaimeejaimes

Answer 3

Use the OpenSSL speed subcommand to benchmark the algorithms and see for yourself.

[dave@hal9000 ~]$ openssl speed aes-128-cbc
Doing aes-128 cbc for 3s on 16 size blocks: 26126940 aes-128 cbc's in 3.00s
Doing aes-128 cbc for 3s on 64 size blocks: 7160075 aes-128 cbc's in 3.00s
...
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes
aes-128 cbc     139343.68k   152748.27k   155215.70k   155745.61k   157196.29k


[dave@hal9000 ~]$ openssl speed rsa2048
Doing 2048 bit private rsa's for 10s: 9267 2048 bit private RSA's in 9.99s
Doing 2048 bit public rsa's for 10s: 299665 2048 bit public RSA's in 9.99s
...
                  sign    verify    sign/s verify/s
rsa 2048 bits 0.001078s 0.000033s    927.6  29996.5

Royalroyalist

Answer 4

Practical PKI-based encryption systems use asymmetric encryption to encrypt a symmetric key, and then symmetric encryption with that key to encrypt the data (having said that, someone will point out a counter-example).

So the additional overhead imposed by asymmetric crypto algorithms over that of symmetric is fixed - it doesn't depend on the data size, just on the key sizes.

Last time I tested this, validating a chain of 3 or so X.509 certificates [edit to add: and the data they were signing] was taking a fraction of a second on an ARM running at 100MHz or so (averaged over many repetitions, obviously). I can't remember how small - not negligible, but well under a second.

Sorry I can't remember the exact details, but the summary is that unless you're on a very restricted system or doing a lot of encryption (like if you want to accept as many as possible SSL connections a second), NIST-approved asymmetric encryption methods are fast.

Estelaestele

After Bullrun was revealed in 2013, the phrase "NIST-approved" sounds almost like a joke. They're fast (and maybe, just maybe leak your data to NSA). – Ingratitude

By that comment I meant that answer didn't really age well :) – Ingratitude

Yes, I think I only mentioned NIST to kind of limit the domain of discourse to the PKI that "people" are mostly using. Certainly one could dig up or invent PKI protocols that are absurdly slow (I dunno, add a key-stretching step or something to make it as slow as you like). But the performance of the ones actually used in 2008 was sometimes an issue for servers managing hundreds or thousands of connections, but not really for clients managing a handful. Whether any given algorithm from 2008 is still good to use now is a completely different matter – Estelaestele

Answer 5

Apparently it is 1000x worse. (http://windowsitpro.com/article/articleid/93787/symmetric-vs-asymmetric-ciphers.html). But unless you're really working through a lot of data it isn't going to matter. What you can do is use asymmetric encryption to exchange a symmetric encryption key.

Conceptionconceptual

Answer 6

Perhaps you can add some details about your project so that you get better quality answers. What are you trying to secure? From whom? If you could explain the requirements of your security, you'll get a much better answer. Performance doesn't mean much if the encryption mechanism isn't protecting what you think it is.

For instance, X509 certs are an industrial standard way of securing client/server endpoints. PGP armoring can be used to secure license files. For simplicity, Cipher block chaining with Blowfish (and a host of other ciphers) is easy to use in Perl or Java, if you control both end points.

Thanks.

Tour

Answer 7

Yes, the hybrid encryption offered by standardized cryptographic schemes like PGP, TLS, and CMS does impose a fixed performance cost on each message or session. How big that impact is depends on the algorithms selected and which operation you are talking about.

For RSA, decryption and signing operations are relatively slow, because it requires modular exponentiation with a large private exponent. RSA encryption and signature verification, on the other hand, is very fast, because it uses the small public exponent. This difference scales quadratically with the key length.

Under ECC, because peers are doing the same math with keys of similar size, operations are more balanced than RSA. In an integrated encryption scheme, an ephemeral EC key can be generated, and used in a key agreement algorithm; that requires a little extra work for the message sender. ECDH key agreement is much, much slower than RSA encryption, but much faster than RSA decryption.

In terms of relative numbers, decrypting with AES might be 100,000x faster than decrypting with RSA. In terms of absolute numbers, depending heavily on hardware, AES might take a few nanoseconds per block, while RSA takes a millisecond or two. And that prompts the question, why would anyone use asymmetric algorithms, ever?

The answer is that these algorithms are used together, for different purposes, in hybrid encryption schemes. Fast, symmetric algorithms like AES are used to protect the message itself, and slow, asymmetric algorithms like RSA are used in turn to protect the keys needed by the symmetric algorithms. This is what allows parties that have never previously shared any secret information, like you and your search engine, to communicate securely with each other.

Jaimeejaimes