"Against Rekeying"

[Jon Callas]

> I'd be interested in hearing what people think on the topic. I'm a bit
> skeptical of his position, partially because I think we have too little
> experience with real world attacks on cryptographic protocols, but I'm
> fairly open-minded at this point.

I think that if anything, he doesn't go far enough.

Rekeying only makes sense when you aren't using the right crypto, and even then might make the situation worse. Rekeying opens up a line of attack. From a purely mathematical point of view, here's a way to look at it:

The chance of beating your cipher is P1 (ideally, it's the strength of the cipher, let's just say 2^-128). The chance of beating the rekey protocol is P2. Rekeying makes sense when P2 is smaller than P1. When P2 is larger than P1, you've reduced the security of your system to the chance of a flaw in the rekeying, not the cipher.

As others have pointed out, it's front of Ekr's mind that there is (was) a major flaw in the SSL/TLS protocol set that came out because of bugs in rekeying. Worse, it affected people who wanted high security in more evil ways than people who just wanted casual security. Many people (including me) think that the best way to fix this is to remove the rekeying. If you need to rekey, tear down the SSL connection and make a new one. There should be a higher level construct in the application that abstracts the two connections into one session.

In most cases where you might want to rekey, the underlying system makes it either so trivial you don't need to think about it, or so hard that you can ignore it because you just won't.

Let me give a couple examples. First the trivial one. Consider a directory of files where each file is encrypted separately with a bulk key per-file. The natural way to do this is that every time someone rewrites a file, you make a new bulk key and rewrite the file. You don't have to worry about rekeying because it just falls out.

Now the hard one. Consider a disk that is encrypted with some full disk encryption system. If you want to rekey that disk, you have to read and write every block. For a large disk, that is seriously annoying. If your disk does 100MB/s (which very fast for a spindle and still pretty fast for SSDs), then you can do 180G per hour (that's 6G per minute, 360G per hour, and halve it because you have to read and write) max. That's about six hours for a terabyte.

If your disk only does 10MB/s, which many spindles do, then it's 60 hours to rekey that terabyte. You can do the math for other sizes and speeds as well as I can. In any event, you're not going to rekey the disk very often. In fact most of the people who really care about rekeying storage are changing their requirements so that you have to do a rekey on the same schedule as retiring media -- which effectively means no rekey.

A long-time rant of mine is that security people don't do layering. I think this falls into a layering aspect. If you design your system so that your connection has a single key and you transparently reconnect, then rekeying is just forcing a reconnect. If you make your storage have one key per file, then rekeying the files is just rewriting them. It can easily vanish.

And yes, obviously, there are exception cases. Exceptions are always exceptional.

	Jon

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com