As you've probably read in the press, DKIM is broken and we're all going to die. But that's OK, it usually happens twice a year.

DKIM is a signature algorithm used to authenticate the domain an email claims to originate from.

  1. spongebob@gmail.com sends an email to eugene@yahoo.com
  2. the gmail MX server signs the body of the email using gmail's RSA private key, thus creating a dkim signature
  3. the email is sent to yahoo's MX server via SMTP
  4. yahoo retrieves gmail's RSA public key from gmail's TXT DNS record
  5. yahoo verifies the dkim signature and, if valid, stores the email in eugene's inbox.

Ideally, DKIM provides a way to authenticate the sender of an email. All messages coming from Gmail must have a valid DKIM signature, and because Gmail ensures that only authenticated users can send email, the email sender is authenticated.

Therefore, DKIM's strength strongly relies on RSA's strength. And RSA's strength relies on the complexity of factoring large number to reduce them to their prime components: the bigger the RSA key, the stronger the signature.

So, why would gmail use keys of 384 bits, when everybody knows that keys below 1024 bits are easily factorizable ?

That's essentially because, in the real world, none of the ESPs are using DKIM for authentication purposes. They use DKIM for protection against spam. Yahoo will verify that an incoming email that has a Gmail From: address has a valid DKIM signature. If it doesn't, it will deliver the email in the user's Spam folder. Gmail will do the same, as well as 90% of the ESPs out there.

For spam protection purpose, 384 bits keys are "good enough". RSA operations are *really* expensive (see below), and increasing the size of the key has non-trivial impacts on the DKIM signing/verification infrastructures of these ESPs.

The vulnerability found is not a new one: we've been able to factorize 384 bits keys for years. Gmail is not broken. But a spammer who obtains Gmail's DKIM private key could send spam with valid DKIM signatures that would pass ESPs spam filters. Thanksfully, DKIM is only one of the many criteria used in spam detection.

Nevertheless, Gmail thought the vulnerability was important enough to increase the size of their RSA modulus to 2048 bits.

On RSA computational cost

                     sign    verify    sign/s verify/s
   rsa  512 bits 0.000051s 0.000004s  19454.6 243901.9
   rsa 1024 bits 0.000178s 0.000012s   5633.6  86925.1
   rsa 2048 bits 0.001246s 0.000039s    802.5  25626.5
   rsa 4096 bits 0.009033s 0.000145s    110.7   6903.2

(output of `openssl speed rsa` on my macbook)

The results above show that doubling the size of the key from 512 bits to 1024 bits multiplies by ~3 the cost of the signature and verification operations. Worse: moving from 1024 to 2048 bits makes the signature operation ~7 times more expensive. At the scale of an ESPs such as Gmail, increase the RSA key size from 384 to 2048 means making the DKIM signing operations ~25 times more expensive. In practice, it means multiplying the number of signing servers by 25. Not a trivial thing to do...

On retrieving RSA keys

Use `dig` to get the TXT record:

   $ dig +short txt 20120113._domainkey.gmail.com @8.8.8.8
   "k=rsa\;
   p=MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA1Kd
   87/UeJjenpabgbFwh+eBCsSTrqmwIYYvywlbhbqoo2DymndFkbjOVIPIld
   /m40KF+yzMn1skyoxcTUGCQs8g3FgD2Ap3ZB5DekAo5wMmk4wimDO+U8QzI3SD0" 
   "7y2+07wlNWwIt8svnxgdxGkVbbhzY8i+RQ9DpSVpPbF7ykQxtKXkv
   /ahW3KjViiAH+ghvvIhkx4xYSIc9oSwVmAl5OctMEeWUwg8Istjqz8BZeTWbf
   41fbNhte7Y+YqZOwq1Sd0DbvYAD9NOZK9vlfuac0598HY+vtSBczUiKERHv1
   yRbcaQtZFh5wtiRrN04BLUTD21MycBX5jYchHjPY/wIDAQAB"

The part after `p=` is the public key. If the key is longer than 512 characters, it will be broken into 2 blocks (DNS limitation).

Put the key in a file:

   -BEGIN PUBLIC KEY-
   MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA1Kd87/UeJjenpabgb
   Fwh+eBCsSTrqmwIYYvywlbhbqoo2DymndFkbjOVIPIldNs/m40KF+yzMn1sky
   oxcTUGCQs8g3FgD2Ap3ZB5DekAo5wMmk4wimDO+U8QzI3SD07y2+07wlNWwIt
   8svnxgdxGkVbbhzY8i+RQ9DpSVpPbF7ykQxtKXkv/ahW3KjViiAH+ghvvIhkx
   4xYSIc9oSwVmAl5OctMEeWUwg8Istjqz8BZeTWbf41fbNhte7Y+YqZOwq1Sd0
   DbvYAD9NOZK9vlfuac0598HY+vtSBczUiKERHv1yRbcaQtZFh5wtiRrN04BLU
   TD21MycBX5jYchHjPY/wIDAQAB
   -END PUBLIC KEY-

And check it using openssl:

   $ openssl rsa -noout -pubin -text < /tmp/gmail_dkim.pubkey 
   Public-Key: (2048 bit)
   Modulus:
       00:d4:a7:7c:ef:f5:1e:26:37:a7:a5:a6:e0:6c:5c:
       21:f9:e0:42:b1:24:eb:aa:6c:08:61:8b:f2:c2:56:
       e1:6e:aa:28:d8:3c:a6:9d:d1:64:6e:33:95:20:f2:
       25:74:db:3f:9b:8d:0a:17:ec:b3:32:7d:6c:93:2a:
       31:71:35:06:09:0b:3c:83:71:60:0f:60:29:dd:90:
       79:0d:e9:00:a3:9c:0c:9a:4e:30:8a:60:ce:f9:4f:
       10:cc:8d:d2:0f:4e:f2:db:ed:3b:c2:53:56:c0:8b:
       7c:b2:f9:f1:81:dc:46:91:56:db:87:36:3c:8b:e4:
       50:f4:3a:52:56:93:db:17:bc:a4:43:1b:4a:5e:4b:
       ff:6a:15:b7:2a:35:62:88:01:fe:82:1b:ef:22:19:
       31:e3:16:12:21:cf:68:4b:05:66:02:5e:4e:72:d3:
       04:79:65:30:83:c2:2c:b6:3a:b3:f0:16:5e:4d:66:
       df:e3:57:db:36:1b:5e:ed:8f:98:a9:93:b0:ab:54:
       9d:d0:36:ef:60:00:fd:34:e6:4a:f6:f9:5f:b9:a7:
       34:e7:df:07:63:eb:ed:48:17:33:52:22:84:44:7b:
       f5:c9:16:dc:69:0b:59:16:1e:70:b6:24:6b:37:4e:
       01:2d:44:c3:db:53:32:70:15:f9:8d:87:21:1e:33:
       d8:ff
   Exponent: 65537 (0x10001)

Further reading:

  • How a Google Headhunter’s E-Mail Unraveled a Massive Net Security Hole http://www.wired.com/threatlevel/2012/10/dkim-vulnerability-widespread/all/
  • DKIM Signature and verification using DKIMproxy http://wiki.linuxwall.info/doku.php/en:ressources:dossiers:postfix:dkimproxy