One-Time Password Algorithm (TOTP, HOTP)
Table of Contents
1. 简介
为了提高安全性，一些系统在登录时，除了需要用户提供正确密码外，往往还需要用户通过其它的认证方式（2FA）。比如，短信验证码校验，密码器中的动态口令校验等都是常见的 2FA。
密码器中的动态口令是一个 6 至 8 位的数字，它是一次一用的密码（One-Time Password, OTP），有硬件形式（如图 1 所示），也有软件形式（如图 2 所示）。
Figure 1: RSA SecurID (model SID800)
Figure 2: Google Authenticator
本文将介绍 One-Time Password 的原理。
2. OTP 原理
One-Time Password 的原理比较简单，它利用 HMAC 和 Truncate 操作来让 Client 和 Server 各自产生相同的动态口令：
hmac_result=HMAC(Key, Message) # Key 是 Client 和 Server 端事先约定好的一个秘密值 code=Truncate(hmac_result) # 通过 Truncate 把 HMAC 结果转换为 6 至 8 位的数字
每次 Client 和 Server 需要产生一个相同的动态口令时，就设置一个相同的 Message 运行上面的函数。有两种类型的 One-Time Password，它们对 Message 取值有不同的规定：
- HOTP，它使用一个每次增加的 Counter 作为 HMAC 的 Message 值；这个 Counter 值需要在 Client 和 Server 之间同步。
- TOTP，它是 HOTP 的特殊情况，使用时间
T = (Current Unix time) / 30作为 HMAC 的 Message 值。这样 Client 和 Server 之间每隔 30 秒就可以产生一个新的一次一用的相同密码。
图 3 演示了 TOTP 作为用户登录系统 2FA 的基本过程。
Figure 3: TOTP 作为用户登录系统 2FA 的基本过程
需要说明的是， 图 3 中 HOTP Client 中的 Shared Secret 和 Server 端的 Shared Secret 必须相同（在用户为帐户绑定 2FA 时会完成这个过程），这样它们才能产生相同的一次一用密码。
用户为帐户绑定 2FA 的过程一般为：Server 端产生 Shared Secret，返回给前端，前端把 Shared Secret 展示为二维码，用户使用某个 TOPT Client（如 Google Authenticator）扫描二维码后，二维码中编码的 Shared Secret 就会保存在 TOTP Client 中，以备需要时使用。
3. Key Uri Format（二维码编码数据）
前面介绍过，在用户为帐户绑定 2FA 时，Server 端会产生 Shared Secret，这个 Shared Secret 需要保存到用户的 TOPT Client（如 Google Authenticator）。一般来说，会把 Shared Secret 编码在二维码中，以方便用户通过 TOPT Client 扫描二维码来得到这个 Shared Secret。
下面介绍一下二维码的编码数据的具体格式：
otpauth://TYPE/LABEL?PARAMETERS
其中：
- TYPE 有两个可选值：
hotp和totp。 - LABLE 格式为
accountname或者issuer:accountname。 - PARAMETERS 中的参数有 secret/issuer/algorithm/digits/period。其中只有
secret是强制参数，它的值是 Shared Secret 的 Base32 编码；issuer是推荐参数（注：issuer 参数既出现在了 LABLE 中，又出现在了 PARAMETERS。但由于旧版本的 Google Authenticator 只会从 LABLE 中读取 issuer，而新版本的 Google Authenticator 从 PARAMETERS 中读取 issuer 值，为了更好的兼容性，推荐在 LABLE 和 PARAMETERS 中同时设置 issuer 参数，且其值一样）。
下面是一个例子：
otpauth://totp/Example:alice@google.com?secret=JBSWY3DPEHPK3PXP&issuer=Example
下面是加上了所有的可选参数后的例子：
otpauth://totp/ACME%20Co:john.doe@email.com?secret=HXDMVJECJJWSRB3HWIZR4IFUGFTMXBOZ&issuer=ACME%20Co&algorithm=SHA1&digits=6&period=30
参考：https://github.com/google/google-authenticator/wiki/Key-Uri-Format
4. TOTP 计算实例
下面通过例子来演示如何计算 TOTP。
前面介绍过，TOTP 是通过下面两步计算而来的：
hmac_result=HMAC(Key=Shared Secret, Message=(Current Unix time) / 30) code=Truncate(hmac_result)
下面例子假设 HMAC 中使用 SHA1 为哈希函数，输出数字为 6 位。
问题：Server 和 Client 约定的 Shared Secret 为 0x3132333435363738393031323334353637383930，当前时间为 UTC 时间 2603-10-11 11:33:20，那么这个时间对应的 TOTP 为多少呢？注：这些数值来自于 RFC6238 的 Test Vectors。
4.1. 计算 HMAC 值
第一步，计算 HMAC 值。UTC 时间 2603-10-11 11:33:20 转换为 Unix 时间戳为 20000000000。所以 Message=20000000000/30=666666666=0x27bc86aa 。 由于在 RFC4226 5.1 中规定了 Counter（也就是这里的 Message）是一个 8 bytes 的值。 所以，整数 666666666 对应的 8 bytes 十六进制就是 0x0000000027bc86aa。从而容易计算出 HMAC 结果：
hmac_result=HMAC-SHA-1(Key=0x3132333435363738393031323334353637383930, Message=0x0000000027bc86aa)
=0xab07e97e2c1278769dbcd75783aabde75ed8550a
4.2. 运行 Truncate 操作
第二步：通过 Truncate 操作把 HMAC 结果转换为 6 位（或者 7 位，或者 8 位）的数字。Truncate 伪代码：
int offset = hmac_result[length_of_hmac_result - 1] & 0xf ; /* 取 HMAC 结果的最后 4 个比特位 */
int bin_code = (hmac_result[offset] & 0x7f) << 24
| (hmac_result[offset+1] & 0xff) << 16
| (hmac_result[offset+2] & 0xff) << 8
| (hmac_result[offset+3] & 0xff) ;
下面通过前面 HMAC 的例子介绍一下 Truncate 操作。
------------------------------------------------------------- | Byte Number | ------------------------------------------------------------- |00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19| ------------------------------------------------------------- | Byte Value | ------------------------------------------------------------- |ab|07|e9|7e|2c|12|78|76|9d|bc|d7|57|83|aa|bd|e7|5e|d8|55|0a| -------------------------------***********-----------------+|
Truncate 的详细过程如下：
- 取 HMAC 结果的最后 4 个比特位，这个例子中就是 0xa，对应的十进制数就是 10，把它作为 offset 从 HMAC 结果中取 4 个字节 （上面示例中用星号标记的数字），得到的 4 个字节（即 32 比特位）的数为：0xd75783aa。
- 把上面得到的 4 个字节的数的首个比特位设置为 0， 即得到 0x575783aa，对应的十进制数就是 1465353130。
- 最后，要输出 6 位 TOTP 时，就进行模运算 \(\bmod 10^6\) ，即取十进制数的最后 6 位，即 353130。类似地，如果要输出 7 位 TOTP，就进行模运算 \(\bmod 10^7\) ，即 5353130；如果要输出 8 位 TOTP，就进行模运算 \(\bmod 10^8\) ，即 65353130。
Truncate 操作总结如图 4 所示。
Figure 4: Truncate 操作
注：为什么要把从 offset 处得到的 4 个字节的数的首个比特位设置为 0 呢？在 RFC4226 中是这样说明的：
The reason for masking the most significant bit of P is to avoid confusion about signed vs. unsigned modulo computations. Different processors perform these operations differently, and masking out the signed bit removes all ambiguity.