On Signatures

Let’s (just) encrypt!

In the early days of public key cryptography, it perhaps wasn’t as widely appreciated as it is today that just encrypting your messages doesn’t cut it.

In the cryptography folklore, we have Eve and Mallory, who are always interfering with poor Alice and Bob. Eve just likes to listen. Eve does not like encryption, obviously.

Mallory is a bit more mischievous, and actually wants to mess with what Alice and Bob are saying. Mallory’s role is that of Man-in-the-middle, or, more usually, MITM. And encryption just isn’t good enough when Mallory is there.

The problem could be illustrated with an oversimplified example. Alice sends to Bob the message “$100 from Mallory”. But Mallory gets it first, receiving “R$IJOR@4rfsdfDF#E” (it being encrypted and all). Mallory doesn’t know what it says, but has a pretty good idea, so he just decides to send “R$IJOR@4rfsdfDF#E” to Bob – twice. Now Bob, being remarkably dull, interprets the received “$100 from Mallory $100 from Mallory” as indicating that $200 has been received, and promptly sends $200 of goods to Mallory.

If this seems ridiculous, it is (for example the same plaintext does not result in the same ciphertext, which is required for this attack, in all except the most woefully insecure systems), but not the “Bob is dumb” part – remember, Bob could be a web server.


Oh, OK then. But we can use digital signatures, right?

Screenshot from 2015-03-14 04:30:57
dat’s me, dat is.

So to get any kind of use out of encrypted communications, you have to have two other properties – authentication and integrity. You have to know who’s talking to you, and that their message hasn’t been chopped up or swapped around. So, that means we need digital signatures, right? I’m guessing anyone reading this has “done” digital signatures 101, but for those not too sure, a reminder that they’re based on the use of a public and private key pair – you know that the owner of the private key corresponding to the public key was the one who did the signing. This does replicate the property of old-fashioned handwritten signatures. If you signed it, I can take it to court and show people that you signed it.

Now here’s why this is relevant. Consider the problem of proving that you received a webpage from VeryImportantSite.com. If they wanted to, the owners of veryimportantsite could attach a digital signature to the page. Then, you could pass this page around to anyone, or take it to court as mentioned, and say, look – that website is the one who signed it, because this signature verifies against their public key. You could point to the certificate info found by clicking on the padlock in your web browser, and get the public key right there.

Why don’t organisations such as banks seem to do this much?

One possible reason is the property of repudiability. Alice wants to tell Bob a secret, but she doesn’t want him to be able to spread it around and prove that Alice said it. This gets very muddy because it’s where the crypto rubber hits the real world road. Might a signature imply a particular legal liability?

While that part is conjecture, here is what is fact: digital signatures are non-repudiable up to the non-repudiability of the public key identity, which is pretty damn non-repudiable in the case of website server certificates for big commercial or governmental entities.

So if you’re paying attention, you’ll have noticed a slight contradiction – to get encryption that’s worth a damn, you need authentication. To get authentication you need digital signatures, but people/business hardly ever use them. So what do they use?


You did not hear this from me…

Enter stage left: HMAC. In ELI5 mode, HMAC is basically a little bit of data created from a message that you could only have generated if you knew a secret. And this is what TLS uses for authentication and integrity. Your browser may well have downloaded 20 bytes of HMAC data once or twice to verify this blog post. But here’s the kicker – HMAC does not give non-repudiability, because in order to check the HMAC, you don’t use a public key recorded in everybody’s browser or on some database – instead, you use part of the secret data that was negotiated in the TLS handshake at the start – in other words, you use a secret that only Alice and Bob were privy to at the time the message was sent.


Looks legit.

If you’re with me so far, you’re probably coming to the conclusion that the way things are isn’t that surprising. When you realise the non-repudiability feature of digital signatures is a little bit ‘heavy’, it makes sense that the security protocol we use on the internet doesn’t have it baked in by default. However, it’s still very surprising that it isn’t used in more situations. The most obvious one is proof of identity or income or residence that is so often required by so many institutions for so many reasons. Why can’t a government website that verifies your professional licensing simply sign the information, so that it’s actually useful!? After all, you already know that you’re a qualified doctor! This kind of thing gets dealt with at the level of stamps, handwritten signatures, crappy embossed paper and jpg scans, which would be alright if we didn’t have, you know … digital signatures! To be fair, there are cases out there where digital signatures are being used in intelligent ways, but they’re quite rare.


Non-repudiable-ish HMAC?

How does TLSNotary fit in? Well, you could look at it either as a stopgap or a disintermediation. You don’t necessarily need a trusted institution to be giving a non-repudiable digital signature to convince someone else of the facts or secrets that the institution attests to. You simply involve a third party in the process of generating secrets such that (a) the third party doesn’t know the secrets, but (b) you don’t know *all* the secrets either, at least not to start with. It’s like this:

In TLSNotary, the auditor doesn’t let you verify the HMACs at the start. You pull in the encrypted data, but you don’t yet know that Mallory hasn’t inserted an extra “$100 from Mallory” into the stream. So at that point, the data you’ve got sitting on your disk is not safe – you don’t know it’s genuine, and neither does the auditor. But you use a well known trick – the cryptographic commitment. Send a sha256 (or any other) hash of the encrypted data to the auditor. After that, you can’t cheat or lie. The auditor sends back the secret material and you can generate the HMAC key, allowing you to authenticate the server you’re talking to. Then you’re back to TLS normality; but the auditor will only believe your HTML page if it matches the original hash commitment.

The result is – non-repudiability becomes fuzzy. You can prove to one other person, at least, what the institution said. And it is possible, perhaps, to go further – but that’s for another post.