基于集合調和的遠程口令恢復方法

摘 要：基于對多項式編碼的集合調和方法的研究，提出一種簡單的遠程口令恢復新方法。其利用容易記憶的低熵口令集經hash變換后加密并存儲高熵口令；利用集合調和多項式容錯求解得到原始的低熵口令集，從而恢復高熵口令。同時，提供了兩個安全的遠程口令恢復協議。分析表明，此方法可以安全廣泛地應用到遠程應用系統中。

關鍵詞：口令；集合調和；加密；特征多項式

中圖分類號：TP309文獻標志碼：A

文章編號：1001-3695(2009)06-2113-03

doi:10.3969/j.issn.1001-3695.2009.06.034

Remote password recovery using set reconciliation

FU Bo，LI Jian-ping，WEN Xiao-yang

(School of Computer Science Engineering， University of Science Technology of China， Chengdu 610054， China)

Abstract:Proposed a simple and novel scheme for remote password recovery based on set reconciliation.Used the set of low entropy passwords to recover a high entropy password.Accomplished the random map of password set using standard hash function. And symmetric cryptography essentially acted as high entropy password storing.Demonstrated two security protocols how to realize the process of password recovery between the end user Alice and the service provider Trent.

Key words:password; set reconciliation; encryption; characteristic polynomial

密鑰保護常采用三種方式，即口令^[1]、智能卡^[2，3]和生物特征技術^[4，5]。智能卡方式使用簡單、方便，但缺乏可靠性，而生物特征技術識別精度卻很難提高。盡管基于口令的密鑰保護存在記憶要求^[5]，在信息安全領域應用卻最為廣泛。采用口令的密鑰保護方式中，低熵口令容易受到字典攻擊，因此，很多系統不得不提高口令長度或縮短口令修改周期。但是如果平凡修改口令，高熵口令使得記憶尤其困難。實際上，隨著在線賬戶的增加，忘記口令是一個非常普遍的問題。用戶常采用以下方式來幫助口令記憶：a）將復雜口令保存在紙張或電腦文件上；b）多個系統采用同樣的口令密碼；c）跟家人共用一個密碼。但是，這些方法使得攻擊者可以采用社會工程學的方法來突破口令^[6]。

口令恢復提供了一種更為有效的口令管理方法。在不降低口令脆弱性的情況下，合法用戶可以快速而安全地恢復口令，同時非法用戶卻難以得到別人的口令。Frykholm等人^[7]指出了兩種口令恢復方法：

a)傳統的依靠可信第三方的方法。當向可信任的管理員提出口令恢復請求后，管理員根據請求信息采用電話或郵件方式恢復用戶口令。但是通過電子郵件傳輸時，口令熵和郵件用戶口令的熵是一樣的。所以，攻擊者可以通過攻擊郵件來攻擊應用系統的用戶口令。

b)(n，k)秘密共享方法^[8，9]。口令被分成n個共享，只有當k個共享收集到后才能重構口令。這需要記憶或保存這n個共享。

以上的口令恢復方法都需要依靠可信第三方，因而，Frykholm等人提出了容錯口令恢復方法。 這個方法是基于Juels等人^[10]的模糊提交技術和Eillison等人^[11]的個人熵，但Frykholm等人的方法需要按嚴格的順序來回答輔助口令，而且此方法只能應用到本地計算機而難以應用到遠程的口令恢復。這使得當大量的在線應用需要口令保護時，本地方法很容易受到攻擊且難以管理。因此，本文將介紹一種簡單而安全的遠程口令恢復方法。該方法來源于集合調和的思想^[12]。與前人的工作相比，其具有三個重要優勢：a）輔助口令無序，且可動態調整；b）安全性更高；c）可以方便地遠程部署，這使得此方法可以得到廣泛應用。

1 基礎知識

針對兩個相似集合的調和問題由Minsky等人^[12]首次提出。采用集合的多項式編碼方法，設XS（Z）是集合S={x1，x2，…，xn}的單變量特征多項式，定義如下：

XS(Z)=(Z-x1)(Z-x2)…(Z-xn)(1)

對兩個集合SA和SB的特征多項式，可以按照如下方法來求其比率：

XSA（Z）/XSB（Z）={XSA∩SB(Z)×XΔA(Z)}/{XSA∩SB(Z)×XΔB(Z)}=XΔA(Z)∩XΔB(Z)

(2)

因而，式(2) 可改寫為

XSA(Z)=XSB(Z)×XΔA(Z)/XΔB(Z)(3)

這表明，如果已知集合SA和SB的集差多項式ΔA和ΔB，可以用XSB來求得XSA。但是，如何在不暴露集合信息的情況下得到集合的集差多項式呢？文獻[12]提出了多項式的根查找方法。Chang等人^[13]則詳細介紹了利用集合的預先評估方法來計算集合的集差。本文會用到這種方法，這里就不再詳述。

在文中，主要會用到以下一些特殊符號：Π表示要恢復的高熵口令；pi和p′i是輔助口令，對應輔助口令集合PS=[p1，p2，…，pN]和P′S=[p′1，p′2，…，p′N]；設fi:{0，1}*→{0，…，q-1}是函數映射，用來映射pi（或p′i）到域GF(q)；WΔ和W′Δ是差集，表示為WΔ=W-W′和

W′Δ=W′-W；Enc是加密過程， 當輸入PS和Π時，輸出密文e和集合Q0；Dec是解密過程，當輸入PS和Q0時，輸出密鑰k；Ek(#8226;)和Dk(#8226;)表示對稱加/解密算法，如3DES或AES；H（#8226;）表示hash函數，如SHA-1。

2 口令恢復

2.1 實現過程

正如圖1所示，為得到輔助口令集PS，系統提出N個問題要求用戶回答。比如：你的第一只寵物叫什么名字，你最喜歡的書的作者是誰，在哪里慶賀你的十歲生日？當得到答案后，PS用來構造特征多項式，以求取輔助數據Q0用于口令恢復。同時，可以利用PS的hash值來作為高熵口令Π的加密密鑰，從而利用對稱加密算法隱藏口令為密文e。當用戶遺失口令后，為從服務器存儲的密文e中恢復口令，首先需要根據對應問題的回答提取出加密密鑰。總的說來，口令的恢復過程分為兩個階段：a)口令的加密保存階段，這為用戶的口令恢復做準備；b)口令恢復階段，一旦用戶無法回憶起自己的口令就需要借助a)的信息來恢復口令。本文用Enc和Dec兩個算法來描述這兩個階段。Enc和Dec算法需要將PS和P′S映射成GF(q)上的元素集合[fi:{0，1}*→{0，…，q}]Ni=1。這個映射過程可以采用hash算法SHA-1來實現。假定PS和P′S中允許的最大錯誤數為t，則兩個集合中的不同元素總數為2t。為求解得到兩個集合中的差集需要借助集合Λ={m-1，m-2，…，m-2t}。其中m滿足m≥q+2t的最小素數。在這里需要說明的是，Λ如果取值于GF(q)中，則可能導致特征多項式XS(Z)為零，從而式（2）會出現問題，所以，需要適當擴大運算的范圍，用GF(m)中Λ來計算GF（q）中的值可以克服此問題。同時，為將口令安全地保存起來還需要借用對稱加密算法。

算法1 Enc(PS，Π)→[e，Q0]

a)將PS=[p1，p2，…，pN]中的每一個口令pi映射成GF(q)上的元素wi。在這里，可以將pi先用SHA-1作hash運算后再變換成有限域上的元素。表示為wi=fi(H(pi))。

b)根據W={w1，w2，…，wN}構造特征多項式XS(z)：

XS(z)=(z-w1)(z-w2)…(z-wN)

c)用集合Λ={m-1，m-2，…，m-2t}計算公開信息Q0：

Q0={X(m-1)，XS(m-2)，…，XS(m-2t)}（4）

d)對{w1，w2，…，wN}作hash運算，將其運算結果作為密鑰k：

H{w1，w2，…，wN}→k（5）

e)用密鑰k加密口令Π，e=Ek(Π)。

f)返回[e，Q0]。

Enc算法中，d）的hash運算后可以根據密鑰的長度要求變換得到密鑰k，最簡單的方式就是截取某些位作為加密密鑰。在整個Enc算法中，最關鍵的就是要生成Q0，Q0雖然是公開的，但是它卻不包含任何PS中的信息。即使攻擊者知道Q0的詳細信息也不可能反向得到PS，所以這個過程非常安全。同樣，當用戶要求口令恢復時，系統提取出該用戶對應的N個問題要求做答，得到答案P′S，將P′S和Q0作為輸入提交給Dec，輸出用戶的口令加密密鑰k′。

算法2 Dec(P′S，Q0)→k′

a)將P′S=[p′1，p′2，…，p′N]中的每一個口令p′i映射成GF(q)上的元素w′i。表示為w′i=fi(H(p′i))。

b)根據W′={w′1，w′2，…，w′N}構造特征多項式XS′(z)：

X′S(z)=(z-w′1)(z-w′2)…(z-w′N)（6）

c）用集合Λ={m-1，m-2，…，m-2t}計算Q1：

Q1={XS′}(m-1)，XS′(m-2)，…，XS′(m-2t)}（7）

d)設XΔ(z)=zt+t-1j=0ajzj，XΔ′(z)=zt+t-1j=0bjzj是次數為t的首一多項式。設aj、bj是未知數，利用Q0和Q1集合構造如下線性方程組：

XS′(m-i)XΔ(m-i)=XS(m-i)SΔ′(m-i) （8）

其中:1≤i≤2t。式（8）中有2t個方程，2t個未知變量，由線性方程的特性可知其一定有解，且是惟一的。

e）求解方程得到XΔ(z)和X′Δ(z)的系數{a0，a1，…，at-1}和{b0，b1，…，bt-1}，并利用求得的系數求解多項式XΔ(z)和XΔ′(z)的根集，令其為WΔ和WΔ′。

f)計算得到W″，W″=(W′∪WΔ)-WΔ′。對W″作hash運算，得到密鑰H(W″)→kg)返回k′。

由算法2中的Dec(PS′，Q0)可以得到合法用戶的口令加密密鑰，可以通過Dk′(e)解密得到用戶的口令。在f)中，如果用戶是合法用戶，則可以使W″=W，從而使k′=k；如果是非法用戶，則他不能正確回答相應的問題，其回答錯誤數大于t，則求解WΔ和WΔ′會出現錯誤，也就無法得到正確的差集，從而無法得到正確的k′。為提高系統的安全性，可以適當調整t的大小來改變安全性。在極端情況下，當t=0時，就要求用戶完全正確回答出所有問題。

2.2 兩個定理

在這里作三個假設：a）假定加密算法是足夠安全的，比如采用192 bit的AES加密，則攻擊者已知密文要得到明文就非常困難；b）假定攻擊者通過某種途徑獲取到了[e，Q0]；c）假設攻擊者有足夠的能力去了解合法用戶的信息，但要了解全部信息又是非常困難的。在以上三個假設條件下，有以下幾個定理：

定理1需要證明的是假設條件c）下，攻擊者對合法用戶有相當的熟悉程度，并對用戶的回答口令發起攻擊。

定理1 當攻擊者知道N個問題中的m（m≤N/4）個答案時，且t≤N/4，則攻擊成功的最大概率為1/2Nl/2。其中2l≤|GF(q)|≤2(l+1)。

證明 若攻擊者知道N個問題中的m個答案，由此攻擊者很容易地得到W′={w′1，w′2，…，w′n}中的m個元素，由于系統容許最多為t個錯誤，用于保證系統安全性的元素就只有N-m-t個，即只要攻擊者能夠攻破這些元素，則系統就完全被攻破了。

假設剩下的N-m-t個元素中，攻擊者以概率為Pr(pi)的概率獲得。若攻擊者沒有其他幫助信息條件下則Pr(pi)=1/q。攻擊成功的概率為N-m-t-1i=0Pr(pi)=N-m-t-1i=01/q=1/q(N-m-t)。所以，1/q(N-m-t)≤1/qN/2，由2l≤|GF(q)|≤2(l+1)得知其最大值為1/2Nl/2。

由此定理1可看出，為提高加密口令的安全性有兩種方式，即增大用戶回答口令的量和在取足夠大的q，使得有限域空間足夠大。

下面的定理2在假設條件b)和c）下，攻擊者具有一定的能力獲取相應的信息。

定理2 已知Q0和W′情況下，若|WΔ|≤t（在這里，|WΔ|=|W′Δ|），可以得到W使得W′=W；否則，W′≠W。

證明 首先證明若|WΔ|≤t，則W′=W。即，若W′和W中的相同元素個數超過N-t時，若已知Q0，則可以利用Q0和W′來恢復W。由式（3）可以看出，XS(z)=XS′(z)×XΔ(z)/XΔ′(z)，而XS(z)和XS′(z)的根分別是W和W′中的所有元素。XΔ(z)和XΔ′(z)的根分別是W和W′中對應的不同元素。只需要求解到XΔ(z)=zt+t-1j=0ajzj，

XΔ′=zt+t-1j=0bjzj的根就可以知道W和W′中對應的不同元素。所以，先利用公開信息Q0來求解XΔ(z)和XΔ′(z)中的系數。

很顯然，在Dec中可以很容易求解到對應的Q1，由Λ={m-1，m-2，…，m-2t}是Q0和Q1的解，則由以下關系式

XΔ′(z)XS(z)=XS′(z)XΔ(z)(9)

可得知

XΔ′(m-i)XS(m-i)=XS′(m-i)XΔ(m-i)(10)

其中:1≤i≤2t。由Q0和Q1已知，所以式（10）將aj、bj看做未知數，則有2t個線性方程，且有2t個未知數，很顯然，方程有解。所以可以求解得到多項式XΔ(z)和XΔ′(z)的根集，令其為WΔ和WΔ′。由W=(W′∪WΔ)-WΔ′可以很容易地恢復出W。

接下來證明若|WΔ|≥t時，W不可能恢復出來。

由|WΔ|≥t，則WΔ和WΔ′就不可能是XΔ(z)和XΔ′(z)的根集，也就是說下列等式

XΔ(z)-λ×XΔ′(z)=0 λ為參變量（11）

無法求解出2|WΔ|個根，所以式（10）也就不能解出WΔ和WΔ′，也就無法恢復W。

由定理1和2可以看出，只要取適當的參數，就能大大提高系統的安全性能。當然，這需要從實際的需求出發，要讓合法用戶可以方便快捷地恢復口令，又要讓攻擊者難以獲取口令。

3 部署協議

考慮這樣一個例子：在一個服務協議中，協議雙方是終端用戶Alice（A）和服務提供者Trent（T）。Alice希望得到服務，而Trent提供服務并管理用戶口令。這里有兩個協議來實現遠程的口令恢復。第一個用來保存口令，另一個用來恢復口令。Alice想要從Trent那里得到服務，首先，她需要發送服務請求給Trent請求注冊，Trent返回一個注冊單和一系列的問題要求回答。當Alice收到后，她需要設置初始口令并填單。之后，利用加密算法Enc(PS，Π)計算[e，Q0]。最后Alice將[e，Q0]發送給Trent保存，并銷毀本地記錄。

當Alice遺失或忘記口令，她希望通過一個恢復協議來恢復自己的口令。首先，她發送一個恢復請求給Trent。一旦Trent接收到請求，他根據Alice的請求發送Alice注冊時提供的N個問題和Q0給她。Alice回答這N個問題，并利用Dec(PS′，Q0)計算得到加密密鑰k′，Alice 用Trent的公鑰加密k′，發送給Trent。Trent利用k′加密Π，比較Ek′(Π)和e是否相等，如果相等，則驗證該用戶確實是Alice。Trent再發送e給Alice，Alice則利用Dk′(e)得到自己的口令Π。

協議1和2實現了口令的安全存儲和恢復功能。其中：數字跟“’”表示是Alice或Trent利用口令恢復軟件作計算處理；沒有加“’”的表示是他們間的協議通信消息。協議1具體描述了在登錄階段時，Alice和Trent協同實現了注冊和口令的安全保存。其中：KT和K-1T是Trent的公鑰和對應的私鑰。Alice使用KT來加密消息，這使得只有Trent可以合法地解密消息。

Protocol 1:

1)A→T:{A，Nq}

2)T→A:{questions，Nq，Nt}K-1T

(1’)Alice 用口令Π和算法Enc(PS，Π)計算[e，Q0]

3)A→T:{e，Q0，Na，Nt}KT

(2’)Trent用私鑰解密信息并保存[e，Q0]

4)T→A:{Na}

協議2描述了當Alice口令丟失后，Alice向Trent請求恢復其口令。這個過程中，Trent通過Alice計算得到的密鑰來驗證Alice的身份，如果通過驗證，將其保存的口令密文e發送給Alice。Protocol 2具體描述如下：

1)A→T:{A，Nr}

2)T→T:{questions，Q0，Nr，Nt}K-1T

(1’)Alice用Trent的公鑰解密消息2并用算法Dec(PS′，Q0)計算k

3）A→T:{k，Nt}KT

(2’)Trent用私鑰K-1T解密消息3得到k，并計算Ek(Π)，將計算結果與服務器中存儲的e作比較。如果Ek(Π)≠e，則生成出錯信息，并退出協議

4)T→A:{e}K-1T

(3’)Alice 用算法Dk(e)解密密文 ，從而可得到其口令Π

在步驟1），Alice向Trent發出要求恢復口令的信息Nr，其與Nq類似的一個挑戰；然后，Trent得到請求后，將問題和Q0簽名發送給Alice。即使攻擊者得到了Q0，其也無法恢復得到用戶的口令。Alice通過Q0和自己記憶中的低熵口令集用Dec(PS′，Q0)可以計算出其加密密鑰，如果Alice不能正確回答足夠的問題，則無法得到正確的密鑰，也就根本計算不出密鑰。在步驟3）中，Alice用Trent的公鑰加密密鑰并發送給Trent。Trent可以用這個密鑰在（2’）中驗證其是否確實為Alice。 只有驗證成功，Trent才簽名返回給Trent口令的密文e。Alice就可以利用e和計算得來的k′，并在(3’)中解密得到自己的口令Π。

從協議1和2中通過利用Trent的公鑰加密和私鑰簽名來保障通信過程的安全性和Trent的身份認證問題。而Alice的身份認證通過計算得到的密鑰來確認。這兩個協議安全地實現了Alice的口令恢復。

4 結束語

集合調和方法在具有一定相識度的集合間信息傳遞的數據量少，而且不泄露任何信息，因此，可以實現安全的口令恢復。正是利用了集合調和方法的這一特性，本文研究了用戶一旦忘記高熵口令而無法再訪問數據系統時，可以通過集合調和方法安全地利用低熵的口令集來恢復訪問口令。本文提供了兩個基本的算法Enc和Dec來實現加密和恢復功能，并展示了兩個安全的遠程恢復部署協議。分析證明，該算法切實可行，能夠保證應用的安全性。將來的工作在于將此方法應用到實際應用系統中，并提高協議在實際應用中的可靠性。

參考文獻：

［1］TSAI C S，LEE C C，HWANG M S.Password authentication schemes: current status and key issues[J].International Joural of Network Security，2006，93(2):101-115.

[2]LEE J K，RYU S R，YOO K Y.Finger-based remote user authentication scheme using smart cards[J].Electronics Letters，2006，38(12):554-555.

[3]CLARK P C，HOFFMAN L J.BITS:a smartcard protected operating system[J].Communications of the ACM，1994，37(11):66-94.

[4]JAIN A K，ROSS A，PANKANTI S.Biometrics: a tool for information security[J].IEEE Information Forensics and Security，2006，1(2):125-143.

[5]SIYAL M Y，AHMED F.A biometric-based scheme for enhancing security of cryptographic keys[C]//Proc of IEEE Region 10 Confe-rence.Piscataway，NJ:IEEE Press，2004:407-410.

[6]HAMILTON S S，CARLISLE M C，HAMILTON J A.A global look at authentication[C]//Proc of IEEE SMC Information Assurance and Security Workshop.West Point，NY:[s.n.]，2007:1-8.

[7]FRYKHOLM N，JUELS A.Error-tolerant password recovery[C]//Proc of the 8th ACM Conference on Computer and Communications Security.New York:ACM Press，2001:1-8.

[8]MENEZES A，OORSCHOT P V，VANSTONE S A.Handbook of applied cryptography[M].[S.l.]:CRC Press， 1996.

[9]SHAMIR A.How to share a secret[J].Communications of the Association for Computing Machinery，1979，22(11):612-613.

[10]JUELS A，WATTENBERG M.A fuzzy commitment scheme[C]//Proc of the 5th ACM Conference on Computer and Communications Security.New York:ACM Press，1999:28-36.

[11]ELLISON C， HALL C， MILBERT R，et al.Protecting secret keys with personal entropy[J].Journal of Future Generation Computer Systems，2000，16(4):311-318.

[12]MINSKY Y，TRACHTENBERG A.Set reconciliation with nearly optimal communication complexity[J].IEEE Information Theory，2003，49(9):2213-2218.

[13]CHANG E C， FEDYUKOVYCH V，LI Qi-ming.Secure sketch for multi-sets[EB/OL].(2006-03).http//citeseerx.ist.psu.edu/viewdoc/summary?doi=10.11.60.1939.