在线演示

Google Authentication 支持 HOTP 和 TOTP 算法生成二次验证(2FA. two-factor authentication)密码。

HOTP(HMAC-base One-Time Passowrd)

HMAC就是 Hash-based Message Authentication Code 的意思。

客户端和服务器事先协商好一个密钥,用于一次性密码的生成过程,此密钥不被任何第三方所知道。

此外,客户端和服务器各有一个计数器,并且事先将计数值同步。计算完成之后客户端计数器计数值加1。

用户将这一组十进制数输入并且提交之后,服务器端同样的计算,并且与用户提交的数值比较,如果相同,则验证通过,服务器端将计数值增加1。如果不相同,则验证失败。

TOTP(Time-base One-Time Password)

理解了上面的HOTP,那TOTP只是将时间戳代替了计数器。于是就随时间戳变化生成不同密码。

Working

而实际上 Google Authentication 使用 TOTP。核心由三个部分组成。

  • 共享密钥
  • 输入(时间戳)
  • 签名

共享密钥

共享密钥用于在其它客户端获得密码,可以手动输入,可以通过链接或者二维码获得。

注意密钥会被Base32编码,所以要去除空格并转换成大写。然后 保证处理后的密钥位数是8的倍数。

Google 服务使用4位8组共32位的密钥。其它使用 Google Authentication 的不尽相同,像 GitHub 则是16位的密钥。

密钥将URL转换成二维码方便手机或其它设备使用时候遵循以下格式:

otpauth://TYPE/LABEL?PARAMETERS

比如这样:

otpauth://totp/Example:alice@google.com?secret=JBSWY3DPEHPK3PXP&issuer=Example

详细内容可以参考Key Uri Format

输入(时间戳)

TOTP 采用时间戳作为变量,不需要与服务器交互就可以得到密码。那么该如何选取呢?

因为时间每时每刻都在变化,如果选择一个变化太快的 input(例如从某一时间点开始的秒数),那么用户来不及输入密码。如果选择一个变化太慢的 input(例如从某一时间点开始的小时数),那么第三方攻击者就有充足的时间去尝试所有可能的一次性密码(试想6位数字的一次性密码仅仅有10\^6种组合),降低了密码的安全性。

除此之外,变化太慢的 input 还会导致另一个问题。如果用户需要在短时间内两次登录账户,由于密码是一次性的不可重用,用户必须等到下一个一次性密码被生成时才能登录,这意味着最多需要等待59分59秒!这显然不可接受。

综合以上考虑,Google选择了30秒作为时间片,时间戳输入的数值为从Unix epoch(1970年1月1日 00:00:00)来经历的30秒的个数。

还有一个问题是,由于网络延时,用户输入延迟等因素,可能当服务器端接收到一次性密码时,input的数值已经改变,这样就会导致服务器计算的一次性密码值与用户输入的不同,验证失败。解决这个问题个一个方法是,服务器计算当前时间片以及前面的n个时间片内的一次性密码值,只要其中有一个与用户输入的密码相同,则验证通过。当然,n不能太大,否则会降低安全性。

签名

签名使用 HMAC-SHA1 算法。以一个密钥和一个消息为输入,生成一个消息摘要作为输出。

因为算法是单向散列加密,结果不可逆,这样在保证密钥不被第三者知道的情况下,只有使用相同密钥和输入(时间戳)才会得到相同结果,服务端才能判断客户端是合法登录。

h = hmac.new(key, msg, hashlib.sha1).digest()

Algorithm

伪代码:

function GoogleAuthenticatorCode(string secret)
    key := base32decode(secret)
    message := floor(current Unix time / 30)
    hash := HMAC-SHA1(key, message)
    offset := last nibble of hash
    truncatedHash := hash[offset..offset+3]  //4 bytes starting at the offset
    Set the first bit of truncatedHash to zero  //remove the most significant bit
    code := truncatedHash mod 1000000
    pad code with 0 until length of code is 6
    return code

Python 实现:

import hmac
import base64
import struct
import hashlib
import time
import sys

def get_hotp_token(secret, intervals_no):
    key = base64.b32decode(secret)
    msg = struct.pack(">Q", intervals_no)
    h = hmac.new(key, msg, hashlib.sha1).digest()
    o = h[len(h)-1] & 0x0f
    h = (struct.unpack(">I", h[o:o + 4])[0] & 0x7fffffff) % 1000000
    return h

def get_totp_token(secret):
    intervals_no = int(time.time()) // 30
    totp_token = get_hotp_token(secret, intervals_no)
    return totp_token

if __name__ == '__main__':
    if len(sys.argv) != 2:
        print('Must specify key to use.')
        exit(1)
    Sec = sys.argv[1]
    Sec = Sec.replace(' ', '').upper()
    if len(Sec) % 8 != 0:
        print('Illegal base32 data at input byte %d' % ((len(Sec)//8+1)*8))
        exit(1)
    validation_code = get_totp_token(Sec)
    print('Code: %06d  (%02d second(s) remaining.)' %
          (validation_code, 30 - int(time.time()) % 30))

这里还有一个Go的实现,点我传送

See Also

https://en.wikipedia.org/wiki/Google_Authenticator
https://blog.seetee.me/post/2011/google-two-step-verification/
https://garbagecollected.org/2014/09/14/how-google-authenticator-works/
https://security.stackexchange.com/questions/35157/how-does-google-authenticator-work