Dave's Bit Bucket

On Risk, Public Key Certificates and Expiry

As part of the discussion I had with Stephen about his latest paper (referenced below, we had a chat about sealing of documents and digital signatures. As is usual when discussing things with Stephen, it set me thinking :-).

One of the questions he asked at some point was "What about the life of a cryptographic key?".

I woke up in the wee small hours of the following morning, and bashed out a bunch of notes which support a conclusion I wasn't initially expecting; I've restructured and extended them a bit and present them here.

First of all, "keys don't expire, certificates do".

A certificate comprises the public half of an asymmetric key pair, a unique description of an entity it is to be tied to (usually as an LDAP distinguished name or email address), some other metadata such as an expiry date, and a signature on a digest of this from some CA somewhere up the issuance chain back to a trust anchor. It is particularly used to address the problem of transitive trust when keys are shared among multiple systems along long chains of transporting intermediaries. Certificates can be intrinsically authorised just for signing or encrypting data, or can be intrinsically authorised to be able to participate in the minting process of new certificates by signing their content.

(OK, Stephen is tech-savvy, but I wanted to start from first principles.)

Keys which aren't either in a certificate or associated with a key contained in a certificate don't intrinsically expire. This is often a Good Thing; if (like me) you keep your home directory in a sparse-image filesystem which is encrypted, you wouldn't want that encryption key to expire. At best, if the encryption key expired you'd have to decrypt your home directory, copy its contents to some new store in cleartext for a while, and then re-encrypt them with a new key; at worst, you'd lose your data. Also, there are some keys for which there is little point in expiry - if we consider an signed NTP feed, while someone could conceivably try to replace your validated feed with a false one, comparing the output of "date" with the handy device on your wrist or a nearby wall would show you if something serious was amiss.

So why, in a world which has yet to adopt Ephemeriser technologies, do certificates expire?

As with everything in security, certificate expiry has to be tied-up somehow with a perceived threat, and expiry has to serve to mitigate that threat. So, what's the threat, and does expiry (as opposed to, or in concert with, other mechanisms such as CRLs) actually address it?

All threats involving keys would seem (to me, at least) to revolve around:

• theft
• loss
• discovery (by brute-force or other analytical techniques)
• falsified revocation (effectively denial of service)

...so let's look at each of these in turn. There's also a somewhat cynical coda as to why the status quo may be as it is.

Theft

Keys can certainly be copied and stolen. Stealing a copy of a disk-based keystore in these times where you don't have a Hardware Security Module (HSM) attached to every computer, and cracking or otherwise obtaining its own encryption key (by whatever means - Trojanning the program used to unlock it, perhaps) is probably easier than brute-forcing the private key corresponding to a certificate with a 2048-bit RSA key in it. You don't know that a copy of your private DSA key has been stolen until it turns up on a document you didn't write, and unless you've always been rigorous to the point of paranoia in your logging infrastructure and have the ability to do data mining on the terabytes of logs you've probably collected as a result, you won't be able to pin down when the theft occurred.

So potentially, proof of your authorship of, and the integrity of, every document you have signed with that DSA key since it was minted is suddenly in question. Admittedly, only the thief who has the copy of your key could transparently modify any documents you might have written, unless he circulates the key; so such documents would also need to be intercepted by him for the key to be useful, unless he wishes to masquerade as you by writing fresh documents he can attribute to you and then circulating them.

Having a DSA key only be valid for a short lifetime limits the number of documents whose authorship and integrity could thus be called into question. Granted, once a key is known to have been stolen its certificate should be immediately be published in a CRL, but if the key and cert are typical (with a 2 year lifetime), you only need to worry about documents written in at most the last 751 days.

However, what happens if you put your private key in a Trusted Platform Module (TPM)? TPMs can work as HSMs in terms of storing keys in a manner such that there's no programmatic way to get cleartext of them out again, and as the TPM is a physical device, you'd know when your key was stolen as the rest of your computer would probably have been stolen with it. Get your certificate onto a CRL post-haste and have a new one cut, and so long as the documents you wrote were also securely timestamped, those documents which were written before the theft remain safe in terms of provable integrity (as long as the timestamp wraps the whole of the document including your digital signature).

Granted, this assumes that the public CRLs of the world are well joined-up. Right now, things could be better in that area. However, key management for private keys suddenly starts to join up with asset management... until you get to session mobility, in which case keys associated with users rather than devices need to live either on the box(es) that the user's home directory is on, or on another box which something in the user's directory profile points at.

Loss

Naturally, if you lose your keys, you lose access to cleartext of any data whose sole copies are encrypted with them. Also, encryption is no protection against deletion; rm will clear a soft keystore's vnode on disk just as effectively as it will any for other file. If your keys are lost, you also lose the ability to sign things - although as the ability to verify a signature is associated with the key contained within the certificate, there should be copies of that out in the rest of the environment anyway.

Backing up of private keys creates another copy of key data which can be stolen. HSMs work to mitigate this risk by encrypting backups with a symmetric key blown into every HSM from that manufacturer, and to which there is no programmatic access at all. TPMs can do the same thing.

However, whereas HSMs are still fairly rare beasts these days, TPMs are expected to be completely commodity items (our current AMD-based servers already have them in, as does a lot of IBM and HP kit). This raises the issue that someone could theoretically steal a backed-up key blob and load it into their own TPM; having a passphrase held as part of the key blob which needs to be matched against a phrase typed in at blob loading time helps mitigate this threat.

Discovery

While the fine folk at http://www.distributed.net/ haven't even tried finding RSA / DSA private keys yet by brute-force factoring RSA, there is a reasonable corpus of academic research (Google for "factor rsa") which shows how hard it is.

To cite some examples:

• MIT cracked RSA-129 (decimal) in 5000 MIPS-years, over the course of 8 months with the participation of 600 volunteers. They subsequently managed to complete the calculation using a matrix generated by these volunteers in 45 hours on a very, very serious massively-parallel system; see http://www.mit.edu:8001/people/warlord/RSA129-announce.txt.
• CWI cracked RSA-140 (decimal) in 1500 MIPS-years over the course of 11 weeks using about 200 systems (8.9 CPU years in total); see http://www.hoise.com/primeur/99/articles/monthly/SW-PR-04-99-3.html.
• CWI subsequently cracked RSA-155 (decimal) using a Grid-style infrastructure based on organisations donating time on spare systems; see .
• BSI (not our British Standards Institute) cracked RSA-576 (binary; 174 decimal) in 1999. There is an excellent paper about this, which also explains a bunch of background info, at http://mathworld.wolfram.com/news/2003-12-05/rsa/.
• RSA-640 (binary; 193 decimal) was cracked just over a year ago, using a grid of Opterons; the figure of "30 2.2GHz-Opteron years" is quoted. See http://www.rsasecurity.com/rsalabs/node.asp?id=2964.

Think about this some more. All these examples involve either highly-parallel grids, supercomputers or both, and a reasonable amount of time. This is to discover the private keys to RSA implementations with keys less than a third the size of the 617 decimal digits of an RSA-2048 key, and the factoring effort goes up exponentially with the number of digits (modulo advances in number theory). RSA are themselves putting their money where their mouth is; see http://www.rsasecurity.com/rsalabs/node.asp?id=2094. Also, this is to discover the private-key counterpart to a given public key; the process would need to be repeated for a different key.

So, while conspiracy theorists may suggest that The Powers That Be in the global intelligence community have bespoke devices that they keep in sub-sub-basements which can factor RSA-2048 before breakfast, the staggering amount of publicly-available computing effort needed to break an RSA key of decent length means that it's not yet a realistic option for industrial espionage and subversion. (Note, though, that this doesn't mean ill-willed folk aren't using Dark Grids to try it - more thoughts on Dark Grids shortly.) If the idea of expiry is to bring a certificate to the end of its life before anyone can reasonably expect to brute-force its associated private key, expiry times should really be a lot longer than they currently are.

Falsified Revocation

A third party could potentially post details of a perfectly valid certificate / key pair to a CRL, thus making the key pair unusable. Expiry does not mitigate this; only the mechanisms involved in submission to the CRL server do.

Cynicism

CAs who maintain worldwide root trust anchors, and who have their trust anchor signature verification keys compiled into the world's most prevalent web browsers, make a significant amount of money out of doing what they do. If you get a procedurally well-backed certificate from one of these guys, it's either going to expire within a couple of years (at which point you have to pay up again in order to get it renewed) or you have to incur a much bigger initial outlay to get one which won't.

For folk who want to do encrypted services which track back to a well-known trust anchor, certificate expiry therefore locks them into a relationship with such a CA which looks remarkably like a time-based licensing model. No business with a sane head on its shoulders would pass up an opportunity to get repeat fees from its customers for zero repeat effort.

While I'm more of a realist than a cynic, I wonder whether this is the main reason why certificate lifetimes are as short as they are.

Conclusion

So, does a combination of TPMs-used-as-HSMs and joined-up worldwide CRL servers mean that certificates which aren't being used for Ephemerising purposes no longer need to expire intrinsically, only being withdrawn in an "on demand" manner by being appended to CRLs? Looking at it from a purely technical perspective, quite possibly - provided posting to a CRL does not automatically bring into doubt the trustworthiness of any artifact associated with the revoked certificate signed and time-sealed before the date of its revocation unless specifically stated, and unless, of course, I've missed something monumentally obvious :-).

I don't currently think that joining CRL servers up worldwide (or at least, within the whole scope of circulation of the entities signed by members of the organisation it relates to) is an intractable problem, although it would take an effort much along the lines of "what rootservers.net did for DNS" to do it. The political traction required for this to happen is, as always, another matter entirely.

(2006-12-12 13:40:18.0) Permalink Comments [0]

Stephen's latest paper

From time to time, I have a chat with Stephen Mason - Barrister, expert on UK e-Commerce law, author and general cool guy - about various technical and legal matters pertaining to security and evidential weight.

Stephen's latest paper, "Proof of the Authenticity of a Document in Electronic Format Introduced as Evidence", is downloadable here, and worth reading for members of the legal community and folk interested in Governance and document archival...

(2006-12-12 13:09:40.0) Permalink Comments [0]

Cheers, dude! :-)

My pal Glenn Brunette is the latest interviewee in Sun's occasional "Contrarian Minds" series, in which various Sun illuminati get to discuss their view of the world.

Glenn's interview includes a nice plug for the Adaptive Security stuff we've been working on from time to time, and which we showcased at RSA 2005. Cool! :-)

(2006-12-12 13:01:59.0) Permalink Comments [0]