Increasing the lifetime of a key: A comparitive analysis of the security of rekeying techniques

Authors: M. Abdalla and M. Bellare

Abstract: Rather than use a shared key directly to cryptographically process (e.g.~encrypt or authenticate) data one can use it as a master key to derive subkeys, and use the subkeys for the actual cryptographic processing. This popular paradigm is called re-keying, and the expectation is that it is good for security. In this paper we provide concrete security analyses of various re-keying mechanisms and their usage. We show that re-keying does indeed ``increase'' security, effectively extending the lifetime of the master key and bringing significant, provable security gains in practical situations. We quantify the security provided by different re-keying processes as a function of the security of the primitives they use, thereby enabling a user to choose between different re-keying processes given the constraints of some application.

Ref: Extended abstract in Advances in Cryptology - Asiacrypt 2000 Proceedings, Lecture Notes in Computer Science Vol. 1976, T. Okamoto ed, Springer-Verlag, 2000. Full paper available below.

Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).