PAP (Password Authentication Protocol): Para identificarte, este método envía la contraseña sin codificar al servidor. Es bastante inseguro porque la contraseña se puede leer sin problemas.
CHAP (Challenge Authentication Protocol o Protocolo de autentificación de desafío): Es más seguro que el anterior. Al conectar con el servidor este te envía un "desafío".
El desafío consiste en una cadena de caracteres aleatorios generados por el servidor. Tu ordenador responde añadiendo tu contraseña a esos caracteres aleatorios (no sé exactamente de que manera, si lo concatena o que hace, pero es algo asi...) y codifica la cadena de caracteres desultantes con MD5 (que es irreversible). Esta cadena codificada con MD5 se envía al servidor.
Mientras tanto el servidor (que también conoce tu contraseña) ha hecho la misma operación. Si al comparar la cadena que ha calculado el servidor y la que le has enviado coinciden, es que la contraseña es válida.
Con este método NUNCA se envía la contraseña en texto sin codificar, se envia por contra una mezcla de los caracteres aleatorios del desafío y la contraseña codificados con un algoritmo irreversible (imposible de obtener la cadena codificada de nuevo).
MS CHAP es la implementación del CHAP por parte de Microsoft, supongo que funcionará parecido al CHAP en su base.
Es lo mejor que sé explicarlo.