Right now, in X.509, there is no such thing as tracking of a number of uses of a given key. This is part of what is meant by "X.509 is context-free": validation is about whether the certificate path you have in front of you is valid or not, irrespective of whether a similar path or something different was shown to you 5 minutes ago when talking to the "same" server for some notion of "same".
Another important point of X.509 is that rogue CA are out of scope. This seems paradoxal, but the idea is that when a CA goes under hostile control, then that CA is "lost" and the only thing that can be done with it is to sever the whole tree branch, by revoking the certificates corresponding to the compromised CA key (where "compromise" means "the private key was used for hostile purposes", not necessarily "a copy of the private key was stolen"). For a compromised root CA, the only possible correction is to remove it from the trust stores of all clients, since root CA, being self-issued, cannot be revoked.
(When Microsoft pushes a Windows patch which removes a root CA from the default trust store, this can be viewed as some kind of revocation, in which case the root CA are not really "root", the "true root" being Microsoft. But all of this occurs outside of X.509.)
In the scenario you describe, whatever the attacker did with the root private key cannot be detected while the attacker does not actually use the rogue certificate. This is unavoidable, in a strong mathematical way: if the attacker can get access to the complete state of the root CA, then he can "clone it" and use the private key on his own machines; the root CA state is thus unimpacted. What you are asking for is some cryptographic magic which would maintain a "use counter" that the attacker could not alter at will even when he can see the full state. As long as computers are what they are, this is not feasible. To get a track of the number of issued signatures, so as to reliably detect rogue signatures, you will need something else, e.g. storing the root private key in a tamper-resistant device (a HSM) which will maintain the counter and, for instance, use it as part of the serial number for all issued certificates (thus allowing for client-side audit). This really is about changing the model by singling a "root CA core" that the attacker cannot seize.
Conceptually, we could envision a distributed database system (similar to the one used in Bitcoin) where all signatures are pushed, in a format which contains a "signature counter". This assumes the following:
- The signature algorithm is altered so that it works over h(c||m) instead of h(m) (c is the counter, m the signed data, and h a cryptographic hash function).
- All signature values are stored, indexed by signer and counter value, in the global database (thus, duplicates are detected).
- Verifiers (clients) don't accept a signature unless they can find it in the database.
- Verifiers enforce a specific counter behaviour, which allows them to notice when a CA has done more signatures than expected.
- The distributed database cannot be altered by attackers.
None of this is supported by X.509, neither now or in the foreseeable future. There is no global database of signature values, and since X.509 is supposed to be usable in offline contexts, there will not be one. Also, in X.509, verifiers are stateless: they don't keep track of verification history, and that's supposed to be a desirable feature.
The cryptographic algorithms for detecting double-spending in electronic cash protocols really are a shortened version of the "database" concept: they occur at the bank level, when the bank indeed sees both transactions. E-cash protocols are thus made so that the spender's identity is revealed in case of double-spending, during this correlation phase.
