ABSTRACT: The Point-to-Point Tunneling Protocol (PPTP) is used to secure PPP connections over TCP/IP link. In response to [SM98], Microsoft released extensions to the PPTP authentication mechanism (MS-CHAP), called MS-CHAPv2. We present an overview of the changes in the authentication and encryption-key generation portions of MS-CHAPv2, and assess the improvements and remaining weaknesses in Microsoft's PPTP implementation.

1 Introduction

The Point-to-Point Tunneling Protocol (PPTP) [HPV+97] is a protocol that allows Point-to-Point Protocol (PPP) connections [Sim94] to be tunneled through an IP network, creating a Virtual Private Network (VPN). Microsoft has implemented its own algorithms and protocols to support PPTP. This implementation of PPTP, called Microsoft PPTP, is used extensively in commercial VPN products precisely because it is already a part of the Microsoft Windows 95, 98, and NT operating systems.

The authentication protocol in Microsoft PPTP is the Microsoft Challenge/Reply Handshake Protocol (MS-CHAP) [ZC98]; the encryption protocol is Microsoft Point to Point Encryption (MPPE) [PZ98]. After Microsoft's PPTP was cryptanalyzed [SM98] and significant weaknesses were publicized, Microsoft upgraded their protocols [Zor98a, Zor98b, Zor99]. The new version is called MS-CHAP version 2 (MS-CHAPv2); the older version has been renamed as MS-CHAP version 1 (MS-CHAPv1). MS-CHAPv2 is available as an upgrade for Microsoft Windows 95, Windows 98, and Windows NT 4.0 (DUN 1.3) [Mic98a,Mic98b]. Even though this upgrade is available, we believe that most implementations of PPTP use MS-CHAPv1.

This paper examines MS-CHAPv2 and discusses how well it addresses the security weaknesses outlined in [SM98].

The most significant changes from MS-CHAPv1 to MS-CHAPv2 are:

• The weaker LAN Manager hash is no longer sent along with the stronger Windows NT hash. This is to prevent automatic password crackers like L0phtcrack [L99] from first breaking the weaker LAN Manager hash and then using that information to break the stronger NT hash [L97].
• An authentication scheme for the server has been introduced. This is to prevent malicious servers from masquerading as legitimate servers.
• The change password packets from MS-CHAPv1 have been replaced by a single change password packet in MS-CHAPv2. This is to prevent the active attack of spoofing MS-CHAP failure packets .
• MPPE uses unique keys in each direction. This is to prevent the trivial cryptanalytic attack of XORing the text stream in each direction to remove the effects of the encryption [SM98].

These changes do correct the major security weaknesses of the original protocol: the inclusion of the LAN Manager hash function and the use of the same OFB encryption key multiple times. However, many security problems are still unaddressed: e.g., how the client protects itself, the fact that the encryption key has the same entropy as the user's password, and the fact that enough data is passed on the wire to allow attackers to mount crypt-and-compare attacks.

This being said, Microsoft obviously took this opportunity to not only fix some of the major cryptographic weaknesses in their implementation of PPTP, but also to improve the quality of their code. The new version is much more robust against denial-of-service style attacks and no longer leaks information regarding the number of active VPN sessions.

2 MS-CHAP, Versions 1 and 2

The MS-CHAPv1 challenge/response mechanism was described in [SM98]. Briefly:

1. Client requests a login challenge from the Server.
2. The Server sends back an 8-byte random challenge.
3. The Client uses the LAN Manager hash of its password to derive three DES keys. Each of these keys is used to encrypt the challenge. All three encrypted blocks are concatenated into a 24-byte reply. The Client creates a second 24-byte reply using the Windows NT hash and the same procedure.
4. The server uses the hashes of the Client's password, stored in a database, to decrypt the replies. If the decrypted blocks match the challenge, the authentication completes and sends a "success" packet back to the client.

This exchange has been modified in MS-CHAPv2. The following is the revised protocol:

1. Client requests a login challenge from the Server.

2. The Server sends back a 16-byte random challenge.

3a. The Client generates a random 16-byte number, called the "Peer Authenticator Challenge."

3b. The Client generates an 8-byte challenge by hashing the 16-byte challenge received in step (2), the 16-byte Peer Authenticator Challenge generated in step (3a), and the Client's username. (See Section 3 for details.)

3c. The Client creates a 24-byte reply, using the Windows NT hash function and the 8-byte challenge generated in step (3b). This process is identical to MS-CHAPv1.

3d. The Client sends the Server the results of steps (3a) and (3c).

4a. The Server uses the hashes of the Client's password, stored in a database, to decrypt the replies. If the decrypted blocks match the challenge, the Client is authenticated.

4b. The Server uses the 16-byte Peer Authenticator Challenge from the client, as well as the Client's hashed password, to create a 20-byte "Authenticator Response." (See Section 4 for details.)

5. The Client also computes the Authenticator Response. If the computed response matches the received response, the Server is authenticated.

A general description of the changes between MS-CHAPv1 and MS-CHAPv2 is given in Figure 1.

MS-CHAP Version 1 MS-CHAP Version 2

Negotiates CHAP with an algorithm value of 0x80. Negotiates CHAP with an algorithm value of 0x81.

Server sends an 8-byte challenge value. Server sends a 16-byte value to be used by the client in creating an 8-byte challenge value.

Client sends 24-byte LANMAN and 24-byte NT response to 8-byte challenge. Client sends 16-byte peer challenge that was used in creating the hidden 8-byte challenge, and the 24-byte NT response.

Server sends a response stating SUCCESS or FAILURE. Server sends a response stating SUCCESS or FAILURE and piggybacks an Authenticator Response to the 16-byte peer challenge.

Client decides to continue or end based upon the SUCCESS or FAILURE response above. Client decides to continue or end based upon the SUCCESS or FAILURE response above. In addition, the Client checks the validity of the Authenticator Response and disconnects if it is not the expected value.

Figure 1: Some basic differences between MSCHAP V1 and MSCHAP V2 authentication

This protocol works, and eliminates the most serious weaknesses that plagued MS-CHAPv1. In MS-CHAPv1, two parallel hash values were sent from the Client to the Server: the LAN Manager hash and the Windows NT hash. These were two different hashes of the same User password. The LAN Manager hash is a much weaker hash function, and password-cracker programs such as L0phtcrack were able to break the LAN Manager hash and then use that information to break the Windows NT hash [L97]. By eliminating the LAN Manager hash in MS-CHAPv2, Microsoft has made this divide-and-conquer attack impossible. Still, the security of this protocol is based on the password used, and L0phtcrack can still break weak passwords using a dictionary attack [L99].

As we will discuss later, multiple layers of hashing are used in the different steps of MS-CHAPv2. While this hashing serves to obscure some of the values, it is unclear what the cryptographic significance of them are. All they seem to do is to slow down the execution of the protocol.

We also have concerns over the amount of control the client has in the influence of the ultimate 8-byte challenge that is used, though we have not yet been able to come up with a viable attack to exploit this. Certainly it opens the possibility of subliminal channels, which can be exploited in other contexts.

3 MS-CHAPv2: Deriving the 8-byte Challenge for the 24-byte Response

In MS-CHAPv1, the Server sends the Client an 8-byte random challenge. This challenge is used, together with the Client's password and a hash function, to create a pair of 24-byte responses.

In MS-CHAPv2, the Server sends the Client a 16-byte challenge. This challenge is not used by the Client directly; the Client derives an 8-byte value from this 16-byte challenge. The derivation process is as follows:

1. The Client creates a 16-byte random number, called the Peer Authenticator Challenge.
2. The Client concatenates the Peer Authenticator Challenge with the 16-byte challenge received from the server and the Client's username.
3. The client hashes the result with SHA-1 [NIST93].
4. The first eight bytes of the hash become the 8-byte challenge.

It is these 8 bytes that the Client will use to encrypt the 16-byte local password hash (using the Windows NT hash function) to obtain the 24-byte response, which the Client will send to the server. This method is identical to MS-CHAPv1, and has been described in [SM98].

3.1 Analysis

It is unclear to us why this protocol is so complicated. At first glance, it seems reasonable that the Client not use the challenge from the Server directly, since it is known to an eavesdropper. But instead of deriving a new challenge from some secret information-the password hash, for example-the Client uses a unique random number that is sent to the Server later in the protocol. There is no reason why the Client cannot use the Server's challenge directly and not use the Peer Authenticator Challenge at all.

4 MS-CHAPv2: Deriving the 20-byte Authenticator Response

In MS-CHAPv2, the Server sends the Client a 20-byte Authenticator Response. The Client calculates the same value, and then compares it with the value received from the Server in order to complete the mutual authentication process. This value is created as follows:

1. The Server (or the Client) hashes the 16-byte NT password hash with [Riv91] to get password-hash-hash. (The Server stores the client's password hashed with MD4; this is the NT password hash value.)
2. The Server concatenates the password-hash-hash, the 24-byte NT response, and the literal string "Magic server to client constant", and then hashes the result with SHA.
3. The Server concatenates the 20-byte SHA output from step (2), the initial 8-byte generated challenge (see Section 3) and the literal string "Pad to make it do more than one iteration", and then hashes the result with SHA.

The resulting 20 bytes are the mutual authenticator response.

4.1 Analysis

Again, this process is much more complicated than required. There is no reason to use SHA twice; a single hashing has the same security properties.

5 Analysis of MS-CHAPv2

We do not know why Microsoft chose such a complicated protocol, since this is not stronger than the following:

1. The Server sends the Client an 8-byte challenge.
2. The Client encrypts the 16-byte local password hash with an 8-byte challenge and sends the Server the 24-byte response, an 8-byte challenge of its own, and the username.
3. The Server sends a pass/fail packet with a 24-byte response to the Client's challenge, which is the user's password-hash-hash encrypted with the Client's 8-byte challenge.

The downside to the MS-CHAPv2 protocol is that an eavesdropper can obtain two copies of the same plaintext, encrypted with two different keys. However, in the current model, watching the network for any length of time will still give you multiple copies of a user challenge/response as the user logs in and out, which will be encrypted with different keys.

As it stands, a passive listener is still able to get the 8-byte challenge and the 24-byte response from the information sent. The popular hacker tool L0phtcrack [L97], which breaks Windows NT passwords, works with this data as input. This task was much easier with MS-CHAPv1, since the weaker LAN Manager hash was sent alongside the stronger Windows NT hash; L0phtcrack first broke the former and then used that information to break the latter [L99]. L0phtcrack can still break most common passwords from the Windows NT hash alone [L97]. And this still does not solve the problem of using the user's hash for MPPE keying, PPTP authentication, etc. without negotiating, at least, machine public key/private key methods of exchanging such an important key.

5.1 Version Rollback Attacks

Since Microsoft has attempted to retain some backwards compatibility with MS-CHAPv1, it is possible for an attacker to mount a "version rollback attack" against MS-CHAP. In this attack, the attacker convinces both the Client and the Server not to negotiate the more secure MS-CHAPv2 protocol, but to use the less secure MS-CHAPv1 protocol.

In its documentation, Microsoft claims that the operating systems will try to negotiate MS-CHAPv2 first, and only drop back to MS-CHAPv1 if the first negotiation fails [Mic99]. Additionally, it is possible to set the Server to require MS-CHAPv2. We find this scenario implausible for two reasons. One, the software switches to turn off backwards compatibility are registry settings, and can be difficult to find. And two, since older versions of Windows cannot support MS-CHAPv2, backwards compatibility must be turned on if there are any legacy users on the network. We conclude that version rollback attacks are a significant threat.

6 Changes to MPPE

The original encryption mechanism in Microsoft's Point to Point Encryption protocol (MPPE) used the same encryption keys in each direction (Client to Server, and Server to Client). Since the bulk data encryption routine is the RC4 stream cipher [Sch96], this created a cryptographic attack by XORing the two streams against each other and performing standard cryptanalysis against the result.

In the more recent version, the MPPE keys are derived from MS-CHAPv2 credentials and a unique key is used in each direction. The keys for each direction are still derived from the same value (the Client's NT password hash), but differently depending on the direction.

6.1 Deriving MPPE Keys from MS-CHAPv2 Credentials

MPPE keys can be either 40 bits or 128 bits, and they can be derived from either MS-CHAPv1 credentials or MS-CHAPv2 credentials. The original derivation protocol (from MS-CHAPv1) was described in [SM98]. Briefly, the password hash is hashed again using SHA, and then truncated. For a 40-bit key, the SHA hash is truncated to 64 bits, and then the high-order 24 bits are set to 0xd1269e. For a 128-bit key, the SHA hash is truncated to 128 bits. This key is used to encrypt traffic from the Client to the Server and traffic from the Server to the Client, opening a major security vulnerability. This has been corrected in MS-CHAPv2.

Deriving MPPE keys from MS-CHAPv2 credentials works as follows:

1. Hash the 16-byte NT password hash, the 24-byte response from the MS-CHAPv2 exchange, and a 27-byte constant (the string "This is the MPPE Master Key") with SHA. Truncate to get a 16-byte master-master key.
2. Using a deterministic process, convert the master-master key to a pair of session keys.

For 40-bit session keys, this is done as follows:

1. Hash the master-master key, 40 bytes of 0x00, an 84-byte constant and 40 bytes of 0xF2 with SHA. Truncate to get an 8-byte output.
2. Set the high-order 24 bits of 0xd1269e, resulting in a 40-bit key.

The magic constants are different, depending on whether the key is used to encrypt traffic from the Client to the Server, or from the Server to the Client.

For 128-bit session keys, the process is as follows:

1. Hash the master-master key, 40 bytes of 0x00, an 84-byte constant (magic constant 2 or 3), and 40 bytes of 0xF2 with SHA. Truncate to get a 16-byte output.

6.2 Analysis

This modification means that unique keys are used in each direction, but does not solve the serious problem of weak keys. The keys are still a function of the password, and hence contain no more entropy than the password. Even though the RC4 algorithm may theoretically have 128-bits of entropy, the actual passwords used for key generation have much less. This having been said, using different keys in each direction is still a major improvement in the protocol.

7 Conclusions

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. As computers get faster and distributed attacks against password files become more feasible, the list of bad passwords-dictionary words, words with random capitalization, words with the addition of numbers, words with numbers replacing letters, reversed words, acronyms, words with the addition of punctuation-becomes larger. Since authentication and key-exchange protocols which do not allow passive dictionary attacks against the user's password are possible-Encrypted Key Exchange [BM92,BM94] and its variants [Jab96,Jab97,Wu98], IPSec-it seems imprudent for Microsoft to continue to rely on the security of passwords. Our hope is that PPTP continues to see a decline in use as IPSec becomes more prevalent.

8 Bibliography

[BM92] S.M. Bellovin and M. Merritt, "Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks," Proceedings of the IEEE Symposium on Research in Security and Privacy, May 1992, pp. 72-84.

[BM94] S.M. Bellovin and M. Merritt, "Augmented Encrypted Key Exchange: A Password-Based Protocol Secure Against Dictionary Attacks and Password File Compromise," AT&T Bell Laboratories, 1994.

[HPV+97] K. Hamzeh, G.S. Pall, W. Verthein, J. Taarud, and W.A. Little, "Point-to-Point Tunneling Protocol," Internet Draft, IETF, Jul 1997. http://www.ietf.org/internet-drafts/draft-ietf-pppext-pptp-10.txt. [link dead]

[Jab96] D. Jablon, "Strong Password-Only Authenticated Key Exchange," ACM Computer Communications Review, Oct 96, pp. 5-26.

[Jab97] D. Jablon, "Extended Password Key Exchange Protocols Immune to Dictionary Attacks," Proceedings of the Sixth Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises, IEEE Computer Society, 1997, pp. 248-255.

[L97] L0pht Heavy Industries, Inc., "A L0phtCrack Technical Rant," Jul 1997. http://www.l0pht.com/l0phtcrack/rant.html. [link dead]

[L99] L0pht Heavy Industries, Inc, L0phtcrack, 1999, http://www.l0pht.com/l0phtcrack/. [link dead; see http://www.atstake.com/research/lc3/]

[Mic96a] Microsoft Corporation, Advanced Windows NT Concepts, New Riders Publishing, 1996. Relevant chapter at http://www.microsoft.com/communications/nrpptp.htm.

[Mic96b] Microsoft Corporation, "Point-to-Point Tunneling Protocol (PPTP) Frequently Asked Questions," Jul 1996. [Mic99] Microsoft, Corporation, "Windows 98 Dial-Up Networking Security Upgrade Release Notes," Feb 1999, http://support.microsoft.com/support/kb/articles/Q189/7/71.asp.

[Mic98a] Microsoft Corporation, "Frequently Asked Questions about Microsoft VPN Security," Dec 1998, http://www.microsoft.com/NTServer/commserv/deployment/moreinfo/VPNSec_FAQ.asp [link dead; see http://www.microsoft.com/ntserver/support/faqs/VPNSec_FAQ.asp

[Mic98b] Microsoft Corporation, "Microsoft Windows 95 Dial-Up Networking 1.3 Upgrade Release Notes," 1998, http://support.microsoft.com/support/kb/articles/q154/0/91.asp

[NIST93] National Institute of Standards and Technology, "Secure Hash Standard," U.S. Department of Commerce, May 1993.

[PZ98] G.S. Pall and G. Zorn, "Microsoft Point-to-Point Encryption (MPPE) Protocol," Network Working Group, Internet Draft, IETF, Mar 1998. http://www.ietf.org/internet-drafts/draft-ietf-pppext-mppe-03.txt. [link dead]

[Riv91] R. Rivest, "The MD4 Message Digest Algorithm," Advances in Cryptology-CRYPTO '90 Proceedings, Springer-Verlag, 1991, pp. 303-311.

[Sim94] W. Simpson, "The Point-to-Point Protocol (PPP)," Network Working Group, STD 51, RFC 1661, Jul 1994. http://www.isi.edu/in-notes/rfc1661.txt.

[Sch96] B. Schneier, Applied Cryptography, 2nd Edition, John Wiley & Sons, 1996.

[SM98] B. Schneier and Mudge, "Cryptanalysis of Microsoft's Point-to-Point Tunneling Protocol (PPTP)," Proceedings of the 5th ACM Conference on Communications and Computer Security, ACM Press, pp. 132-141. http://www.schneier.com/pptp.html.

[Wu98] T. Wu, "The Secure Remote Password Protocol," Proceedings of the 1998 Internet Society Network and Distributed System Security Symposium, Mar 1998, pp. 97-111.

[ZC98] G. Zorn and S. Cobb, "Microsoft PPP CHAP Extensions," Network Working Group Internet Draft, Mar 1998. http://www.ietf.org/internet-drafts/draft-ietf-pppext-mschap-00.txt [link dead as of 1999-08-27; still available here]

[Zor98a] G. Zorn, "Deriving MPPE Keys from MS-CHAP V1 Credentials," Network Working Group Internet Draft, Sep 1998. http://www.ietf.org/internet-drafts/draft-ietf-pppext-mschapv1-keys-00.txt [link dead; still available here].

[Zor98b] G. Zorn, "Deriving MPPE Keys from MS-CHAP V2 Credentials," Network Working Group Internet Draft, Nov 1998. http://tools.ietf.org/wg/pppext/draft-ietf-pppext-
mschapv2-keys/draft-ietf-pppext-mschapv2-keys-02-from-01.wdiff.html.

[Zor99] G. Zorn, "Microsoft PPP CHAP Extensions, Version 2," Network Working Group Internet Draft, Apr 1999. http://www.ietf.org/internet-drafts/draft-ietf-pppext-mschap-v2-03.txt.