As an update to yesterday’s post, Gmail is contacting postmasters at domains signing with 512 bit keys to warn them of the upcoming changes. This message also clarifies “DKIM keys failing.” Messages signed with 512 bit keys or less will be treated as unsigned by Gmail in the next week or so.
We noticed that your domain is sending email to Gmail users that is DKIM signed with a 512-bit RSA key. RFC 6376 requires DKIM signing mail using RSA keys of at least 1024-bits for long-lived keys (https://tools.ietf.org/html/rfc6376#section-3.3.3). Shorter keys could be factored by an attacker. As you may know, this attack has been publicly reported. US-CERT has also issued an advisory to upgrade all keys lower than 1024-bits (http://www.kb.cert.org/vuls/id/268267).
As such, we strongly encourage you to upgrade your RSA keys to be at least 1024-bits long.
To best protect our users, Gmail will begin treating emails signed with 512-bit keys as unsigned in about a week. If you continue to use your current key, your messages will not DKIM authenticate.
example._domainkey.example.com descriptive text “k=rsa; p=AKDA3adkelLHaK653IuYD aVgIFc/FBvErvNOkCAwEAAQ==;”