Non-Repudiation, and Digital Signatures

Using cryptography, we can add four powerful features to just about anything we produce in the digital world. They are:

  • Authenticity
  • Integrity
  • Non-Repudiation, and
  • Confidentiality

These aren’t new concepts, but I’ve run into a few discussions where the terminology is used wrong, or the understanding of the limits of these features is wrong. Especially when it comes to Non-Repudiation.

I think the best way to illustrate these concepts is through examples. Let’s start with sending an email that looks like this:

1
2
3
To: The Accountant <accounts@company.com>
From: Tim <tim@company.com>
Message: Please transfer $1,000,000 from our bank account to this account: 123-123 12345678

On it’s own, this email looks pretty straightforward. You can see who sent it, and who it’s meant to go to. But just by itself, you don’t have:

  • Assurance of who sent it. Yes, the “From” field has “Tim \<tim@company.com>“ inside of it, but someone else could’ve faked that.
  • Integrity of the message. The message might’ve actually said “Please transfer $1,000 from our bank account to this account: 123-123 87654321”, but there’s no way of knowing if it was changed.
  • Non-Repudiation for the message. Even if the message was correct, I could later argue that someone broke into my email account and sent that message instead.
  • Confidentiality of the message. Anyone listening could’ve intercepted and read the message contents.

So how does cryptography help? The first step is we can add a Digital Signature to the message.

Digital Signatures

Adding a Digital Signature would change the message to look something like this:

1
2
3
4
To: The Accountant <accounts@company.com>
From: Tim <tim@company.com>
Message: Please transfer $1,000,000 from our bank account to this account: 123-123 12345678
Signature: A1B2C3D4E5F6A7B8C9D0E1F2A3B4C5D6E7F8...

The Digital Signature is not an electronic signature, despite the similar name to Digital Signature:

  • An Electronic Signature is just like an ink, or “wet”, signature on a document - it’s just in electronic format so you don’t have to print out a document, sign it, and scan it again. Services like DocuSign provide electronic signatures, not digital signatures.
  • A Digital Signature is a special piece of data created using cryptography to provide Authentication, Integrity, and maybe Non-Repudiation to a document.

How to Make a Digital Signature - Hashing

Digital Signatures are made by first taking a fingerprint of the document, also called a “hash”, which is a short piece of data that can uniquely identify the document.

If I fingerprint, or hash, this message:

1
2
3
To: The Accountant <accounts@company.com>
From: Tim <tim@company.com>
Message: Please transfer $1,000,000 from our bank account to this account: 123-123 12345678

I get the fingerprint, or hash:

1
07caa1dab6b0a9ca4bc76757a50a12464d9b8c6cea08343f80b42520ed12f837

If I then change one single letter in that message, for example the last digit in the bank account number:

1
2
3
To: The Accountant <accounts@company.com>
From: Tim <tim@company.com>
Message: Please transfer $1,000,000 from our bank account to this account: 123-123 12345679

The fingerprint, or hash, is totally different:

1
fc33f0c2b1731da5691350c29beaadbdd4ffab75d18f553a966772caaa16c7cd

It’s really obvious how different they are when they’re side by side:

1
2
Hash 1: 07caa1dab6b0a9ca4bc76757a50a12464d9b8c6cea08343f80b42520ed12f837
Hash 2: fc33f0c2b1731da5691350c29beaadbdd4ffab75d18f553a966772caaa16c7cd

So by hashing a document, we know immediately if any part of it changes.

If you sent a document with it’s hash included, it would look like this:

1
2
3
4
To: The Accountant <accounts@company.com>
From: Tim <tim@company.com>
Message: Please transfer $1,000,000 from our bank account to this account: 123-123 12345678
Hash: 07caa1dab6b0a9ca4bc76757a50a12464d9b8c6cea08343f80b42520ed12f837

The Accountant could check to see if the hash matched, but there’s nothing stopping someone changing that bank account number and updating the Hash value to make the message still look correct:

1
2
3
4
To: The Accountant <accounts@company.com>
From: Tim <tim@company.com>
Message: Please transfer $1,000,000 from our bank account to this account: 123-123 12345679
Hash: fc33f0c2b1731da5691350c29beaadbdd4ffab75d18f553a966772caaa16c7cd

What we want to have is the hash sent with the email, and The Accountant to know that it wasn’t changed by somebody else. This is where Cryptography plays its part.

How to Make a Digital Signature - Signing

So, I have the hash of the document created, next I need to turn it into a digital signature. What does this actually mean?

First, I take the hash:

1
07caa1dab6b0a9ca4bc76757a50a12464d9b8c6cea08343f80b42520ed12f837

And then I encrypt it. We don’t have to know exactly how encryption works, but just know that the hash can now only be decrypted if you have the correct key. This is what the encrypted hash now looks like:

1
2b02e024f2293bb07eaa314cc7e074da830f15b73a30ef126173b6f8d973e449366cb50feeedae33a58381301e4058f2ce49aafc931b97c1e93bea9bd19665aa6025e4c61df1107197c3ca801d583e02

This is a Digital Signature.

If put that encrypted hash onto the email, along with a key that The Accountant can use to decrypt the Digital Signature, then I have a message that looks like this:

1
2
3
4
5
To: The Accountant <accounts@company.com>
From: Tim <tim@company.com>
Message: Please transfer $1,000,000 from our bank account to this account: 123-123 12345679
Signature: 2b02e024f2293bb07eaa314cc7e074da830f15b73a30ef126173b6f8d973e449366cb50feeedae33a58381301e4058f2ce49aafc931b97c1e93bea9bd19665aa6025e4c61df1107197c3ca801d583e02
Key: 101112131415161718191a1b1c1d1e1f

The Accountant can then decrypt the Signature to see the hash, and then hash the email themselves, and see if the hash I sent and the hash they made are the same. If they are, then the message is exactly the same as I sent it.

This is a little simplistic view of the Encryption side of things, but it’s just to illustrate the point. In reality we use Public Key Cryptography to encrypt the hash so we can safely send the key with it.

Authenticity and Integrity

So this email signing process gives us only two security features. We get Integrity because we can now see if the message has changed at all. We get Authenticity because we know who sent the message to us by the keys they used.

We still haven’t got Non-Repudiation or Confidentiality though.

Achieving Non-Repudiation

Let’s start with defining Non-Repudiation. In fact it also has another name that might make more sense: Content Commitment. If someone wants to repudiate a message, it means they are denying that they sent it. It can also mean that the recipient denies that they received it, but that’s a little more rare and harder to deal with.

In the physical world, non-repudiation is usually handled by having important signatures on documents witnessed by trusted people, like Police Officers, Medical Personnel, Public Officials, etc. In this way, if you try to deny you ever signed the document, then the witness can be brought forward to say “No your honour, I was there, and saw him sign it!”.

To get a digital message to the point where you can say there is Non-Repudation on it, you need to be certain that the sender, and only the sender, has control of their cryptographic keys, you know who the sender is, and if they lose control of their keys, then there needs to be a way to prevent those keys being used ever again.

Key Storage

To keep control over cryptographic keys, we can use a bunch of different tools. Inside most computers now there are special cryptographic chips that let you store keys and never be able to take them out again. Products like Yubikeys are smart cards (just like the chip in credit cards) that also let you store keys safely. Most of the major smart phones have chips like these too.

Keys just sitting on your hard disk or drive, or protected by a password only, are not stored safely enough for non-repudiation.

The basic requirements for key storage to achieve non-repudiation are:

1) That the key is stored somewhere that prevents it being copied.
2) That the key is stored somewhere that can resist tampering.
3) That the key can only be used if the owner knows the correct password, and only the owner knows that password.

Some examples of key storage that can’t achieve non-repudiation:

  • Stored encrypted in a file, like how a lot of web servers store their TLS Certificates - someone can steal the file at any time and try to break into it without you knowing.
  • Stored within the Windows Certificate Store, or Apple Keychain - someone could guess your password correctly, and steal the certificates without you knowing.
  • Burned onto a CD and locked in a safe - if someone manages to take a copy of the contents of the CD, then you again have no idea that it happened and they have all the time in the world to try to break into it.

Identity Proofing

You may have gone to all the effort to protect how your keys are stored, but the other side of achieving non-repudiation is that you need to have assurance that the owner of the keys is who they say they are.

Consider the example from before of the non-digital approach to non-repudiation. Sometimes you need to present your photo identity documentation to the witness so they can have an assurance that you are who you say you are before witnessing your signature.

The same applies to the digital world. If you’re providing cryptographic keys to people that can be used for non-repudiation, you need to be certain that the owner of the keys is who they say they are before you give them the keys. Otherwise anyone can say they’re anyone, and everything becomes meaningless.

This is where things get complicated. Generally you’ll need to perform some sort of identity proofing process, but that process needs to be defined. Most countries have an identity proofing process documented (e.g. show your birth certificate, driver’s licence, and passport), and some sort of accreditation process for organisations to undergo to prove that they’re following the proofing process correctly.

To be certain that an email is sent and signed by tim@company.com, and not someone who’s managed to pretend to be Tim and been given those keys, a high level of trust needs to be put in the authority that issues those keys.

Revocation

The final requirement for non-repudiation is that you need to have a way to revoke uncontrolled keys. It’s all well and good that you’ve satisfactorily identified the owner of the keys, and they’ve kept them protected in proper storage, but then they’re forced to give up the password with a rubber hose, then the non-repudation assurance is useless.

If someone loses or is forced to give up their keys, then they should be able to report this to an authority to have those keys revoked, so that everyone who tries to verify messages using those keys from now on won’t trust them any more.

Achieving Confidentiality

So you’ve gone to all the effort to set up credentials that provide Authentication, Integrity, and Non-Repudiation. You still don’t have Confidentiality though.

In fact, you shouldn’t really mix Confidentiality with the others. Especially Non-Repudiation. Encrypting entire messages is generally something you do to stop someone else reading it, and then you decrypt them later, sometimes several times like if you’re reading an old encrypted email years after you received it.

This means that you then need to hold on to your encryption keys for a long time, and back them up somewhere safe in case you lose them. This goes against all of the other features, especially non-repudiation, because if you lose control of a key that’s used for Digital Signatures, you should revoke it and just get a new one.

For completeness sake, if we were to add confidentiality to our email from before, we would first generate an encryption key (for example: 202122232425262728292a2b2c2d2e2f - that’s right, keys are just random numbers), and then encrypt the whole message so it goes from:

1
2
3
4
5
To: The Accountant <accounts@company.com>
From: Tim <tim@company.com>
Message: Please transfer $1,000,000 from our bank account to this account: 123-123 12345679
Signature: 2b02e024f2293bb07eaa314cc7e074da830f15b73a30ef126173b6f8d973e449366cb50feeedae33a58381301e4058f2ce49aafc931b97c1e93bea9bd19665aa6025e4c61df1107197c3ca801d583e02
Key: 101112131415161718191a1b1c1d1e1f

To:

1
d835e80c06dd108b550fbaac466e81a5ebd483fb30e3bd948843b64259e50863d006a7747a92706e9240f9439e9d0738a7c06cc2e31969205b98f55b5f267faaaaf0db72d0c42b410b9aeca050825d12cb74fce0cc2887961e1febaaccb37176ff7d5c0c4c242222db6b6768056077b436125244108b0ddc6cc99efd5cbfa54e97f68f10a9f8702caa3df0506393c7df488102c8bd68cb66fc81473e25f039010135afcdfaf586a4fbec9cb1c167641819c41cc198e68abcf6bffa5cdc56c833db47a872426cd227ccfea5a55c4a04697a1949e089d3caeeb55efcd305538ed0deb4f1f98d5741bd00ede49fe026e955860cc60c12311c7f5aaf78db393b6164f10f301e891974688294e03059bb18f9192d733cf123b51b05895e4ae47348a15a6f0d7bd3163f059106fcd5b57bd0140ec42a033d395245b8a3b48636a3875783ae94d44602802649eb3f2b130661778d98ee3f385838282eb14307d47c569cc29f32974fa0314e5b5c4286dd5405dcd88bb06be8436c1e475f1299a4a01b60

So you can see now it looks like total nonsense, and no-one can look at the message unless they know what the encryption key is.

The Answer to Non-Repudiation

In conclusion, to be able to create and use credentials that provide everything including Non-Repudiation, a Public Key Infrastructure (PKI) is the right tool for the job combined with something to store credentials securely (like Smart Cards).

PKI isn’t the only solution, but it is the most battle-tested and fully functional approach available today. The criticisms of it are entirely valid (especially the expense and complexity to do it properly), but I’m still waiting for the replacement solution to appear.

If none of this made sense, at the very least these are the rules that must be remembered:

  • You cannot have Non-Repudiation unless the credentials are stored securely.
  • You cannot have Non-Repudiation unless you know for certain who owns the credentials.
  • You cannot have Non-Repudiation unless the credentials can be revoked.