Alice signs a letter: metonymy and computer security

Digital signature algorithms are a very clever idea. Suppose that Alice wants to send a letter to Bob so that Bob can be confident it comes from her, not someone else. It works like this. Alice’s message can be thought of as a large number – that’s how computers represent all information, after all. This number can be turned into a shorter hash number H, perhaps 128 binary digits, using a hash function, a complicated mathematical operation that is effectively impossible to reverse. If the hash function is well-designed, no-one else can make a new message with the same 128-bit summary. The 128-bit hash is then encoded with Alice’s private key, a secret number known only to Alice. The RSA algorithm, for example, involves computing an encoded version

where D is Alice’s secret key and n is part of her public key. Alice sends the encoded version to Bob, who can reverse the encoding using Alice’s public key (E,n) by computing

and check that the 128-bit hash matches the original message. Even though Bob knows Alice’s public key he can’t work out the private key and forge her signature.

At this point you might be thinking one of several things

1. if you’ve never heard of public key encryption: “That doesn’t sound possible”

2. if you know a bit about public keys “When will we be able to vote this way?”

3. if you’re a bit more sophisticated: “So where does Bob get Alice’s public key?”

Surprisingly few people think “Gee, Alice sure is good at math”.

The computer security writers are using a rhetorical device called metonymy, in which they say “Alice raises this huge number to this large power”, when they really mean “Alice’s computer raises this huge number to this large power”. If someone points this out we all understand what’s going on, just as we don’t take it literally when Tom Brokaw says “The White House had no comment on this issue”. The danger of this particular metonymy is that a lot of writing on digital signatures consciously or unconsciously sweeps it under the carpet.

If Alice creates a hash of her message, encodes it with the RSA algorithm, and sends it to Bob, we can be confident that she meant to sign the message. If Alice is the only person who knows the key, the message couldn’t have come from anyone else. The digital signature really is like a signature. If Alice’s computer does the work then we don’t know what Alice intended. We do know that Alice isn’t the only one who knows the key – in a lot of schemes Alice doesn’t know the key at all, she just knows how to get it out of her computer.

Why is this metonymy particularly worrying for computer security? After all, when Alice’s fax machine sends a message to Bob’s fax machine we are happy to say “Alice faxed Bob the letter”. The problem lies in the nature of general-purpose computers. Alice trusts her fax machine to transmit the document she puts in the feeder. This works because fax machines are really, really dumb. They don't have the ability to make up new documents to send. Computers (or their software) are smarter. Viruses, Trojan Horses, or crackers breaking into Alice’s computer can wait until she is about to sign the message and then substitute a resignation letter, or a bank transfer, or a vote for Pat Buchanan.

A legally enforceable digital signature scheme means, then, that you are legally responsible for the actions of your computer. This is the computer that crashes just as you are about to save a document, that loses your files or corrupts your databases, that sends ILOVEYOU letters to everyone in your address book. I’m not planning to give my PC power of attorney over my affairs, and if Alice wants to send me a message she can use Western Union.