* Brian Keefer:
My apologies if you were commenting on some other aspect, or if my understand is in some way flawed.
I don't think so. There's a rule of thumb which is easy to remembe: Never revoke anything just because some weak algorithm is involved. The rationale is that that revocation is absolute and (usually) retroactive, but we generally want a more nuanced approach. If certain algorithms are too weak to be used, this is up to the relying party to decide whether it's fine in a particular case. On the other hand, replacing MD5-signed certificates in the browser PKI is costly, but the overhead is very finely dispersed (assuming that reissuing certificates has very little overhead at the CA). I think it's doable if the browser vendors could agree on a flag date after which MD5 signatures on certificates are no longer considered valid. (The implicit assumptions in that rule of thumb do not always apply. For instance, if weak RSA keys are discovered which occur with sufficiently high probability as the result of the standard key generating algorithms to pose a real problem, the public key may not reveal this property immediately, it may only be evident from the private key, or only after a rather expensive computation. In the latter case, we would be in very deep trouble.)