4
$\begingroup$

I'm new to cryptography, and I'm trying to understand the concept of rekeying. What is the motivation (necessity) behind rekeying? What is the detailed mechanism for generating new session keys for an encrypted established connection?

Clear explanations of basic concepts would be very helpful, as would links to good videos or blogs. (I have been unable to find such materials online.)

$\endgroup$

1 Answer 1

2
$\begingroup$

I would say that rekeying is used in cryptography in order to limit the number of messages (talking about encryption and decryption here) that are sent from the same key. This is just a preventive measure to thwart the attacker from getting much information about the same family of messages (encrypted with the same key) by looking at the encryption of messages with the same key.
If you have heard about the standard security definitions of encryption schemes and the standard attacks, like ciphertext only attacks, chosen ciphertext attacks, etc. then you might know that if the adversary gets hold of many many messages encrypted with the same key then in some encryption schemes and in some use case scenarios, the adversary might get some information about the messages which he ideally shouldn't have.
Let me give you a very primitive example.
You might know what a caeser cipher is (if not, then look it up). In case of caeser cipher (or any substitution cipher), if the adversary sees a lot of messages, encrypted with the same key, then they can easily run a frequency analysis attack on the cipher to learn the key and then get the message in plain. Rekeying, very frequent in such cases, in such a case might at least prevent the attacker from getting enough information to run an attack like this or at least make it an attack more difficult to run.
Don't assume that this is how weak the modern ciphers are, they are pretty great at prevent many attacks, even more sophisticated ones like linear and differential cryptanalysis on DES and AES.
But still, if an adversary gets hold of $2^{43}$ known plaintexts then it can successfully cryptanalyse DES encryption (although because of this, DES is not used these days and it is replaced by AES and 3DES) meaning that if the adversary somehow knows the encryptions of $2^{43}$ messages, all encrypted with the same key, then it can find the key and decrypt all of the upcoming messages (if encrypted with the same key) by using Linear Cryptanalysis.
Now in the above case, if one puts a limit on the time for which a key is used, say for only $2^{30}$ messages, then the attacker will never get $2^{43}$ encrypted messages with a single key because the key will be refreshed or rekeyed after just $2^{30}$ messages and this prevents the Linear Cryptanalysis attack on the cipher. Note that this above discussion assumes that adversary somehow gets to know the messages and their encryptions whenever they are sent. This may be true if adversary knows what the other 2 parties are talking about for some time but doesn't know what they will talk about, say a month later, and he wants to get the key somehow so that he can listen to their talk after a month. If he has already seen $2^{43}$ messages in the part where he knew what they were talking about, then he will recover the key and then use that key to listen to their chats after the month. If the 2 communicating parties change their keys, then he won't be able to use that old key to listen to their chats after the month.

In practice, say in the browser, a hybrid type of encryption is usually used where a public key handshake is used to establish a symmteric key and then that key is used to encrypt messages by symmetric encryption (AES) because symmetric encryption is way faster than public key encryption. Then you might ask that why don't we use symmetric key encryption to establish the keys also? This is so because symmetric key encryption doesn't provide a way for 2 parties to negotiate a key over an untrusted channel like internet but public key cryptography does (like Diffie Hellman Key Exchange Protocol).
Once a connection has been established, then across multiple sessions public key cryptography is used to rekey the symmetric encryption through which messages will finally be encrypted.

$\endgroup$
2
  • $\begingroup$ Can you explain how time based rekey is helpful $\endgroup$
    – Genie
    Jun 25, 2018 at 5:36
  • 1
    $\begingroup$ In systems like Kerberos, which used widely in the web, certificates are associated with keys that are issued with each certificate having an expiry date and time. Once that date and time have passed, the sending party cannot use that key to send messages to the receiving party anymore. It will need to renew its certificate. $\endgroup$
    – Mayank
    Jun 25, 2018 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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