基于熵的密码强度估计

网 络 安 全 基于熵的密码强度估计

严霄凤

中国赛迪实验室中国软件评测中心 北京 100048

摘要：密码是电子认证的基础，密码的保护以及密码强度或抗破解能力对受保护信息或信息系统的安全至关重要。目前还没有一个准确定义密码强度的方法，基于熵的概念，借助猜测熵和最小熵对密码强度进行大致估计，将对密码的选择具有一定的指导作用。本文介绍了基于熵对密码的强度进行估计的方法。

关键词：电子认证；密码；密码熵；熵

0 引言

密码由用户记忆并用于证明其身份，是认证因素的重要组成部分，是电子认证的基础。在只使用密码的情况下，假冒者只需获取密码即可进行身份假冒。由于人类记忆较长任意密码的能力有限，所以密码往往很容易受到猜测攻击、常用密码字典攻击以及尝试所有可能密码组合的暴力攻击。各种密码认证协议的脆弱性相差很大，许多密码机制对于被动和主动的网络攻击都很脆弱。尽管某些密码加密协议能够防止几乎所有的直接网络攻击，但目前这些技术并没有被广泛采用，并且所有的密码认证机制，在输入密码时都容易受到按键记录攻击和密码偷窥攻击。实践还表明，用户很容易受到“社会工程学”攻击，将自己的密码透露给自己不了解、但认为是“可信任”的人。由此可见，密码的保护以及密码强度或抗破解能力对受保护信息或信息系统的安全至关重要。

密码强度取决于密码的长度、形成密码的字符空间(字符集)，以及密码字符选择的随机性等多个方面。目前还没有一个准确定义密码强度的方法，基于熵的概念，借助猜测熵和最小熵对密码强度进行大致估计，将对密码的选择具有一定的指导作用。

之父克劳德·艾尔伍德·香农借鉴热力学的概念，提出“信息熵”的概念，解决了对信息的量化度量问题。

“信息熵”的概念在信息理论与通信中有很多应用，并且香农还将其用于度量英文文本中的实际信息量。香农认为，熵是一个统计参数，在一定意义上，用于测量语言文字中每个字母产生的平均信息量。如果以最有效的方式将语言转换成二进制数字(0或1)，熵是原文每个字母需要的二进制数字的平均数。熵一般用符号H表示，其数学定义如下：

这里，P(X=x)是变量X取值为x的概率。变量的不确定性越大，熵就越大。

对于一个密码，熵越大，不确定性就越大，就越难被破解。因此，密码熵可作为攻击者破解密码的难度度量，单位是比特。

依据熵的概念，密码学家导出了许多熵的替代形式或定义，包括“猜测熵”和“最小熵”等。

2 随机选择的密码

熵表示了密码值的不确定性。一个随机选择的k位密码，有2k个可能的值，具有k位熵。从b个字符(如典型键盘上的94个可打印ISO字符)的字符集(94符号的字符集)中随机选择长度为l个字符的密码，熵是bl(例如，由94符号的字符集中选择8个字符组成的密码，熵是948≈6.09×1015，即大约252，具有大约52位熵)。用位表示的熵(H)的计算公式如下：

1 密码熵

密码的破解难度依赖密码的不确定性，与其提供给破解者的信息量大小有直接的关系。密码提供的信息量越大，其不确定性就越小，越容易被破解；相反，密码提供的信息量越小，其不确定性就越大，破解难度就越大。

信息是个很抽象的概念。人们常常说信息很多，或者信息较少，但却很难说清楚信息到底有多少。1948年，信息论

显然特定长度真正随机选择的密钥或密码信息熵最高，

本文由国家发展改革委信息安全专项项目(项目名称：电子认证服务风险评估与验证专业化服务项目)资助。 作者简介：严霄凤(1964-)，女，通信专业硕士，中国软件评测中心电子认证实验室副主任，研究方向：信息安全、电子认证相关标准、规范和测评方法。 36 2012.11

破解难度最大。对于随机选择的密码，猜测熵、最小熵和信息熵都具有相同的值。

表1给出了从标准的94符号的字符集中随机选择字符生成密码的长度与熵的对应。

3 用户选择的密码

通常，用户选择密码时并不是随机进行的，选择的密码不具有随机分布，所以估计用户自选密码的熵更加困难。用户选择的密码可能大致反映了普通英文文本的模式和字符频率分布。经验表明，许多为自己选择密码的用户，会选择自己能够记住，但很容易被猜到的密码，这些密码存在于只有几千个常用密码的相当短的密码字典中，用这样的密码字典进行攻击时，很多实际用户选择的密码被轻易“破解”。

3.1 猜测熵

猜测熵是对攻击者猜测系统中通常使用密码的难度度量。在很大程度上，猜测熵决定了抵抗有针对性的在线密码猜测攻击的能力，是密码强度最重要的度量。

香农通过实验发现，虽然字母具有非均匀概率分布，预测英文文本字符串的第一个字母比较困难，但是，如果给出第一个字母，猜测第二个字母将容易得多，而给出头两个字母，猜测第三个字母将更容易，……。香农估计第一个符号的熵在4.6至4.7位，第8个字符后，熵逐步下降到大约1.5位。很长的英文字符串(例如莎士比亚的作品集)估计每字符的熵低至0.4位。同样，在词串中，预测单词的第一个字母比预测单词后面的字母更难，第一个字母携带了第五个字母或更后面字母大约6倍以上的信息。

攻击者为了找到密码，首先尝试最有可能选择的密码，为此创建了各种密码字典。用户往往倾向选择常用词或非常简单的密码，为了阻止用户选择这种“不好”的密码，系统常常将限制规则强加于密码的选择，以提高用户自选密码抵抗猜测攻击的能力。这些规则包括。

3.1.1 字典规则

使用常用词和常用密码形成的密码字典测试将要选择的密码，禁止使用在字典中找到的密码，拒绝选择在英文字典缩略本中找到的任何一个单词的简单转换作为密码，测试字典至少包括50,000个词汇。可以选择长密码(如16个字符以上的短语)，对长密码不强制进行字典测试。

3.1.2 组合规则

通常要求用户选择的密码包括小写字母、大写字母和非

网 络 安 全 字母符号(例如，;: “ ~ ! @ # $ % ^ & * ( ) _ - + = { } [ ] | \\ : ;’ < ,

> . ? / 1 2 3 4 5 6 7 8 9 0 ”)。

密码选择限制规则，虽然可能为一个真正的穷举攻击减少了工作量，但消除了许多明显的密码选择，通常提高了密码的“实际熵”。

表1提供了不同长度用户选择的密码的平均熵的粗略估计。密码选择94符号的字符集，经过字典测试，并遵守组合规则。该表还提供了在10个数字的字符集中选择密码或

PIN码的熵估计。

表1 密码猜测熵估计

用户选择的密码 随机选择的密码

94符号的字符集

10个数字的 94符号的长度无检查 字典规则字典与组合规则字符集

字符集

1 4 - - 3 3.3 6.6 2 6 - - 5 6.7 13.2 3 8 - - 7 10.0 19.8 4 10 14 16 9 13.3 26.3 5 12 17 20 10 16.7 32.9 6 14 20 23 11 20.0 39.5 7 16 22 27 12 23.3 46.1 8 18 24 30 13 26.6 52.7 10 21 26 32 15 33.3 65.9 12 24 28 34 17 40.0 79.0 14 27 30 36 19 46.6 92.2 16 30 32 38 21 53.3 105.4 18 33 34 40 23 59.9 118.5 20 36 36 42 25 66.6 131.7 22 38 38 44 27 73.3 144.7 24 40 40 46 29 79.9 158.0 30 46 46 52 35 99.9 197.2 40 56 56 62

45 133.2263.4 对于从94符号的字符集中抽取用户自选密码，表1形成逻辑如下：

(1) 第一个字符的熵取4位；

(2) 接下来的7个字符，每个字符的熵是2位；这大致与香农的估计一致，香农估计：“当统计的影响范围不超过8个英文字符时，每个字符的熵大约是2.3位”；

(3) 从第9至第20个字符，每个字符的熵是1.5位； (4) 第21及以后的字符，每个字符的熵是1位； (5) 组合规则得到6位熵的增强。虽然规则强制使用大写字母和非字母符号，但在许多情况下，这些字符将仅出现在密码的开头或结尾，缩小了总的搜索空间，所以这个增强可能被中和并且几乎与密码的长度无关；

(6) 字典规则可以得到最多6位熵的增强。如果攻击者

2012.11

37

网 络 安 全 知道字典，就能够避免测试那些密码，使字典测试带来的部分好处被抵消。这里假设大多数字典测试对猜测熵的增强局限于相对较短的密码，因为任何可记住的长密码，必然是一个字典中的单词组成的“密码短语”，在长度达到20个字符时熵的增强下降到零。

图1给出了用户选择的密码字符长度与估计熵的位数关系。

对系统的访问，而不是冒充一个预定用户，这就是一次成功 的攻击。忽略这种可能性将是非常危险的。

由于没有用户在密码系统规则下选择的实际密码情况，所以无法提供准确估计用户选择的密码最小熵的一般方法。但是通过相当大的字典测试用户选择的密码，将提高密码的最小熵。为了确保至少有10位的最小熵，字典测试如下：

(1) 密码中的大写字母全部转换为小写字母，并与至少包含50,000个密码的密码字典进行比较，拒绝采用与字典条目匹配的密码。

(2) 不允许采用可检测用户名排列的密码。

图1 用户选择的密码字符长度与估计熵的位数关系

可以选择其他方法确保至少有10位最小熵。例如，用户选择的至少15个字符的密码被认为至少有10位最小熵；一个随机选择的短字符串(从94符号的字符集中随机选择的两个字符串，有大约13位熵)；将一个密码与一个短的系统选择的随机元素组合形成一个较长的用户选择的密码，能够保证具有10位最小熵。

对于用户选择的PIN码，表1假设遵守这样的基本规则：“1234”不选择所有数字都相同或按顺序排列的数字(例如，或“76543”)作为PIN码。

3.2 最小熵

最小熵是攻击者猜测系统中最常使用密码的难度度量。 经验表明，大量的用户会选择非常容易被猜到的密码。例如，假设在1000个用户中，有个用户选择了最常见的两个密码，当前系统设置为在锁定密码前允许用户进行3次尝试。已经掌握用户名列表的攻击者，可以利用每个用户名尝试那两个密码，有望通过700个用户名与那两个密码的组合尝试，至少发现一个密码。显然，如果攻击者的目标是获得

参考文献 

[1]Matt Bishop著,王立斌等译.计算机安全学－安全的艺术与科学.电子工业出版社.2005.

[2]冯尚友.信息熵与最大熵原理.水利电力科技.2006. [3]敖红.对信息熵的探讨.辽宁高职学报.2007.

[4]Electronic Authentication Guideline.NIST Special Publication 800-63-1.December. 2011.

Estimating Password Strength Based on Entropy Yan Xiaofeng

Abstract:The password is the basis of electronic authentication.It’s essential that password protection and password Keywords:Electronic Authentication;Password;Password Entropy;Entropy

38 2012.11