Introduction on Non-Repudiation and Digital Signature

Non-repudiation is a much desired property in the digital world. This article describes that property and shows how it can be achieved by using digital signatures.

Defining the problem

Digital documents are ubiquitous. Having received a document, we want to make sure that:

  1. The sender is really the one who claims to be the sender of the document. 2. That exact document was sent by the sender: it hasn’t been modified on the way to the receiver. Let’s first discuss how hashing can be used to achieve the integrity of the document.

Hash

The hash of document D is denoted by H(D). The ideal hash function is irreversible, and there are no two different documents D1 and D2 such that H(D1)=H(D2) . The longer the hash, the less likelihood of an occurrence of collision. Collision takes place when the same hash is created for two different documents. Hashing is used to achieve data integrity and there’s no key involved. What we also need is authentication of the sender.

HMAC

Let’s assume that Mark is going to send the document to Kevin, and they share a key. HMAC is a hash of the document and the key. Mark calculates HMAC, appends it to the document and sends it to Kevin. Kevin calculates the HMAC: hash of the document he received and the key he shares with Mark. Then, Kevin compares the HMAC with the HMAC appended to the document. When they match, Kevin knows that it was Mark who sent this document. When the attacker (man-in-the-middle) changed the document and HMAC, it’d be detected by Kevin: the attacker doesn’t know the key. That way, data integrity and authentication can be verified by Kevin. HMAC is used to provide data integrity and authentication. The problem is that HMAC doesn’t provide non-repudiation, because Mark and Kevin share the key. How can we solve this problem? A digital signature is the solution.

Digital signature

First, one needs to know the relationship between the keys in asymmetric cryptography (the public and the private) in order to understand how digital signatures work. The public key is available to everyone. The private key is known only by the owner and can’t be derived from the public one. When something is encrypted with the public key, only the corresponding private key can decrypt it. Moreover, when something is encrypted with the private key, then anyone can verify it with the corresponding public key. Now, let’s return to the story of Mark and Kevin to better understand how it works. Mark’s private key is used to encrypt the hash of the document. That encrypted hash is called a digital signature. Mark sends Kevin the document with the appended digital signature of the document. Kevin uses Mark’s public key to decrypt the digital signature. Then, Kevin calculates the hash of the document and compares it to the decrypted digital signature of the document, which is the hash of the document. When those hashes match, Kevin knows who the sender of the message really is, and exactly which message was sent. The property of non-repudiation is achieved by using a digital signature. There’s one question remaining. How does Kevin know that the public key is really the one from Mark? There might be a man-in-the-middle introducing themselves as Mark. A digital certificate is used to solve that problem. Kevin gets the digital certificate from Mark, which includes Mark’s public key and his name. The certificate is digitally signed by the trusted Certificate Authority (CA) – the hash of the certificate is encrypted with the private key of the trusted CA. Kevin has the list of trusted CAs (with their public keys) in his operating system. It allows Kevin to verify that the public key actually belongs to Mark.

Storing the private key

Once the private key of Mark is stolen, the security is broken. Then, Mark isn’t the only one who knows his private key, and non-repudiation isn’t established. That’s why the private key needs to be securely stored. Complexity is the worst enemy of security. Thus, personal computers and smartphones aren’t a good choice for storing private keys. We need something dedicated. It’s recommended to store private keys on smart cards to minimize the risk of them being stolen. Private keys don’t leave smart cards when digital signatures are being created.

Summary

In the digital world, we want to verify who’s really the sender of the document, and which document was sent by the sender (the man-in-the-middle might have changed the document on the way to the receiver). In other words, we want to adhere to the property of non-repudiation. HMAC is used to provide data integrity and authentication. It doesn’t provide non-repudiation, because it involves using the key, which is shared by communicating entities. Digital signatures are used to provide non-repudiation. Security is broken when private keys are stolen. That’s why private keys should be stored on smart cards to reduce the risk of them being stolen.