基于熵的密碼強度估計

嚴霄鳳

中國賽迪實驗室中國軟件評測中心 北京 100048

0 引言

密碼由用戶記憶并用于證明其身份，是認證因素的重要組成部分，是電子認證的基礎。在只使用密碼的情況下，假冒者只需獲取密碼即可進行身份假冒。由于人類記憶較長任意密碼的能力有限，所以密碼往往很容易受到猜測攻擊、常用密碼字典攻擊以及嘗試所有可能密碼組合的暴力攻擊。各種密碼認證協議的脆弱性相差很大，許多密碼機制對于被動和主動的網絡攻擊都很脆弱。盡管某些密碼加密協議能夠防止幾乎所有的直接網絡攻擊，但目前這些技術并沒有被廣泛采用，并且所有的密碼認證機制，在輸入密碼時都容易受到按鍵記錄攻擊和密碼偷窺攻擊。實踐還表明，用戶很容易受到“社會工程學”攻擊，將自己的密碼透露給自己不了解、但認為是“可信任”的人。由此可見，密碼的保護以及密碼強度或抗破解能力對受保護信息或信息系統的安全至關重要。

密碼強度取決于密碼的長度、形成密碼的字符空間(字符集)，以及密碼字符選擇的隨機性等多個方面。目前還沒有一個準確定義密碼強度的方法，基于熵的概念，借助猜測熵和最小熵對密碼強度進行大致估計，將對密碼的選擇具有一定的指導作用。

1 密碼熵

密碼的破解難度依賴密碼的不確定性，與其提供給破解者的信息量大小有直接的關系。密碼提供的信息量越大，其不確定性就越小，越容易被破解；相反，密碼提供的信息量越小，其不確定性就越大，破解難度就越大。

信息是個很抽象的概念。人們常常說信息很多，或者信息較少，但卻很難說清楚信息到底有多少。1948年，信息論之父克勞德·艾爾伍德·香農借鑒熱力學的概念，提出“信息熵”的概念，解決了對信息的量化度量問題。

“信息熵”的概念在信息理論與通信中有很多應用，并且香農還將其用于度量英文文本中的實際信息量。香農認為，熵是一個統計參數，在一定意義上，用于測量語言文字中每個字母產生的平均信息量。如果以最有效的方式將語言轉換成二進制數字(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給出了從標準的94符號的字符集中隨機選擇字符生成密碼的長度與熵的對應。

3 用戶選擇的密碼

通常，用戶選擇密碼時并不是隨機進行的，選擇的密碼不具有隨機分布，所以估計用戶自選密碼的熵更加困難。用戶選擇的密碼可能大致反映了普通英文文本的模式和字符頻率分布。經驗表明，許多為自己選擇密碼的用戶，會選擇自己能夠記住，但很容易被猜到的密碼，這些密碼存在于只有幾千個常用密碼的相當短的密碼字典中，用這樣的密碼字典進行攻擊時，很多實際用戶選擇的密碼被輕易“破解”。

3.1 猜測熵

猜測熵是對攻擊者猜測系統中通常使用密碼的難度度量。在很大程度上，猜測熵決定了抵抗有針對性的在線密碼猜測攻擊的能力，是密碼強度最重要的度量。

香農通過實驗發現，雖然字母具有非均勻概率分布，預測英文文本字符串的第一個字母比較困難，但是，如果給出第一個字母，猜測第二個字母將容易得多，而給出頭兩個字母，猜測第三個字母將更容易，……。香農估計第一個符號的熵在4.6至4.7位，第8個字符后，熵逐步下降到大約1.5位。很長的英文字符串(例如莎士比亞的作品集)估計每字符的熵低至0.4位。同樣，在詞串中，預測單詞的第一個字母比預測單詞后面的字母更難，第一個字母攜帶了第五個字母或更后面字母大約6倍以上的信息。

攻擊者為了找到密碼，首先嘗試最有可能選擇的密碼，為此創建了各種密碼字典。用戶往往傾向選擇常用詞或非常簡單的密碼，為了阻止用戶選擇這種“不好”的密碼，系統常常將限制規則強加于密碼的選擇，以提高用戶自選密碼抵抗猜測攻擊的能力。這些規則包括。

3.1.1 字典規則

使用常用詞和常用密碼形成的密碼字典測試將要選擇的密碼，禁止使用在字典中找到的密碼，拒絕選擇在英文字典縮略本中找到的任何一個單詞的簡單轉換作為密碼，測試字典至少包括50,000個詞匯。可以選擇長密碼(如16個字符以上的短語)，對長密碼不強制進行字典測試。

3.1.2 組合規則

通常要求用戶選擇的密碼包括小寫字母、大寫字母和非字母符號(例如，;: “ ～ ! @ # $ % ^ & * ( ) _-+ = { } [ ] | : ;’ ＜ ,＞ . ? / 1234567890 ”)。

密碼選擇限制規則，雖然可能為一個真正的窮舉攻擊減少了工作量，但消除了許多明顯的密碼選擇，通常提高了密碼的“實際熵”。

表1提供了不同長度用戶選擇的密碼的平均熵的粗略估計。密碼選擇 94符號的字符集，經過字典測試，并遵守組合規則。該表還提供了在 10個數字的字符集中選擇密碼或PIN碼的熵估計。

表1 密碼猜測熵估計

對于從94符號的字符集中抽取用戶自選密碼，表1形成邏輯如下：

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

(2) 接下來的7個字符，每個字符的熵是2位；這大致與香農的估計一致，香農估計：“當統計的影響范圍不超過8個英文字符時，每個字符的熵大約是2.3位”；

(3) 從第9至第20個字符，每個字符的熵是1.5位；

(4) 第21及以后的字符，每個字符的熵是1位；

(5) 組合規則得到 6位熵的增強。雖然規則強制使用大寫字母和非字母符號，但在許多情況下，這些字符將僅出現在密碼的開頭或結尾，縮小了總的搜索空間，所以這個增強可能被中和并且幾乎與密碼的長度無關；

(6) 字典規則可以得到最多 6位熵的增強。如果攻擊者知道字典，就能夠避免測試那些密碼，使字典測試帶來的部分好處被抵消。這里假設大多數字典測試對猜測熵的增強局限于相對較短的密碼，因為任何可記住的長密碼，必然是一個字典中的單詞組成的“密碼短語”，在長度達到20個字符時熵的增強下降到零。

圖1給出了用戶選擇的密碼字符長度與估計熵的位數關系。

圖1 用戶選擇的密碼字符長度與估計熵的位數關系

對于用戶選擇的PIN碼，表1假設遵守這樣的基本規則：不選擇所有數字都相同或按順序排列的數字(例如，“1234”或“76543”)作為PIN碼。

3.2 最小熵

最小熵是攻擊者猜測系統中最常使用密碼的難度度量。

經驗表明，大量的用戶會選擇非常容易被猜到的密碼。例如，假設在 1000個用戶中，有個用戶選擇了最常見的兩個密碼，當前系統設置為在鎖定密碼前允許用戶進行3次嘗試。已經掌握用戶名列表的攻擊者，可以利用每個用戶名嘗試那兩個密碼，有望通過700個用戶名與那兩個密碼的組合嘗試，至少發現一個密碼。顯然，如果攻擊者的目標是獲得對系統的訪問，而不是冒充一個預定用戶，這就是一次成功的攻擊。忽略這種可能性將是非常危險的。

由于沒有用戶在密碼系統規則下選擇的實際密碼情況，所以無法提供準確估計用戶選擇的密碼最小熵的一般方法。但是通過相當大的字典測試用戶選擇的密碼，將提高密碼的最小熵。為了確保至少有10位的最小熵，字典測試如下：

(1) 密碼中的大寫字母全部轉換為小寫字母，并與至少包含50,000個密碼的密碼字典進行比較，拒絕采用與字典條目匹配的密碼。

(2) 不允許采用可檢測用戶名排列的密碼。

可以選擇其他方法確保至少有 10位最小熵。例如，用戶選擇的至少15個字符的密碼被認為至少有10位最小熵；一個隨機選擇的短字符串(從94符號的字符集中隨機選擇的兩個字符串，有大約13位熵)；將一個密碼與一個短的系統選擇的隨機元素組合形成一個較長的用戶選擇的密碼，能夠保證具有10位最小熵。

[1]Matt Bishop著,王立斌等譯.計算機安全學-安全的藝術與科學.電子工業出版社.2005.

[2]馮尚友.信息熵與最大熵原理.水利電力科技.2006.

[3]敖紅.對信息熵的探討.遼寧高職學報.2007.

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