基于混沌映射的HMAC算法設計與分析

李慧佳，龍 敏

長沙理工大學 計算機與通信工程學院，長沙 410114

1 引言

消息認證碼（Message Authentication Code，MAC）是保證數(shù)據(jù)完整性的基本算法，被廣泛應用于金融、商業(yè)系統(tǒng)等各種安全系統(tǒng)中。MAC算法能夠避免攻擊者通過偽造、重放、篡改、亂序等手段來改變數(shù)據(jù)，而且能驗證報文發(fā)送者和接收者的真實性以及報文的完整性。目前，有多種用于構造MAC算法的方法，除了基于分組密碼設計的CBC-MAC、TBC-MAC、XOR-MAC外，采用帶密鑰的散列函數(shù)也常用于設計MAC，其中具有代表性的是M.Bellare等人于1996年提出的HMAC算法[1]，被廣泛使用于各種網(wǎng)絡協(xié)議以及身份認證系統(tǒng)中，并已經(jīng)取代RFC1828成為了IPSec協(xié)議中的認證算法[2]。

一直以來，散列函數(shù)是現(xiàn)代密碼學中重要的組成部分，優(yōu)良的單向性能使得它在保密通信中倍受青睞，是確保許多密碼協(xié)議和密碼算法安全的前提條件。然而，在2004年美密會上，我國的學者王小云等宣布了經(jīng)典散列函數(shù)MD4、MD5、SHA-1的成功“碰撞”[3]，由它們構造的HMAC算法也被證實存在偽造攻擊和部分密鑰恢復攻擊[4]的可能性；基于39步SHA-256函數(shù)的LPMAC算法以及秘密前綴MAC算法也因為能夠成功找到特殊

CNKI網(wǎng)絡優(yōu)先出版：2014-04-01,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1311-0176.html的差分路線使得SHA-256算法出現(xiàn)了碰撞[5]證實基于SHA-256的MAC算法易遭受區(qū)分攻擊。

除了上述基于傳統(tǒng)散列函數(shù)的HMAC算法外，還存在不同hash種類形式的HMAC算法，如基于三維Rossler系統(tǒng)的增強型HMAC[6]、采用SHA256與HMAC相結合的優(yōu)化方案[7]等等，這些算法采用結構不一的壓縮函數(shù)，外加一系列簡單的邏輯運算及數(shù)學運算來獲得最終的MAC值。然而由于壓縮函數(shù)的構造不嚴謹以及部分細節(jié)處理不當，HMAC算法仍舊存在被攻破的可能。如文獻[8]中，作者針對一種塊分組結構的hash函數(shù)作出安全性分析，由于該壓縮函數(shù)在生日攻擊下僅需要216.5計算復雜度就能夠找到一個碰撞對，使得輸出的MAC值相同，攻擊者可以通過密鑰恢復攻擊或者區(qū)分攻擊來獲得其想要的認證消息。

因此，用于構造HMAC的單向Hash函數(shù)的安全性至關重要，本文將融入混沌映射設計單向Hash函數(shù)，以提高HMAC算法的防偽造攻擊能力。

2HMAC算法及攻擊分析

2.1HMAC算法描述

HMAC是消息和密鑰的公開hash函數(shù)，它要求所使用的hash函數(shù)具備迭代結構，反復使用壓縮函數(shù)將任意長度的消息映射為定長的短消息。設h是嵌入的hash函數(shù)，m是輸入HMAC的消息，b是消息m分塊后每一塊的比特長度，K是密鑰，若長度小于b則在K末尾用0填充至b比特長，記為K+；若K長度大于b則K+=h(K)，ipad和opad是HMAC兩個固定的長度為b的參數(shù)，分別是x36、x5C（十六進制）重復b/8的結果，HMAC算法描述如下[9]：

HMACk(m)=h(IV,(K+⊕opad)||h(IV,(K+ipad)||m))（1）

HMAC算法的構造流程圖如圖1所示。

圖1HMAC算法流程圖

其中IV是hash迭代函數(shù)的固定初始值，n為hash函數(shù)輸出的hash值長度。HMAC算法步驟闡述如下：

步驟1在字長為b的密鑰K+與ipad做異或運算，并將結果字符串填充于消息m的數(shù)據(jù)流中。

步驟2用hash函數(shù)作用于上一步生成的數(shù)據(jù)流。

步驟3將密鑰K+再與opad做異或運算，結果填充至第一輪hash后的比特流中。

步驟4再調(diào)用hash函數(shù)作用于上一步的比特流，輸出最終的MAC值。

概括來說，HMAC算法是由一組固定參數(shù)與明文消息m經(jīng)簡單處理（填充、異或）后在壓縮函數(shù)F的多輪迭代作用下生成MAC值。據(jù)此HMAC算法結構還可以迭代狀如圖2展現(xiàn)出來。

圖2HMAC的迭代狀結構

圖中，壓縮函數(shù)F在處理明文時是分塊獨立進行壓縮處理，故hash函數(shù)的初始向量IV、固定參數(shù)ipad、opad可看作壓縮函數(shù)F進行第一輪壓縮處理的輸入值，即Kin=F(IV,K+⊕ipad)，Kout=F(IV,K+⊕opad)。

2.2 攻擊實例及原因分析

攻擊實例：由于各參數(shù)未知且固定，明文消息是公開的，從Kin，Kout計算式子可知，Kin和Kout的值雖是未知但卻是固定的，因而第一輪hash后輸出的值是一固定常數(shù)，顯然在處理消息明文塊時其鏈接變量是通過hash一個固定常數(shù)而得，攻擊者可以利用這一固定常數(shù)偽造一個新消息的MAC值并且通過合法驗證。假設攻擊者通過隨機選擇消息得到消息M1=m1‖m2‖m3…‖mn，M2=m′1‖m′2‖m′3…‖m′n，并且獲得兩者的MAC值滿足相等關系，即H1=HMAC(Kin,Kout,M1)=HMAC(Kin,Kout,M2)=H2；攻擊者再獲得一組消息M3=m1‖m2‖…‖mn‖mn+1‖…‖mr的MAC值為H3=HMAC(Kin,Kout,M3)，則攻擊者可以成功偽造消息值也為H3，其中n、r都為正整數(shù)。

攻擊原因分析：由于HMAC算法中密鑰K未知且固定，固定參數(shù)ipad、opad為兩個不相等的常數(shù)，在壓縮迭代處理不同明文消息塊的情況下，使用的初始向量及常態(tài)參數(shù)相同，且Kin和Kout值不變，則易發(fā)生上述存在性偽造攻擊。此外，上述攻擊實例是基于找到兩個不同消息的MAC值相同的假設條件下進行驗證的，而根據(jù)生日攻擊原理[10]，找到一對消息M≠M′滿足MAC(M)=MAC(M′)所需要的計算復雜度大約為其中n為MAC值的長度，即上述攻擊實例能夠成功實施攻擊需要的計算復雜度約為，這個數(shù)值遠低于帶密鑰hash函數(shù)的安全攻擊復雜度下限O(2n)，故而上述的假設條件是成立的。

3 一種基于混沌映射HMAC算法的構造

3.1 隨機序列發(fā)生器的構造

算法使用Logistic映射和Chebyshev映射兩個混沌系統(tǒng)構造隨機序列發(fā)生器。Logistic映射定義為[11]：

當xn∈(0,1)，r∈(3.569 9…,4]時，系統(tǒng)處于混沌狀態(tài)。Chebyshev映射定義為[12]：

其中yn∈[-1,1]，k為Chebyshev映射的階數(shù)，當k＞2時李雅普諾夫指數(shù)λ=lnk＞0，即系統(tǒng)處于混沌狀態(tài)。

為了抵御偽造消息等攻擊，本文采用一個混沌序列發(fā)生器來動態(tài)生成HMAC算法中的參數(shù)ipad和opad，在處理不同的消息時，使得用戶使用的參數(shù)也不同，從而防止攻擊者采用相等MAC值的兩組消息試圖偽造新消息來獲得驗證的通過。該混沌序列發(fā)生器由四部分組成：邏輯函數(shù)G、Logistic映射、Chebyshev映射以及線性反饋移位寄存器。其總體結構如圖3所示。

圖3 混沌序列發(fā)生器的構成

圖中，明文消息和密鑰分別經(jīng)過由一系列邏輯運算組成的邏輯函數(shù)G處理之后左右輸出兩組實數(shù){μ,x0}、{k,y0}，分別作為混沌映射的控制參數(shù)以及迭代初始值；兩組數(shù)據(jù)分別驅動混沌映射進行迭代，并將迭代次數(shù)加1次后的值反饋到下一輪迭代開始前，與相應的參數(shù)做關聯(lián)處理后再進行迭代操作；同時分別輸出兩組混沌映射的末尾4組迭代值，兩者異或后作為線性移位反饋寄存器的初始狀態(tài)值；此外再獲得Logistic映射的迭代次數(shù)加1~5次的4組迭代值（共128 bit），從中分別抽取兩組5bit二進制并轉換成兩個十進制數(shù)，作為LFSR的移位控制參數(shù)來控制初始序列的循環(huán)移位；LFSR經(jīng)過兩路循環(huán)移位后輸出兩組128 bit序列，即為HMAC參數(shù)ipad和opad的值。

邏輯函數(shù)G是一組由循環(huán)移位、按位異或、取反、按位與、或等操作混合運算實現(xiàn)的擴散機制。它能夠有效將明文消息塊變化數(shù)最大可能擴散影響，使得明文初始條件產(chǎn)生微小變化的情況下引發(fā)該狀態(tài)變量內(nèi)部的動態(tài)強差分擴散，增強混沌序列發(fā)生器初值敏感性能。邏輯函數(shù)G的構造如圖4所示。

圖4 邏輯函數(shù)G的結構

將一組明文消息塊Mt按照一定方式進行分組后(P1,P2,P3,P4)兩兩異或再分別進行四次循環(huán)移位，其中si=(i+14)mod4+5*i，zi=(i+12)mod4+6*i，且i=1,2,3,4；再次異或后每組128 bit分組輸出四輪32 bit的序列（Ai,Bi,Ci,Di），輸入fi函數(shù)中結合密鑰K進行邏輯操作的混合運算。fi函數(shù)表述如下：

混合運算后，fi函數(shù)的四組輸出再經(jīng)移位、異或等處理后分別輸出四組數(shù)據(jù)，即為兩個混沌映射的控制參數(shù)初值和初始迭代初值。

3.2 基于混沌映射的HMAC算法描述

本文所設計的HMAC算法采用上述隨機序列發(fā)生器來將明文消息轉化成為定長的數(shù)據(jù)流，通過一系列邏輯運算與混沌映射相結合達到消息擴散最大化，明文消息與數(shù)據(jù)流產(chǎn)生不可逆轉的關聯(lián)以防止攻擊者有可乘之機。本文提出的HMAC算法參數(shù)生成步驟描述如下：

步驟1消息分塊與填充。將任意長度的明文消息M分割成128 bit的消息塊M1,…,Mi…,Ms，并將消息長度嵌入到填充消息中，消息長度為128 bit的整數(shù)倍，填充后的消息形式表示為M′=100…length(M)M10…0。

步驟3混沌迭代。將上一步驟獲得的各個參數(shù)值對應輸入兩個混沌映射中進行迭代，取x0，y0數(shù)值的低十位和低十五位數(shù)字組成兩個十進制數(shù)I,J，迭代次數(shù)定義為：N=230+(IorJ)+i，i為消息塊數(shù)目。

步驟4截取和移位。消息塊迭代N次后，輸出兩個映射迭代值的最末尾四個數(shù)，截取兩串128 bit二進制流，逐位異或后獲得線性移位反饋寄存器的初始狀態(tài)值SIV；取兩映射的N+1次迭代值反饋到下一輪消息塊處理，并與原混沌映射初始值相乘獲得新初始值繼續(xù)參與下一輪迭代。

步驟5重復混沌迭代過程直到處理完最后一組消息塊，最后從N+2~N+5次logistic映射迭代開始輸出系統(tǒng)當前4個值X′1,X′2,…,X′4，截取128 bit二進制序列后從中抽取出10位組成兩個十進制數(shù)（每5位一個數(shù)）Or，Oe作為控制LFSR的初始狀態(tài)值SIV循環(huán)移位的比特數(shù)，最終獲得兩串移位后的128 bit序列，即分別為HMAC參數(shù)ipad和opad的序列值。

3.3 算法性能分析

3.3.1 初值敏感性分析

原有的HMAC算法由于其內(nèi)在參數(shù)的固定存在被攻破的風險，本文提出的改進算法采用了相關混沌理論生成動態(tài)可變的參數(shù)為HMAC算法提供了安全保障。由于HMAC應用時明文消息與最終認證碼是公開的，攻擊者一般通過大量觀察和統(tǒng)計兩者之間存在的關聯(lián)來施以攻擊手段，若明文消息的微小變化能夠引起認證碼翻天覆地的改變，則攻擊者無的放矢，無疑能夠保證認證的安全性。

取一段初始明文文本1“Cryptography is the study of mathematical techniques related to aspects of information security such asconfidentiality，data integrity，entity authentication，and data origin authentication，and data origin authentication.”做仿真實驗，設密鑰（十六進制表示）K="FC50ADB815BF2C00ADF379EEA046BC2E"，以明文文本1和密鑰混合擴散后映射到混沌的參數(shù)空間，經(jīng)過混沌序列發(fā)生器后獲得兩串128 bit二進制流。

改變初始明文文本，使得文本發(fā)生微小變化以測試混沌系統(tǒng)的初值敏感性能，采用下述幾種情況來測試系統(tǒng)結果：

情況1：將文本1的首字母C改為B；

情況2：將文本1中的data origin改為data origim；

情況3：將文本1中entity authentication改為entity authentications；

情況4：刪除文本1中最后一個字符“.”；

情況5：將密鑰K的首字符F改為E；

將各個改變后的文本逐個經(jīng)過混沌序列發(fā)生器后生成序列結果如下所示（用十六進制表示）。

理想狀態(tài)下的混沌加密函數(shù)在初值的微小擾動情況下產(chǎn)生的結果能夠以每比特50%的概率產(chǎn)生變化。與初始文本1的ipad和opad值相比，上述五種不同條件下生成ipad和opad結果的變化比特數(shù)分別為：（61，61）、（64，68）、（63，65）、（65，63）、（74，68），每一個變化比特數(shù)都接近于128-bit的50%，這說明混沌序列發(fā)生器對初值的變化非常敏感，混沌映射的初值敏感特性得到了充分的體現(xiàn)。

3.3.2 統(tǒng)計性能分析

本文提出的HMAC算法以混沌映射方式生成HMAC的參數(shù)，整個過程可看作是一次數(shù)據(jù)加密過程，文獻[13]提出采用混亂與擴散兩個標準來衡量一個加密算法的安全性能，加密體制中要求明文在密文空間中呈現(xiàn)充分的擴散與混亂，明文一比特變化須盡可能影響密文空間的所有比特位?；靵y與擴散性能分析可通過以下幾組定義來實現(xiàn)：

定義P的均方差為：

測試方法：隨機選取一段明文進行加密，得到相應的結果序列，然后改變明文1 bit的值進行加密得到另一個序列結果，比較兩個結果得到變化比特數(shù)Bi。令測試次數(shù)N=256,512,1 024,2 048,4 096，測試結果如表1所示，圖5為N=4 096時結果序列的置亂數(shù)分布情況。圖中，平均變化比特數(shù)-B和平均變化概率P都趨近于理想狀況下的64 bit和50%，4096次測試的變化比特數(shù)介于40到83之間，波動較小。因此，基于混沌映射的HMAC算法能夠產(chǎn)生對初值非常敏感的動態(tài)參數(shù)值，且保障了參數(shù)選取所屬的參數(shù)空間值充分均勻，均方差ΔB和ΔP都很小，保證了混亂與擴散程度聚集在一個平均穩(wěn)定的水平上。

表1 基于混沌映射HMAC算法的統(tǒng)計性能分析

圖5 測試次數(shù)為4 096的置亂分布圖

3.3.3 抗碰撞性能分析

HMAC算法屬于一種基于帶密鑰的hash函數(shù)，其安全性高度依賴于hash函數(shù)的安全性，而hash函數(shù)潛在的可能性安全隱患一般在于hash函數(shù)內(nèi)部出現(xiàn)碰撞。本文通過統(tǒng)計相同位置上hash值對應的ASCII值相同的數(shù)目分布來測試HMAC改進算法的抗碰撞性能（如圖6所示）。

針對本文的改進算法采用以下實驗來定量測試其抗碰撞能力：隨機選取一段明文生成128比特ipad和opad結果，用ASCII碼的形式存儲；然后隨機選擇改變該明文中1 bit的值得到另一組新的結果，比較兩組結果，統(tǒng)計在相同位置上ASCII碼值相同的數(shù)的情況。以ipad結果為例，經(jīng)過4 096次測試，相同位置上出現(xiàn)相同ASCII碼值的碰撞次數(shù)如圖6所示。由圖可知，在4 096次測試中，3 850次沒有發(fā)生碰撞，240次發(fā)生了一次碰撞，僅僅6次發(fā)生了二次碰撞，碰撞程度非常低，攻擊者找到碰撞對的概率微乎其微。

圖6 相同位置ASCII值相同的數(shù)目分布

3.3.4 抗存在性偽造攻擊分析

4HMAC的安全性要求

HMAC算法主要由密鑰與hash函數(shù)相結合而成，即修正了迭代hash函數(shù)固有缺陷，也充分考慮到了不同攻擊模型的攻擊代價；由于離線攻擊比在線攻擊更易于完成，在構造HMAC時特別在二次hash運算中使用密鑰，以此加強對離線攻擊的抵御能力。盡管如此，HMAC安全性除了高度依賴于參數(shù)ipad和opad的取值以外，還與嵌入的hash函數(shù)安全性以及密鑰的安全性相關聯(lián)。

目前針對HMAC算法提出的攻擊實例基本都是由于嵌入的hash函數(shù)內(nèi)部結構發(fā)生碰撞而導致的[7-8，11]，其主要攻擊方式為碰撞攻擊，攻擊強度取決于hash函數(shù)的hash值以及密鑰的長度。文獻[14]指出，消息的散列值長度n應不小于128比特，使得找到一對消息m≠m′滿足h(m)=h(m′)所需要的計算復雜度約為，可以防止生日攻擊。對于任意一種MAC算法，存在一個無可避免的缺陷，即算法認證過程中，即使在密鑰未知的情況下，通過隨機選擇消息反復測試，總能找到一個明文消息對應的偽MAC值，并能通過驗證，其中找到該偽MAC值的概率為(1/2)n[15]。因此在HMAC算法中，若要對hash函數(shù)輸出值進行截短處理，則截取的MAC值長度應不小于hash輸出值長度的一半，以此來減小MAC算法自身不足帶來的危害。

除此之外，恢復密鑰也是攻擊HMAC算法的主要手段。由于密鑰是私有的，在不考慮持有方泄露的情況下，密鑰的安全性依賴于密鑰的長度和隨機性。對于長度為K比特的密鑰，實施強力攻擊需要2K次操作即可恢復密鑰，在現(xiàn)有計算機計算強度前提下，為了防止密鑰窮盡搜索攻擊，要求密鑰的長度不能小于128比特，且不小于hash函數(shù)輸出值的長度，而大于hash值長度的密鑰雖然可以使用，但額外的長度并不能顯著提高HMAC算法的安全性，因此推薦使用密鑰長度等于hash值長度的密鑰[15]。此外，密鑰起源函數(shù)必須是偽隨機的，并且要周期性的更新，以此保證密鑰的安全性。

除上述分析以外，要確保HMAC算法的安全性還須滿足以下幾個基本要求：如（1）hash函數(shù)須滿足本身幾點特性，如單向性、弱抗碰撞性以及良好的雪崩效應等；（2）hash散列值呈均勻分布，以抵御統(tǒng)計分析；（3）攻擊者已知消息m和MAC值C(m)情況下，構造滿足C(m1)=C(m)的消息m1在計算上不可行。

5 結束語

HMAC算法在消息認證方面有著重要而廣泛的應用，本文在提出該算法存在固有缺陷的基礎上，分析了該缺陷致使HMAC存在存在性偽造攻擊，并予以實例證明；同時提出一種基于混沌映射的HMAC算法方案，該方案采用混沌Logistic映射和Chebyshev映射相結合組成一個混沌序列發(fā)生器，通過循環(huán)移位、邏輯異或、取反等來完成拉伸和折疊操作，實現(xiàn)了消息明文生成HMAC動態(tài)參數(shù)的目的。實驗與分析結果表明，本文的改進方案有著良好的混亂與擴散性能，且碰撞程度非常低，消息明文的微小改變能產(chǎn)生極為不同的參數(shù)結果，故采用此方案來動態(tài)生成HMAC算法的固定參數(shù)ipad和opad能夠有效防御因HMAC算法的參數(shù)ipad和opad是常態(tài)參數(shù)而造成的偽造攻擊。最后針對目前HMAC算法構造存在的攻擊模式提出了安全性要求，及其嵌入的hash函數(shù)需滿足的安全性條件。

[1]Bellare M，Canetti R，Krawczyk H.Keying hash function for message authentication[J].Advances in Cryptology，1996，1109：1-15.

[2]Khan E，EI-Kharashi M W，Gebali F，et al.Design and performance analysis of a unified，reconfigurable HMACHash unit[J].IEEE Trans，2007，45（12）：2683-2695.

[3]Wang X Y，F(xiàn)eng D G，Lai X J，et al.Collisions for hash functions MD4，MD5，HAVAL-128，and RIPEMD[C]//Advances in Cryptology-CRYPTO 2004；The 24rd Annual International Cryptology Conference.Berlin：Springer-Verlag，2004.

[4]Contini S，Yin Yiqun Lisa.Forgery and partial key-recovery attacks on HMAC and NMAC using Hash collisions[J].ASIACRYPT 2006，LNCS 4284，2006：37-53.

[5]Yu Hongbo，Wang Xiaoyun.Distinguishing attack on the secret-prefix MAC based on the 39-Step SHA-256[C]//ACISP 2009.Berlin Heidelberg：Springer-Verlag，2009，5594：185-201.

[6]Idris S，Zorkta H，Khawatmi S，et al.Enhanced HMAC based upon 3-D rossler system[J].IEEE Computer Society，2009.

[7]須磊.HMAC-SHA256算法的優(yōu)化設計[J].價值工程，2012，29（2）：202-204.

[8]Yuan Zheng，Ren Xiaoqiu，Liu Jintao.Distinguishing attacks on MAC/HMAC based on a new dedicated compression function framework[J].International Association for Cryptologic Research，2010：2-5.

[9]于廣威，何文才.基于HMAC的加密狗設計[J].信息安全與通信保密，2011，11（3）：68-72.

[10]鄭世慧，張國艷，楊義先，等.基于混沌的帶密鑰散列函數(shù)安全分析[J].通信學報，2011，32（5）：146-152.

[11]李進，徐紅.基于MD5算法和Logistic映射的圖像加密方法研究[J].信息網(wǎng)絡安全，2011，8（9）：25-47.

[12]鄧紹紅，黃桂超，陳志建，等.基于混沌映射的自適應圖像加密算法[J].計算機應用，2011，31（6）：1502-1511.

[13]Kanso A，Yahyaoui H，Almulla M.Keyed hash function based on a map[J].Information Sciences，2012，186（2）：249-264.

[14]Bakhtiari S，Safavi-Naini R，Pieprzyk J.Keyed Hash Functions[R].Department of Computer Science，University of Wollongong，NSW 2522.

[15]Evans D L，Bond P J，Bement A L.The keyed-Hash message authentication Code（HMAC）[J].Federal Information Processing Standards Publication，2002.