改進的經典信道消息完整性認證方法

周瑞瑞 張 博 魚 冰

（國家知識產權局專利局專利審查協作河南中心，河南 鄭州 450000）

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

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

圖1 基于循環校驗碼CRC的認證方案

1 基于CRC的認證方案安全性分析

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

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

2 改進的完整性認證方案

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

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

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

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

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

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

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

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

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

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

3 結語

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

［1］Menezes.應用密碼學手冊［M］.北京：電子工業出版社，2005.

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

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

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