Non-repudiation

Non-repudiation in public-key technology is traditionally defined as the inability of a person (to whom a public key has been bound by a recognized certification authority through issuance of a public key certificate) to deny having made some digital signature.  There are problems with this concept, starting with the fact that this contradicts standard legal practice. Some of the other problems with this concept are listed below.

It should be noted that there are really two different definitions of non-repudiation: Legal and Cryptographic. This rant is about Legal Non-repudiation. Cryptographic Non-repudiation is provably achieved by all practical public-key cryptosystems. It is defined as being able to prove that if you have a digital signature that verifies with public key K, then you know that the associated private key was used to make that signature. This definition says nothing about any human who might or might not have instigated the creation of that digital signature.

It is not achievable

Non-repudiation is defined in terms of proving to a third party the intention or at least behavior of some person.  That is, Bob proves to the judge, John, that Alice intended to sign some document. Hardware and software are incapable of providing that proof.  The only thing that is proved is the behavior of some cryptographic key, buried deep in a computer system, with layers of hardware and software between whatever person is instigating the action and the action itself.  Those layers anonymize the person. They could also be under the control of some attacker. Therefore, there are opportunities for attack both physically (at the computer keyboard) and by software (through the intermediate software layers).

It may be that all the problems with non-repudiation stem from the fact that the traditional definition refers to the behavior and state of mind of a human being, but the technology is that of computers, processes and cryptographic keys. There is no provable link between the person and the computer.  There is also no hardware in the standard implementation of a public-key system to monitor the behavior of the human being and operate as a witness to the human’s actions[1]. Even if there were such hardware as part of the individual computers doing public key operations, there is no case law to establish that such hardware could offer testimony in court.

It is the product of a false syllogism

The reason that Legal Non-repudiation is not achievable is that the logic by which it was formulated is a false syllogism. The observed fact is that a person can run one program to view or create a file or a message and can run another program to use a private key to create a digital signature of that file or message. By Cryptographic Non-repudiation, anyone with that file, digital signature and public key can prove that the signature was formed over an exact copy of the file by the private key associated with the public key used in verification. The false logic is that the other steps in this process are also invertible. They are obviously not invertible.

It is counter to consumer protection law

In a transaction between a consumer and a merchant, the presumption of non-repudiation assigns presumed liability to the consumer rather than the merchant. This is exactly counter to the spirit of US consumer protection law.

It discourages e-commerce

What made e-commerce work the first time (with mail order and telephone order) was giving the consumer the right to repudiation. This is the real protection that allows a consumer to shop electronically with a feeling of safety.  It is this right of repudiation guaranteed by credit card companies that makes web shopping safe – not cryptography. [Cryptography (e.g., SSL) does almost nothing to protect the consumer. That is, the marginal utility to the consumer of using SSL over shopping without it is almost 0, when shopping with a credit card.]

It tries to take a shortcut around contract practice and law

If one were to do a contract (e.g., “I, the undersigned, will stand behind any digital transaction signed by the key whose SHA-1 hash is: ____________.”), then contract law would apply and non-repudiation would be moot.  By trying to skip that contract step, the presumption of non-repudiation is discarding a legal practice that has been carefully developed over years – without first showing that the steps being discarded are superfluous.

It is in conflict with good key management

Whether key management is implemented by CRL or an online validation service, the issuer of the CRL or the validation service needs to learn that a key needs to be revoked.  That service is not omniscient. This knowledge has to come from somewhere.

  1. If the person who steals a private key were to publish that fact immediately, then the validation service would learn from the thief and revocation would be straight-forward. However, the attacker is not likely to make that announcement. Rather, the attacker is likely to use the stolen key in secret.
  2. If the attacker were to distribute the stolen key widely, then from the massive increase in usage of that one key, those accepting the key might conclude that the key had been stolen and cloned.  This can be seen as another form of publication.
  3. If the attacker keeps the stolen key to himself and uses it personally and sparingly, the only way to detect this misuse is for the proper keyholder to review an audit log of uses of that key, find items that are bogus and infer from those that the private key was stolen or the attacker had found a channel to the private key so that it could be misused.  That proper keyholder can then announce to the validation service that the given key can not be trusted.  This assumes, however, that there is an audit log of all key uses and that the proper keyholder reviews that log.
  4. If there is no audit log of all key uses (the normal case), then the proper keyholder learns of an improper use of a key when the other party in a transaction reveals the use of the key (e.g., a signed purchase order) and demands some further action. This is the time when the other party cares the most about non-repudiation. However, this might be the first time that the proper keyholder has any evidence that the key was misused and the proper keyholder needs to react to this discovery by
    1. repudiating that earlier transaction, and
    2. announcing to the validation service that that signature (perhaps plus those after some transaction before the one discovered to be bad) was a forgery.
Carl Ellison; cme@acm.org

[1] ..such as, for example, the TV camera that is part of an ATM, recording the face and behavior of the person at the keyboard and card reader of the ATM