3

Let's assume that we are designing a binary protocol for message exchange between devices. Part of the message will be RSA encrypted and there will also be an RSA signature block in the message.

Is there any advantage in using two separate key pairs, one for encryption and one for signing? This is opposed to using the same key pairs for encryption and signing.

To clarify:

Option 1. Device A has keypair A and device B has keypair B. These are used for both encryption and signing.

Option 2. Device A has keypairs Aenc and Asign and device B has keypairs Benc and Bsign, and these keypairs are used for encryption and signing respectively.

kaidentity
  • 2,634
  • 13
  • 30
Andrew Savinykh
  • 1,630
  • 3
  • 14
  • 22

1 Answers1

4

Definitely. There are two main advantages of having one keypair for encryption and another keypair for signing.

The first reason is that you will want to keep backups of expired keys that have been used for encryption, which is not the case with signing keys. You normally store encrypted data encrypted and decrypt it to view it. If you lose an encryption private key you lose data. If you lose a signing private key you lose nothing (since the public key will be somewhere public, right?). Our favourite bear made a huge discussion about this point in a previous answer.

A second reason is that an encryption protocol may be broken. It is plausible that only the encryption part or only the signing part of the protocol is broken (e.g. by watermarking data inside a cyphertext). If RSA encryption is broken and you have 2 keys, you need to revoke all encryption keys (and substitute by another protocol) but does not need to do anything about the signing keys. The opposite (signing is broken) also holds.

Due to popular demand (in the comments), I'll defend the second point above by presenting two scenarios: one in which an asymmetric signature can be broken without breaking the encryption, and one in which the encryption can be broken without breaking the signing algorithm. Let's rock:

(I'm not a theoretician, therefore there may be something wrong if you look at it with enough pedantry, don't feel afraid of pointing it out.)

Breaking signing without breaking the encryption

Assuming that the signing is performed in the following fashion (it is a common fashion for asymmetric encryption):

encrypt(privkey, hash(plaintext))

The purpose of an attacker is to be able to sign a message of his own creation with my key. He can steal the key or attack the algorithm. If the attacker finds a way to efficiently find collisions in the hash() function, he can take a message previously signed by me retrieve the hash (by decrypting the signature) and craft a message of his own that collides to the same hash value.

In other words, by breaking hash() an having access to at least one of messages signed by me, the attacker defeats the signing algorithm without touching encrypt().

Breaking encryption without breaking the signing

One common way to break the encryption is being able to guess the key based on information in the cyphertext and the plaintext. This is often called watermarking (although that is more often used against symmetric encryption). The encryption will be performed by:

encrypt(pubkey, plaintext)

Now, let's assume that the attacker will send me several cyphertexts encrypted with my public key. And that he will convince me to reveal to him the content of the plaintext that I decrypted using my private key. This is not far fetched at all: imagine encrypted mails with password resets, I'll decrypt the mail and send the plaintext back to the attacker.

Now, if it is possible to guess (with high probability), based on certain bits in the cyphertext, that a certain bit in the plaintext will be 1 or 0 if another bit in the private key is 1 or 0, then we have a high probability chance that we discovered a single bit of the private key. This is akin of an attack against the S-BOX model of the algorithm had we been talking about symmetric encryption.

(The previous paragraph is considerably far fetched. Thinking of RSA as using bits is not very realistic. I'm using bits because it is how watermarking works against block ciphers, but you can think of it as any statistical attack on RSA)

Repeating the procedure above several times the attacker can recover my private key, and the encryption is broken since he can now decrypt all messages sent to me.

Why doesn't this work for signatures? Because of the same hash() function as above. If the hash is cryptographic, it should be impossible to determine the location of bits in the plaintext based on the hash output. Therefore, if hash() is sound but the encryption algorithm can be attacked with watermarking, we can break encryption without breaking the signing algorithm.

But wait, aren't cryptographic hashes used (on the plaintext) during the encryption? Ekhm... nope, the encryption need to preserve all data so it is possible to decrypt it. A hash will lose some data, therefore it cannot be used in the same form as in the signing algorithm in the encryption.

Of course, these two scenarios are not the only possible scenarios. But are plausible scenarios, woth enough attention to warrant using 2 keypairs (one for signing and one for encryption)

Community
  • 1
grochmal
  • 5,677
  • 2
  • 19
  • 30
  • Most signing protocols use encryption on the hash of the document (encrypt(key_private,hash(doc))). That means a broken encryption protocol also affects signing. What I mean is, I like your first point, but don't agree with your second. Otherwise I'd upvote. – Andrew Philips Oct 05 '16 at 02:52
  • 1
    I agree with Andrew Philips. If RSA was broken I have hard times to believe that this would only affect encryption xor signing. I remember having read that breaking RSA is equivalent to efficiently factor large numbers, even though I'm not sure... if this is true then if you break one you also break the other. – kaidentity Oct 05 '16 at 09:46
  • @AndrewPhilips - If encrypt() was broken I completely agree with you. But that is not the only way of breaking an encryption protocol, I have added a good digression about plausible scenarios for point 2. – grochmal Oct 06 '16 at 01:51
  • @kaidentity - I just attempted to defend my point 2. It is correct to say that if RSA was completely broken both (signing and encrypting) would be likely useless. But there are more subtle attacks out there that may break only one side of the algorithm. I have added a digression, i.e. you do not need to break the factorisation of large numbers to break RSA, there *may* be other ways. – grochmal Oct 06 '16 at 01:55
  • @grochmal, Good elaboration, however, still some problems. In the break sign example, you suggest hash could be broken which is not the same as breaking RSA encryption. Furthermore, I believe you misunderstand current, common Public Key crypto algorithms. Sign = Enc(Key_Private, Hash(doc)), Encrypt = Enc(Key_Symmetric, Doc) || Enc(Key_Public, Key_Symmetric). No one encrypts a document with RSA keys, they use symmetric crypto and public key encrypt the sym key. Encryption RSA key loss => revocation; Sign RSA key loss => untrusted docs for all time (past, included), unless notarized/witnessed. – Andrew Philips Oct 06 '16 at 13:58
  • By "loss" I mean "stolen", not unable to retrieve. – Andrew Philips Oct 06 '16 at 14:05
  • @AndrewPhilips - Whelp, but I ain't trying to break RSA (there's enough people trying to do that already). By the contrary, I'm trying to render a corpus of singed documents or cyphertexts tainted. And, as much as I can, avoid (hypothetically) breaking RSA itself in the process. The second example is completely far fetched, it is closer to science fiction than reality so I completely give that to you. But the signing example is pretty plausible, and, if it happens, will force signing keys to be revoked (and the singing procedure reviewed). – grochmal Oct 06 '16 at 18:21
  • Without digging in deeper, I'll yield that point. However, that's not what your original 2nd paragraph states - at least not its most obvious premise. You drew out more what you meant below, but you weren't using standard public key crypto signing and encryption protocols in your examples, so I'm having a hard time agreeing with your point. I still maintain your original 2nd para is not really correct. Your first is sound. It's been an enlightening discussion, nevertheless. Cheers. – Andrew Philips Oct 06 '16 at 18:39