On DKIM strength
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.
- firstname.lastname@example.org sends an email to email@example.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 @188.8.131.52 "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)
- 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