HOTP和TOTP算法图解

创作时间:

作者:

@小白创作中心

HOTP和TOTP算法图解

引用

CSDN

https://m.blog.csdn.net/wulex/article/details/132750310

本文根据RFC4226和RFC6238文档，详细介绍了HOTP和TOTP算法的原理和实现。两步验证已经被广泛应用于各种互联网应用当中，用来提供安全性。本文将使用图文并茂的方式详细介绍HOTP和TOTP的算法原理，并在最后分析其安全性。当然所有内容都是基于协议的，通过自己的理解更加直观的表达出来。

协议解决的核心问题

通过前面两步验证的使用场景分析，不难看出问题的核心在于如何能够让用户手机应用产生的验证码和服务器产生的验证码一致，或者是在一定范围内一致。参考下图

所以我们的算法就是在解决如何更好的生成这个验证码，既能保证服务器端和客户端同步，还能保证验证码不重复并且不容易被别人反向破解出共享密钥。其中如果是计数，则是HOTP，如果是使用时间来生成验证码，则是TOTP。

HOTP算法图解

符号定义

对于HOTP，通过上图我们已经看到输入算法的主要有两个元素，一个是共享密钥，另外一个是计数。在RFC算法中用一下字母表示：

K 共享密钥，这个密钥的要求是每个HOTP的生成器都必须是唯一的。一般我们都是通过一些随机生成种子的库来实现。
C 计数器，RFC中把它称为移动元素（moving factor）是一个8个byte的数值，而且需要服务器和客户端同步。

另外一个参数比较好理解，Digit表示产生的验证码的位数

最后两个参数可能暂时不好理解，我们先放在这，等用到在解释
T称为限制参数（Throttling Parameter）表示当用户尝试T次OTP授权后不成功将拒绝该用户的连接。
s称为重新同步参数（Resynchronization Parameter）表示服务器将通过累加计数器，来尝试多次验证输入的一次性密码，而这个尝试的次数及为s。该参数主要是有效的容忍用户在客户端无意中生成了额外不用于验证的验证码，导致客户端和服务端不一致，但同时也限制了用户无限制的生成不用于验证的一次性密码。

算法流程

核心步骤主要是使用K C和Digit。

第一步：使用HMAC-SHA-1算法基于K和C生成一个20个字节的十六进制字符串（HS）。关于如何生成这个是另外一个协议来规定的，RFC 2104 HMAC Keyed-Hashing for Message Authentication. 实际上这里的算法并不唯一，还可以使用HMAC-SHA-256和HMAC-SHA-512生成更长的序列。对应到协议中的算法标识就是

HS = HMAC-SHA-1(K,C)

第二步：选择这个20个字节的十六进制字符串（HS下文使用HS代替）的最后一个字节，取其低4位数并转化为十进制。比如图中的例子，第二个字节是5a，第四位就是a，十六进制也就是0xa，转化为十进制就是10。该数字我们定义为Offset，也就是偏移量。

第三步：根据偏移量Offset，我们从HS中的第10（偏移量）个字节开始选取4个字节，作为我们生成OTP的基础数据。图中例子就是选择50ef7f19，十六进制表示就是0x50ef7f19，我们成为Sbits

以上两步在协议中的成为Dynamic Truncation （DT）算法，具体参考以下伪代码：

Let Sbits = DT(HS)  // DT, defined below, 
                    // returns a 31-bit string

展开就是

DT(String) // String = String[0]...String[19]
    Let OffsetBits be the low-order 4 bits of String[19] 
    Offset = StToNum(OffsetBits) // 0 <= OffSet <= 15 
    Let P = String[OffSet]...String[OffSet+3] 
    Return the Last 31 bits of P

第四步：将上一步4个字节的十六进制字符串Sbits转化为十进制，然后用该十进制数对10的Digit次幂进行取模运算。其原理很简单根据取模运算的性质，比如比10大的数MOD 10结果必然是 0到9，MOD 100结果必然是0-99。图中的例子，50ef7f19转化为十进制为1357872921，然后如果需要6位OTP验证码，则1357872921 MOD 10^6 = 872921。

872921就是我们最终生成的OTP。

对应到协议中的算法为：

Let Snum = StToNum(Sbits) // Convert S to a number in
                          // 0...2^{31}-1 
Return D = Snum mod 10^Digit // D is a number in the range
                             // 0...10^{Digit}-1

这一步可能还需要注意一点就是图中案例Digit不能超过10，因为即使超过10，1357872921取模后也不会超过10位了。所以如果我们希望获取更长的验证码，需要在三步中拿到更多的十六进制字节，从而得到更大的十进制数。这个十进制决定了生成的OTP编码的长度。