In the recent DKIM vulnerability, how did someone determine key length by looking at headers?

Question

Having read this recent article : Wired-DKIM vulnerability, I have a couple of questions.

How can one determine the key length that is being used simply by looking at the headers ?

And I'm assuming the attack is as follows: correct me if I'm wrong:

Factor the private key (of short key length) by knowing the public key, the mechanism (i.e. RSA etc)
Spoof the e-mail, replace the DKIM hash with hashes illegally calculated
Fool the verifier into thinking that the e-mail's origin is proper

Interesting question. It's certainly an odd situation - I'll have to read into it. — Polynomial, Oct 25 '12 at 18:54

score 10 · Accepted Answer · edited Mar 17 '17 at 10:46

I've written a DKIM parser and signer for Microsoft Exchange so this is pretty straightforward. Just note that the public key stored in DNS isn't a typical public key, it is in a more compact form called "public key subject form".

How can one determine the key length that is being used simply by looking at the headers ?

Do a TXT query for the following values in the header: {s value}._domainkey.{d value} (omit brackets)
Extract the value named "p=" in the above DNS query
Use an ASN.1 parser to determine the key length and other things that are stored within the

Example Public 2048 bit key found in a DKIM "p=" query with an exponent of 65537

MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAoSd6ya7haEmQl1sWoEVVou8iC618evFqluT5zb
0aMEgBEfHSJRjT/FojPWqhjAtCYMAIggaE0ZxVzPDsMeRc3Mixy2WO9DWYAJuzwP7DyzUAclhGTfP4cG44SlbSsEsMM/91cu5zr9+TulnqPDxUyPvLZjGpJEHXoEWc4m
f6tbksyxZTI+wssw84NLfEs3VC4jN9P1CnfG2aTCC74lj1mePbEBCsg83+Ilz/dsDcH2FGmWVa5ytNCP7kkzyBYkfF09YpDiSXxowRGZbRkGveDvOP3ONUhLrXumpTP6
+/Hm34kbG/kGBSxNOXn8/2jf2m+08Bt8ci9Orzb2s8J81q6QIDAQAB

Simply paste this key into the ASN.1 Javascript decoder to figure out the key length. Most programmers will just have a library to figure this out.

There are many software to facilitate brute force password hashes (john, cryptohaze, hashcat, etc). So, what software do you recommend for factoring an RSA key ? — Yohann, Oct 28 '12 at 12:34

score 3 · Answer 2 · edited May 23 '17 at 12:40

The RSA signature size is dependent on the key size. A 512 bit key produces a 64 byte long signature. The header ends with a Base64 encoded signature, so with padding my memory tells me that will be 88 bytes long. So, key length can be determined just by looking at a signature.

Factor the key, sign with the key (because you now have it), and send with all the expected headers.

For the longer version / explanation of this, see RSA signature size? on StackOverflow.

In the recent DKIM vulnerability, how did someone determine key length by looking at headers?

2 Answers2