新的在標準模型中可證安全身份鑒別協議
2009-01-01 00:00:00李艷平
計算機應用研究 2009年6期
摘 要：基于RSA衍生的判定性Dependent RSA問題的困難性假設，提出一個安全高效的身份鑒別方案。在標準模型下，可證明該身份鑒別協議在主動并行攻擊下能抵抗冒充攻擊和中間人攻擊。由于交互簡單自然、低存儲量、低計算量和好的安全性能，該身份鑒別協議更適合用于廣泛應用的智能卡。
關鍵詞：身份鑒別協議;中間人攻擊;RSA問題;標準模型
中圖分類號：TP319文獻標志碼：A
文章編號：1001-3695(2009)06-2138-03
doi:10.3969/j.issn.1001-3695.2009.06.042
New provably secure identification protocol in standard model
LI Yan-ping
(College of Mathematics Information Science， Shaanxi Normal University， Xi’an 710062， China)
Abstract:Based on the hardness assumption of the decisional relevant RSA (DDRSA for short， which derived from RSA problem)，presented a secure and efficient identification protocol.Proved the proposed identification protocol secure against impersonation and man-in-the-middle attack under both active and concurrent attacks in standard model. Due to its simplicity and naturalness， low-memory， low-computation loads， and better security， the proposed scheme is well suitable for using in smart cards.
Key words:identification protocols；man-in-the-middle attack；RSA problem；standard model
身份鑒別協議是基于公鑰密碼體制的一種基礎的關鍵性技術，該技術在電子現金的認證傳輸和系統的訪問控制等應用中具有重要作用。初期較為著名的身份鑒別協議有基于RSA問題的Guillou-Quisquater(GQ)身份鑒別協議[1]和基于離散對數問題(DLP) 的Schnorr身份鑒別協議[2]。它們被認為是高效的， 但被指出兩協議在中間人攻擊下是不安全的， 同時作者沒有提供方案的安全性證明[3]。最近許多基于橢圓曲線的身份鑒別協議被陸續提出[4，5]，但這些協議后來均被證明在中間人攻擊下是不安全的[6]。事實上，多數鑒別協議都不能抵抗中間人攻擊，即中間人攻擊是很多安全協議的疾瘤。一般來說，為了保證身份鑒別協議可抵抗各種攻擊，設計的鑒別協議要用嚴格數學規約來證明其安全程度。但由于敵手攻擊行為不拘一格且層出不窮，為身份鑒別協議作安全性證明一直被視為是一件極為困難的工作[7]。本文在RSA衍生的判定性Dependent RSA問題(decisional relevant RSA，DDRSA)的困難性假設下，將給出一個安全的新的身份鑒別協議。該協議的安全性主要體現在本文方案能抵抗中間人攻擊，且基于較弱的困難性問題DDRSA在標準模型下給出新鑒別協議的安全性證明。
1 預備知識
1.1 中間人攻擊
中間人攻擊是指攻擊者不僅能夠截獲通信雙方的消息，而且能夠任意刪除、修改，甚至插入新的消息。這是一種基于消息截獲和轉發而欺騙信任或獲取通信內容的較強攻擊方式，也是一種對網絡協議比較典型的主動攻擊方式。下面給出中間人攻擊的抽象數學模型。不失一般性，假設敵手Mallory介入一雙方通信協議， 該協議由某通信方Alice發起協議。
AliceMSG1MalloryMSG′1Bob
AliceMSG′2MalloryMSG2Bob
Alice… Mallory…Bob
AliceMSGn/MSG′nMalloryMSG′n/MSGnBob
假設通過若干輪交互后，Mallory可解讀通信雙方Alice與Bob之間通信的秘密信息， 或以其中一方的身份騙得另一方的信任， 則稱該中間人攻擊協議成功。只要敵手Mallory沒有導致明顯的網絡延遲， 真正通信雙方Alice和Bob也沒辦法知道有人正在他們中間解讀他們自認為是秘密的消息或正在假冒某方騙取另一方的信任。特別注明， 若Mallory對收發雙方的信息不作任何修改進行轉發， 那么此類中間人攻擊沒有本質意義， 本文不予考慮。
1.2 困難性假設
1)RSA問題 設n為兩大素數p、q的乘積且|p|=|q|≥512 bit，|x|表示數串x的二進制長度。計算φ（n）=(p-1)(q-1)，設Ω={x|1≤x≤φ(n)且gcd(x，φ(n))=1}，選取公開密鑰e∈Ω，并私下計算私鑰d=e-1mod(φ(n))并保存。RSA問題是指，給定公鑰(n，e)及密文c，求滿足c=me mod n的加密消息m。一般認為RSA問題是困難的，即不存在能以不可忽略的概率解決RSA問題的多項時間算法。
2)計算性Dependent RSA問題(computational dependent RSA，CDRSA) 已知α∈Zn。其中α=xe mod n，x≠0，x∈Zn，求(x+1)e mod n。在RSA問題中模數n足夠大的情況下(|n|≥1 024 bit)，CDRSA也是困難的，即不存在能以不可忽略的概率解決CDRSA問題的多項時間算法。
3)提取性Dependent RSA問題(extraction dependent RSA，EDRSA) 已知n，e，α=xe mod n，β=(x+1)e mod n，x∈Zn，x≠0，計算x∈Zn。在RSA問題中公鑰|e|≥60 bit的假設下，EDRSA也是困難的。
4)判定性Dependent RSA問題(DDRSA) 給定一點對(α，β)(α，β∈U Zn)及RSA模數n和指數e，以大于1/2的概率判斷(α，β)屬于Rand集合還是Dependent集合。其中：Rand集={（α，β）|α=xe mod n，β=(y+1)e mod n，x，y∈R Zn}；Dependent集={(α，β)|xe mod n，(x+1)e mod n，x∈R Zn}；∈U表示一致均勻地屬于某個集合。
5)判定性Relevant RSA問題(DRRSA) 已知給了一點對（α，β）和RSA模數n，在e，1/e未知的情況下以大于1/2的概率判斷(α，β)屬于Rand集合還是Relevant集合。其中：Rand集=
{（α，β）|α=xe mod n，β=(y+1)1/e mod n，x，y∈R Zn，e∈Ω}；Relevant集={(α，β)|xe mod n，(x+1)1/e mod n，x∈R Zn，
e∈Ω}。本文定義區分者的優勢為Adv()=PrRand[A(α，β)=1]-PrRelevant[A(α，β)=1]。
注: DDRSA問題中即使公開參數n、e，因不知x，很難判斷任意給定的一對(α，β)屬于哪個集合。而DRRSA問題中只給了參數n，在不知道e與x的情況下去判定（α，β）屬于哪個集合，困難性更大。在DDRSA問題中α與β關系不明顯，除非找出x，才能驗證α與β的關系。在DRRSA問題中若找出e，就能驗證（βe-1）e?=α mod n。從而能確定（α，β）屬于哪個集合，但找到e的概率為1/|Ω| →0。
定理1 CDRSA+ EDRSARSA，CDRSA，EDRSADDRSA。
定理2 稱DDRSA問題是難解的，當且僅當公鑰指數e大于260，對于某個較大的模數n(≥1 024 bit)[8]。
定理3 稱DRRSA問題是難解的，當且僅當公鑰指數e一致均勻取自Ω集，對于很大的模n(>>1 024 bit)。
2 身份鑒別協議的定義及安全性要求
2.1 身份鑒別協議的定義
定義1 一個身份鑒別協議是由兩個概率多項式時間(PPT)算法(s，ε)和一個交互協議(p，v)來描述，它們依次被稱為參數建立算法，私鑰提取算法和鑒別協議:
a)參數建立算法(s=setup)。輸入安全參數1k，產生全局系統參數params并公開。
b）密鑰提取算法(ε=extract)。輸入系統參數params和用戶私鑰sk，輸出對應的用戶公鑰pk。某權威機構為(pk，sk)頒發證書cert，將用戶現實身份與公私鑰對(pk，sk)捆綁一起，這時(pk，sk)就可表示某用戶身份。
c)標準的三趟身份鑒別協議(p，v)。P將(params，sk)作為輸入，向V發送一個承諾commitment(CMT)后，V從挑戰集中隨即選一個挑戰challenge(CH)發送給P，接著P向V提供一個響應response(Rsp)；然后V驗證響應Rsp，最后輸出一個布爾判定1(接受)或0(拒絕)。合法的P應該總是被任意驗證者V接受。
2.2 安全概念
對于身份鑒別方案，主要考慮的攻擊是冒充攻擊，即敵手可使任何驗證者確信自己是某個冒充身份的合法擁有者。考慮的攻擊類型有被動攻擊、主動攻擊、并行攻擊[3]。被動攻擊是指，敵手在冒充之前只可竊聽并記錄某挑戰者身份的誠實示證者與驗證者之間的會話腳本。主動攻擊和并行攻擊是指敵手可主動出擊獲得相關信息后再進行冒充攻擊。兩者的區別在于主動攻擊中，欺騙性驗證者依次與示證者交互獲取有用信息，而在并行攻擊中，欺騙性驗證者可并行地與多個不同的誠實示證者“克隆”交互。這些克隆都具有相同私鑰和獨立的隨機初始化狀態。中間人攻擊前面已經簡單闡述過。重放攻擊是敵手將來自誠實的示證者的會話腳本CMT、CH、Rsp進行重放，希望冒充示證者來騙取新的驗證者的信任。重置攻擊、中間人攻擊和重放攻擊均屬于主動攻擊的具體攻擊方式。多數身份鑒別方案不能抵抗中間人攻擊。
3 高效的身份鑒別協議
1）參數建立算法s 輸入安全參數1k，生成公開參數n和h(#8226;)，n(>>1 024 bit)為RSA模數，是兩大素數之積，保密素因子；h(#8226;)為單向無碰撞哈希函數，h(#8226;):{0，1}→{0，1}l滿足l＜n。||表示二進制比特串的級聯。
2）密鑰提取算法ε 用戶輸入d∈RZn，ε算法輸出e=d-1 mod φ(n)，要求|e|≥60 bit否則要求用戶重新選擇輸入私鑰d。將e作為用戶公鑰公開。某權威機構為用戶公鑰e頒發電子證書cert并發布在權威網站上以供查詢，cert中明確標出密鑰有效期。設示證者P（prover）的公私鑰分別為(e，d)。這里允許驗證者V（verifier）與示證者P的公私鑰不屬于同一個公鑰密碼系統，即公私鑰不同公鑰密碼系統內的用戶均可實施本鑒別協議。
3)身份鑒別協議(p，v) 設任何通信雙方都有一個記錄表(U，s)。其中：U為通信對方；s為第幾次通信的數字序號。這是非常自然的一種記錄行為且幾乎不占內存，只需用簡單的累加器改變數字序號即可。這個序號只有通信雙方知道，相當于雙方的共享秘密。鑒別協議如下：
a)P隨機選取k∈Zn使K=k‖s‖t＜n，計算A=Ke mod n與certP 一并發給驗證者V。
b）V驗證certP中公鑰是有效的，記錄A值，t表示發送第一條信息的時戳，V隨機選擇c∈Zn發給示證者P。
c)P計算B=c×(K+1)d modn，H=h(P‖V‖K‖A‖c‖B)，并將B和H均發給V。
V接收到B和H后，計算K=（（B/C)e?-1) mod n并檢驗序列號s是否正確。若正確， 則計算Ke mod n=A，H=?h(P‖V‖K‖A‖c‖B)后輸出布爾判定1或0，表明是否接受P是公鑰e、n的合法擁有者。
3.1 安全性分析
1)正確性 若K=（（B/C)e-1) mod n且Ke mod n=A經檢驗是有效的，則A、B均來自示證者P。而驗證式H=h(P‖V‖K‖A‖c‖B)中用到了通信雙方共享的秘密值s、驗證者的隨機挑戰c、示證者的響應值B，若通信雙方不是P、V，不可能生成和驗證有效的校驗值H。若P是誠實的示證者，則驗證結果總為布爾值1。
2)抗被動攻擊與重放攻擊 任何知道公開參數為n、h和用戶公鑰e的敵手只允許竊聽(p，v)協議會話腳本(Ai，ci，Bi，Hi)，又因為Ai、ci、Bi、Hi都是隨機生成且逐次變化的，敵手也不可能進行重放攻擊。所以敵手在監測P、V通信及其會話腳本后，因無法為任意消息生成P的合法簽名，故無法冒充P通過鑒別，即冒充不成功。
3）抗中間人攻擊 本協議采用以下四種策略來抵抗中間人攻擊：
a）讓通信雙方共享隨機秘密值s(也可采用密鑰協商來協商一個只用于本次協議的隨機數)。協議中將這個共享秘密值定義為雙方成功交易次數。只有鑒別雙方知道這個秘密值，任何不知該秘密值的中間敵手都不能冒充成功。
b）采用先簽名技術，使得中間敵手不能生成P的有效簽名，從而很難冒充成功。或者說V發出挑戰c，由于中間敵手不知道P的私鑰d，不能為挑戰c生成正確的響應值B。雖然敵手在獲得兩個來自P的有效的A1=(K1)e mod n和A2=(K2)e mod n后能合成一個A=(K1K2)e mod n，但是V獲得后驗證序列號s就可知道對方真偽。
c)單向無碰撞哈希函數h(#8226;)將每次協議的全部腳本捆綁在一起，構成本輪協議的認證信息。敵手只有擁有K中正確的序列號，才能生成有效的哈希值。
d）時戳t來提示鑒別者V對通信時間的把握，P、V從協議開始到結束，包括網絡時延應該有個大概的估計，若超過一定的時限，可放棄本輪協議。
前面已提到過，不考慮敵手對收發雙方的信息不作任何修改進行轉發，因此類攻擊沒有本質意義， 且所有設計嚴謹的非面對面的交互中都有路由(敵手)中轉存在。
3.2 協議的效率與進一步擴展
本文方案所給鑒別協議用了兩個模冪運算ME、一次模乘運算MUL和一次hash運算H。其中hash運算主要用于認證。因模冪運算ME最費時，與同樣是基于RSA問題的文獻[1，4，5]中鑒別方案相比，幾個方案計算量和通信量相當。本文鑒別協議能抗中間人攻擊，安全性好。
3.3 安全性證明
設A是一個敵手算法，其目的是冒充某個用戶P。B是一個試圖解決DRRSA問題的挑戰者。B以A為他的一個挑戰子程序。設B擁有一組（α，β），需要判定其屬于Rand集或屬于Relevant集。允許冒充者A在冒充之前可以與將要被冒充的誠實的示證者P交互qA＜|n|，次交互過程中A扮做欺騙性驗證者，交互的方式可以是依次進行的，也可與誠實的示證者P進行并行交互；最后A將做一些交互腳本記錄(Ai，ci，Bi，Hi)(主要用于被動攻擊)。最后假設A能成功冒充P，即對適應性挑戰c，冒充者A總能以ε的優勢在時間t內生成正確的響應B，使得驗證者認為A就是P，那么可設計冒充者A與攻擊者B之間的游戲。其中若冒充者A能以大于1/2的概率區別承諾和響應(A，B)對應c0、c1中那個挑戰，則攻擊者B就會以大于1/2的概率解決給定的DRRSA問題。游戲如下：
{攻擊者B擁有一個（α，β），或屬于Rand集或屬于Relevant集，然后BA=αB
{A隨機選擇兩個c0，c1∈U，Zn然后c0、c1B
B擲幣的結果y∈{0，1}，計算B=cy×β mod n，然后BBA
A輸出(A，B，b)，其中b∈{0，1}}
若b=y，則B輸出1，表示(α，β)∈Relevant集；若b≠y，則B輸出1，表示(α，β)Rand集}
下面分析冒充者A回答b=y的概率。（α，β）∈Rand集，則(A，B)=(α，cyβ)=(xe mod n，cy(y+1)d mod n)一直均勻的分布于Zn×Zn空間中，因此確定b∈{0，1}的概率為1/2，即PrRand[β(α，β)=1]=PrRand[b=y]=1/2。若（α，β）∈Relevant集，則(A，B)=(α，cyβ)=(xe′ mod n，cy(x+1)d mod n）能正確地通過此次驗證，即PrRelevant[β(α，β)=1]=Prrelevant[b=y]=1/2±ε/2， 由假設知ε是敵手A的優勢。
定理1 在上述游戲中，如果一個多項式有界的冒充者在t時內主動并行攻擊中具有ε優勢(q次提前交互)，那么Zn中的DRRSA問題可在時間t′=t內以優勢ε′＞ε/2解決。
4 結束語
身份鑒別方案是一種非常重要的認證技術，中間人攻擊是身份鑒別方案很難抵抗的一種攻擊模式，文獻[1，2，4，5]中方案均因在中間人攻擊下不安全導致易被敵手冒充。為了抵抗中間人攻擊，需要一種技術來對所有消息的完整性和正確性驗證。基于RSA問題衍生困難問題——DRRSA問題，提出一個在隨機預言模型下可證安全的身份鑒別方案，該方案能抵抗各種攻擊模式，從而在冒充攻擊下是安全的。對中間人攻擊的防范策略是通過在通信雙方安全地傳送兩個隨機數，然后用這兩個隨機數導出保密的會話密鑰以保證后續通信的安全。在協商會話密鑰的過程中不僅驗證了客戶端身份，而且還保證了服務器證書的有效性。使用這種策略，不需要客戶端身份認證，客戶端也不需要驗證服務器證書的有效性，就能建立安全的連接，可以成功地防止中間人攻擊， 這在實際中具有普遍的實用價值。下一步的研究工作是設計在標準模型下可證安全的雙向身份鑒別方案。
參考文獻：
［1］GUILLOU L S，QUISQUATER J J.A practical zero-knowledge protocol fitted to security microprocessors minimizing both transmission and memory[C]//GNTHER C G.Proc of EUROCRYPTO’88.Berlin:Springer-Verlag，1988:123-128.
[2]SCHNORR C P.Efficient identification and signatures for smart cards[C]//Proc of CRYPTO’89.Berlin:Springer-Verlag，1990:239-252.
[3]BELLARE M，PALACIOY A.GQ and Schnorr identification schemes:proofs of security against impersonation under active and concurrent attacks[C]//YUNG M.Proc of CRYPTO’02.Berlin:Springer-Verlag， 2002:167-177.
[4]TSENG Y M， JAN J K. ID-based cryptographic schemes using a non-interactive public-key distribution system[C]//Proc ofthe 14th Annual Computer Security Applications Conference.Washington DC:IEEE Computer Society， 1998:237-243.
[5]HWANG M S， LO M S，LIN S C.An efficient user identification scheme based on ID-based cryptosystem[J].Computer Standards Interfaces，2004，26(6):565-569.
[6]TANG Qiang， MITCHELL C J. Cryptanalysis of two identification schemes based on an ID-based cryptosystem [J].Communications， IEE Proceedings，2005，152(5):723- 724.
[7]SHAO Jun，CAO Zhen-fu，LU Rong-xing.A new efficient identification scheme based on strong Diffie-Hellman assumption[C]//Proc of International Symposium on Future Software Technology(ISFST-2004).Software Engineers Association，2004.
[8]POINTCHEVAL D.New public key cryptosystems based on the dependent RSA problems[C]//STERN J.Proc ofEUROCRYPT’99.Heidelberg，Berlin:Springer-Verlag，1999:239-254.
