The problem lay with the DKIM key (DomainKeys Identified Mail) Google used for its google.com e-mails. DKIM involves a cryptographic key that domains use to sign e-mail originating from them – or passing through them – to validate to a recipient that the domain in the header information on an e-mail is correct and that the correspondence indeed came from the stated domain. When e-mail arrives at its destination, the receiving server can look up the public key through the sender’s DNS records and verify the validity of the signature.
For security reasons, the DKIM standard calls for using keys that are at least 1,024 bits in length. But Google was using a 512-bit key – which could be easily cracked with a little cloud-computing help.