改進的經(jīng)典信道消息完整性認(rèn)證方法

周瑞瑞 張 博 魚 冰

（國家知識產(chǎn)權(quán)局專利局專利審查協(xié)作河南中心，河南 鄭州 450000）

在信息安全領(lǐng)域，基于CRC的MAC［1］是一種已經(jīng)證明了的具有信息論安全的消息認(rèn)證碼，其滿足了通信過程中對所需要的認(rèn)證機制的安全性要求。該體制先將認(rèn)證的消息用通用哈希函數(shù)作用得到其散列值，然后用一次一密密鑰填充散列值作為MAC與認(rèn)證的消息一起發(fā)送給接收方。

經(jīng)典的基于循環(huán)校驗碼CRC的認(rèn)證方案如圖1所示，接收者收到信道中傳過來的消息以后，首先提取原始消息比特串M以及附加在后面的n位MAC值，并根據(jù)手中事先共享的p（x）和K計算M的MAC值與所接收到的MAC值進行對比，如果二者相同，則認(rèn)證成功，否則認(rèn)為認(rèn)證失敗。這里的認(rèn)證是一個雙重認(rèn)證，一方面，通過MAC值能夠檢驗消息在傳輸過程中是否被篡改，達到了消息完整性認(rèn)證的目的；另一方面，由于所使用到的p（x）和K是由通信雙方事先共享的，因此只有合法的發(fā)送方才知道其值，并計算得到MAC，從而完成對消息發(fā)送者的身份認(rèn)證。

圖1 基于循環(huán)校驗碼CRC的認(rèn)證方案

1 基于CRC的認(rèn)證方案安全性分析

對任意值m和n＞1，設(shè)h（·）是雜湊函數(shù)，c（x）是其所有可能余式多項式的集合，p（x）是函數(shù)中使用的不可約多項式，則在基于CRC的MAC中h（M（x））=c?M（x）·xnmod p（x）=c（x），當(dāng)且僅當(dāng)p（x）除盡M（x）·xn-c（x），該式的次數(shù)最高為m+n次，p（x）的次數(shù)是n，所以該式最多可分解成（m+n）/n個n次不可約多項式。此時有（m+n）/n個p（x）的選擇會產(chǎn)生碰撞，而p（x）的總數(shù)不會超過2n-1/n。所以碰撞概率是（m+n/n）/=（2n-1/n）=（m+n）/（2n-1），在未獲取MAC密鑰的情況下，攻擊者偽造MAC的概率最多是（m+n）/（2n-1），當(dāng)n的值足夠大時，這個概率幾乎為0，因此，該認(rèn)證方案具有無條件安全性。

以上考慮的認(rèn)證方案適用于理想的、沒有噪聲的經(jīng)典信道，不考慮噪聲的干擾。而實際應(yīng)用中，例如衛(wèi)星通信系統(tǒng)等，由于系統(tǒng)自身的原因，信道中通常都不可避免地有一定的噪聲干擾存在，從而導(dǎo)致接收方收到的消息比特串中存在一定比率的錯誤。而對于認(rèn)證方案中使用的CRC-based消息認(rèn)證體制而言，1比特的消息錯誤都可以被無限放大，從而導(dǎo)致認(rèn)證失敗，這是由其所使用的雜湊函數(shù)的性質(zhì)決定的。

2 改進的完整性認(rèn)證方案

本文提出了一種改進的消息完整性認(rèn)證方案，在原始數(shù)據(jù)串和相應(yīng)的MAC值發(fā)送之前，為了防止集中攻擊，將MAC插入原始消息串的特定位置，為了防止噪聲的干擾導(dǎo)致認(rèn)證失敗，對所要發(fā)送的原始數(shù)據(jù)比特串進行糾錯碼編碼，然后使編碼后的消息在信道中傳輸以抵抗信道噪聲。接收方通過解碼獲得原始的消息比特串和對應(yīng)的MAC值，進而進行消息完整性認(rèn)證。

圖2 采用隨機置換的糾錯編碼方案

在通信雙方的交互過程中，MAC值是需要重點保護的數(shù)據(jù)。經(jīng)典的MAC值認(rèn)證方案中常常將MAC值以前置或尾隨的方式與原始消息一起發(fā)送到接收方［2-4］。攻擊者可以輕易地針對MAC值的放置方式對其進行提取，并進行集中攻擊。為了防止攻擊者集中對MAC進行攻擊，發(fā)送方在計算出消息的MAC值后，將MAC插入到原始消息串的特定位置中。其插入的位置由發(fā)送方（Alice）和接收方（Bob）事先共享的密鑰決定，這個密鑰是可以重復(fù)使用的。然后Alice對整個數(shù)據(jù)串進行級聯(lián)糾錯編碼。編碼后的碼字可以抵抗敵手對某部分?jǐn)?shù)據(jù)的竊聽引入的錯誤，其編碼過程圖2所示。

在消息傳輸過程中，攻擊者會對部分信息竊聽，從而引入類似噪聲的錯誤。這類錯誤通常較集中，通過單輪糾錯碼糾錯后，仍然存在譯碼錯誤，所以往往不能將整個比特序列的誤碼率降到一個可以接受的水平。本文通過在容錯編碼中加入隨機置換，以防止攻擊者選定某些信息的編碼塊來進行破壞。

發(fā)送方對消息進行指定輪數(shù)的糾錯編碼，每一輪編碼之前都對所要編碼的消息進行隨機置換，采用“置換→編碼”的方式將錯誤均勻地分散到每一個分組塊中。接收方收到碼字后，反過來按照“譯碼→置換”的方式進行多層譯碼，從而恢復(fù)原始的消息和對應(yīng)的MAC值。多層級聯(lián)的構(gòu)造能夠大大提高所能容忍的錯誤率上限。

在糾錯編碼中，數(shù)據(jù)串被分為長度相等的多個分組。為了保證隨機置換的均勻性，應(yīng)盡量使得每個分組內(nèi)各比特經(jīng)置換操作后均勻分散在下一輪不同組中，將各組的比特逐一依次取出排列，從而使得分組后每個分組內(nèi)各比特經(jīng)置換操作后均勻分散在分組后的序列中。

糾錯編碼包括多輪編碼，各輪糾錯前均需要做隨機置換。將長度為m*n的數(shù)據(jù)串分為長度為n的m組，則第i輪隨機置換可采用如下所示：

實際的隨機置換可以有很多種，為了保證置換的均勻性，可使得每輪糾錯編碼前使用的隨機置換均不同，使用的置換方法由通信雙方的密鑰決定。對于正常消息的誤碼率，經(jīng)過事先約定的糾錯輪數(shù)后，糾錯后的密鑰存在錯誤的概率很小。如果接收方發(fā)現(xiàn)經(jīng)過事先約定的糾錯輪后誤碼率仍然不可忽略，則需通知發(fā)送方誤碼率過大，重新開始一輪數(shù)據(jù)傳輸。級聯(lián)糾錯方案之所以能將誤碼率降到一個任意小量，是因為每級糾錯后誤碼率都會有所下降，這就需要選擇糾錯能力足夠強的糾錯碼，以抵抗因敵手攻擊而引入較大的誤碼率。

接收方在獲取信道傳輸?shù)臄?shù)據(jù)后，首先對收到的數(shù)據(jù)進行相應(yīng)級數(shù)的譯碼，譯碼后按照約定的位置提取出MAC，對剩余的數(shù)據(jù)進行逆置換，恢復(fù)出原始消息比特串；計算所恢復(fù)出的消息比特串的MAC，和提取出的MAC進行對比，以驗證消息在傳送的過程是否被篡改。其過程如圖3所示。

圖3 采用隨機置換的譯碼和驗證方案

3 結(jié)語

本文提出改進的消息完整性認(rèn)證方案，將消息認(rèn)證碼以隨機插入的方式融入原始消息比特串中，避免了攻擊者截獲信道中的消息對消息認(rèn)證碼進行集中攻擊。采用隨機置換結(jié)合容錯編碼的方式，在每一輪糾錯編碼前都進行了隨機置換，將消息傳輸過程中的錯誤均勻地分布于整個消息比特串中，提高了所能容忍錯誤率的上限，保證了認(rèn)證的安全性和有效性。

［1］Menezes.應(yīng)用密碼學(xué)手冊［M］.北京：電子工業(yè)出版社，2005.

［2］李勇.消息認(rèn)證碼的原理與實現(xiàn)［J］.通信世界，2006（47）：15-18.

［3］王紅霞，等.基于HMAC-SHA1算法的消息認(rèn)證機制［J］.山西師范大學(xué)學(xué)報（自然科學(xué)版），2005（1）：89-92.

［4］于華章.HMAC算法安全性分析［J］.計算機安全，2005（7）：58-61.