Revoke and let live: A secure key revocation api for cryptographic devices. Research Report RR-7949

While extensive research addresses the problem of establish-ing session keys through cryptographic protocols, relatively little work has appeared addressing the problem of revoca-tion and update of long term keys. We present an API for symmetric key management on embedded devices that sup-ports key establishment and revocation, and prove security properties of our design in the symbolic model of cryptogra-phy. Our API supports two modes of revocation: a passive mode where keys have an expiration time, and an active mode where revocation messages are sent to devices. For the first we show that once enough time has elapsed after the compromise of a key, the system returns to a secure state, i.e. the API is robust against attempts by the at-tacker to use a compromised key to compromise other keys or to keep the compromised key alive past its validity time. For the second we show that once revocation messages have been received the system immediately returns to a secure state. Notable features of our designs are that all secret val-ues on the device are revocable, and the device returns to a functionally equivalent state after revocation is complete