参见：http://forge.mysql.com/wiki/mysql_internals_clientserver_protocol#password_functions
我意译一下，大致就是以下内容：
4.0版本之前
1、服务器发送随机字符串(scramble_buff)给客户端.
2、客户端把用户明文密码加密一下，然后将hash加上服务器的随机字符串加密一下变成新的scramble_buff。(参见sql/password.c:scramble()).
3、客户端将加密后的scramble_buff值发给服务端.
4、服务器将mysql.user.password的值加上原始随机字符串进行加密.
5、服务器比对加密后的hash值和服务端送过来的加密后的scramble_buff.
6、如果一样，则验证成功.
基本就是一个挑战机制。但是注意一点：实质上真正意义上的密码是明文密码的加密hash值; 如果有人知道了这个用户的mysql.user.password(而不用知道原始明文密码)他就能直接登录服务端.
4.1以后版本
4.1以后数据库保存的密码是用sha1加密的：sha1(sha1(password))
1、服务器发送随机字符串(scramble)给客户端.
2、客户端作如下计算:
stage1_hash = sha1(明文密码).
token = sha1(scramble + sha1(stage1_hash)) xor stage1_hash
3、客户端将token发送给服务端
4、服务端作如下计算：
stage1_hash = token xor sha1(scramble + mysql.user.password)
5、服务端比对sha1(stage1_hash)和mysql.user.password，如果匹配，则认证正确。
注意：sha1(a+b)意思是sha1(a字符串连接b字符串).
这次没上一个版本的缺陷了. 有了mysql.user.password和scramble也不能获得token。因为他没法获得stage1_hash。
但是如果这人有这用户的 mysql.user.password 及网络上截取的一次完整验证数据, 他也能根据这次截获的token和scramble反解出stage1_hash的值。而由于stage1_hash是不变的，因此下次连接，他获取了新的scramble后，自己加密一下token，送给服务端也能通过验证而连接到服务器.
最后放一个5.1的认证的抓包结果，注意标红的地方：
server > 127.0.0.1.49130: handshake
127.0.0.1.49130 > server: handshake (new auth)
server > 127.0.0.1.49130: handshake    127.0.0.1.49130 > server: handshake (new auth)    server > 127.0.0.1.49130: ok