Alice and Bob Sign Messages

Alice and Bob can send messages privately via a nosy postman, but how does Bob know that a message he receives is really from Alice, rather than from the postman pretending to be Alice?
If they’re using symmetric-key encryption, and Bob is sure that he was talking to Alice when they exchanged keys, then he already knows that the mail is from Alice – as only he and Alice have the keys that are used to encrypt and decrypt messages, so if Bob can decrypt the message, he knows that either he or Alice encrypted it. But that’s not always possible, especially if Alice and Bob haven’t met.
Alice’s shopping list is longer for signing messages than for encrypting them (and the cryptography to real world metaphors more strained). She buys some identical keys, and matching padlocks, some glue and a camera. The camera isn’t a great camera – funhouse mirror lens, bad instagram filters, 1970s era polaroid film – so if you take a photo of a message you can’t read the message from the photo. Bob also buys an identical camera.
sign1
Alice takes a photo of the message.
sign2
Then Alice glues the photo to one of her padlocks.
sign3
Alice sends the message, and the padlock-glued-to-photo to Bob.
sign4
Bob sees that the message claims to come from Alice, so he asks Alice for her key.
sign5
(If you’re paying attention, you’ll see a problem with this step…)
Bob uses Alice’s key to open the padlock. It opens (and, to keep things simple, breaks).
Bob then takes a photo of the message with his camera, and compares it with the one glued to the padlock. It’s identical.
sign6
Because Alice’s key opens the padlock, Bob knows that the padlock came from Alice. Because the photo is attached to the padlock, he knows that the attached photo came from Alice. And because the photo Bob took of the message is identical to the attached photo, Bob knows that the message came from Alice.
This is how real world public-key authentication is often done.

  • Alice generates a key pair, consisting of her public key (blue key) and private key (not shown here, but it’s how she acquires the blue padlock)
  • Alice takes a cryptographic hash of the message she wants to sign (the photo) using a commonly known hash algorithm (the funhouse cameras that both alice and bob have)
  • Alice encrypts the cryptographic hash with her private key, creating a signature for the message (the padlock with attached photo)
  • Alice sends the message and the signature to Bob (they can be sent separately, but the signature is almost always attached to the message to create a signed message)
  • Bob fetches Alice’s public key (the blue key)
  • Bob takes a cryptographic hash (photo) with the same algorithm that Alice used (identical funhouse camera)
  • Bob validates the signature against the hash (unlocks the blue padlock) with Alice’s public key

Some things to note:

  • The message was publicly visible – there was nothing to stop the postman reading it. You could use encryption to protect it, but that’s a separate process – encryption and signing are orthogonal. You can encrypt, or you can sign, or you can do both.
  • We inverted what the keys and padlocks mean compared to the last Alice and Bob story. Today the key is Alice’s public key, last time it was Bob’s private key.
  • The key pair for signing messages is generated in exactly the same way as the one used for encrypting messages. It’s very common to use the same key pair for both signing and encryption. When you send a signed, encrypted message to someone else you sign it with your private key and encrypt it with their public key. When your recipient receives the message they decrypt it with their private key and validate the signature with your public key.

How does DKIM use this to sign messages?
The algorithm (funhouse camera) that’s used to generate the hash is defined in the DKIM-Signature header by the c= and a= headers (there are several steps, but the final one is the cryptographic hash proper, typically SHA256). The hash (photo) is stored in the bh= field of the DKIM-Signature header, and the signature itself (padlock-with-photo) is stored in the b= field. The recipient uses the d= header to find out who signed the message, and retrieves the signers public key (blue key) via a DNS lookup. Then they use that public key to validate via RSA the signature (unlock the padlock). They then normalize and hash the message in the same way as the sender did, and confirm that the hashes match.
There’s a more detailed description at dkimcore.org and the formal specification is in [rfc 4871].
About that problem …
There’s a huge hole in the process as described. When Bob retrieves Alice’s public key, how does he know it wasn’t tampered with en-route? If an attacker, Mallory, has access to the communication channel he can send a message claiming to be from Alice but signed with Mallory’s private key. When Bob requests Alice’s public key Mallory can intercept that too, and replace it with Mallory’s public key. That signature will validate, and Bob will believe that the imposter message he received from Mallory really came from Alice.
There are several solutions to that. The simplest is to rely on a supposedly more secure channel to retrieve a public key with. That’s the approach DKIM uses to sign messages, relying on the integrity of the domain name system to publish the senders public key. That’s really not terribly secure, as there are lots of ways to compromise DNS. But it’s simple and it’s “good enough” for DKIM’s purpose – being able to bypass some spam or phishing filters by masquerading as someone else isn’t a particularly valuable target. That’ll get more secure as DNSSEC support is deployed more widely. (If your DNS isn’t protected by DNSSEC you should probably put it on your medium-term list of things to consider.)
Another approach is to use a web or hierarchy of trust. But that, and certificates, is another article.
 

Related Posts

May 2014: The month in email

It’s been a busy and exciting month for us here.
Laura finished a multi-year project with M3AAWG, the Messaging, Malware and Mobile Anti-Abuse Working Group (look for the results to be published later this year) and continued working with clients on interesting delivery challenges and program opportunities. Steve focused on development on the next version release of Abacus, our flagship abuse desk tool, which will also be available later this year.
And as always, we had things to say about email.
The World of Spam and Email Best Practices
We started the month with a bit of a meta-discussion on senders’ fears of being labeled spammers, and reiterated what we always say: sending mail that some people don’t want doesn’t make you evil, but it is an opportunity to revisit your email programs and see if there are opportunities to better align your goals with the needs of people on your email lists. We outlined how we’ve seen people come around to this position after hitting spamtraps. That said, sometimes it is just evil. And it’s still much the same evil it’s been for over a decade.
We also wrote a post about reputation, which is something we get asked about quite frequently. We have more resources on the topic over at the WiseWords section of our site.
Gmail, Gmail, Gmail
Our friends over at Litmus estimate Gmail market share at 12%, which seems pretty consistent with the percentage of blog posts we devote to the topic, yes? We had a discussion of Campaign Monitor’s great Gmail interview, and offered some thoughts on why we continue to encourage clients to focus on engagement and relevance in developing their email programs. We also wrote a post about how Gmail uses filters, which is important for senders to understand as they create campaigns.
SMTP and TLS
Steve wrote extensively this month about the technical aspects of delivery and message security. This “cheat sheet” on SMTP rejections is extremely useful for troubleshooting – bookmark it for the next time you’re scratching your head trying to figure out what went wrong.
He also wrote a detailed explanation of how TLS encryption works with SMTP to protect email in transit, and followed that with additional information on message security throughout the life of the message. This is a great set of posts to explore if you’re thinking about security and want to understand potential vulnerabilities.
DKIM
Steve also wrote a series of posts about working with DKIM (DomainKeys Identified Mail), the specification for signing messages to identify and claim responsibility for messages. He started with a detailed explanation of DKIM Replay Attacks, which happens when valid email is forwarded or otherwise compromised by spammers, phishers or attackers. Though the DKIM signature persists (by design) through a forward, the DKIM specification restricts an attacker’s ability to modify the message itself. Steve’s post describes how senders can optimize their systems to further restrict these attacks. Another way that attackers attempt to get around DKIM restrictions is by injecting additional headers into the message, which can hijack a legitimately signed message. If you’re concerned about these sort of attacks (and we believe you should be), it’s worth learning more about DKIM Key Rotation to help manage this. (Also of note: we have some free DKIM management tools available in the WiseTools section of our site.)
As always, we’re eager to hear from you if there are topics you’d like us to cover in June.

Read More

Cryptography with Alice and Bob

Untrusted Communication Channels
This is a story about Alice and Bob.
Alice wants to send a private message to Bob, and the only easy way they have to communicate is via postal mail.
closedletter
Unfortunately, Alice is pretty sure that the postman is reading the mail she sends.
openletter
That makes Alice sad, so she decides to find a way to send messages to Bob without anyone else being able to read them.
Symmetric-Key Encryption
Alice decides to put the message inside a lockbox, then mail the box to Bob. She buys a lockbox and two identical keys to open it. But then she realizes she can’t send the key to open the box to Bob via mail, as the mailman might open that package and take a copy of the key.
Instead, Alice arranges to meet Bob at a nearby bar to give him one of the keys. It’s inconvenient, but she only has to do it once.
lockstore
After Alice gets home she uses her key to lock her message into the lockbox.
shared1Then she sends the lockbox to Bob. The mailman could look at the outside, or even throw the box away so Bob doesn’t get the message – but there’s no way he can read the message, as he has no way of opening the lockbox.
shared2
Bob can use his identical key to unlock the lockbox and read the message.
shared3
This works well, and now that Alice and Bob have identical keys Bob can use the same method to securely reply.
Meeting at a bar to exchange keys is inconvenient, though. It gets even more inconvenient when Alice and Bob are on opposite sides of an ocean.
Public-Key Encryption
This time, Alice and Bob don’t ever need to meet. First Bob buys a padlock and matching key.
public1
Then Bob mails the (unlocked) padlock to Alice, keeping the key safe.
public2
Alice buys a simple lockbox that closes with a padlock, and puts her message in it.
public3
Then she locks it with Bob’s padlock, and mails it to Bob.
public4
She knows that the mailman can’t read the message, as he has no way of opening the padlock. When Bob receives the lockbox he can open it with his key, and read the message.
public5
This only works to send messages in one direction, but Alice could buy a blue padlock and key and mail the padlock to Bob so that he can reply.
Or, instead of sending a message in the padlock-secured lockbox, Alice could send Bob one of a pair of identical keys.
publichared
Then Alice and Bob can send messages back and forth in their symmetric-key lockbox, as they did in the first example.
shared2
This is how real world public-key encryption is often done.

Read More

DKIM replay attacks

Replay attacks on DKIM signed messages
When you receive an email validly signed with DKIM by example.com that might not mean that example.com sent the email to you, or that they even sent this email at all.
What it does tell you is that at some point in the past, example.com signed an email with exactly the same headers and body and sent it to someone. That’s often close enough to the same thing. But if that original recipient were to resend the email to you completely unchanged then the DKIM signature would still validate when you received it. That’s not a bug; it’s one of the design features of DKIM that it typically survives mail forwarding.
That original recipient could also forward the exact same email to a million of their closest friends, and the DKIM signature would validate at each of those million recipients ISPs. This is one form of a replay attack, and it isn’t something DKIM prevents.
DKIM doesn’t prevent replay, but does mitigate it
Completely eliminating replay attacks over SMTP is difficult – it’s inherently a store-and-forward protocol, so there’s no way to have the sender and recipient do any sort of handshake to ensure that a particular signature is only used once. It’s not unheard of for email to be delayed for days, and delays of hours aren’t unusual, so allowing a signature to be valid for only a few seconds after it’s sent won’t work. And the design requirement that DKIM signature survive forwarding means that it has to survive the final recipient’s email address not being the same as the email address the mail was originally sent to so you can’t include the envelope recipient in the signature.
So what does DKIM do to mitigate replay attacks? The answer to that is surprising – almost everything DKIM does is there to mitigate them. The DKIM signature depends on the body of the message, the subject line and the content of any other headers the sender chooses to include; changing any of that will invalidate the signature. That means that while anyone can grab a copy of an email sent by, for example, paypal and forward it on to someone else, if they modify the content at all it will no longer have paypal’s signature. So an attacker can’t just grab someone else’s signed email and replace it with modified content – and if they can’t do that, where’s the benefit to a spammer or phisher to replay a message?
But all that work is for naught if you allow the attacker to choose the content before you sign the message. There are several ways an attacker can do that, but one example that’s particularly relevant today is ESP trial accounts.
I’m stealing your reputation
If you allow anonymous signups for trial accounts that let a potential customer try out your system you’ll want to put very tight limits on how it can be used, so as to avoid spammers signing up and spamming through your servers. Maybe you’ll limit the number of email addresses the trial user can upload, or the number of emails they can send. At the most extreme you might even limit the trial account to sending mail solely to the trial users own (confirmed) email address.
But if an attacker can send even one piece of email they create through your trial account to themselves, and you sign that email, they can take it and send it to a million recipients – and it’ll still have your DKIM signature on it so it’ll use your reputation to avoid filters and end up in the recipients inbox. And then the recipients will report it as spam, and all that spam will be counted against the reputation associated with your DKIM identifier. If you share a DKIM identifier (“d=”) across all your customers that could cause all your customer mail to start being rejected or sent to the spam folder. (Even if you don’t it could still affect your delivery negatively, as spam filtering systems – both automated and human – sometimes aren’t entirely rational or predictable).
Spam that’s sent like this will be a little “off”, compared to legitimate email – the To: field won’t have the email address of the recipient, for instance, and there’ll be no personalization in the Subject or body of the message. It’s no worse than most spam, and it’s more than balanced out by being able to hijack someone else’s reputation.
So if you provide any way for unvetted non-customers to send email through your systems you should consider adding some DKIM limitations to the constraints you already have on that mail path. Not signing with DKIM at all avoids the problem altogether, but also means you can’t demonstrate your DKIM prowess to legitimate potential customers. You might want to sign with a DKIM d= domain that’s different to your production signatures, perhaps even a completely different top level domain to avoid any risk of confusion (but don’t try and hide that it’s your domain – that’s what spammers do).
Other operational mistakes
There are some grubby corners of the email and DKIM specs that sometimes interact to cause other holes that this sort of reputation hijacker can exploit. I’ll talk about header duplication tomorrow.

Read More