At Defcon 20 last weekend, David Hulton and I gave a
presentation on cracking MS-CHAPv2. This blog post is meant to be a rough overview of what we covered
in our talk.
Why MS-CHAPv2?
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. This included some high profile examples such as iPredator,
The Pirate Bay's VPN service, which is presumably designed to protect communication from state-level observation:
We believe that MS-CHAPv2 remains so prevalent because previous examinations of the protocol's potential
weaknesses have focused mostly on dictionary attacks. Combine this narrow focus with its extremely wide
base of supported clients and default OS compatibility, and it's understandably very tempting to deploy
as the user experience with the least amount of friction.
In their 1999 analysis of the protocol, for instance, Bruce Schneier and Mudge conclude "Microsoft has improved PPTP to correct the major security weaknesses described in [SM98]. However, the fundamental weakness of the authentication and encryption protocol is that it is only as secure as the password chosen by the user." [emphasis added] This, along with other writings, has led both service providers and users to conclude that they can use MS-CHAPv2 in the form of PPTP VPNs and mutually authenticating WPA2 Enterprise servers safely, if they choose good passphrases.
In their 1999 analysis of the protocol, for instance, Bruce Schneier and Mudge conclude "Microsoft has improved PPTP to correct the major security weaknesses described in [SM98]. However, the fundamental weakness of the authentication and encryption protocol is that it is only as secure as the password chosen by the user." [emphasis added] This, along with other writings, has led both service providers and users to conclude that they can use MS-CHAPv2 in the form of PPTP VPNs and mutually authenticating WPA2 Enterprise servers safely, if they choose good passphrases.
As an example, based on the analysis of the Schneier paper, Riseup.net, a security-focused VPN provider, went so
far as to generate uniformly random 21-character passphrases for their users, without ever allowing the user
the opportunity to choose their own, in order to ensure that they could deploy their PPTP VPN service safely.
The Protocol
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:
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:
Given that everything else is known, we can try ignoring everything but the core unknown, and seeing if
there are any possibilities available to us:
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.
Typically, given a packet capture, this is where a network adversary would attempt to employ a dictionary
attack. Using a tool such as asleap, it's possible to rapidly attempt a series of password
guesses offline. The attacker can simply calculate MD4(password_guess), split that hash up into three DES
keys, encrypt the known plaintext three times, and see if the concatenated output from those DES operations
matches the known ciphertext.
The problem with this approach is that it won't give the attacker a 100% success rate, and relies on the user's propensity for selecting a predictable password. In the case of the riseup.net PPTP VPN service, for instance, the attacker would need to attempt guesses across the full 96 key character set for all 21 characters of the generated password. That's a total complexity of 9621 — slightly larger than 2138, or what you could think of as a 138 bit key.
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 2128 — which will likely be forever computationally infeasible.
Divide And Conquer
The problem with this approach is that it won't give the attacker a 100% success rate, and relies on the user's propensity for selecting a predictable password. In the case of the riseup.net PPTP VPN service, for instance, the attacker would need to attempt guesses across the full 96 key character set for all 21 characters of the generated password. That's a total complexity of 9621 — slightly larger than 2138, or what you could think of as a 138 bit key.
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 2128 — which will likely be forever computationally infeasible.
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
2128),
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 257.59
This is certainly better than 2138 or 2128, 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:
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 257.59
This is certainly better than 2138 or 2128, 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:
Since the third DES key is only two bytes long, a keyspace of 216, 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 257.
Again, still a big number, but considerably better. We're left with, essentially, this core problem:
Again, still a big number, but considerably better. We're left with, essentially, this core problem:
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. The naive approach to cracking these DES operations
would look like:
...iterate over every key in the keyspace, and use each key to encrypt our known plaintext and compare it to
our first known ciphertext. When we find a match, we start over and iterate through every key in the keyspace,
encrypt our known plaintext, and compare it to our second known ciphertext.
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:
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.
Cracking DES
This means that, effectively, the security of MS-CHAPv2 can be reduced to the strength of a single DES encryption.
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.
With Pico Computing's DES cracking machine in hand, we can now crack any MS-CHAPv2 handshake in less than
a day.
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.
What do you win?
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.
At this point, you can plug the cracked MD4 hash CloudCracker gives you back into chapcrack,
and it will decrypt the entire network capture (and all future captures for that user). Alternately, you can
also use it to login to the user's VPN service or WPA2 Enterprise radius server.
We hope that by making this service available, we can effectively end the use of MS-CHAPv2 on the internet once and for all. And as always, submitting MS-CHAPv2 jobs to CloudCracker is available through the standard web interface as well as the API.
What Now?
We hope that by making this service available, we can effectively end the use of MS-CHAPv2 on the internet once and for all. And as always, submitting MS-CHAPv2 jobs to CloudCracker is available through the standard web interface as well as the API.
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.
Thanks
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.
Big thanks are due to Marsh Ray, for advocating and collaborating
on this work.
— Moxie Marlinspike, Jul 29, 2012
No comments:
Post a Comment