【IoT】加密与安全:动态密码图解:HOTP与TOTP算法

2023年7月31日发(作者：)

【IoT】加密与安全：动态密码图解：HOTP与TOTP算法1、简介本⽂根据 RFC4226 和 RFC6238 ⽂档，详细的介绍 HOTP 和 TOTP 算法的原理和实现。两步验证已经被⼴泛应⽤于各种互联⽹应⽤当中，⽤来提供安全性。对于如何使⽤两步验证，⼤家并不陌⽣，⽆⾮是开启两步验证，然后出现⼀个⼆维码，使⽤⽀持两步验证的移动应⽤⽐如 GoogleAuthenticator 或者 LassPass Authenticator 扫⼀下⼆维码。这时候应⽤会出现⼀个 6 位数的⼀次性密码，⾸次需要输⼊验证从⽽完成开启过程。以后在登陆的时候，除了输⼊⽤户名和密码外，还需要把当前的移动应⽤上显⽰的 6 位数编码输⼊才能完成登陆。这个过程的背后主要由两个算法来⽀撑：HOTP 和 TOTP。分别对应着两份 RFC 协议 RFC4266 和 RFC6238。前者是 HOTP 的标准，后者是 TOTP 的标准。本⽂将使⽤图⽂并茂的⽅式详细介绍 HOTP 和 TOTP 的算法原理，并在最后分析其安全性。当然所有内容都是基于协议的，通过⾃⼰的理解更加直观的表达出来。2、协议解决的核⼼问题通过前⾯两步验证的使⽤场景分析，不难看出问题的核⼼在于如何能够让⽤户⼿机应⽤产⽣的验证码和服务器产⽣的验证码⼀致，或者是在⼀定范围内⼀致。参考下图：所以我们的算法就是在解决如何更好的⽣成这个验证码，既能保证服务器端和客户端同步，还能保证验证码不重复并且不容易被别⼈反向破解出共享密钥。其中如果是计数，则是 HOTP，如果是使⽤时间来⽣成验证码，则是 TOTP。3、HOTP 算法图解3.1、符号定义对于 HOTP，通过上图我们已经看到输⼊算法的主要有两个元素，⼀个是共享密钥，另外⼀个是计数。在 RFC 算法中⽤⼀下字母表⽰：K 共享密钥，这个密钥的要求是每个 HOTP 的⽣成器都必须是唯⼀的，⼀般我们都是通过⼀些随机⽣成种⼦的库来实现。C 计数器，RFC 中把它称为移动元素（moving factor）是⼀个 8 个 byte 的数值，⽽且需要服务器和客户端同步。另外⼀个参数⽐较好理解，Digit 表⽰产⽣的验证码的位数。T 称为限制参数（Throttling Parameter）表⽰当⽤户尝试 T 次 OTP 授权后不成功将拒绝该⽤户的连接。s 称为重新同步参数（Resynchronization Parameter）表⽰服务器将通过累加计数器，来尝试多次验证输⼊的⼀次性密码，⽽这个尝试的次数及为 s。该参数主要是有效的容忍⽤户在客户端⽆意中⽣成了额外不⽤于验证的验证码，导致客户端和服务端不⼀致，但同时也限制了⽤户⽆限制的⽣成不⽤于验证的⼀次性密码。3.2、算法流程核⼼步骤主要是使⽤ 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 编码的长度。4、TOTP 算法图解在 HOTP 算法的基础上，对于 TOTP 算法的解释是不难了，因为 TOTP 实际上是基础 HOTP 的，只不过 HOTP 的计数器在 TOTP 中不再是直接的计数器了，⽽是使⽤时间来简介计数的。下图将会详细介绍 TOTP 是如何在 HOTP 基础上使⽤时间来计数的。4.1、符号定义时间窗⼝ X ：表⽰多长时间算作计数器的⼀步，通常会设为30秒；初始计数时间戳 $T_0$：使⽤ Unix 时间戳来表⽰ OTP ⽣成的时候的初始计数时间。4.2、算法流程TOTP 算法的关键在于如何更具当前时间和时间窗⼝计算出计数，也就是如何根据当前时间和 X 来计算 HOTP 算法中的 C。HOTP 算法中的 C 是使⽤当前 Unix 时间戳减去初始计数时间戳，然后除以时间窗⼝⽽获得的。5、算法安全性分析上⼀节我们的算法中有两个参数没有⽤ T 和 s。这两个参数对安全有重要的作⽤。官⽅协议在这⾥给出了5点安全要求，其中第⼀点是协议本⾝的要求，理论上进⾏约束，我们主要关⼼另外4点，分别是 HOTP 的验证，限制访问参数，重新同步参数以及共享密钥的管理。对于⼆步验证的安全问题实际上就是如何保证第⼆步验证尽可能不被攻击的前提下向⽤户提供更⽅便的服务。通过下图我们可以详细的了解 HOTP 的验证过程，同时还可以了解参数 s 和 T 的⽤途。如果⽤户严格按照⽣成⼀次 OTP，然后验证⼀次的话，服务器直接可以验证成功。因为算法将会输⼊相同的参数。如果⽤户⽆意间多⽣成了若⼲次 OTP 但是没有⽤来验证，服务器和客户端就产⽣差异，这时候服务器端会⾃动累积计数器来尝试匹配⽤户输⼊的 OTP，但是这种尝试是有限制的，这也就是前⾯说到的参数 s 的作⽤。⼀旦服务器尝试 s 次仍未匹配成功，那么就会通知客户端需要重新⽣成验证来验证，只要验证成功。协议中对于参数 s 给出的建议是：服务器建议设置该参数，但是在保证可⽤性的前提下，尽可能⼩。另外还可以要求⽤户输⼊⼀个 HOTP 序列（⽐如连续⽣成多个 OTP 发送到服务器进⾏验证）来进⾏重新同步计数器。既然涉及到重试，服务器同样对重试次数有所限制，从⽽防⽌暴⼒破解。这⾥当⽤户重试次数超过了阈值 T，服务器就应该将该账号标记为有安全风险，需要提醒⽤户。协议中对个参数 T 给出的建议是：同样 T 也不建议设的很⼤。另外还提供了另外⼀个基于延时的策略还防⽌暴⼒破解攻击，服务器设置⼀个惩罚时间，⼀旦⽤户验证失败，需要在惩罚时间乘以失败次数的时间内禁⽌⽤户重新尝试验证。这个延时需要跨不同的登陆会话，以防⽌并发的攻击。

refer：

2023年7月31日发(作者：)

【IoT】加密与安全：动态密码图解：HOTP与TOTP算法1、简介本⽂根据 RFC4226 和 RFC6238 ⽂档，详细的介绍 HOTP 和 TOTP 算法的原理和实现。两步验证已经被⼴泛应⽤于各种互联⽹应⽤当中，⽤来提供安全性。对于如何使⽤两步验证，⼤家并不陌⽣，⽆⾮是开启两步验证，然后出现⼀个⼆维码，使⽤⽀持两步验证的移动应⽤⽐如 GoogleAuthenticator 或者 LassPass Authenticator 扫⼀下⼆维码。这时候应⽤会出现⼀个 6 位数的⼀次性密码，⾸次需要输⼊验证从⽽完成开启过程。以后在登陆的时候，除了输⼊⽤户名和密码外，还需要把当前的移动应⽤上显⽰的 6 位数编码输⼊才能完成登陆。这个过程的背后主要由两个算法来⽀撑：HOTP 和 TOTP。分别对应着两份 RFC 协议 RFC4266 和 RFC6238。前者是 HOTP 的标准，后者是 TOTP 的标准。本⽂将使⽤图⽂并茂的⽅式详细介绍 HOTP 和 TOTP 的算法原理，并在最后分析其安全性。当然所有内容都是基于协议的，通过⾃⼰的理解更加直观的表达出来。2、协议解决的核⼼问题通过前⾯两步验证的使⽤场景分析，不难看出问题的核⼼在于如何能够让⽤户⼿机应⽤产⽣的验证码和服务器产⽣的验证码⼀致，或者是在⼀定范围内⼀致。参考下图：所以我们的算法就是在解决如何更好的⽣成这个验证码，既能保证服务器端和客户端同步，还能保证验证码不重复并且不容易被别⼈反向破解出共享密钥。其中如果是计数，则是 HOTP，如果是使⽤时间来⽣成验证码，则是 TOTP。3、HOTP 算法图解3.1、符号定义对于 HOTP，通过上图我们已经看到输⼊算法的主要有两个元素，⼀个是共享密钥，另外⼀个是计数。在 RFC 算法中⽤⼀下字母表⽰：K 共享密钥，这个密钥的要求是每个 HOTP 的⽣成器都必须是唯⼀的，⼀般我们都是通过⼀些随机⽣成种⼦的库来实现。C 计数器，RFC 中把它称为移动元素（moving factor）是⼀个 8 个 byte 的数值，⽽且需要服务器和客户端同步。另外⼀个参数⽐较好理解，Digit 表⽰产⽣的验证码的位数。T 称为限制参数（Throttling Parameter）表⽰当⽤户尝试 T 次 OTP 授权后不成功将拒绝该⽤户的连接。s 称为重新同步参数（Resynchronization Parameter）表⽰服务器将通过累加计数器，来尝试多次验证输⼊的⼀次性密码，⽽这个尝试的次数及为 s。该参数主要是有效的容忍⽤户在客户端⽆意中⽣成了额外不⽤于验证的验证码，导致客户端和服务端不⼀致，但同时也限制了⽤户⽆限制的⽣成不⽤于验证的⼀次性密码。3.2、算法流程核⼼步骤主要是使⽤ 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 编码的长度。4、TOTP 算法图解在 HOTP 算法的基础上，对于 TOTP 算法的解释是不难了，因为 TOTP 实际上是基础 HOTP 的，只不过 HOTP 的计数器在 TOTP 中不再是直接的计数器了，⽽是使⽤时间来简介计数的。下图将会详细介绍 TOTP 是如何在 HOTP 基础上使⽤时间来计数的。4.1、符号定义时间窗⼝ X ：表⽰多长时间算作计数器的⼀步，通常会设为30秒；初始计数时间戳 $T_0$：使⽤ Unix 时间戳来表⽰ OTP ⽣成的时候的初始计数时间。4.2、算法流程TOTP 算法的关键在于如何更具当前时间和时间窗⼝计算出计数，也就是如何根据当前时间和 X 来计算 HOTP 算法中的 C。HOTP 算法中的 C 是使⽤当前 Unix 时间戳减去初始计数时间戳，然后除以时间窗⼝⽽获得的。5、算法安全性分析上⼀节我们的算法中有两个参数没有⽤ T 和 s。这两个参数对安全有重要的作⽤。官⽅协议在这⾥给出了5点安全要求，其中第⼀点是协议本⾝的要求，理论上进⾏约束，我们主要关⼼另外4点，分别是 HOTP 的验证，限制访问参数，重新同步参数以及共享密钥的管理。对于⼆步验证的安全问题实际上就是如何保证第⼆步验证尽可能不被攻击的前提下向⽤户提供更⽅便的服务。通过下图我们可以详细的了解 HOTP 的验证过程，同时还可以了解参数 s 和 T 的⽤途。如果⽤户严格按照⽣成⼀次 OTP，然后验证⼀次的话，服务器直接可以验证成功。因为算法将会输⼊相同的参数。如果⽤户⽆意间多⽣成了若⼲次 OTP 但是没有⽤来验证，服务器和客户端就产⽣差异，这时候服务器端会⾃动累积计数器来尝试匹配⽤户输⼊的 OTP，但是这种尝试是有限制的，这也就是前⾯说到的参数 s 的作⽤。⼀旦服务器尝试 s 次仍未匹配成功，那么就会通知客户端需要重新⽣成验证来验证，只要验证成功。协议中对于参数 s 给出的建议是：服务器建议设置该参数，但是在保证可⽤性的前提下，尽可能⼩。另外还可以要求⽤户输⼊⼀个 HOTP 序列（⽐如连续⽣成多个 OTP 发送到服务器进⾏验证）来进⾏重新同步计数器。既然涉及到重试，服务器同样对重试次数有所限制，从⽽防⽌暴⼒破解。这⾥当⽤户重试次数超过了阈值 T，服务器就应该将该账号标记为有安全风险，需要提醒⽤户。协议中对个参数 T 给出的建议是：同样 T 也不建议设的很⼤。另外还提供了另外⼀个基于延时的策略还防⽌暴⼒破解攻击，服务器设置⼀个惩罚时间，⼀旦⽤户验证失败，需要在惩罚时间乘以失败次数的时间内禁⽌⽤户重新尝试验证。这个延时需要跨不同的登陆会话，以防⽌并发的攻击。

refer：