Two-Factor Authentication and One-Time Password
双因子认证(Two-Factor Authentication)认证是指结合密码以及实物(令牌、SMS等)两种条件对用户进行认证的方法，提高了系统的安全性。一次性密码(One-Time Passcode)是最为常用的双因子认证方法之一，如：
- HOTP: HMAC-Based One-Time Password
- TOTP: Time-Based One-Time Password
本文主要介绍基于事件的一次性密码的生成算法 HOTP，它由 RFC 4226 定义。
HOTP Aligorithm
HOTP 的生成算法如下：
HOTP(K,C) = Truncate(HMAC-SHA-1(K,C))
其中:
- C: 8-byte 的移动因子，对于客户端，每次生成一次性密码，C 的值加 1；对于服务端，每次认证客服端产生的一次性密码，C 的值加 1，所以客服端和服务端必须同步该数值。
- K: 客户端和服务端的共享密钥，不同的客户端的密钥各不相同。
- HMAC-SHA-1: Hash-based Message Authentication Code, 采用了 SHA1 哈希算法，输出值为 20 Bytes 的消息摘要。
- Truncate: 将消息摘要缩减为一次性验证码，通常为 6 位数字。
该算法可分为 3 个步骤
- Step 1: 生成 20 Byte 的消息摘要 HS，其中 HS = HMAC-SHA-1(K,C)。
- Step 2: 根据 HS 生成 4 Byte 的字符串 Sbits，其中 Sbits = DT(HS)，DT 的步骤请见后面。
- Step 3: 把 Sbits 转换为数字 Snum，再让 D = Snum mod 10^6，D 即为一次性密码。
HMAC-SHA-1
HMAC 是密钥相关的哈希运算消息认证码，由 RFC 2104 定义，hmac 是一个实现该算法的 Python 库，它支持 md5, sha1 等哈希算法，HTOP 采用了 sha1 算法。
import hashlib
import hmac
def get_hmac_sha1(secret, msg):
result = hmac.new(secret, msg, hashlib.sha1).hexdigest()
return result
例如，以 C = 0、K=’12345678901234567890’ 为例，其 hmac_sha1 的摘要为：
>>> K = '12345678901234567890'
>>> C = bytearray([0, 0, 0, 0, 0, 0, 0, 1])
>>> print get_hmac_sha1(K, C)
cc93cf18508d94934c64b65d8ba7667fb7cde4b0
以下为 C 从 0 到 9 时的摘要值:
Secret = '12345678901234567890'
+-------+------------------------------------------+
| Count | Hexadecimal HMAC-SHA-1(secret, count) |
+-------+------------------------------------------+
| 0 | cc93cf18508d94934c64b65d8ba7667fb7cde4b0 |
| 1 | 75a48a19d4cbe100644e8ac1397eea747a2d33ab |
| 2 | 0bacb7fa082fef30782211938bc1c5e70416ff44 |
| 3 | 66c28227d03a2d5529262ff016a1e6ef76557ece |
| 4 | a904c900a64b35909874b33e61c5938a8e15ed1c |
| 5 | a37e783d7b7233c083d4f62926c7a25f238d0316 |
| 6 | bc9cd28561042c83f219324d3c607256c03272ae |
| 7 | a4fb960c0bc06e1eabb804e5b397cdc4b45596fa |
| 8 | 1b3c89f65e6c9e883012052823443f048b4332db |
| 9 | 1637409809a679dc698207310c8c7fc07290d9e5 |
+-------+------------------------------------------+
Truncation
20 Bytes 的消息摘要过于冗长复杂，不利于用户的输入，所以需要将其浓缩为长度合适的验证码。Truncation 就是将 20 Bytes 的消息摘要生成 6 位数字的过程，即上述的 Step 2 和 Step 3。具体步骤如下：
假定用 String 表示消息摘要，String[0] 表示第一个 Byte，依次类推，String[19] 表示第 20 个 Byte。
- 选取 String[19] 的低位 4 bit，用 Offset 表示，其中 0 <= Offset <= 15。
- 令 P = String[Offset]…String[Offset + 3]
- 令 Sbits = P & 0x7fffffff
- 把 Sbits 转换为十进制数字 Snum，再让 D = Snum mod 10^6，D 即为一次性密码。
以值为 0x1f8698690e02ca16618550ef7f19da8e945b555a 的消息摘要为例：
+-----------------------------------------------------------+
| Byte Number |
+-----------------------------------------------------------+
|00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19|
+-----------------------------------------------------------+
| Byte Value |
+-----------------------------------------------------------+
|1f|86|98|69|0e|02|ca|16|61|85|50|ef|7f|19|da|8e|94|5b|55|5a|
+------------------------------***********------------------+
- String[19] 为 0x5a，低位的 4 bit 为 0xa，所以 Offset = 0xa = 10。
- P = String[10]…String[10 + 3] = 0x50ef7f19。
- Sbits = P & 0x7fffffff = 0x50ef7f19
- Snum = 0x50ef7f19 = 1357872921
- 最后的验证码为 D = Snum mod 10^6 = 872921
注意到 Sbits = P & 0x7fffffff，之所以不取 P 的最高位，是为了确保 Sbits 为无符号数，避免在不同硬件平台因为符号位而产生的差异。
以下为 C 从 0 到 9 生成的的一次性密码:
Secret = '12345678901234567890'
+-------+-------------+------------+--------+
| Count | Hexadecimal | Decimal | HOTP |
+-------+-------------+------------+--------+
| 0 | 4c93cf18 | 1284755224 | 755224 |
| 1 | 41397eea | 1094287082 | 287082 |
| 2 | 82fef30 | 137359152 | 359152 |
| 3 | 66ef7655 | 1726969429 | 969429 |
| 4 | 61c5938a | 1640338314 | 338314 |
| 5 | 33c083d4 | 868254676 | 254676 |
| 6 | 7256c032 | 1918287922 | 287922 |
| 7 | 4e5b397 | 82162583 | 162583 |
| 8 | 2823443f | 673399871 | 399871 |
| 9 | 2679dc69 | 645520489 | 520489 |
+-------+-------------+------------+--------+
附：Python Demo
import hashlib
import hmac
def get_hotp_passcode(secret, count):
data = bytearray([int(hex(count >> i & 0xff), 16) for i in (56, 48, 40, 32 ,24, 16, 8, 0)])
hs = hmac.new(secret, data, hashlib.sha1).hexdigest()
offset = int(hs[-1], 16)
sbits = int(hs[offset * 2: offset * 2 + 8], 16) & 0x7fffffff
return sbits % 1000000
Memo
本文转载至 http://wsfdl.com/algorithm/2016/04/05/%E7%90%86%E8%A7%A3HOTP.html
