改进的经典信道消息完整性认证方法

周瑞瑞 张 博 鱼 冰

（国家知识产权局专利局专利审查协作河南中心，河南 郑州 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.