February 12, 2008

on Revocation of Signing Certs and Public Key Signing itself

Philipp pointed me to another issue that turns the good ship Digital Signature into yet another Nautilus, rapidly going down the whirlpool.

Consider compromise of my signing key. If my key is compromised, then it can be used to sign any document on behalf of the erstwhile owner (was, me). Now, a curiosity of this is that the signature can be backdated, so if I lose my signing key to you, then you can sign away my house, back date it to a few years back to when it was a valid key, and take my house for a buck.

Hence, when my key is compromised, I have to revoke the key, and also potentially revoke all the signatures. The revocation of a signing cert can result in signatures of all dates becoming invalid, or questionable, even back in time. (Apparently, some proportion of client software works this way, because once a cert is revoked, all signatures are deemed "unacceptable" and thus effectively revoked. Nautilus, meet whirlpool.)

This could even be used by myself, in a nefarious mood, to cast doubt over the my own validly-made signatures. If I was homesick, I could conceivably use this to deny a valid contract to sell my house. Hey presto, Grandma gets her house back! (For other woes in the use of public keys for signing purposes, see Signed Confusion)

So how do we solve this problem? Skip down to **** if you are fully informed on that invention known as the Ricardian Contract, which does solve this issue.

In the Ricardian Contract I solved it by taking the hash of the signed contract, making that the identifier for the contract, and then embedding that hash into every transaction that happens thereafter. So, in effect, all new transactions accept and affirm the contract; and therefore form part of the evidence over the signature; if we question the original digsig, we also question all the transactions in the issuance, which is not reasonable beyond the first few dozen transactions.

What happens in more conventional PKI-land, where wisdom is writ, and standards are dusty? As is frequently pointed out, any human-meaningful use of digital signatures would then need to be confirmed with a secure timestamp, perhaps so that any later key revocation can avoid revoking that signature. Makes some sense, and indeed, every single Ricardo transaction sums to achieve that timestamp, as it builds up a tree of timestamped, signed transactions, pyramided on the original contract and its certificate.

We could then propose a rule in the use of public key digsigs for digital signing:

digital signatures cannot be relied upon over time without secure timestamping

The problem with this is that it undermines the very architecture of PKI; if we are assuming online, authoritive entities such as timestamping or digital cash issuers, then we don't actually need PKI, as it is written. Click on lynn://frequent.rant/ at this point... or for my version, in Ricardo as described above, the strength was the fact that strong evidence of the contract was kept over time, not the digsig. In this case, the evidentiary hash over the total document is what is kept, and the digsig added no more than the sweetness of headline confirmation of intent to the picture.

Because PKI (and in this case, OpenPGP cleartext signing) established a convention of signalling an intent with a digsig, it was handy to use that signal.

But we never relied on that, and a specific requirement was that someone could steal the signing key and create a bogus contract. The real strength that captured the signing over the contract was this: we took the hash of the document, and used that hash as the identifier for the contract. We are talking about Ivan, a person who is an issuer of value, and is purporting to the world that his contract is good. Them we arrange matters so that in every statement he makes to the world, he uses a strong identifier. By including the hash of the contract in every transaction, we establish Ivan's intent, understanding, liability on the basis of strong acts by the signer himself. The subtext is that the dominating evidence of intent on the document was the hash over the document, and the transactions that embedded that hash preserved and published that evidence [1].

**** The conclusion is that the hash is a better "signature" than a public-private-key digsig, if we are talking about evidence of time, leading to intent, etc; both need to be accompanied by an infrastructure that isolates the realtime of effect of the original event, and an environment where that intent is preserved. In which case, we can take the above, spin it and say that simple hashes are as good as public key digsigs at the application known as digital signing, and better because they are cheaper. Or, if the infrastructure is present, then public key digsigs makes a good carrier of hashes, as long as their use doesn't damage the application in other ways (which unfortunately it does, c.f. revocation).

What does a timestamped hash lack? It has no indicator of who the signer is. Hence, the hash does not quite defeat the digsig on the basis of Occam's razor.

But we need that in other ways anyway, as the pure cryptographic notion of a public key signature is no better than "this set of bits saw that set of bits" and we know from practical cryptography that there is no easy way to measure and control the distance from a human (intent) to a set of bits. PKI fails to achieve this because it outsources identity to a thing called Certificate Authorities, which so far have not shown themselves to be useful harbingers of your signatory, if in part because they are more expensive than the old pen&ink method.

Let's step back then, and place this in terms of requirements. We need these things to create any system of digital signing:

  • a contract
  • who is the person(s) that is "intending" the contract
  • the time of original intent
  • the preservation of all the above

Public key signatures add very little if anything over hashes and timestamps, as the former needs independent timestamping and revocation, which means that their PKI claims of offline-checking are unravelled. Neither public key digsigs or simple hashes establishes who, easily (consider the cost of PKI infrastructures versus the low statements of reliance), and neither establishes intent.

Indeed, the requirements are so badly met that we can invent a system in 30 seconds that beats the incumbent "approved digital signing systems", hands down:

Iang is who Iang says he is.

This is strong, because, it was me that said it, me that posted it, and this blog, google, the time machine and all the other net tricks will preserve it [2]. Oh, and the hash adds some precision.

Are public key signatures dead? In technical and legal terms, yes. Public key signatures are at least brain-dead, and should be terminated for lack of sentience. While they retain some residual value in marketing senses and in infrastructure senses, they cannot be relied upon as signatures. We'll continue to put in the cryptocandy of the OpenPGP signatures on contracts, but the strength is elsewhere.

Which also means that we do not need to worry about revocation in digsig signing applications: the PKI digsigs as signing applications already revoked themselves, and we shouldn't spend any time over the issue except to say that they are not reliable enough for reliance applications. Instead, if you want a reliable digital signing application, read the Ricardian Contract paper carefully, and construct a protocol that carries the cryptocandy of the existing infrastructure alongside a proper chain that evidences the perfection of the contract: reading/understanding/intent/delivery.

Notes [1]: To follow a digital issuance through in technical, accounting terms: in a digital currency, we start out with one transaction to create value. This is of necessity a double entry transaction that puts large positive value into a manager's account, against large negative value into a float account. Then, the freshly minted positive value is distributed to the users, resulting in more transactions. The value is probably split in the second transaction and further split and recombined in each succeeding transaction, resulting in something like a tree structure.

Each of these transactions evidence an intent to honour the contract, as they all point back by means of the same hash over the same document. Hence, the OpenPGP signature is crypto-icing over the real cake within the Ricardian contract; in this particular case at least, the OpenPGP signature adds little to what the evidentiary chain of transactions provides.

Note [2]: If you want to wrap some cleartext signing sugar onto it, try this:

----- BEGIN OpenPGP Hash-Signed Document -----
I am who I say I am.
----- BEGIN HashSIG -----
----- END HashSIG -----

Note [3]: how did we do that hash? Like this:

$ openssl sha1
Hash-signing my contract is as easy as typing text and adding newline then control-D at the end

Cut and paste the text line into a Unix terminal application, and follow the instructions. Don't forget to hit return, then hit ctrl-D. Don't include the spaces at the beginning.

Posted by iang at February 12, 2008 10:48 AM | TrackBack

the certification authorities have been looking to go up the value chain for sometime now.

the x.509 identity digital certificates from the early 90s ran into a number of issues. the paradigm is basically targeted at offline email authentication that existing in the early 80s (taking a page from the letters of credit/introduction from sailing ship days).

the paradigm ran into numerous discontinuities by the mid-90s

1) online was becoming ubiquitous so relying parties would have connectivity to authoritative agency and get timely information as to the party they were dealing with (as opposed to the information in the stale, static digital certificates)

2) attempting to increase the value of the certificates, there was direction of increasingly overload them with personal information. however, by the mid-90s, is had become apparent to most institutions that identity certificates, grossly overloaded with personal information, represented severe liability and privacy problems. the approach then was to retrench to relying-party-only certificates
however, it was trivial to demonstrate that the repositories required as part of the RPO-paradigm, made any digital certificate redundant and superfluous

Certification authorities then look at branching into

1) no-value applications ... possibly internet operations that couldn't justify the cost of maintaining their own repositories and/or making online transactions

2) non-repudiation

we had been called in to help word-smith the cal. electronic signature legislation (and later the federal electronic signature legislation) ... and the lawyers involved laid down the requirements for equivalence to human signature ... i.e. indication that the human had read, understood, agrees, approves, and/or authorizes

examing x.509 standard digital signature defined processes ... it was possible to drive large aircraft carriers thru the holes with regard to non-repudiation.

part of the efforts attempting to address some of the gaps was trusted time-stamping ... and a decade ago, we actually reviewed some number of the startups getting into trusted time-stamping.

Other gaps are related to possible "dual-use" vulnerabilities ... i.e. same private key being used for normal authentication operations as well as non-repudiation operations. In numerous purely authentication implementations, the human never actually examines the bits being digitally signed. An attack pattern involves substituting legal documents for random bits (normally used in authentication operations). The countermeasure isn't appended a disclosure to every digital signed message which claims to meet human signature requirements (since that could also be faked). The actual countermeasure would either a) never use the same key-pair for both purposes and/or b) always append a disclosure on every set of bits that have been digitally signed w/o first having been directly examined by the human ... explicitly stating that the bits are being digitally signed w/o having been read (aka every authentication message will require disclosure appended to the bits before signing ... aka included as part of the signed bits).

Posted by: Lynn Wheeler at February 12, 2008 02:25 PM

The countermeasure: appending a disclosure on every signed message that is not read, only, would be inadequate, because there would then not be any default human / legal meaning to the signed messages without disclosure.

That is, there would be an implication that there was a meaning to the signature, but what would it be? "Signed?" "Seen?" "Not my department, try down the hall?"

The only way to deal with this use of public key digsigs is to wrap so much extra candy around it that (I posit) you can leave off the digsig, and it's still as strong. E.g., for public key digital signing applications, the public key is optional.

What one CA is doing is simply kicking the problem back to the user, by stating that it is in unreliable by default, in the CPS. Then, it goes on to say it is possible, but only if you follow a long list of imponderables, with a final warning that it is still not available. This might work.

Posted by: Iang at February 12, 2008 05:39 PM

the dual-use scenario was just one of the gaps that aircraft carriers could be driven thru ... and the disclaimer appended to every non-read, digitally signed, bit-string ... was at "least" required.

as in past posts about electronic signatures

there are significant other requirements for indicating that something has been read, understood, aggrees, approves, and/or authorizes (i.e. the disclaimer on non-read messages are just there to eliminate attackers spoofing claims that the bit-string had been read).

an example is pin-debit at point of sale ... digital signatures (aka demonstration of "something you have" authentication, aka possession of the respective private key) is analogous to pin entry ("something you know" authentication) at the POS terminal. However, the authentication is totally separate and independent of demonstration of human having read, understood, agrees, approves, and/or authorizes. In the POS terminal scenario ... it is the pressing of the "yes" button in response to question about agreeing to the transaction. This scenario has authentication and "human signature" equivalence as totally independent operations.

as in other posts about human signatures and digital signatures ... there apparently is lots of semantic confusion caused by both terms containing the word "signature".

Posted by: Lynn Wheeler at February 13, 2008 09:50 AM
Post a comment

Remember personal info?

Hit preview to see your comment as it would be displayed.