Slashdot Mirror
How a Google Headhunter's E-Mail Revealed Massive Misuse of DKIM
concealment writes with a tale of how an email sent to a mathematician led to him discovering that dozens of high profile companies were using easily crackable keys to authenticate mail sent from their domains. From the article: "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 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. Harris wasn't interested in the job at Google, but he decided to crack the key and send an e-mail to Google founders Brin and Page, as each other, just to show them that he was onto their game."
I'm surprise Mr. Harris wasn't accosted by lawyers or law enforcement. Huzzah for common sense.
How could he seriously think it was a headhunter challenge?
He is clearly lying or been living too much outside real world..
This is Obama, please vote for me. This email is from me, you can verify it using DKIM public keys.
Regards
Romney
It's possible that some of the short DKIM keys were due to concerns over compatibility with other systems. When you have a large heterogeneous environment like email, you sometimes get caught catering to the lowest common denominator.
DKIM keys can exceed the TXT DNS record limit or the UDP byte limit. Some software may not handle joining split TXT DNS records. Others may handle DNS over UDP but not handle TCP for long records.
News flash.
Email wasn't broken. DKIM was. Or rather DKIM wasn't really broken, just being misused by Google.
This was not a misuse of DKIM, or perhaps it was his own misuse in that he thinks DKIM validates the sender of an email. All it does is validate that the email originated from Google's mail servers, but it doesn't neccessarily mean that the address in the From: header wasn't spoofed before it was signed.
In any case, he found that Google (and others) are using an easily cracked 512 bit key, which they silently fixed with a 1024 bit key after he reported it to them by spoofing an email to appear as though it originated at Google.
There was no misuse, 512 bit keys are allowable under the DKIM spec, though they aren't recommended for long-lived keys.
So the reality is that, on top of being useless as an anti-spam mechanism, it now turns out to be even worse, and in fact vulnerable to malicious attacks. In other words, it's useless and uselesser.
I was heavily involved in a lot of the discussions surrounding SPF, DKIM and related "solutions" back in the early 2000s, and about the most that we could say about these "solutions" was that you could add a positive number to the score of an email in a weighting system if things checked out, but other than that, there was little to recommend them.
The world's burning. Moped Jesus spotted on I50. Details at 11.
If it's easy to misuse, doesn't that make it broken?
There are two types of people in the world: Those who crave closure
Individual's sharp-mindedness against corporate stupidity. Happens all the time. I'm proud to be an individual having studied mathematics, even if I landed in IT later on...
Religous speak to God. Insane are spoken to by God. When all shut up, one can finally hear Shostakovich in peace
that Swordfish was a premonition — Hugh Jackman really does crack encryption...
Shame on Google for using a weak key, but also shame on this article for being more than a little hyperbolic.
If you, you know, actually read the standard, or even the Wikipedia page, you'll see that DKIM is not intended to be used as a signature mechanism in the same way as S/MIME or PGP. Rather, it's a means to assert responsibility for sending the message, it's done at the domain rather than user level, and verification results are intended to be used for message filtering, not for asserting that so-and-so actually signed the message.
Sure, the underlying technology is based on hashes, signatures, signature verification, and so on but that's because there's no other way to do it. The fact that DKIM allows for the application of relaxed interpretation of both message header and body data kinda tells you it's not intended to be used to provide an absolute assurance that what you got is authentic in every way.
DKIM is also not intended to be the ultimate source of information for filtering. Rather, DKIM results are supposed to be combined with other metrics to form an overall assessment of message validity. And that's a very good thing, since I get all sorts of spammy stuff that makes it through Google, including getting a legitimate DKIN signature attached. Other filtering mechanisms are needed to block such crap.
All that said, it's very disappointing to see yet another case where Google has seen fit to play fast and loose with standards. This is happening much too often.
If I fly an airplane into a building, does that mean the airplane's design is broken?
I am literally 3000 tokens away from the chaotic crossbow --Stephen
Is it this guy's supposition that Brin and Page were using weak, crackable keys deliberately?
#DeleteChrome
The core E-mail protocol itself is supposed to be a brain-dead simple protocol that almost any machine can understand, thus the "S" in SMTP.
It is the additions which are used by the MTAs to allow who can and cannot connect and relay, as well as MUAs to figure out what to do with incoming messages.
Realistically, the ideal for verifying authentication would be an OpenPGP plugin and a far-reaching WoT that each user maintains. However, because certs and having domains sign outgoing mail is "good enough", that has become the standard these days.
I had until more recently been getting a bunch of "backscatter" hits to my gmail hosted account.
While the return message seemed legit, the email that supposedly went out from (an nonexistent account) at my domain was not.
I wonder if the spammers were already taking advantage of this vulnerability. I do notice that more recently I haven't got any of these.
If it's easy to misuse, doesn't that make it broken?
No.
If I convince ignorant people that PGP signatures prove that they've actually won $47,325,443 in the Nigerian lottery, and all they need to do is send their account details so I can deposit their winnings, is PGP broken?
This wasn't even a true misuse of DKIM. It was use of a 512 bit key.
Something that many people seem to forget is that the strength of the security should be matched against the risk and costs of being broken. If I'm sending you a message that says "meet me at the corner of 5th and Smith St in five minutes", and it takes someone who intercepts the message an hour to break it, then the encryption has done its job just fine. By the time they break it, we will no longer be at 5h and Smith St, and they will have had no time to set up surveillance.
Given the intended use of DKIM, 512 bits is plenty.
If the airplane's design allows you AS A REGULAR PASSENGER to do so, then yes.
So if the pilots all die for whatever reason while flying the plane, then it will crash as designed? Because regular passengers can try to fly it?
Half the spam that makes it through my filters is DKIM-signed. Spammers use it to make the email look less bogus. Of course, that means that they have to use a real domain and hosting provider that they eventually lose — but domains are cheap, and changing hosts is no big deal.
Ru-oh!
I'd better take a closer look at the automatically generated DKIM keys for the several Google Apps domains I oversee....
And how does an airplane distinguish between pilots and "regular passengers" so that only the former can fly them?
This problem has been reported by the US-CERT (part of the US Department of Homeland Security [Insecurity?]) at http://www.kb.cert.org/vuls/id/268267. See that link for an authoritative report on the meaning of this problem and how to avoid it.
From the article, the line:
Harris thought there was no way Google would be so careless, so he concluded it must be a sly recruiting test to see if job applicants would spot the vulnerability.
That's exactly how I would think.
The DKIM key isn't changing. Once you have broken the DKIM key you can spoof as many emails from that source as you want until they change their key. This is not like SSL. It doesn't encrypt the message in any way, it is a way to verify the source of the message.
And how does an airplane distinguish between pilots and "regular passengers" so that only the former can fly them?
The pilots are up front, and the regular passengers sit behind. There's a wall between the two sets of people.
All ideas^H^H^H^H^Hprocesses in this post are Patent Pending. (as well as the process of patenting all postings)
All my knives are broken.
See if your intrusion is noticed.
"if ( it ain't broken, ||
the original coder has since left the company ||
no one has touched that header for four years ||
the code is abandoned without any "owner" in the company ||
it is living in a branch of source code deemed "legacy"){
don't fix it;
}
sed -e 's/Chuck Norris/Rajnikant/g' joke > fact
Instead, two days later, he noticed that Googleâ(TM)s cryptographic key had suddenly changed to 2,048 bits. And he got a lot of sudden hits to his web site from Google IP addresses.
So, googlers: How'd misc react to this? I can see all sorts of spoofing fun going on...
-B
Ash and Hickory, straight-grained and true, make excellent bludgeons, dandy for the cudgeling of vegetarians.
I dont understand. Obviously there are different crypto algos out there... but why is a 512-bit DKIM key insecure, when AES-192 is considered very secure (actually more secure than 256 due to some flaws AFAIK) with a 192 bit key?
I mean, AES is like a decade old. DKIM is AFAIK much more recent than that. Why do they need larger keys for the same security?
AES is synchrounous, same (secret) key used for encrypting and decrypting. Those are generally much harder to break than public key cryptos (with the same key-size), but also not usable for the same things.
There's no way he seriously believed this was a sly test the recruiters were sending out to weed applicants. He's just saying that to cover his ass if Google actually peruses him legally for what he did.
But really though, all this system is for is for certifying that mail actually did come from a specific domain, not a specific sender. I'm not seeing the huge misuse here.
Email wasn't broken. DKIM was. Or rather DKIM wasn't really broken, just being misused by Google.
Misused implies some sort of dishonest intent, whereas they were actually just negligent in using a really weak key that the researcher could break on his laptop.
Not only Google but a bunch of other important web sites as well, such as Yahoo, eBay, major banks etc.
Exactly. It's about authentication, not encryption.
To add more detail to the AC's response.
AES is based on a subsitution-permutation network.
DKIM is based on the RSA signature algorithm which relies on the difficulty of factoring large integers.
Elliptic curve public key cryptography is based on the difficulty of solving a discrete logarithm problem.
The difference in the size of keys between one type of algorithm or another is an expression of the difficulty in solving the underlying problem. Factoring a large integer of X bits (RSA) is relatively easy compared to working through the substitutions and permuations of X bits of AES.
The link below provides a guideline for comparing the key sizes of AES, EC, RSA/DH.
http://www.nsa.gov/business/programs/elliptic_curve.shtml
The DKIM spec itself (RFC6376) says: "Signers MUST use RSA keys of at least 1024 bits for long-lived keys."
It's pretty unequivocal. Google just misconfigured their mailserver.
No it means the building was built in the wrong place.
AES is synchrounous
I think you meant "symmetric" :-)
Need to type accents and special characters in Windows? Use FrKeys
(Parent means "symmetric", not "synchronous".)
You can't always compare key sizes between different encryption schemes. For AES with 128-bit keys there are 2**128 possible keys. An RSA key, on the other hand, is the product of two prime numbers. Because prime numbers are rather sparse, there are far fewer than 2**128 possible keys for 128-bit RSA, so we need much larger key sizes than AES for a similar level of security.
And how does an airplane distinguish between pilots and "regular passengers" so that only the former can fly them?
The pilots are up front, and the regular passengers sit behind. There's a wall between the two sets of people.
OMFG!!!1! HUNDREDS of Pilots!? Only TWO passengers?! What the --Oh, never mind, "behind" is that way... For a second there I had an signed integer overflow in the velocity vector and thought we were just flying backwards, which means that behind and forwa-- Oh, never mind. Sorry about that, I'll try to be a good auto-pilot from here on out.
Boy, the sky sure is blue today... And shiny. I think I can see my reflectioOOOOOOO!!!!!
This is public key cryptography we're talking about. 512 bit is not plenty, because it allows you to break the key and then pose as the legitimate private key owner.
It would only be OK if this was a one-time key, and that's not the case.
which they silently fixed with a 1024 bit key after he reported it to them...
From TFA:
Harris made sure the return path for the e-mails went to his own e-mail account, so that Brin and Page could ask him how heâ(TM)d cracked their puzzle. But Harris never got a response from the Google founders. Instead, two days later, he noticed that Googleâ(TM)s cryptographic key had suddenly changed to 2,048 bits. And he got a lot of sudden hits to his web site from Google IP addresses.(emphasis mine)
'The tyrant will always find pretext for his tyranny.' - Aesop's Fables
Others gave good answers, but I'd just take it a step further - you can't really directly compare key lengths for different algorithms.
How long does it take you to solve 100 math problems by hand? Well, when I was in elementary school I was expected to do it in 5 minutes, but those were single-digit add/subtract/multiple/divide problems.
If I asked you to calculate the log of 10 10-digit numbers by hand it would take you a LOT longer than 5 minutes, though a computer could do this quickly.
If I asked you to factor a single number 100 digits long it would take an awfully long time even for a computer, though it would be in the realm of possibility.
Different algorithms use different math, so keys need to be different lengths to be secure. These algorithms are chosen for many reasons, and a shorter key length is only one of them. In many applications it might make more sense to just make all the keys 10x longer if it means that you can do the math on a cheaper and lower power chip. In this particular case, having to use a really long key is worth it because the design of this particular type of crypto system allows n people to communicate with each other with a total of only 2n keys, and not 2^n.
The DKIM spec itself (RFC6376) says: "Signers MUST use RSA keys of at least 1024 bits for long-lived keys."
Keep in mind that RFC 6376 was issued in September of 2011. Prior versions did allow 512-bit keys, though they cautioned against them.
It's pretty unequivocal. Google just misconfigured their mailserver.
More likely, I think, is that Google failed to reconfigure their server. When Google started using DKIM, cracking 512-bit keys was significantly harder than it is now. The change is less due to increases in computing power (though that has helped) than it is to the availability of cloud-based compute clusters. Granted that it was always a little risky to use such small keys, it was much more reasonable than it is today.
So my guess is that it went down like this: A few years ago when Google implemented DKIM someone looked at RFC 4871's discussion of key sizes, which says:
... and thought "yeah, we can use 512-bit keys and change them occasionally, that will provide higher performance for less CPU load, and as the RFC says the security goals here really aren't that high". I imagine that the decision to implement DKIM at all may have been a tad controversial given the additional load it was going to place on the servers, so that 512-bit key usage may even have been an important design point. Then the "change them occasionally" bit got dropped on the floor.
Fast-forward a few years, the problem is discovered and fixed -- but this time the engineers decided to make sure it doesn't happen again and jumped to 2048-bit keys even if it required provisioning more capacity.
(Disclaimer: I work for Google, and do cryptographic security stuff for Google, but I don't have any more information than the rest of you about how all of this happened. The above is pure speculation based on my 15 years as a security consultant before joining Google. I saw lots of stuff just like it from the few companies I worked with who were actually quite good about security. And even more insanely stupid stuff from all the rest.)
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
Yup, all of that is likely what happened.
A critical part of DKIM is selector-based key rotation (as even the 2048 bit key won't help you at all when an ex-employee or a contractor walks off with the private key, while key rotation will reduce the window of exposure from that sort of event). Google aren't the only ones to have missed that.
(Many of the original - and current - examples of how to set up DKIM suggest using a date as part of the selector, so as to make it clear that the key was supposed to be fairly transient. That leads to the lovely situation that you can look at a lot of peoples DKIM setups and see that they created their key pair once, several years ago, using the current date and haven't changed it since - their failure to rotate keys is self-documenting.)
There are many reasons why DKIM doesn't need to be "really strong crypto" - it's intended just for someone to assert that they're responsible for an email message, that they're prepared to accept complaints about the mail they send, and that you should pay attention to their previous behaviour when deciding whether or not to deliver a message. Stealing someones DKIM private key lets you piggy back on their good reputation to get spam or phishing emails into an inbox rather than a spam folder for a short time period, and that's about it. It's nowhere near as high value a target as anything like TLS certificates.
Googles reputation is certainly worth more than the estimated $75 it would cost to crack their short key, so it's good they've fixed that. And even though much of the media coverage of this has been tech-tabloid drivel it's a good thing if it gets other companies to look at key length and rotation frequency.
(Disclaimer: I've been working with the DKIM spec since the early days of DomainKeys. http://dkimcore.org/ is me.)
I hardly know what spam is anymore: since years, when I switched to GMail, I hardly get any spam. I'm always amazed when I see articles about the spam issue: "spam, do people still get *that*!?". I take it the more emails account you have (6 digits number of users at least), then it gets easier and easier to find and trash spam...
Do DKIM and/or SPF help get less spam? Less spoofed emails?
Isn't it a complete aberration that because 512 bits keys for DKIM were way too small that people do think that DKIM is useless? Apparently in less than 48 hours GMail's DKIM changed to 2048 bits keys.
Why exactly would DKIM be useless? Which problem does it solve? Which are its drawbacks? (IFF the keys are big enough)
Look at the photo. He does math in mirror writing!