In our study on the SPF, DKIM, and DMARC records of the top 1M websites, we were surprised to uncover more than 1,700 public DKIM keys that were shorter than 1,024 bits in length. This finding was unexpected, as RSA keys shorter than 1,024 bits are considered insecure, and their use in DKIM has been deprecated since the introduction of RFC 8301 in 2018.
Driven by curiosity, we decided to explore whether we could crack one of these keys. Our goal was to extract the private key from a public RSA key, enabling us to sign emails as if we were the original sender. We were also curious to see whether emails signed with this compromised key would pass the DKIM verification checks of major email providers like Gmail, Outlook.com, and Yahoo Mail, or if they would outright refuse to verify a signature generated with such a short key.
For our experiment, we chose redfin.com after discovering a 512-bit RSA public key at key1._domainkey.redfin.com (now no longer available):
$ dig +short TXT key1._domainkey.redfin.com "k=rsa; p=MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAMx7VnoRmk/wFPeFWxrVUde6AJQI51/uPFL2CbiHGMnRSnLjPs72AgxAVHIe5QrNQ2riR5+7u47Sgh5R5va/d0cCAwEAAQ=="
Decoding the RSA Public Key
The public key, located in the DKIM record’s p
tag, is encoded in ASN.1 DER format, and further encoded as Base64. To decode the key to obtain the modulus (n) and the public exponent (e), we used a couple of lines of Python code:
$ python3 >>> from Crypto.PublicKey import RSA >>> RSA.import_key('-----BEGIN PUBLIC KEY-----n' + 'MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAMx7VnoRmk/wFPeFWxrVUde6AJQI51/uPFL2CbiHGMnRSnLjPs72AgxAVHIe5QrNQ2riR5+7u47Sgh5R5va/d0cCAwEAAQ==' + 'n-----END PUBLIC KEY-----') RsaKey(n=10709580243955269690347257968368575486652256021267387585731784527165077094358215924099792804326677548390607229176966588251215467367272433485332943072098119, e=65537)
Factorizing the RSA Modulus
With the modulus n in hand, our next step was to identify the two prime numbers, p and q, whose product equals n. This process, known as factoring, c