31

What's the purpose of key-rotation?

Does it have any effect on the probability of keys being breached in the first place? Does it refer to avoiding access after a breach to all past data, all future data, both or none?

e-sushi
  • 17,891
  • 12
  • 83
  • 229
Filip Haglund
  • 1,043
  • 1
  • 8
  • 17
  • 1
    Uhm, limit damage if keys get breached? – SEJPM Nov 24 '16 at 21:52
  • Does it have any effect on the probability of keys being breached in the first place? Does it refer to avoiding access after a breach to all past data, all future data, both or none? – Filip Haglund Nov 24 '16 at 22:02
  • 2
    Key rotation doesn't decrease the risk of keys being breached. It mainly limits the amount of data encrypted under a certain key, so one may say it's done to so if a future key gets breached past comms are safe(r). – SEJPM Nov 24 '16 at 23:26
  • 2
    @SEJPM Some attacks gets easier to perform as the adversary gathers more data protected under the same key. So in some sense the probability of a breach does increase the longer time the key is used. I wouldn't recommend using the same AES key for more than 64GB due to the increasing risk of having two exactly identical cipher blocks. – kasperd Nov 25 '16 at 20:29
  • @kasperd what could you do with two identical cipher blocks? – Filip Haglund Nov 25 '16 at 20:34
  • 1
    @FilipHaglund In all the encryption modes I know of, that would leak some information about the clear text. For example in CBC mode the adversary could compute the XOR of the two plaintext blocks if he had seen two identical cipher blocks. – kasperd Nov 25 '16 at 20:56

3 Answers3

32

As @SEJPM notes, the primary purpose of rotating encryption keys is not to decrease the probability of a key being broken, but to reduce the amount of content encrypted with that key so that the amount of material leaked by a single key compromise is less.

However, for signing keys there is a concrete reason: say it takes $X$ months of computation (expected value given your threat model) to crack a key, and you rotate your signing key every $X-1$ months and revoke the old one, then by the time an attacker has cracked the key, any new signatures produced by the attacker will either be A) rejected by clients because of key expiry, or B) back-dated to before the key revocation (which should also raise warning in clients).

Mike Ounsworth
  • 3,627
  • 1
  • 18
  • 28
  • Is this specifically for RSA-like signing schemes? With e.g. hash-based signatures, the best attack method is a simple, stateless brute for search, and since success is a Poisson process, switching keys won't slow down an attacker at all. – Daniel Lubarov Jul 14 '18 at 16:54
  • @DanielLubarov I don't follow. Say an attacker starts brute forcing your hash-baned key. Halfway through you rotate keys. You're saying that the attacker does not lose any time? – Mike Ounsworth Jul 15 '18 at 17:07
  • I think it depends on the signing scheme. E.g. with Picnic, an attacker would be brute force searching for a single block cipher key. Say the attacker can test all keys in two years. If keys are never rotated, the attack will take two years. If keys are rotated annually, there's a 50% chance of breaking key 1 in the year 1, 50% chance of breaking key 2 in year 2, etc. There's no guaranteed completion date, but the expected time is 2 years. Agree? – Daniel Lubarov Jul 16 '18 at 06:36
  • @DanielLubarov Agreed, ... I think, but that's weaker than "switching keys won't slow down an attacker at all", right? – Mike Ounsworth Jul 16 '18 at 11:41
  • 1
    I guess you're right, but the difference in expected cracking time is up to a factor of two, depending on the rotation frequency. (Again assuming a simple brute force search.) Why not just add one bit to the key size instead of bothering with rotation? – Daniel Lubarov Jul 16 '18 at 20:48
  • @DanielLubarov Because key rotation is something you can do on an already deployed system (try switching your web server over to RSA-2049). – Mike Ounsworth Jul 16 '18 at 21:22
1

There is no practical reason to rotate keys as a matter of practice, save one, provided the keys you are using are crytographically strong to begin with. This is one of those cases where people assert "best practice" when in fact it's just a practice that has become a standard without any real justification. It MIGHT be appropriate depending on your risk assessment, but it is not a "best practice."

Other than a known breach of the key, the one exception to the general case is when keys are NOT cryptographically strong, or become weak over time, or the algorithm is compromised. In that case, you manually rotate keys (and if necessary algorithms) as soon as you become aware. If you depend on key rotation you will average the rotation interval divided by two of exposure.

I.e., For keys << than 80 bits, like 1DES, and particularly for 8-character passwords which have 47-52 bits of entropy, no frequency of key rotation is sufficient. Say "no" to password rotation and set detective action thresholds--you will save about 1 man hours per person per year in lost productivity, and you gain a real chance of identifying an attack, rather than depending on rotation to limit its extent. And if you can, set minimum password lengths to 16 characters or more.

  • "Reducing the volume of compromised material." Theoretically yes, but practically no. If you are rotating keys every year (AWS customer-managed KMS for example), or every three years (AWS managed KMS keys, for example) the majority of your information assets will have been touched during that period in the general case, meaning the person who cracked the key will already have them by the time you rotate. If you have lots of older, extremely valuable data then you might want to rotate, but that is an outlier case, not the general case, and would be reflected in your risk assessment.

  • "Rotation of signing keys." I am not aware that signing keys are cryptographically weaker than keys in general. If you accept that passwords should be rotated every 180 days, then a key with 256 bits of entropy can be rotated every 4.6 x 10^63 days. If one wants to argue for setting key rotation to a century or so, just in case, sure -- but short of that it is adding overhead that may bite later (you have to retain the old keys as long as the data they encrypted is valuable, or you have to re-encrypt all your data every time you rotate). For a public CA it MAY (I doubt it) make sense to rotate signing keys "just to be safe," but again this is a matter of risk assessment, not "best practice."

In short, there is no logical or empirical basis for key rotation as a standard or "best practice." It MAY be a good idea depending on an individual organization's risk assessment, but it is by no means a good idea in the general case because of the risks key rotation itself introduces into information governance.

Andy Robinson
  • 31
  • 2
  • 3
    So what is be the purpose of rotating keys every minute, as done on the encryption devices controlled by quantum key distribution networks? – Paul Uszak Aug 20 '19 at 22:35
  • 2
    @PaulUszak Selling more units by sounding more secure? – forest Aug 21 '19 at 05:51
  • 1
    I think there is both a logical and an empirical basis for Mike Ounsworth's answer. If I have your subkeys, then I don't want you to change them. – Patriot Aug 21 '19 at 10:28
  • @PaulUszak Read more, write less: you are referring to a special case. In the general case, the billions of people who use or may use cryptographic keys, regular rotation is neither desirable nor does it mitigate risk. – Andy Robinson Aug 21 '19 at 12:36
  • @forest Not an argument. In fact, by encouraging people to make risk-based decisions rather than enforcing "best practices" that are not only not "best," they aren't even good in many cases, because of the increased risk associated with implementing them, I cost myself business. I would do better to encourage your FUD. Those who think in terms of key compromise see a tree but miss the forest of risk associated with key rotation in the general case. – Andy Robinson Aug 21 '19 at 12:39
  • @Patriot I address that case: if your key is known to be compromised, it must be rotated. If you don't know it's been compromised and rotate it every 365 days, on average I will have access to your data for 365/2 days, and in the worst case 365 days.

    By the time you rotate, the horse has left the barn. Sorry, but key rotation is not only not a best practice, the associated key management risks make it a BAD practice in the general case. And if you doubt this, I suggest you research availability loss through key management failures.

     – Andy Robinson Aug 21 '19 at 12:43
  • @Andy Robinson I do agree with you that changing subkeys might involve a bit of risk. But which risk is greater: one change of subkeys, or keeping them too long? Your point about general use is well-taken. If we only consider the general user, your argument seems stronger. Still, you will surely acknowledge that many general users are victimized by en masse attacks. I would rather err on the side of caution in this game. – Patriot Aug 21 '19 at 13:31
  • @Patriot It is a matter of risk analysis, which is why I keep hammering the general case: the danger of data loss and other availability loss tends to be greater as a result of key management failures than as a result of brute force attacks. Let's consider an AES128 key: are their known exploits that make this algorithm or key cryptographically "weak?" If not, how long will it take to crack that key based on known computing capabilities? Knowing that computational power increases over time, how many orders of magnitude do you need to feel comfortable your key is still "strong?" – Andy Robinson Aug 21 '19 at 13:53
  • @Patriot PS - Also consider this. What gains you more, and which carries the lowest risk to availability? Rotating your key twice as often, or implementing detective controls that let you known when an attack is in progress, and/or when vital data is being exfiltrated? Key rotation is not a control in any meaningful sense, as the bad guy will have your data for interval/2 in the average case. Do you rekey your house locks periodically, or when you suspect an attack is imminent, or know one has happened? – Andy Robinson Aug 21 '19 at 13:58
  • @AndyRobinson Perhaps you misunderstood me. I was referring to Paul's comment. Key rotation is fine, but key rotation by the minute can be excessive, and in some cases can even reduce security (see: multitarget attacks). If you need forward sealing (different from forward secrecy), you can use the double ratchet protocol, which rekeys far more often. – forest Aug 21 '19 at 19:11
  • 2
    @forest My apologies. My argument is with key rotation as a "best practice." It is a practice that may be appropriate, but not by default. If you wish, compare realized losses due to compromised keys versus realized losses due to failures of key management and storage. – Andy Robinson Aug 21 '19 at 20:18
  • @AndyRobinson Ah, I fully agree then. Key rotation itself is indeed a good practice. – forest Aug 21 '19 at 21:19
  • Key rotation has tradeoffs. The person who answered this question is correct in that a key for a sufficiently strong cryptographic algorithm which is only used to encrypt as much data as recommended for it's lifecycle should not need to be rotated, provided you are certain that the key itself has not leaked. AES256 GCM should never be used to encrypt more than 2^32 blocks of data with the same key for example. Key rotation is one way to reduce the volume of information encrypted with the same key, provided you don't do something stupid like re-encrypt all your data with the new key. – Steve Owens Feb 14 '20 at 17:42
0

Key rotation converges the security of your system to that of perfect information theoretical security. It reduces the size of the data vulnerable to a key breech. Rotating keys on a monthly basis still allows a great deal of information loss under a single key if your network is operating at 10Gb/s (26 quadrillion bits total loss).

But consider the (admittedly) special case of quantum key distribution networks (QKDN). QuintessenceLabs and ID Quantique QKDNs create new keys every few minutes. These systems are approaching the theoretical security of one time pads (OTP). And speeds are ever increasing. Tokyo has demonstrated a OTP based video conferencing system with constant key rotation. And NIST have a CCTV system rotating the same way. These efforts demonstrate the already fast rate of key generation/rotation.

There is a strong trend towards increasing adoption of QKDNs, and we're likely to see more and more data encrypted under single use keys. This constant rotation has the potential to reduce data loss from key compromise to virtually zero as you can't break a OTP.

Paul Uszak
  • 15,390
  • 2
  • 28
  • 77
  • 1
    Greetings! That first sentence... I see how sentence two can certainly be the case, but I cannot bend sentence one so that it makes sense to me. Perfect information theoretical security applies to the one-time pad. If I rotate a GPG encryption subkey, that is not going to get me to me any nearer to the security level of the one-time pad. Do you mean what you say here, did you misspeak, or am I mistaken? – Patriot Oct 06 '19 at 14:38
  • 2
    For an OTP I would say that the theoretical security is so high because you cannot distinguish between a correct key and a non correct key. However, even if you decrease the amount of data encrypted with a key, you still need preciously few data to validate that a specific key is correct or not. So I don't see this convergence happening at all. Sure, less data is compromised on key loss, but the attack itself doesn't become any less feasible until the key size is about as small as the data size. Hence I cannot agree with this answer. – Maarten Bodewes Oct 06 '19 at 15:01