張小梅+吳福生+彭長根

摘 要： 主要研究隨機密鑰協(xié)商問題，針對Diffie?Hellman協(xié)議、SAKA協(xié)議和改進Lin協(xié)議、E?SAKA協(xié)議等存在的不具有認證功能和不能抵抗中間人攻擊等缺陷，應(yīng)用動態(tài)雙向認證因子認證方法和非時間同步技術(shù)提出一種隨機密鑰協(xié)商協(xié)議，該協(xié)議適用于OTP動態(tài)口令系統(tǒng)設(shè)計，同時解決密鑰協(xié)商過程中的動態(tài)認證和時間同步問題。最后，在標(biāo)準(zhǔn)模型下證明了方案的安全性。

關(guān)鍵詞： 隨機密鑰協(xié)商； Diffie?Hellman密鑰協(xié)商； DDH問題； 可證明安全

中圖分類號： TN918?34； TP309 文獻標(biāo)識碼： A 文章編號： 1004?373X（2017）13?0087?04

Abstract： The random key agreement issue is studied. Since the Diffie?Hellman protocol， SAKA protocol， improved Lin protocol and E?SAKA protocol don′t have the authentication function， and can′t resist the man?in?the?middle attack， a random key agreement protocol is proposed on the basis of the factor authentication method of dynamic bidirectional authentication and non?time synchronization technology， which is suitable for the design of OTP dynamic password system， and can solve the problems of dynamic authentication and time synchronization in the key agreement process. The security of the proposed scheme is proved with the standard model.

Keywords： random key agreement； Diffie?Hellman key agreement； DDH problem； provable security

0 引 言

密鑰協(xié)商協(xié)議是通信雙方建立安全會話鏈接的主要工具之一，能有效保障通信參與方間的安全通信。早在1976年，Diffie和Hellman在“密碼學(xué)的新方向”一文中提出的公玥密碼思想為密鑰協(xié)商提供了新的解決途徑[1]。后續(xù)有大量學(xué)者在密鑰協(xié)商方面做了重要的工作[2?4]。文獻[4]在標(biāo)準(zhǔn)模型下提出了一種可證明安全的基于身份的認證密鑰協(xié)商協(xié)議；最近，文獻[5]提出一種面向無線傳感器網(wǎng)絡(luò)的雙因子用戶認證協(xié)議。可見，密鑰協(xié)商協(xié)議一如既往地受到廣大研究人員的重視。

Diffie?Hellman[1]算法是一個著名的雙方生成共享密鑰的經(jīng)典協(xié)議算法，但是該協(xié)議不具有認證功能，不能抵抗中間人攻擊。針對Diffie?Hellman協(xié)議的不足，文獻[2]提出簡單密鑰交換協(xié)議（SAKA），但其存在如下三個缺陷：攻擊者雖然不能獲得會話密鑰，但是可以模仿Bob與Alice建立連接；協(xié)議不能抵抗密鑰猜測攻擊； 協(xié)議不能保證前向的安全性。另外一些學(xué)者還提出了針對SAKA協(xié)議的一些改進協(xié)議，如文獻[6?9]。但是這些研究未能解決安全認證問題和中間人攻擊問題。針對這一不足，本文提出一種改進的新SAKA協(xié)議，該協(xié)議應(yīng)用動態(tài)雙向認證因子認證方法實現(xiàn)密鑰協(xié)商的動態(tài)認證，并利用非時間同步技術(shù)解決密鑰協(xié)商雙方的時間同步問題，最后在標(biāo)準(zhǔn)模型下給出協(xié)議的安全性證明。

1 基礎(chǔ)知識和協(xié)議原理

1.1 基本知識

Diffie?Hellman的DDH難解問題[11]（又稱Diffie?Hellman的判斷問題）：如果對任何概率多項式時間算法D，都不能區(qū)分和其中是一個隨機數(shù)。

定義1 偽隨機函數(shù)：設(shè)是偽隨機函數(shù)，如果對于每個概率多項式算法和有足夠大的，滿足：。

其中：是一個均勻分布的函數(shù)；是一個可忽略函數(shù)。表示對所有攻擊者可能取到的最大值。

定義2 單向函數(shù)：設(shè)是一個單向函數(shù)，則滿足：

任意給一個，求出很容易，即一定存在一個概率多項式算法，在多項式時間內(nèi)有：。

已知求出不可能的，即：如果對于任意的任何概率多項式算法都不能從得出即：其中是一個可忽略函數(shù)。

定理1 如果存在單向函數(shù)，則存在加密方案具有選擇密文攻擊下不可區(qū)分加密，以及存在消息鑒別碼具有選擇消息攻擊下不可偽造。

引理1 如果存在離散對數(shù)的偽隨機單向函數(shù)，那么滿足DDH難解問題。

1.2 密鑰交換原理及分析

Lin提出的增強算法是為了克服原始SAKA算法的不足。而根據(jù)文獻[10]的分析，Lin的算法仍然會受到密碼猜測攻擊。

通信雙方為A與B預(yù)先共享一個密碼系統(tǒng)參數(shù)是一個大素數(shù)，是有限域的一個本原元，和是公開的，通信雙方用指定方法從密碼得到和具體方法不做規(guī)定，要求與互質(zhì)，并且由不同的生成具有抗碰撞性。協(xié)議過程如下：

Step1： A選擇一個隨機整數(shù)并且發(fā)送給B：；

Step2： B選擇一個隨機整數(shù)并且發(fā)送給A：；

Step3：A計算共享密鑰，并計算

Step4：B計算共享密鑰并計算發(fā)給

Hsieh攻擊分析中，攻擊者可以在第（1）步中得到第（4）步中得到，然后進行如下的離線猜測攻擊：攻擊者首先猜測密碼并且得到和，然后通過驗證等式是否成立來離線猜測出和的正確性，使攻擊成功。

文獻[7]提出了E?SAKA協(xié)議，但存在離線猜測等弱點；文獻[8]提出了另一種改進協(xié)議，雖然能抵抗Hsieh分析，但不能抵抗E的假冒而進行猜測攻擊。

2 改進的SAKA協(xié)議算法

基于Diffie?Hellman算法、SAKA協(xié)議思想，通過兩次Diffie?Hellman算法生成一個臨時共享密鑰和一個雙方之間的會話密鑰，并進行雙向認證。生成的第一個共享密鑰稱為臨時輔助共享密鑰，產(chǎn)生的第二個共享密鑰稱為A與B之間的會話密鑰。

本協(xié)議共分為三個階段：

（1） 雙向認證因子注冊階段，其中雙向認證因子是實體A與B雙方共同具有的某一特性標(biāo)識，或者雙方都認可的某一特性標(biāo)識；

（2） 臨時輔助共享密鑰生成階段；

（3） 會話密鑰生成以及雙向認證與驗證階段。

2.1 雙向認證因子注冊階段

通過安全信道注冊一個雙方認可的雙向認證因子，用表示雙向認證因子，此因子是靜態(tài)的，且具有惟一性和認可性。注冊的雙向認證因子明文本身不參與認證與驗證，而是經(jīng)過一個單向函數(shù)[8]轉(zhuǎn)換成一個隨機數(shù)值參與認證與驗證。

2.2 臨時輔助共享密鑰生成階段

基于第一次用Diffie?Hellman協(xié)議生成本次臨時輔助共享密鑰，生成過程如下：

Step1： A選擇兩個隨機整數(shù)并且發(fā)送給；

Step2： B收到A發(fā)送的消息后，選擇兩個隨機整數(shù)，并且發(fā)送給A：

Step3： A收到B發(fā)送的消息后，判斷收到的與自己原有的是否相等，相等則計算和發(fā)送{}給否則，協(xié)議終止；

Step4： B收到Step2中A發(fā)來的{}，判斷收到的與自己原有的是否相等，相等則計算和。否則，協(xié)議終止。

說明：當(dāng)協(xié)議完成時，本階段臨時輔助共享密鑰生成成功，這時系統(tǒng)消除由于整數(shù)都是隨機選取，具有很好的隨機性，因此也具有很好的隨機性，而只是作為一個隨機數(shù)值參與到認證與驗證。而協(xié)議中的與只是作為保證A與B之間生成的臨時輔助共享密鑰相同而已，不會參與到后續(xù)協(xié)議的任何階段中。

2.3 會話密鑰生成以及雙向認證與驗證階段

由注冊與臨時輔助共享密鑰生成階段可知，與都已知，且是靜態(tài)，是動態(tài)隨機。在本階段還要求有一個單向函數(shù)，用表示。的主要作用是把靜態(tài)的雙向認證因子通過加入動態(tài)隨機的轉(zhuǎn)換為動態(tài)隨機的雙向認證因子，用表示動態(tài)隨機雙向認證因子，函數(shù)輸入值相同時輸出值也相同，輸入值不同時，具有抗碰撞性。這樣保證了A與B的雙向認證因子同步進行。分別表示實體A與B的身份。

協(xié)議系統(tǒng)參數(shù)是一個大素數(shù)，是有限域的一個本原元，和是公開的。具體實施協(xié)議過程如下：

Step1： A計算再計算同時計算生成且與互質(zhì)，并發(fā)送，給B；

Step2： B計算再計算同時計算生成且與互質(zhì)，并發(fā)送給

Step3： A計算和并發(fā)送給B；

Step4： B計算和并發(fā)送給A；

Step5： A計算相等，則A確認對方通信的是B，即A認證B成功，否則失?。?/p>

Step6： B計算相等，則B確認對方通信的是A，即B認證A成功，否則失敗。

當(dāng)且僅當(dāng)Step5和Step6同時成立時，則密鑰為雙方共享會話密鑰。

2.4 攻擊分析

由Hsieh分析可知，攻擊者（E）可能在第（1）與第（4）步可以得到與第（2）步與第（3）步得到與不可能得到。所以能抵抗由Hsieh方法分析。

E假冒B與A通信，進行猜測攻擊：

Step1： E得到。

Step2： E選擇自己的一個數(shù)計算 發(fā)給A。

Step3： A收到E發(fā)來的消息后，計算，由于是E自己選取，很容易計算得到然后計算比較等式，這樣E可以進行離線或在線猜測。一旦等式成立，則E攻擊成功。但是由函數(shù)動態(tài)得到的是一個隨機動態(tài)值，E不可能在線猜測成功，即使E能夠攻擊通信A或B得到靜態(tài)的但是得不到臨時輔助共享密鑰生成階段生成的（要得到就必須解離散對數(shù)），所以E不可能猜測得到故該協(xié)議能抵抗在線或離線猜測。

2.5 全安性分析

本文提出改進的SAKA算法的安全性主要依賴于離散對數(shù)困難問題，同時還充分利用了隨機性以及單向函數(shù)的安全性。其安全性具體分析如下：

（1） 無論是生成的臨時輔助共享密鑰還是后面生成的雙方共享會話密鑰都依賴于離散對數(shù)困難問題，攻擊者不可能得到這兩次密鑰。

（2） 雖然攻擊者在臨時輔助共享密鑰生成階段可以冒充A或B，生成一個替換臨時輔助共享密鑰但是攻擊者沒有雙向認證因子以及轉(zhuǎn)換后的動態(tài)隨機雙向認證因子則無法生成與從而有效地防止攻擊者的冒充攻擊和中間人攻擊。

（3） 如果攻擊者攻擊靜態(tài)的雙向認證因子即使得到了但也無法得到創(chuàng)新性分析說明了E無法猜測得到。

（4） 由于是動態(tài)隨機的，所以生成的都是動態(tài)隨機的，這就有效阻止了對在線或離線猜測攻擊。

（5） 由于是動態(tài)隨機新鮮的，則都具有動態(tài)隨機新鮮性，所以本協(xié)議能夠保證前向的安全性。

3 安全性證明

本節(jié)給出所提協(xié)議的安全性證明，主要從協(xié)議的后兩個階段（臨時輔助共享密鑰生成階段、會話密鑰生成及雙向認證與驗證階段）證明其安全性。

首先證明第二階段的安全性：

第二階段：由改進協(xié)議第二階段可知，其安全性主要是基于Diffie?Hellman算法的安全，而對于實體A與B所選取的隨機數(shù)在此階段中只是判斷A與B在本階段協(xié)議完成之后，是否共享密鑰的臨時作用。對協(xié)議安全沒有決定性作用。所以，本階段的改進協(xié)議滿足Diffie?Hellman的難解問題DDH，故攻擊者要想得到是不可能的。

然后證明第三階段的安全性：

第三階段：由改進協(xié)議的第三階段可知，協(xié)議的安全也是基于Diffie?Hellman難解問題，只要滿足了Diffie?Hellman協(xié)議算法的要求即可，所以主要是證明雙向認證動態(tài)因子是否滿足真正偽隨機，且已知是偽隨機的，是單向函數(shù)。

不妨設(shè)事件分別為：表示是偽隨機的，由定義1得：

表示是單向函數(shù)，由定義2得：

由于可知，事件是由事件同時發(fā)生才發(fā)生的，如果令表示事件則事件可表示為：。由此可知：

由于與是兩個獨立事件，因為是偽隨機與是單向函數(shù)是相互獨立的，所以由式（3）得到：

由式（1）～式（4）得到：即由此可見，對于每個概率多項式算法和有足夠大的存在一個單向函數(shù)使得事件

滿足：所以是一個真正偽隨機數(shù)。由定理1可知具有抗選擇密文攻擊下不可區(qū)分，不可偽造等安全性。同理可證也是真正偽隨機數(shù)，滿足定理1。

由此可以得到是真正偽隨機數(shù)。從改進協(xié)議第三階段得到，通信實體A與B相互之間在網(wǎng)上傳輸與。由引理1可知，這些網(wǎng)上傳輸?shù)南M足DDH難解問題。

由兩階段的安全性證明可知，本文提出的協(xié)議安全性是基于DDH困難性假設(shè)的，也就是說如果DDH是困難的，則該協(xié)議在標(biāo)準(zhǔn)模型下是安全的。

4 結(jié) 論

本文研究隨機密鑰協(xié)商協(xié)議的可證明安全問題。首先分析密鑰協(xié)商協(xié)議的相關(guān)算法，基于Diffie?Hellman協(xié)議提出隨機密鑰協(xié)商協(xié)議。該協(xié)議解決了SAKA及其改進協(xié)議的一些缺陷， 繼承了SAKA及其改進協(xié)議的優(yōu)點，并能抵抗猜測攻擊；在協(xié)議中，應(yīng)用動態(tài)雙向認證因子認證方法和非時間同步技術(shù)，使得該協(xié)議適合OTP動態(tài)口令系統(tǒng)設(shè)計，從而解決了Diffie?Hellman協(xié)議算法以及它的改進協(xié)議SAKA，E?SAKA等算法的動態(tài)認證問題，解決了協(xié)商雙方的時間非一致性問題。

參考文獻

[1] DIFFIE W， HELLMAN M E. New directions in cryptography [J]. IEEE transactions on information theory， 1976， 22（6）： 644?654.

[2] SEO D， SWEENEY P. Simple authenticated key agreement algorithm [J]. Electronics， 1999， 35（13）： 1073?1074.

[3] 王圣寶，曹珍富，董曉蕾.標(biāo)準(zhǔn)模型下可證安全的身份基認證密鑰協(xié)商協(xié)議[J].計算機學(xué)報，2007，30（10）：1842?1852.

[4] 任勇軍，王建東，王箭，等.標(biāo)準(zhǔn)模型下基于身份的認證密鑰協(xié)商協(xié)議[J].計算機研究與發(fā)展，2010（9）：1604?1610.

[5] JIANG Qi， MA Jianfeng， LU Xiang， et al. An efficient two?factor user authentication scheme with unlinkability for wireless sensor networks [J]. Peer?to?peer networking and applications， 2015， 8（6）： 1070?1081.

[6] 任艷麗，谷大武.公鑰密碼方案的可證明安全性注記[J].計算機應(yīng)用研究，2008，25（4）：1130?1133.

[7] 楊炤璐，范磊，李建華.E?SAKA密鑰協(xié)商算法[J].通信技術(shù)，2003（3）：85?86.

[8] 李亞敏，李小鵬，吳果.身份認證的密鑰交換算法[J].計算機工程，2006，32（12）：171?172.

[9] BONEH D. The decision Diffie?Hellman problem [C]// Proceedings of 1998 the Third Algorithmic Number Theory Symposium. Berlin： Springer， 1998： 48?63.

[10] HSIEH B T， SUN H M， HWANG T. Cryptanalysis of enhancement for simple authentication key agreememt algorithm [J]. Electronics letters， 2002， 38（1）： 20?21.

[11] 德爾夫斯，克內(nèi)貝爾.密碼學(xué)導(dǎo)引：原理與應(yīng)用[M].肖國鎮(zhèn)，張寧，譯.北京：清華大學(xué)出版社，2008.