HOTP和TOTP算法图解

该文章来自我的博客

摘要:本文根据 RFC4226RFC6238 文档,详细的介绍 HOTPTOTP 算法的原理和实现。

两步验证已经被广泛应用于各种互联网应用当中,用来提供安全性。对于如何使用两步验证,大家并不陌生,无非是开启两步验证,然后出现一个二维码,使用支持两步验证的移动应用比如 Google Authenticator 或者 LassPass Authenticator 扫一下二维码。这时候应用会出现一个6位数的一次性密码,首次需要输入验证从而完成开启过程。以后在登陆的时候,除了输入用户名和密码外,还需要把当前的移动应用上显示的6位数编码输入才能完成登陆。

这个过程的背后主要由两个算法来支撑:HOTPTOTP。也分别对应着两份 RFC 协议 RFC4266RFC6238。前者是 HOTP 的标准,后者是 TOTP 的标准。本文将使用图文并茂的方式详细介绍 HOTPTOTP 的算法原理,并在最后分析其安全性。当然所有内容都是基于协议的,通过自己的理解更加直观的表达出来。

协议解决的核心问题

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

enter description here
enter description here

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

HOTP 算法图解

符号定义

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

K 共享密钥,这个密钥的要求是每个 HOTP 的生成器都必须是唯一的。一般我们都是通过一些随机生成种子的库来实现。

C 计数器,RFC 中把它称为移动元素(moving factor)是一个 8个 byte的数值,而且需要服务器和客户端同步。

另外一个参数比较好理解,

Digit 表示产生的验证码的位数

最后两个参数可能暂时不好理解,我们先放在这,等用到在解释

T 称为限制参数(Throttling Parameter)表示当用户尝试 T 次 OTP 授权后不成功将拒绝该用户的连接。

s 称为重新同步参数(Resynchronization Parameter)表示服务器将通过累加计数器,来尝试多次验证输入的一次性密码,而这个尝试的次数及为 s。该参数主要是有效的容忍用户在客户端无意中生成了额外不用于验证的验证码,导致客户端和服务端不一致,但同时也限制了用户无限制的生成不用于验证的一次性密码。

算法流程

enter description here
enter description here

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

第一步:使用 HMAC-SHA-1 算法基于 K 和 C 生成一个20个字节的十六进制字符串(HS)。关于如何生成这个是另外一个协议来规定的,RFC 2104 HMAC Keyed-Hashing for Message Authentication. 实际上这里的算法并不唯一,还可以使用 HMAC-SHA-256HMAC-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 = 872921872921 就是我们最终生成的 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 编码的长度。

TOTP 算法图解

HOTP 算法的基础上,对于 TOTP 算法的解释是不难了,因为 TOTP 实际上是基础 HOTP 的,只不过 HOTP 的计数器在 TOTP 中不再是直接的计数器了,而是使用时间来简介计数的。下图将会详细介绍 TOTP 是如何在 HOTP 基础上使用时间来计数的。

符号定义

时间窗口 X :表示多长时间算作计数器的一步,通常会设为30秒

初始计数时间戳 $T_0$: 使用 Unix 时间戳来表示 OTP 生成的时候的初始计数时间。

算法流程

TOTP 算法的关键在于如何更具当前时间和时间窗口计算出计数,也就是如何根据当前时间和 X 来计算 HOTP 算法中的 C。

enter description here
enter description here

HOTP 算法中的 C 是使用当前 Unix 时间戳 减去初始计数时间戳,然后除以时间窗口而获得的。

算法安全性分析

上一节我们的算法中有两个参数没有用,Ts。这两个参数对安全有重要的作用。

官方协议在这里给出了5点安全要求,其中第一点是协议本身的要求,理论上进行约束,我们主要关心另外4点,分别是 HOTP 的验证,限制访问参数,重新同步参数以及共享密钥的管理。

对于二步验证的安全问题实际上就是如何保证第二步验证尽可能不被攻击的前提下向用户提供更方便的服务

通过下图我们可以详细的了解 HOTP 的验证过程,同时还可以了解参数 sT 的用途。

enter description here
enter description here

如果用户严格按照生成一次 OTP,然后验证一次的话,服务器直接可以验证成功。因为算法将会输入相同的参数。

如果用户无意间多生成了若干次 OTP 但是没有用来验证,服务器和客户端就产生差异,这时候服务器端会自动累积计数器来尝试匹配用户输入的 OTP,但是这种尝试是有限制的,这也就是前面说到的参数 s 的作用。一旦服务器尝试 s 次仍未匹配成功,那么就会通知客户端需要重新生成验证来验证,只要验证成功。

协议中对于参数 s 给出的建议是:服务器建议设置该参数,但是在保证可用性的前提下,尽可能小。另外还可以要求用户输入一个 HOTP 序列(比如连续生成多个 OTP 发送到服务器进行验证)来进行重新同步计数器。

既然涉及到重试,服务器同样对重试次数有所限制,从而防止暴力破解。这里当用户重试次数超过了阈值 T,服务器就应该将该账号标记为有安全风险,需要提醒用户。

协议中对个参数 T 给出的建议是:同样 T 也不建议设的很大。另外还提供了另外一个基于延时的策略还防止暴力破解攻击,服务器设置一个惩罚时间,一旦用户验证失败,需要在惩罚时间乘以失败次数的时间内禁止用户重新尝试验证。这个延时需要跨不同的登陆会话,以防止并发的攻击。

总结

通过上面的图解,基本解释了 HOTPTOTP 两种算法的关键步骤,并且通过验证的场景对其安全要求进行了分析。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 194,457评论 5 459
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 81,837评论 2 371
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 141,696评论 0 319
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 52,183评论 1 263
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 61,057评论 4 355
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 46,105评论 1 272
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 36,520评论 3 381
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 35,211评论 0 253
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 39,482评论 1 290
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,574评论 2 309
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,353评论 1 326
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,213评论 3 312
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 37,576评论 3 298
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,897评论 0 17
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,174评论 1 250
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 41,489评论 2 341
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 40,683评论 2 335

推荐阅读更多精彩内容

  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 134,497评论 18 139
  • 国家电网公司企业标准(Q/GDW)- 面向对象的用电信息数据交换协议 - 报批稿:20170802 前言: 排版 ...
    庭说阅读 10,800评论 6 13
  • 从三月份找实习到现在,面了一些公司,挂了不少,但最终还是拿到小米、百度、阿里、京东、新浪、CVTE、乐视家的研发岗...
    时芥蓝阅读 42,137评论 11 349
  • 一、概念(载录于:http://www.cnblogs.com/EricaMIN1987_IT/p/3837436...
    yuantao123434阅读 8,322评论 6 152
  • UDAF 前两节分别介绍了基础UDF和UDTF,这一节我们将介绍最复杂的用户自定义聚合函数(UDAF)。用户自定义...
    raincoffee阅读 10,525评论 0 7