DKIM and Gmail

After they were a a little embarrassed by their own DKIM keys being poorly managed a few months ago, Google seem to have been going through their inbound DKIM handling and tightening up on their validation so that badly signed mail that really shouldn’t be treated as DKIM signed, won’t be treated as signed by Gmail.
This is a good thing, especially as things like DMARC start to be layered on top of DKIM, but it does mean that you really need to check your signing configuration and make sure you’re not doing anything silly.

What Gmail is requiring

Here are some things that Gmail seem to be requiring in order for them to consider your mail DKIM signed, based either on statements from Google or watching what Gmail does with badly signed mail.
1024 bit keys
Keys must be at least 1024 bits long. 1024 bits is plenty for now, you don’t need to use anything longer, but you shouldn’t be using anything shorter.
Sign visible headers
Signatures should cover the user visible headers of the message. If you don’t sign your Subject line, an attacker can replay your message with a different subject line and it will still be validly DKIM signed by you.
The DKIM spec lists Date, Subject, Reply-To and Sender as highly advised and I’d add To and Cc to that list too. (From is explicitly required).

What Gmail probably isn’t requiring

And then there are some things that, as far as I know, Gmail aren’t requiring (yet) but you should do anyway.
Sign any headers that can affect message display
As well as the headers that are directly visible, all the MIME headers – MIME-Version, Content-Type, Content-ID, Content-Description, Content-Transfer-Encoding – can affect the display of the message. While an attacker can’t use that to replace your content, they might be able to break the rendering of it such that it isn’t displayed.
Sign any headers that can affect your compliance
Replay attacks that use all your original content, but redirect your List-Unsubscribe URLs to somewhere completely inappropriate are pretty unlikely – but why should a recipient ISP trust that your List-Unsubscribe link is suitable for use by their automation if you aren’t signing it.
Sign headers, even if you don’t use them
If you DKIM sign headers you aren’t using nobody can add those headers later without breaking your DKIM signature. There’s no need to add a laundry list of all headers, but if there’s a potentially sensitive header, like Cc perhaps, that you don’t use then adding that to the DKIM signature is worth considering.
Rotate your keys
The longer a key is unchanged, the more likely it is that someone will be able to compromise it. Using a long enough key will prevent someone from cracking the cryptography, but no key length will prevent an ex-employee walking it out of the building, or someone recovering it from a dump tape, or a machine compromise. Regularly changing keys is an important part of keeping them secure, by reducing the time window in which they can be abused.
You rotate keys by creating a new {selector, private key, public key} set, publishing the new public key to DNS, then configuring your DKIM signer to use the new selector and private key. Then, after a couple of days, you can remove the old public key from DNS.
If you’re an ESP, this is all much easier to do if your customers delegate part of their domainkey space to you, as described here, so that you can publish the public keys and manage rotation without any customer interaction.