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.
- spongebob@gmail.com sends an email to eugene@yahoo.com
- the gmail MX server signs the body of the email using gmail's RSA private key, thus creating a dkim signature
- the email is sent to yahoo's MX server via SMTP
- yahoo retrieves gmail's RSA public key from gmail's TXT DNS record
- 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