This started from the confluence of two things. One was the news that the NSA had pretty much stuck their snout into any data trough they could find and was sucking up everything. Phone “contact trace” information on everyone. “Who talks to whom” (and how often, and when, and from where, and…) Phone location data (they admitted to “testing” tracking folks GPS location data). Any and all email. Even statements that they had managed to break into VPN Virtual Private Network encrypted tunnels and PPTP Point To Point Protocol links.
That kind of set me on my haunches to think for a bit.
I know a bit about encryption. As the VPN methods were described to me, they ought not be easy to break. “Triple DES” encryption. DES Data Encryption Standard uses a 56 bit key. When proposed, it could not be broken, but over time more compute power made it crackable. Triple DES used DES three times and made it much harder to crack. Eventually all such fall before Moore’s Law. But… It takes (took?) about a 1/4 $Million bit of hardware to crack DES. More than most folks can spare, but chump change for a TLA Three Letter Agency like the NSA.
But generally I’d figured VPN and PPTP were “secure enough”. They needed lots of hardware to crack one “round” of DES, and there were three rounds.
Then there was a bit of news that the Windows Phone was crackable and could be used to gain credentials to a corporate network. In looking down the chain of information, I found out that most all Microsoft encryption relied on one method, and it was deeply flawed. It is called PEAP-MS-CHAPv2 and it is, IMHO, “broken by design”.
For some time I’d groused that Microsoft software seemed designed to leave “crap” all over the place that was useful to law enforcement, TLA’s, and anyone breaking into your box. That it just wasn’t secure. No, worse than that, that it seemed DESIGNED to be a tattletale and information leaker. But other than a vague “I’d never do it that way” and a frequent “that is either damn stupid or they are being pushed to do it badly” feeling, there wasn’t hard data to point at. I think that has changed.
Here’s the security advisory that sent me down this path:
Microsoft Security Advisory (2876146)
Wireless PEAP-MS-CHAPv2 Authentication Could Allow Information Disclosure
Published: Sunday, August 04, 2013
Microsoft is aware of a public report that describes a known weakness in the Wi-Fi authentication protocol known as PEAP-MS-CHAPv2 (Protected Extensible Authentication Protocol with Microsoft Challenge Handshake Authentication Protocol version 2), used by Windows Phones for WPA2 wireless authentication. In vulnerable scenarios, an attacker who successfully exploited this issue could achieve information disclosure against the targeted device. Microsoft is not currently aware of active attacks or of customer impact at this time. Microsoft is actively monitoring this situation to keep customers informed and to provide customer guidance as necessary.
To exploit this issue, an attacker controlled system could pose as a known Wi-Fi access point, causing the targeted device to automatically attempt to authenticate with the access point, and in turn allowing the attacker to intercept the victim’s encrypted domain credentials. An attacker could then exploit cryptographic weaknesses in the PEAP-MS-CHAPv2 protocol to obtain the victim’s domain credentials. Those credentials could then be re-used to authenticate the attacker to network resources, and the attacker could take any action that the user could take on that network resource.
Recommendation. Apply the suggested action to require a certificate verifying a wireless access point before starting an authentication process. Please see the Suggested Actions section of this advisory for more information.
Turns out that Microsoft phones try to do that “Authentication” against a WiFi Hotspot, and in the process an attacker can get your “credentials” for logging onto your whole network. (so a corporate network can be exposed via any person with a Microsoft Phone visiting a Starbucks where someone else has set up a bogus WiFi hotspot) That “intercept the victim’s encrypted domain credentials” part.
So lets break down that name a little:
Protected Extensible Authentication Protocol with Microsoft Challenge Handshake Authentication Protocol version 2
Version 2 means there was an earlier one that got changed / dumped.
In the beginning, there was CHAP. Challenge Handshake Authentication just means the server “challenges” you to present some credentials, and you do, and that authorizes your connection. This was changed by Microsoft to become a MS variation. Over time, CHAP was a bit ‘light’, so the spec was modified to allow extensions to the encryption method. That “extensible” authentication part. So with PEAP, we ought to get some more hard core and hard to crack extensions. And Microsoft proceeded to use PEAP-MS-CHAPv2 in pretty much everything they do.
What did we really get?
This site lays out the problems, and how they enable the “crack”:
First, note that this is from July 2012 so we are pushing 1.5 years and no fix. You don’t leave a known exposure open for a year and a half without some reason. Like maybe an “Agency” wants it.
Next some text from the posting:
The first obvious question is why we looked at MS-CHAPv2, given a lingering sense that the internet should already know better than to rely on it. Unfortunately, however, even as an aging protocol with some prevalent criticism, it’s still used quite pervasively. It shows up most notably in PPTP VPNs, and is also used quite heavily in WPA2 Enterprise environments — often in cases where its mutual authentication properties are being relied upon. For the talk, we put together a list of the hundreds of VPN providers which depend on PPTP.
It’s used all over the place.
So how about the protocol itself?
Let’s take a look at the protocol itself, in order to see what we’re dealing with:
At first glance, one is initially struck by the unnecessary complexity of the protocol. It almost feels like the digital equivalent of hand-waving — as if throwing in one more hash, random nonce, or unusual digest construction will somehow dazzle any would-be adversaries into submission. The literal strings “Pad to make it do more than one iteration” and “Magic server to client signing constant” are particularly amusing.
If we look carefully, however, there is really only one unknown in the entire protocol — the MD4 hash of the user’s passphrase, which is used to construct three separate DES keys. Every other element of the protocol is either sent in the clear, or can be easily derived from something sent in the clear:
That kind of “lots of complexity doing nothing” indicates either profound lack of understanding by the folks who wrote it; or that “this behaviour is by design”… It’s just do darned “sloppy” that I find it hard to believe that someone who knows crypto could actually write it like that by accident. But are there any particulars to support that notion?
We have an unknown password, an unknown MD4 hash of that password, a known plaintext, and a known ciphertext. Looking back at the larger scope, we can see that the MD4 hash of the user’s password serves as a password-equivalent — meaning that the MD4 hash of the user’s password is enough to authenticate as them, as well as to decrypt any of their traffic. So our objective is to recover the MD4 hash of the user’s password.
In a situation with an unbounded password length across a large character set, it would make more sense to brute force the output of the MD4 hash directly. But that’s still 128bits, making the total keyspace for a brute force approach on that value 2^128 — which will likely be forever computationally infeasible.
So at a ‘top level’ with a shallow look, it looks like 128 bits of ‘key’ and an impossible brute force attack. So the “top look” is like something you don’t want to tackle. But look a bit more…
Divide And Conquer
The hash we’re after, however, is used as the key material for three DES operations. DES keys are 7 bytes long, so each DES operation uses a 7 byte chunk of the MD4 hash output. This gives us an opportunity for a classic divide and conquer attack. Instead of brute forcing the MD4 hash output directly (a complexity of 2^128), we can incrementally brute force 7 bytes of it at a time.
Since there are three DES operations, and each DES operation is completely independent of the others, that gives us an additive complexity of 256 + 256 + 256, a total keyspace of 2^57.59
This is certainly better than 2^138 or 2^128, but still quite a large number. There’s something wrong with our calculations though. We need three DES keys, each 7 bytes long, for a total of 21 bytes:
Those keys are drawn from the output of MD4(password), though, which is only 16 bytes:
We’re missing five bytes of key material for the third DES key. Microsoft’s solution was to simply pad those last five bytes out as zero, effectively making the third DES key two bytes long:
It is at this point that the hackles start to rise. “pad those last 5 bytes out as zero”? Really? That is throwing away those bytes. It’s obviously and incredibly stupid as complexity is what provides the protection and each bit is far more valuable than the last as it’s an exponent.
Since the third DES key is only two bytes long, a keyspace of 2^16, we can immediately see the effectiveness of divide-and-conquer approach by brute forcing the third key in a matter of seconds, giving us the last two bytes of the MD4 hash. We’re left trying to find the remaining 14 bytes of the MD4 hash, but can divide-and-conquer those in two 7 byte chunks, for a total complexity of 2^57.
The next interesting thing about the remaining unknowns is that both of the remaining DES operations are over the same plaintext, only with different keys.
Oh Dear. This is looking worse and worse. Skipping down a bit.
The expensive part of these loops are the DES operations. But since it’s the same plaintext for both loops, we can consolidate them into a single iteration through the keyspace, with one encrypt for each key, and two compares:
This brings us down to a total complexity of 256!
This means that, effectively, the security of MS-CHAPv2 can be reduced to the strength of a single DES encryption.
When a single DES is known to be breakable.
This has all the look and feel of a backdoor. Mindless confusing ‘wrapper’ complexity that looks good, but inside the lock is very weak with a method that reduces to being subject to a known attack.
It’s been done, but it isn’t easy. Typically about $250,000 of hardware is needed. Well inside an ‘agency’ budget, but beyond the typical individual. Just the kind of threshold the NSA would like in a backdoor just for them…
At this point, a question of feasibility remains. In 1998, the EFF used ASICs to build Deep Crack, which cost $250,000 and took an average of 4.5 days to crack a key.
David Hulton’s company, Pico Computing, specializes in building FPGA hardware for cryptography applications. They were able to build an FPGA box that implemented DES as a real pipeline, with one DES operation for each clock cycle. With 40 cores at 450mhz, that’s 18 billion keys/second. With 48 FPGAs, the Pico Computing DES cracking box gives us a worst case of ~23 hours for cracking a DES key, and an average case of about half a day.
Thanks to Moore’s Law that cost will be cut in half about every 18 months. In not too many years, anyone can do it.
But Wait! There’s more! These good folks have made the hardware available to anyone.
It wouldn’t be a ton of fun if only David or I could crack MS-CHAPv2 handshakes, however. So we’ve integrated the DES cracking box with CloudCracker, in order to make David and his team’s genius/skills/resources available to everyone.
We’ve published a tool called chapcrack, which will parse a network capture for any MS-CHAPv2 handshakes. For each handshake, it outputs the username, known plaintext, two known ciphertexts, and will crack the third DES key. It will also output a CloudCracker “token,” which is an encoded format of the three parameters we need for our divide and conquer attack.
When this token is submitted to CloudCracker, the job is transmitted to Pico Computing’s DES cracking box, and you receive your results in under a day.
Yes, they’ve made it available for free to anyone.
IMHO, the NSA most likely “leaned” on Microsoft to put this bit of buggery in place. It is just complicated enough to pass casual inspection, while being just broken enough that Agency Guys can get in with $1/4 Million toys, and the ‘riff raff’ was kept out. Not something any experienced crypto programmer would choose to do (if they had a brain) but just the things an Agency would do to get selective access.
It is used all over Microsoft, so grants access all over Microsoft. From the phone to the desktop to VPNs and PPTP links.
The article goes on to list some alternative ideas:
1) All users and providers of PPTP VPN solutions should immediately start migrating to a different VPN protocol. PPTP traffic should be considered unencrypted.
2) Enterprises who are depending on the mutual authentication properties of MS-CHAPv2 for connection to their WPA2 Radius servers should immediately start migrating to something else.
In many cases, larger enterprises have opted to use IPSEC-PSK over PPTP. While PPTP is now clearly broken, IPSEC-PSK is arguably worse than PPTP ever was for a dictionary-based attack vector. PPTP at least requires an attacker to obtain an active network capture in order to employ an offline dictionary attack, while IPSEC-PSK VPNs in aggressive mode will actually hand out hashes to any connecting attacker.
In terms of currently available solutions, deploying something securely requires some type of certificate validation. This leaves either an OpenVPN configuration, or IPSEC in certificate rather than PSK mode.
OpenVPN is not subject to these ills, so IMHO it is the solution of choice for VPNs.
In related news, the leaks keep adding up. The NSA looks to be fulfilling the worst paranoids dream. From tracking cell phone GPS to find where everyone likes to go, and path to get there; to gathering all email and dredging it; to generally spying on everyone, everything, and both breaking into private encrypted communications and computers and leaning on major businesses to provide all their data.
This means that using products from Microsoft, Google, Twitter, whatever is pretty much guaranteed to get you bagged, tagged, and had.
It does look like, for now, Truecrypt and GPG are both snoop proof.
In general, you want to use open source software with no place for government control to be inserted into your processes without your knowledge.
From this posting (of a PDF): https://www.schneier.com/paper-pptpv2.pdf you can get a more in depth look at the encryption method. They do have some interesting observations, like:
It is not clear to us why the MS-CHAPv2 designers chose such a complicated and insecure algorithm for generating 24-byte responses, when a simpler and more secure alternative was available.
The most obvious reason was that it was requested to be done that way by someone with authority.
What can I say. I’m torn between a certain degree of smugness and a large dose of resentment. Put “Snowden NSA” into any search engine and step back. After years of folks “poo-pooing” my concerns over privacy, security, and the leaky nature of Microsoft (not to mention the potential evil of phones with GPS in them and the potential for abuse in ‘social networking’); I’m finally vindicated.
Like that old Unix Sysadmin’s joke: “I’m not paranoid, they are out to get me! I’m the SysAdmin.” I’ve spent a long time defending companies against outside attacks and hacking. So yes, they were out to get me. Every single day (and I had the log files to prove it….)
So OK, a minute or two of being smug.
But I’m also aghast at how completely and easily folks have accepted that their cell phone is a personal tag and tracker for the Government, that their email is for public consumption, and that their medical records are Big Brother’s Property. (The “right to an abortion” rested on an implied right to privacy in the constitution. How can that stand when the medical record of that abortion must be sent to The Government….)
I’ve worked out how to make a “DIY” cell phone without GPS and that can run over cell circuits or WiFi. I need to put some more work into it, but in a few days ought to have it small enough to be portable. I’ve posted some clues on how to secure your machine from intrusion (TruCrypt and Dongle Pi for example). I resent that I have to spend that much time to secure my constitutional right to privacy and my constitutional right to be secure in “my papers and effects”.
As hardware prices plunge, DIY decryption engines will be ever cheaper. Putting back door weaknesses in code just begs for folks to exploit them. It is, at it’s core, both immoral and profoundly stupid.
Yet our government is doing it to us.
OK, if you are not using Linux now, start getting comfortable with it. It is not “owned” by anyone, so is harder to force it to do something. The source code is widely used. Folks ought to notice “odd things” inserted into the code (should it happen) and remove them. In short, a global “barn raising” team of millions is looking at the code all the time. And a TLA “leaning” on someone has the hard job of figuring out who, and how to prevent everyone else from seeing the work product.
OpenVPN is stronger than MS-VPN and is likely safe even in the heat. Linux isn’t as prone to being a “chatty Cathy) as MS. So tend to that direction. encrypt files with any messages in them and send those encrypted files though email agents such as yahoo or Google. Encrypt everything you can. Even if you don’t need to.
Even the NSA can’t spend the money needed to decrypt all versions encrypted things. So having more encrypted files to hide among is a valuable thing.
That’s it for now, but over time I’ll be posting more bits of pointers on being secure in a police state with paid snoops and corrupted corporate trust. That seems to be where we are headed. Even little things like just turning the cell phone off when driving. It’s illegal to talk on it anyway, so just shut it down. Remember, you are not paranoid when it has been demonstrated that the government is spying on everyone. And pressuring companies to provide data / access and install back doors. The only thing you can trust is open source software.
And with that, it’s time for bed (as the sun comes up ;-) Time for “sweet dreams”.