多步验证那些事#
作者 小山 (ArcBlock 后端工程师)
现如今，越来越多的网站开启了多步验证模式进行登录。在ArcBlock，我们开发的BlockAuth模块就很好地支持了MFA，让开发者可以很容易在自己开发的区块链应用中使用多步验证来提高安全性。
开启验证时候的二维码到底藏了什么不能说的秘密？手机上身份验证器的核心功能只要6行代码就能实现？多步验证的过程中蕴藏了那些有趣的密码学原理？多步验证安全吗？如何破解多步验证？本文将和你聊聊多步验证那些事。
什么是多步验证？#
多步验证即Multi-Factor Authentication(MFA)，顾名思义，就是需要进行多步的验证。如果只验证两步那就叫两步验证Two-Factor Authentication(2FA)。
两步验证举个例子。当我们登录github的时候首先输入用户名密码进行第一步验证；接下来在手机上的身份验证器app上输入一个生成的六位数密码进行第二步验证，之后便可顺利登陆。
多步验证背后用到了不少密码学的知识，还有一系列rfc的规范。
一次性密码otp#
我们把时间回到1998年，ietf发布了rfc 2289。这套规范定义了一次性密码(one-time password, otp)。为啥要一次性密码呢？因为当用户通过用户名和密码进行登录时，如果密码一旦被获取，则黑客可以用该密码进行登录，这个叫重放攻击。如何避免重放攻击呢？用一次性密码就行了。一次性密码就像一次性筷子一样，用完扔掉即可，别人捡起来也没啥用。
MD5 ENCODINGS
Pass Phrase Seed Cnt Hex Six Word Format
====================================================================================
This is a test. TeSt 0 9E87 6134 D904 99DD INCH SEA ANNE LONG AHEM TOUR
This is a test. TeSt 1 7965 E054 36F5 029F EASE OIL FUM CURE AWRY AVIS
This is a test. TeSt 99 50FE 1962 C496 5880 BAIL TUFT BITS GANG CHEF THY
AbCdEfGhIjK alpha1 0 8706 6DD9 644B F206 FULL PEW DOWN ONCE MORT ARC
AbCdEfGhIjK alpha1 1 7CD3 4C10 40AD D14B FACT HOOF AT FIST SITE KENT
AbCdEfGhIjK alpha1 99 5AA3 7A81 F212 146C BODE HOP JAKE STOW JUT RAP
OTP's are good correct 0 F205 7539 43DE 4CF9 ULAN NEW ARMY FUSE SUIT EYED
OTP's are good correct 1 DDCD AC95 6F23 4937 SKIM CULT LOB SLAM POE HOWL
OTP's are good correct 99 B203 E28F A525 BE47 LONG IVY JULY AJAR BOND LEE这是rfc里给的一个例子。当服务器选定一个密码、种子和计数器时，会生成一个固定长度的二进制数，通过查表得到6个由大写字母组成的字符串，此为一次性密码。用户输入这些字符串来进行登录，用后即弃。服务器的计数器改变，下次再登录会生成另一个一次性密码。
98年那会互联网刚兴起，有个用户名密码登录就不错了，用一次性密码登录还不是很流行，而且用户每次要输入6个英文单词，比较麻烦。于是乎2005年ietf又发布了一套rfc 4226定义了基于hmac的一次性密码(hmac-based one-time password, hotp)。hmac又是什么鬼？
hmac#
直接讲hmac是什么会比较没有上下文，我们先问自己一个问题，我们为什么需要哈希函数？
假设alice要向bob发送一条消息show me the money。当bob收到该消息的时候，他怎么知道这条消息在传送的过程中没有被人篡改过？于是他和alice商量了一下，发消息时，不仅发送消息，再附加上一条该消息的哈希值。哈希值就是对于任意输入，哈希函数会生成一个固定长度的输出。当bob收到消息的时候，他也进行一次哈希计算，如果他算出来的哈希值和alice发过来的哈希值匹配的话，则表示该消息没有被篡改过。
show me the money
alice ------------------------------------------------------------------> bob
3f3a323ba2bc但是这样会有一个问题，假设eve在监听alice与bob的通讯，她可以改动alice发送的消息成show me the honey，然后她把改过的消息的哈希值算出来附加出去发给bob。当bob收到消息进行哈希计算验证一下，发现和eve发过来的哈希值是一致的。于是bob认为这条消息是没被篡改过的。但是这其实并不是alice发的原始消息。
show me the money show me the honey
alice ----------------------------> eve ----------------------------> bob
3f3a323ba2bc 37954357d876也就是说，单靠哈希值只能保证数据的完整性，但却不能保证数据的真实性，因为任何人都可以计算哈希值。那么有什么方法能既保证数据完整性，又保证数据真实性呢？
一个可能的解决方案#
我们还是来发送show me the money这条消息，但是这次我们选一个密钥rA9。算法很简单，把密钥和要发送的信息连起来，算一次哈希；接着把密钥和刚才算出的哈希连起来，再算一次哈希。我们把第二次的哈希值和消息一起发送给bob。如下图所示
sha
rA9show me the money -------> f023a7d109f1
sha
rA9f023a7d109f1 -------> b15c701d5e63
show me the money
alice ------------------------------------------------------------------> bob
rA9 b15c701d5e63 rA9我们假设alice和bob都有该密钥rA9，当bob收到消息和哈希的时候，也做两次哈希，比较一下，如果一致的话，就证明消息不仅没有篡改过，而且发过来的人有rA9这个密钥，也就是说是从alice发来的。
如果此时eve在中间监听，她可以把消息篡改，但是因为她没有密钥rA9，所以她无法计算出来新的哈希值。所以当bob收到消息时验证一下会发现哈希不一致，于是他可以得出结论，该消息被篡改过了。
show me the money show me the honey
alice ----------------------------> eve ----------------------------> bob
rA9 b15c701d5e63 b15c701d5e63 rA9
233999963a1dhotp#
刚才描述的算法，就是hmac的算法。当我们知道这个之后，我们可以描述一下基于hmac的一次性密码(hotp)的算法。
rA9
hmac(sha,"rA9","0000000000000000")
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
d8 41 ef 1c 96 ac 02 0c d1 a3 32 06 15 58 ec 69 4d d2 3f 32
*
** ** ** ** 2
ef 1c 96 ac
1110 1111 0001 1100 1001 0110 1010 1100
110 1111 0001 1100 1001 0110 1010 1100
1864144556
144556算法如上图所示，首先选定一个密钥rA9。用hmac算法计算出一个消息验证码。这里我们不再用show me the money，而是用一个32位的整数，上面的例子是用0来计算。算出来一个20字节的验证码，我们取最后一个字节的最后半个字节，也就是2，找到索引2之后的4个字节，也就是ef 1c 96 ac，把该32位用二进制表示出来，之后去掉最左边一位的符号位，剩下31位，把该二进制对应的十进制写出来就是1864144556，取末尾的6位既是最后结果144556。这个数字就是我们平日用身份验证器生成的6位数一次性密码。
totp#
基于hmac的一次性密码需要用一个整数作为参数，服务器和客户端之间需要对这个计数器进行同步，那么我们更加常用的一次性密码则是基于时间的(time-based otp, totp)。
时间在计算机中的存储方式其实就是一个整数，unix时间表示从1970年1月1日0点0时0分开始算起到当前时间所经过的秒数。整个totp算法如下
unix epoch time
1970-01-01 00:00:00 0
2018-10-23 17:00:00 1540314000
2038-01-19 03:14:07 2147483647
1901-12-13 20:45:52 -2147483648
hotp("rA9",1540314000/30)
386452把当前时间的unix时间计算出来，除以30后传给hotp函数即可。为什么要除以30呢？因为用户输入这个六位数密码需要时间，给个30秒时间应该足够了，30秒过后这个一次性密码就失效了。
如何交换密钥#
还记得之前的密钥rA9吗？服务器和用户之间是如何交换该密钥的？这就是启动多步验证时候出现的二维码里面的内容。
该二维码是一个叫做uri密钥的格式的编码，长这样
otpauth://totp/GitHub:hellokitty?secret=4fakhx6cibvwwngp&issuer=GitHub其中的secret就是服务器生成的密钥的base32编码。
一个简单身份验证器的实现#
mfa.erl
totp(Key0) ->
T = calendar:datetime_to_gregorian_seconds(calendar:now_to_datetime(erlang:timestamp())) - ?epoch,
Key = decode32(string:uppercase(Key0)),
hotp(Key,T div 30).
hotp(Key,C) ->
<<_:156,Sz:4>> = Hmac = crypto:hmac(sha,Key,<<C:64>>),
<<_:Sz/binary,_:1,N:31,_/binary>> = Hmac,
N rem 1000000.这是一个totp/hotp的Erlang实现，核心部分只要6行代码，跑一下看看
$ cat ~/.mfa/config
{github,"somerandpassword"}.
{gitlab,"somecoolpassword"}.
{google,"somegoodpassword"}.
$ escript mfa.erl
github: 583309, valid in 26s
gitlab: 166210, valid in 26s
google: 704368, valid in 26s多步验证安全吗？#
我们可以看到，实现多步验证并不困难，那么多步验证到底有多安全？我们可以看看如何破解多步验证。因为多步验证的核心其实就是hmac，破解hmac的唯一方法就是用暴力破解密钥。我们可以通过写一个小程序来模拟破解过程。
先随机生成一个3字节长的密钥，再通过暴力算法计算，用1个CPU大约16秒可以破解。
$ erl
1> hack:run().
Key is <<91,101,252>>, hotp for 73 is 076127
potential key found <<12,243,176>>, hotp is 076127
potential key found <<41,163,60>>, hotp is 076127
potential key found <<54,214,149>>, hotp is 076127
potential key found <<57,134,46>>, hotp is 076127
potential key found <<57,206,238>>, hotp is 076127
potential key found <<68,189,61>>, hotp is 076127
potential key found <<70,78,253>>, hotp is 076127
potential key found <<90,172,149>>, hotp is 076127
potential key found <<91,101,252>>, hotp is 076127
potential key found <<96,226,141>>, hotp is 076127
...
*** found key <<91,101,252>> in 16s ***因为是用Erlang，所以可以稍微修改一下程序，用全部的CPU来进行破解
$ erl
1> phack:run(3).
Started 12 worker processes.
Random generated key is <<154,226,246>>, hotp for 360 is 917202
potential key <<22,72,233>> found by worker <0.172.0>, hotp is 917202
potential key <<67,6,87>> found by worker <0.170.0>, hotp is 917202
potential key <<110,133,18>> found by worker <0.168.0>, hotp is 917202
potential key <<153,173,223>> found by worker <0.166.0>, hotp is 917202
potential key <<197,0,181>> found by worker <0.164.0>, hotp is 917202
potential key <<154,226,246>> found by worker <0.166.0>, hotp is 917202
key <<154,226,246>> found by worker <0.166.0> in 1s在这里，我们在一个6核笔记本上跑一下，等同于12个CPU，速度快了12倍，大约1秒就破解了。
当然破解的只是3个字节的密钥。如果我们尝试破解4个字节:
2> phack:run(4).
Started 12 worker processes.
Random generated key is <<81,10,150,35>>, hotp for 375 is 655173
potential key <<170,170,211,211>> found by worker <0.111.0>, hotp is 655173
potential key <<64,3,113,77>> found by worker <0.116.0>, hotp is 655173
potential key <<106,175,21,120>> found by worker <0.114.0>, hotp is 655173
potential key <<0,5,110,147>> found by worker <0.119.0>, hotp is 655173
potential key <<149,93,101,149>> found by worker <0.112.0>, hotp is 655173
potential key <<170,179,226,52>> found by worker <0.111.0>, hotp is 655173
potential key <<213,98,135,55>> found by worker <0.109.0>, hotp is 655173
potential key <<0,21,166,137>> found by worker <0.119.0>, hotp is 655173
potential key <<149,107,68,31>> found by worker <0.112.0>, hotp is 655173
...
key <<81,10,150,35>> found by worker <0.116.0> in 849s花了大概14分钟。每增加一个字节，就相当于增加2^8=256倍破解的难度。下表展示了在一个笔记本上破解mfa要花的时间。
key length bits crack time
1 8 ~0s
2 16 ~0s
3 24 ~16s
4 32 ~1.1h
5 40 ~11.7d
6 48 ~8.2y
7 56 ~2099y
8 64 ~537ky
9 72 ~137my
10 80 ~35kmy可以看到，10字节的密钥通过暴力根本无法破解。目前大多数网站都会用至少10个字节来作为服务器随机生成的密钥。
以上所有的代码都可以在github上找到https://github.com/sunboshan/mfa。
和本文配套的视频讲解可以在这里找到。
希望通过本篇博客让大家对多步验证可以有所了解。在ArcBlock，我们的工程师会对我们所用的工具和技术进行总结，并且分享给大家，希望我们可以一起共同进步。我们还在招人，有兴趣的同学请点击这里。