基于特殊字符间距的Honeyword生成机制

A Honeyword Generation Method Based on Special Character Distance

摘要: Honeyword可以用于提升口令存储的安全性，并能够及时检测口令数据集的泄漏。然而，当前的honeyword生成机制依然存在安全性较弱、占用存储空间过大等问题。为此，本文提出了基于特殊字符间距的虚拟honeyword生成机制。分析结果显示该方案可以显著地减少存储空间开销，并提升安全性和口令集泄漏被检测的概率。

Abstract: Honeyword can be used to improve password storage security, and timely detect password data set disclosure. Nevertheless, existing honeyword generation schemes are of low security, and require large storage overhead. In this paper, we propose a virtual honeyword generation method based on special character distance. Additionally, our analysis shows that the proposed scheme can dramatically reduce the storage cost, and improve the security and detection probability of password.

1. 引言

口令文件的泄露是非常严重的安全问题，其影响已经波及到百万用户和相关的公司，比如Yahoo [1] ，Dropbox [2] ，Weebly [3] ，Myspace [4] ，LinkedIn [5] ，eBay [6] ，eHarmony，RockYou，Adobe [7] ，以及国内的网易邮箱泄露事件、12306用户帐户泄露等。今天，那些赫赫有名的网站被攻击、百万级别的用户口令流出已经不是什么新闻了。正是这些泄露的口令让用户成为了潜在的网络攻击目标。这些口令泄露事件也说明了一个严重的问题，很多网站依然在采用安全性较弱的方法来存储用户的口令。例如，LinkedIn网站采用不加盐混淆的SHA-1算法对口令进行哈希后存储，类似的eHarmary网站采用的是未加盐混淆的MD5算法对口令进行哈希后存储 [8] 。实际上，一旦口令文件被盗，借助诸如Weir等人提出的口令破解算法 [9] ，很容易得到大多数口令的明文。尽管MD5在众多哈希算法中是安全性较高的，但是随着计算机计算能力的提高，以及王等提出的“杂凑碰撞算法” [10] ，使得MD5的碰撞攻击成功概率大大提高，能够在较短时间内针对某个MD5哈希值进行碰撞。

更严重的是，探测到这些泄露事件常常是在口令刚被盗取后的几个月，有的甚至是数年。在此期间，攻击者已经挖掘、利用完数据中的信息、把口令文件发布在网上之后，或者是转手卖给了其他人。例如，最近在2017年10月报道的灾难性口令泄露事件，涉及到Yahoo所有30亿用户，然而泄密实际上是在4年前发生的 [1] ；2016年10月揭露的Weebly泄露的口令涉及到4300万用户，要求用户修改他们的口令，然而泄密发生在8个月之前 [3] ；Dropbox的6800万泄密发生在2012年，直到4年之后的2016年5月份 [2] ，用户才被要求修改他们的口令；Myspace的3.6亿用户数据泄露8年后才被得知：数据库在2008年被窃取 [4] ，直到2016年5月有人在网上出售相关文件才知道。2016年由Version公司做出的数据泄露报告指出，在调查的2260起泄露事件中，超过85%的最先由第三方的组织发现，91%的事件几个星期之后才发现，70%的事件要在几个月甚至几年之后才被探测到 [11] 。因此，设计一种主动的、及时的口令泄露探测方案具有重要的应用价值。

鉴于上述问题，本文提出了一种基于伪造口令或者帐户的方式来实现一种简单可行、经济有效的口令安全存储和泄露预警方案。蜜罐(Honeypot)技术是众多确认口令数据库泄露中的一种。在蜜罐方案中，系统管理员蓄意的创建一些虚假帐户来诱惑攻击者，如果任一虚假帐户被使用了，就可以探测到口令的泄露 [12] 。Herley和Florencio [13] 改造了这种技术，用来保护银行账户，免受暴力猜测的攻击。根据Herley和Florencio的研究，用每个用户的帐户和某些口令组合，进行错误登录的尝试会指向蜜罐帐户，也就是说，能够识别恶意行为。例如，长度为8的纯数字口令有 种可能，假设系统将10,000个错误口令与蜜罐帐户关联，那么攻击者进行10,000次暴力猜解就很可能命中一个蜜罐帐户。Bojinov等人基于诱饵构建了口令防盗的模型 [14] ，被称为Kamouflage。在此模型中，虚假口令和用户真正的口令放在同一个集合中，因此攻击者必须进行大量的在线尝试才能得到正确的帐户信息。近来，Juels和Rivest提出了一种可改善口令泄露问题的方法，引入诱饵口令(被称为“honeyword”)，能够探测到尝试使用破解的口令进行登录的攻击行为 [15] 。基本的思想是，对于每个用户，构建一个与之关联的“sweetword”集合，该集合中只有一个元素是正确的口令，其他的都是“honeywords”(decoypasswords)。因此，当攻击者尝试用honeyword进入系统时，就会触发警报、通知系统管理员口令文件已经泄露。此后，一些改进的honeyword生成机制被陆续提出。然而，目前基于honeyword的认证方案都存在或多或少的缺陷。最明显的一点是为了存储honeyword，对存储空间有较大的需求。除了存储开销，也有很多与此技术相关的安全性和适用性问题。现有的方法只能解决这些问题当中的一部分，无法兼顾所有。我们提出的基于honeyword的认证技术正是为了解决这些问题。

概括地说，本文提出了一种新的技术——特殊字符间距机制(Special Character Distance Mechanism, SCDM)——来生成honeyword。SCDM不需要对系统的用户接口进行更改，也不需要用户记忆额外的字符。SCDM的部署对用户来说是透明的，因此保证了系统的用户友好性和适用性。SCDM运用少量特殊字符生成honeyword，能够规避口令与用户名的关联问题(例如：bond007)、口令与用户名的关联问题(例如：用户名为James，口令为bond007)。采用我们提出的方案，系统只需要额外存储少量的信息，就可以生成虚拟的honeyword列表，因此极大程度上降低了存储开销。

论文其余部分安排如下。第2部分介绍了honeyword相关的基础知识和背景信息；第3部分详细地展示了我们所提方案的步骤；第4部分对本文所提方案进行了深入分析；第5部分总结了本文。

2. 背景知识

这里，我们对基于honeyword的认证技术进行简短的介绍，以及一些与此技术相关的问题，这有助于理解我们的方案。

2.1. 基于Honeyword的认证技术

在表1中，我们给出了一些本文使用的相关名词及其注解。

从本质上来说，honeyword技术背后的思想是：生成虚假口令——被称为honeyword——使这些口令与每个帐户都关联起来。当攻击者得到口令列表后，即便她将口令列表中的大部分或者全部哈希值逆转为明文，她依然无法确定列表当中的哪个口令才是用户真正的口令。因此，当攻击者贸然用honeyword尝试访问系统时，系统管理员就可以探测到这种恶意行为。

Table 1. Annotation

表1. 注释表

Honeyword的工作机制简述如下：对于每个用户 $u_i$ ，系统调用honeyword生成算法 $Gen\left(k\right)$ 生成一个sweetword列表， $W_i$ 。方法 $Gen\left(k\right)$ 输入参数为 $k$ ，即想要生成的sweetword的个数；输出结果为sweetword列表 $W_i=\left(w_{i,1},w_{i,2},\cdots ,w_{i,k}\right)$ 和 $c_i$ ，其中 $c_i$ 为第 $i$ 个用户的真正口令(sugarword)在列表 $W_i$ 中的索引。其中，用户名 $u_i$ 和sweetwords的哈希值组成一个元组 $\langle u_i,\left(v_{i,1},v_{i,2},\cdots ,v_{i,k}\right)\rangle$ 存在主服务器上，而存在另一个被称为“honeychecker”服务器上。通过将系统中的私密信息多元化——将口令的哈希值存在一个服务器上，将 $c_i$ 存在honeychecker上，攻击者就难以将整个系统作为一个整体攻破。换句话说，就是提供了基本形式上的分布式安全。需要强调的一点时，传统的口令认证方案中，每个帐户存储的是用户名 $u_i$ 和口令 $p_i$ 的哈希值 $H\left(p_i\right)$ 的键值对，即 $\langle u_i,H\left(p_i\right)\rangle$ ，而基于honeyword的认证方案中，数据库中存储的是用户名 $u_i$ 和sweetwords的哈希值列表 $V_i$ 构成的元组，即 $\langle u_i,V_i\rangle$ ，其中 $V_i=\left(v_{i,1},v_{i,2},\cdots ,v_{i,k}\right)$ 。honeyword方案中用户的登录过程如下：

1) 用户 $u_i$ 输入口令 $g$ 登陆系统。

2) 服务器首先检查 $H\left(g\right)$ 是否在列表 $V_i$ 中，如果不在，则拒绝访问。

3) 如果 $H\left(g\right)$ 在列表 $V_i$ 中，系统则进一步检查 $g$ 到底是honeyword还是sugarword。

4) 假设 $v_{i,j}=H\left(g\right)$ ，即 $H\left(g\right)$ 在列表 $V_i$ 中，且是 $V_i$ 中第 $j$ 个元素。 $j$ 的值通过确保安全的信道传送给honeychecker。

5) honeychecker检验 $j$ 是否和 $c_i$ 相等。如果相等，则返回TRUE；如果不想等，则返回FALSE并根据系统既定的安全策略触发警报。

在进一步讨论honeyword生成方法之前，我们需要先对honeyword的生成算法 $Gen\left(\right)$ 进行说明。需要注意的是，honeyword的优点、有效性和 $Gen\left(\right)$ 是如何构造的息息相关。因此，honeyword的作者引入了一个新的定义—— $Gen\left(\right)$ 的flatness——来度量攻击者从sweetwords中选中正确口令的可能性大小。换句话说，如果honeyword生成方法是 $ϵ-flat$ ，那么攻击者就有至少 $1-ϵ$ 的可能选中honeyword。例如，若 $ϵ=1/4$ ，那么攻击者从 $W_i$ 中选中正确口令 $p_i$ 的可能性至多为25%。简而言之，如果算法不够平滑(flat)，那么真正的口令与剩下的虚假口令相比就很显眼，攻击者就可以轻易的发现哪个是用户的原始口令。

2.2. 引入Honeyword的主要问题

基于honeyword的认证技术可以认为是对基于口令的认证技术的一种扩展。因此，人们对于基于honeyword的认证技术的接受程度主要取决于它如何在安全性和适用性上取得平衡。基于honeyword的认证技术需要额外的大量空间用于维护honeywords，所以空间开销也对其接受程度产生了影响。下面，我们讨论了主要问题当中和存储空间、安全以及适用性相关的某些问题。

1) 存储开销：现有的honeyword生成方法中，大多数需要在系统中为每个用户的帐户存储 $k-1\left(k\ge 2\right)$ 个honeyword。因此，一个拥有N个用户的系统需要额外存储 $N\times \left(k-1\right)$ 大小的信息。假设 $h$ 是口令哈希值的字节数目。如果系统采用流行的哈希技术，譬如：SHA-1，那么h的值就是20字节。考虑到Juels和Rivest在 [15] 推荐的k大小为20，那么每个用户的存储开销就要增加380个字节。近来的研究工作也都证实了存储开销是基于honeyword的认证技术的一大缺点 [15] [16] 。

2) 相互关联风险：在用户名和口令之间可能存在着关联。例如，如果用户选择“姚明”作为用户名，用“basketball”作为口令，那么着两者之间就存在着关联。在此种情境下，honeyword起不到掩盖原始口令的作用。

3) 易辨识的知名口令模式：如果用户选择的口令是和一些众所周知的事物、事实相关的，也非常容易从sweetword列表中被辨认出来。属于此类的口令像bond007，james007，007bond，007007等。这些例子是从10,000个最常用的口令 [17] 中挑选出来的。

4) 拒绝服务式攻击抗性相关问题：在没有得到口令文件 $F_p$ 的前提下，攻击者如果能够猜中任何honeyword，那么这种基于honeyword的认证方案就是一种拒绝服务式攻击抗性较弱的方案。为了猜测用户 $u_i$ 的honeyword，攻击者必须要事先知道用户 $u_i$ 的真正口令。在已知正确口令信息的前提下，攻击者若能成功猜中honeyword，那么攻击者就可以蓄意使用honeyword进行登录，让系统错误的以为口令文件 $F_p$ 已经被盗取了，而事实并非如此。一旦系统感应到某个用户用honeyword尝试访问系统了，它可能会按照既定的预警策略对每个用户进行封锁，这样十分影响用户体验。为了发起拒绝服务式攻击，攻击者可能会先进行观察攻击 [18] 或者自己去注册一个帐户，从而得到原始的口令信息。

5) 多系统薄弱性相关问题：大部分人在不同的系统帐户中使用相同的口令，近来的关于口令泄漏事件的报道几乎都支持这一事实 [19] 。用户 $u_i$ 提交了口令 $p_i$ 用于注册之后，系统根据原始口令 $p_i$ 生成列表 $W_i$ ，其中包含honeywords和用户的真正口令 $p_i$ 。即使用户在两个系统提交的口令 $p_i$ 相同，但是任何honeyword生成算法的基本特性之一就是每次运行生成的honeywords是不能完全相同的。因此，即使使用相同的口令 $p_i$ ，不同系统上的 $W_i$ 列表也是不同的。假设攻击者成功的获取了这两个系统的口令文件 $F_p$ 对同一用户的两个 $W_i$ 列表进行集合的交集运算，得到该用户真正口令的概率就非常大。这就是所说的基于honeyword的认证技术中的多系统薄弱性问题。

6) 更改系统用户界面：现有的基于honeyword的认证方案中，为了取得更好的flatness，需要对系统原本的用户界面进行更改。比如：加尾巴、密码圆盘、基于问卷调查的方案等。若是现有的系统想要部署这些方案，就必须对系统界面进行更改，可能需要用户额外花费一些时间才能弄明白如何注册系统，以及应该记住哪些改动，以便下次能够成功登录。所以这些方案大大降低了方案的适用性，没能较好的平衡适用性和安全性。

7) 系统对用户的干扰和用户的记忆压力：这是两个和适用性相关的互补标准。在Juels和Rivest的工作中 [15] ，作者阐明为了满足honeyword方案的安全性要求，某些基于honeyword的方案会干扰用户对于口令的选择(例如，让用户选择距离满足距离测量函数的尾巴)，强制用户记忆系统产生的信息(额外记忆尾巴，记忆问卷的答案等)。这些额外的信息是被系统用来生成honeywords的。因此，一个基于honeyword的认证方案，一旦有系统扰动，就意味着要对用户增加额外的记忆压力。总的来说，此类系统已经明示了它们采用了honeyword技术，而且需要和用户进行额外的交互、影响用户对口令的选择。

3. 基于字符间距的Honeyword生成机制

我们提出的方案名为“特殊字符间距机制(Special Character Distance Mechanism, SCDM)”。该方案无需对用户界面做出任何更改，唯一的要求就是用户的口令当中需要含有两个不同的特殊的字符。所以，我们的方案既不会干涉用户对口令的自主选择，也不会对用户施加额外的记忆压力——我们的方案具有极好的适用性。此外，SCDM中与honeyword相关的仅有特殊字符，而在绝大多数口令中，特殊字符与口令的其他部分、与用户名不存在语义上的关联，所以SCDM能够规避口令–用户名关联问题。SCDM理应归属到传统UI类honeyword生成方法中，所以也具有传统UI类共同的有点，即由于不需要更改系统的用户接口，攻击者不会轻易的从系统界面上判断出是否采用了基于honeyword的认证方案。

3.1. 生成特殊字符链

随着Unicode的引入和广泛使用，系统能够接受和处理的特殊字符越来越多，我们的方案并不局限于某种特定的字符集合。不过为了分析之便，我们仅在美国信息交换标准代码(ASCII [20] )上讨论我们的方案。在ASCII表中，可用于口令的可打印字符有95个，其中个特殊字符有33个，我们将这33个特殊字符以随机顺序排放在一个环形的链表中。为了叙述方便，将其称为“特殊字符链(Special Character Chain, SCC)”。特殊字符链被系统用来生成honeywords，为该系统所有用户共享，所以系统仅需存储一个特殊字符链即可，即只需存储33个特殊字符的一种排列。特殊字符链的某种排列如图1所示。

Figure 1. Special character chain

图1. 特殊字符链

利用用户口令当中的两个不同的特殊字符，根据特殊字符链，SCDM就可以计算出两个特殊字符的距离。在系统初始化时，一旦生成特殊字符链，就不再改变。除生成特殊字符链外，部署SCDM不需要进行用公开的口令文件建立概率模型等工作。即，SCDM初始化非常简单便捷。

3.2. 虚拟Honeyword

定义：特殊字符间距(Special Character Distance)为特殊字符 $e_1$ 和 $e_2$ 的间距 $SCD\left(e_1,e_2\right)$ 为从 $e_1$ 沿特殊字符链的顺时针方向到 $e_2$ 经过的节点的数目，其中 $e_1\ne e_2$ 。

由上述定义可知，口令当中必须含有两个不同的特殊字符，而且特殊字符间距的值是大于0的。

在主服务器上，SCDM需要保存用于用户认证的信息，除了用户名、去掉两个特殊字符的口令外，还需要保存特殊字符的距离。在honeychecker上，SCDM则需要保存用户的用户名和口令中的第一个特殊字符。

假设某个用户 的用户名是“Ironman”，口令是“Revenge~2018!”。根据图1，可以得到两特殊字符“~”、“!”的间距为1。则用户 $u_i$ 在口令文件 $F_p$ 和honeychecker上的信息如表2和表3所示。

考虑到用户 $u_i$ 的口令可能含有相同的特殊字符，系统管理员在部署SCDM时，可以自由选择使用某重复特殊字符第一次出现、或者最后一次出现的位置用来生成Honeyword。譬如：对于口令“!Revenge~2018!”，若选取第一个“！”，则SCDM在 $F_p$ 中存储的口令为“Revenge2018!”；若选取最后一个“！”，则SCDM在 $F_p$ 中存储的口令为“!Revenge2018”。

Table 2. User u i ’s information in F p

表2. 文件 $F_p$ 中用户 $u_i$ 的信息

Table 3. User u i ’s information in honeychecker

表3. Honeychecker上用户 $u_i$ 的信息

接下来我们阐述特殊字符间距是如何在生成honeywords中发挥作用的。对于既定的字符间距，以任一特殊字符链中的字符作为开头，SCDM可以产生 $\left|\text{SCC}\right|$ 个特殊字符对。其中， $\left|\text{SCC}\right|$ 表示特殊字符链中的字符个数。

假设攻击者已经得到了文件F_p，她可以看到的信息有用户名、去除了两特殊字符的口令，但是特殊字符间距会产生 $\left|\text{SCC}\right|$ (此处为33)个可能的口令，供攻击者挑选。因此，只需要额外存储特殊字符间距，SCDM就能构造出含有33个sweetwords的虚拟列表，从而使攻击者感到迷惑。

4. 方案分析

4.1. 探测口令泄露的概率

用户登录时输入用户名 $u_i$ 和口令 $p_i$ ，系统首先在文件F_p中查看用户 $u_i$ 是否存在；若存在，系统从文件 $F_p$ 中得到与 $u_i$ 对应的口令哈希值， $H\left({p^{\prime }}_i\right)$ 。接下来，系统按照SCDM的具体实现，从 $p_i$ 中选取两特殊字符，去除后得到 $g_i$ ，然后比对 $H\left(g_i\right)$ 是否和 $H\left({p^{\prime }}_i\right)$ 一致。如果不一致，则提示口令错误，拒绝登录；如果一致，则对两个特殊字符进行验证。首先，根据存储的特殊字符链，生成两特殊字符距离。只有生成的距离和 $F_p$ 中存储的距离一致时，系统才和honeychecker进行交互；否则，拒绝登录，并记录该用户的登录行为——因为可能是攻击者仅仅得到文件 $F_p$ 后，在不了解系统已经采用了SCDM，而尝试进行登录。

由于攻击者可能猜到的特殊字符之间的距离和系统中存储的一致，所以系统和honeychecker进行下一步校验是有必要的。当系统和honeychecker进行校验时，系统只用将用户名和第一个特殊字符传送给honeychecker。此处需要强调的是，只有当攻击者猜测的特殊字符完全正确，她的第一个特殊字符才能和honeychecker匹配成功。如果honeychecker找到正确匹配，则返回正面的反馈；否则，触发警报通知管理员——已经探测到口令泄露。

因此，即使攻击者得到了泄露的口令文件 $F_p$ 并把所有的信息转化为明文，SCDM依然能够通过虚拟出一个含有33个sweetwords的列表来迷惑攻击者。因此，仅仅通过要求用户在口令当中含有两个不一样的特殊字符，SCDM就能以 $32/33$ (96.97%)之高的概率探测到攻击行为。

4.2. 安全性分析

泄露的口令文件 $F_p$ 中，每个用户都有 $k$ 个sweetwords，攻击者因此而感到迷惑。然而有些时候攻击者可以从 $W_i$ 中轻易的选出用户 $u_i$ 的原始口令(例如，用户名和口令之间存在着关联)。一个完全flat的、基于honeyword的认证方案中，攻击者在从 $W_i$ 中甄选用户 $u_i$ 的口令时不应有任何优势。因此，一个完全flat的honeyword生成算法，从 $W_i$ 中选出原始口令概率应该是 $1/k$ 。

SCDM中特殊字符链是随机排列而成的，SCDM在生成虚拟的sweetword列表时，每个sweetword出现的概率都是相等的；此外，在前面的例子中，用户名Ironman和口令Revenge~2018!存在着关联，但是由于每个honeyword只是特殊字符不同，所以每个honeyword和用户名也存在这种关联，攻击者从sweetwords中选择时不具有任何优势。因此，SCDM是可以生成完全flat的sweetwords的。

5. 结束语

本文分析了现有的honeyword生成机制依然存在安全性较弱、占用存储空间过大等问题。然后，提出了基于特殊字符间距的虚拟honeyword生成机制，并对所提方案进行了深入分析。分析结果显示本文所提方案可以显著地减少存储空间开销，并提升安全性和口令集泄漏被检测的概率。

致谢

本文工作受到国家重点研发计划(项目号：2017YFB0802300)的资助。