参见：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 <proto 10 ver 5.1.41-3ubuntu12.6 thd 55 scramble 1EGu9\Aq8_UnI_'@L<*Y >
- 127.0.0.1.49130 > server: Handshake (new auth) <user root db (null) token 6d2c7025c412b997788525b19a5167c89dafcbe max pkt 16777216>
- server > 127.0.0.1.49130: OK <fields 0 affected rows 0 insert id 0 warnings 0>