基于循环移动与取反运算的双向认证协议

左文涛

(广州工商学院 计算机科学与工程系， 广州 510850)

射频识别技术产生于20世纪，进入2000年后，随着信息科技进步，射频识别技术得到飞速发展和广泛应用[1-2]。电子标签具有无接触、成本低、易部署、体积小等优势，在经济社会各领域中得到广泛应用[3-4]。

在经典的射频识别通信模型中电子标签与读卡器间通过无线方式交换信息，因无线方式固有的开放性，使得信息易被攻击者获取，从而造成一定的安全隐患[5-6]。为确保用户隐私信息等各方面的安全性，需保障通信实体双方非第三方伪造，双向认证协议可解决此问题[7-9]。

文献[10]利用伪ID给出一个协议，协议因部分重要隐私信息采用明文传送方式，使得攻击者获取之后结合其他消息可穷举出一些重要隐私信息。文献[11]中基于经典哈希函数给出一个协议，虽哈希函数具备较好的安全性，但信息加密过程中仅只有一个参量攻击者不知晓，使攻击者可以采用穷举方式穷举出部分隐私信息。文献[12]采用分组匿名认证的方式给出一个协议，协议在设计过程中未考虑共享密钥更新步骤，使得协议中标签位置易被攻击者追踪。文献[14]指出文献[13]的协议存在无法抗攻击者的异步攻击，同时也无法保证标签的位置隐私安全，在该协议基础之上提出了一个改进的协议。协议基于哈希函数实现加密，但随机数等信息明文发送，易被攻击者获取，攻击者再结合其他消息可穷举出部分隐私信息。

在对现有经典协议安全性分析基础之上，给出一个改进的基于循环移动与取反运算的认证协议。协议主要从以下方面进行改进，其一，明文发送的参数，不再参与其他消息运算，使攻击者获取明文参数也与消息破解无任何关联；其二，文中自定义一个新的加密算法，即循环移动与取反运算，循环移动与取反运算实现过程中将结合加密参数汉明重量值不同进行不同方向的移动变化以及不同位上取反操作，使得攻击者不知晓参数汉明重量值情况下，无法进行破解。多协议的多角度实验比较表明文中协议具备较高的安全性能及较低的计算量。

1 基于循环移动与取反运算的协议

1.1 循环移动与取反运算

循环移动与取反运算的定义：K、X都是长度为L位的二进制串，Wt(K)、Wt(X)分别表示K、X的汉明重量。当Wt(K)≥Wt(X)时，对X进行循环左移≪≪操作，循环左移(Wt(K)-Wt(X))位，然后再对循环左移所得二进制串的奇数位进行取反操作；当Wt(K)

如图1所示为Wt(K)≥Wt(X)时循环移动与取反运算示意过程，其中X=010100011000、K=110101101010、L=12，则可得到Wt(K)=7、Wt(X)=4、Wt(K)-Wt(X)=3，循环左移结果为100011000010，循环移动与取反运算运算最终结果为001001101000；如图2所示为Wt(K)

图1 循环移动与取反运算示意图(Wt(K)≥Wt(X))

图2 循环移动与取反运算示意图(Wt(K)

1.2 协议步骤

1) 协议符号含义。R表示读卡器；T表示电子标签；

IDTR表示T标识符右半边；IDTL表示T标识符左半边；K表示R与T之间共享密钥；Knew表示R与T之间当前共享密钥；Kold表示R与T之间上轮共享密钥；x表示R生成的随机数；y表示T生成的随机数。

2) 协议步骤描述。与其他协议[15-16]一样做出如下假设：R与T之间会话存在安全隐患。文中协议示意图如图3。

图3 基于循环移动与取反运算的协议示意图

具体协议步骤描述：

①R向T发送Request认证请求命令。

②T将IDTR发送给R。

③R收到消息，查找数据库中是否存放与IDTR相等的值。找到，则R获悉与之通信的标签基本信息，并取出相对应的IDTL、K；然后R产生随机数x，分别计算通信消息M、N的值，并最终向T发送M、N。未找到，则T未通过R的第一次验证，协议终止。其中M=x⊕IDTL、N=AIDTL(x)。

④T收到消息，通过计算得到随机数x′，将结合IDTL计算得到N′，对比N′与N的值。N′=N，则R通过T的第一次验证，并表明x′=x，接着T产生随机数y，分别计算P、Q的值，并向R发送P、Q。N′≠N，则R未通过T的验证，协议终止。

其中，x′=M⊕IDTL、N′=AIDTL(x′)=AIDTL(M⊕IDTL)、P=y⊕x、Q=AK(y&IDTL)。

⑤R收到消息，通过计算得到随机数y′，将Knew、IDTL、y′运用相同的运算法则计算得到Q′，比对Q′与Q的值。

Q′≠Q，R将用Kold替换Knew，同时结合IDTL、y′再次运用相同的运算法则计算得到Q″，并再次比对Q″与Q的值。仍不相等，T未能通过R的第二次验证，协议终止；若Q″=Q，则表明y′=y，然后R计算会话消息V的值，接着R开始更新共享密钥Knew=AK(y&x)，最后向T发送V。

Q′=Q，则表明y′=y，然后R计算会话消息V的值，接着R开始更新共享密钥Kold=Knew、Knew=AK(y&x)，最后向T发送V。

其中y′=P⊕x、Q′=AKnew(y′&IDTL)、Q″=AKold(y′&IDTL)、V=AIDTL(K&x&y)。

⑥T收到消息，T运用相同的运算法则计算得到V′，将V′与V进行对比。V′≠V，则R未能通过T的第二次验证，协议终止。V′=V，则T开始更新共享密钥Knew=AK(y&x)。到此，T与R之间的双向认证顺利完成，R与T之间可以进行其他信息交换。其中V′=AIDTL(K&x′&y)。

2 基于BAN逻辑形式化分析

读卡器用R符号表示，电子标签用T符号表示。

1) 协议理想化

消息①R→T：Query；

消息②T→R：IDTR；

消息③R→T：M，N；

消息④T→R：P，Q；

消息⑤R→T：V。

2) 协议初始假设

P5∶R|≡#(x)；P6：T|≡#(x)；

P7∶R|≡#(y)；P8：T|≡#(y)；

P9∶R|≡T|⟹P；P10：R|≡T|⟹Q；

P11∶T|≡R|⟹M；P12：T|≡R|⟹N；

P13∶T|≡R|⟹V。

3) 协议安全目标

G1∶T|≡M；G2∶T|≡N；

G3∶T|≡V；G4∶R|≡P；

G5∶R|≡Q。

4) 协议分析推理

3 安全性分析

1) 双向认证。双向认证是会话实体之间需具备的最基本的安全需求。文中协议R对T第一次认证通过IDTR完成，R对T第二次认证通过P、Q完成；T对R第一次认证通过N、M完成，T对R第二次认证通过V完成。上述信息中，除了IDTR是明文，其他信息均是密文，但IDTR明文对协议安全性并无影响，因后续计算过程中并未用到IDTR信息。攻击者在缺少必要隐私信息情况下，无法计算正确的会话消息。因此，协议可以提供会话实体间双向认证安全。

2) 假冒攻击。选取攻击者假冒成R进行分析。攻击者假装查找到IDTR，并产生一个随机数，亦按照相同的运算法则计算得到消息M、N的值，并将M、N发给T以企图通过T的验证。但攻击者缺少T的IDTL值，因此攻击者在计算M、N过程中，只能随机选择一参量作为IDTL值参与运算。当T收到消息后，通过协议中第4步的方法进行简单计算即可识别R是伪造，攻击者无法通过T的验证，攻击者获取隐私信息失败。因此，协议可以提供抗假冒攻击安全。

3) 异步攻击。R一端存放有Kold、Knew前后两轮通信共享密钥，根据协议第五步中描述，当R用Knew验证T失败之后，立刻用Kold替换Knew再次进行对T的验证，前后两次对T的验证操作，确保了R与T之间信息一致性。即便是R与T之间有短暂的异步，经过用Kold替换Knew再次进行对T的验证操作后，T与R之间将再次恢复一致性。因此，协议可以提供抗异步攻击安全。

4) 穷举攻击。文献[14]提出的协议在信息加密过程中仅有一个参量信息攻击者无法获取，而导致隐私信息易被攻击者穷举出，但本文协议攻击者无法进行穷尽。选择M、N为例进行模拟攻击者发起穷举攻击，对M进行变形后带入N中，可以得到N′=AIDTL(x′)=AIDTL(M⊕IDTL)。在N中攻击者看似只有IDTL一个参量值不知晓，似乎可穷举出IDTL值，但根据文中对循环移动与取反运算的定义可得知，攻击者无法穷举，原因如下：其一，IDTL值不知晓，则IDTL自身汉明重量值不知晓，同理M⊕IDTL汉明重量值亦不知晓，则攻击者无法判定是循环左移还是循环右移；其二，参数汉明重量值不知晓，攻击者在取反操作时不知是对奇数位取反还是对偶数位取反。因此，协议可以提供抗穷举攻击安全。

5) 重放攻击。消息M、N、P、V中混入有随机数x，消息P、Q、V中混入有随机数y，随机数x、y都是由随机数产生器随机产生，攻击者无法预测、逆推，使得会话通信消息可以每轮中保持新鲜性。当攻击者重放上轮会话消息时，当前正在通信消息加密用到随机数值已发生变更，攻击者重放上轮消息将会失败。因此，协议可以提供抗重放攻击安全。

6) 后向安全。攻击者采用窃听等手段可以获取一个完整会话中所有消息，并对消息进行分析，企图分析出之前的隐私信息。文中协议在所有消息加密过程中混入随机数，从而确保每个消息的新鲜性，即前后两轮会话用到消息值并不相同，且因随机数具备互异性、不可预测性等特征，使得攻击者无法从当前获取消息中分析出之前的隐私信息。因此，协议可以提供后向安全。

4 性能分析

将文中协议与其他经典协议从通信量、标签计算量角度进行对比分析，见表1所示。

表1 计算量与通信量

表1中出现的符号含义如下：L表示协议会话消息长度；m表示认证请求命令长度，一般只需要一比特长度即可。Za表示位运算计算量，比如异或运算、与运算；Zb表示循环移动与取反运算计算量；Zc表示哈希函数计算量；Zd表示产生随机数计算量；Ze表示模运算计算量。在上述不同的计算量中，Za和Zb运算的计算量最小，都属于超轻量级别计算量；而其他运算的计算量都不属于超轻量级，且计算量远大于超轻量级的计算量，因此协议中这些非超轻量级的运算使用的次数越少，整个系统计算量就越少。

文中协议在第4步中计算随机数x′需要第1次用到Za运算，计算N′过程中需要第1次用到Zb运算，生成随机数y需要用到1次Zd运算，计算Q消息过程中需要第2次用到Zb运算，在计算消息P过程中需要第2次用到Za运算；文中协议在第6步中计算V′过程中需要第3次用到Zb运算，在最后更新共享密钥K时需要用到第4次Zb运算。基于上述，文中协议标签一端总共计算量为2Za+4Zb+1Zd。

从标签一端计算量角度出发分析，文中协议与其他文献中协议相比较，具备一定的优势，主要加密算法计算量属于超轻量级，因此标签端整体计算量得到一定程度上降低。从系统会话消息通信量角度出发分析，虽然文中协议通信量比其他协议通信量略大，但综合整体计算量而言，文中协议存在一定优势。基于上述分析，文中协议在计算量及安全性角度具备优势，而通信量稍大，因此文中协议适用于会话次数少、安全需求高的应用场景。

5 仿真实验

本小节先从安全角度对文中协议进行仿真实验，然后从计算量角度对文中协议进行仿真实验。

1) 安全仿真实验。设计的协议在实际运用过程中会遭受来自不同角度的网络攻击，文中仿真实验过程中选择某一个时间段内不同的文献中设计的协议抵抗来自不同角度的网络攻击次数为对象进行仿真，并记录仿真过程中网络攻击成功的次数。假定选定仿真实验过程中会话电子标签个数都为10 000个，仿真时间选择一个时间段，并从0秒钟开始计时，依次选择1 000 ms、3 000 ms、5 000 ms、7 000 ms、9 000 ms为结点进行仿真实验的数据统计。同时为提高仿真实验的准确性，每个时间点的统计数据时进行不低于200次的仿真实验数据，并将记录的不低于200次的仿真实验数据求取平均值最终仿真实验数值，最终绘画出如图4所示。

图4 不同时间点网络攻击成功次数统计图

对图4进行分析可以得出，文中协议相对其他协议来说，具备更高的安全性。当时间点在5 000 ms之前时，不同的协议对网络攻击成功次数相比较相错并不是很大；但当时间点超过5 000 ms之后，除了文中协议，其他协议面对来自不同角度的网络攻击成功次数增加的趋势越来越明显，表明其他协议存在一定的安全缺陷。时间越长，文中协议曲线增加幅度较为平缓，表明文中协议具有良好的安全性。

结合上述，从性能角度进行仿真实验，能够表明文中协议在电子标签端的计算时间开销存在一定优势；从安全性角度进行仿真实验，能够表明文中协议能够抵抗一定数量的网络攻击，具备良好的安全性需求。

2) 计算量仿真实验。在性能方面，文中选择电子标签端的计算量为对象进行仿真实验。电子标签本身计算能力受到严格的限制，因此协议只有选择的加密算法计算量越少，则电子标签端的计算量才会越少，计算所需要的时间开销也就越小。

选择在惠普笔记本WIN 8操作系统、I5处理器、基于 C++ 编程语言实现编程环境下进行仿真实验。为能够验证不同协议是实际环境中适用情况，文中在进行仿真时将依次选择一个相同的时间段内，读卡器与不同数量的电子标签进行交互信息时，电子标签一端计算时间开销；所选择的电子标签数量依次为 1 000个、3 000个、5 000个、7 000个、9 000 个。为提高仿真实验数据的准确性，在每组数量不同的电子标签仿真过程中，进行相同环境下的100次仿真实验，并同时记录这100次仿真实验的数据，最后求取这100次仿真实验数据的平均值作为最终的仿真实验结果，并绘制出如图5所示的不同协议电子标签端的计算量开销对比图。

图5 电子标签数量与电子标签计算开销直方图

结合图5可以得出：文中协议电子标签整体计算时间开销优于其他对比文献。其中在对比的文献中，文献[11-13]中协议电子标签端的计算时间开销比较大；文献[10,14]中协议电子标签端的计算时间开销有一定程度上的降低；相对于上面文献中协议，文中协议电子标签端计算时间开销总是最少的，主要原因在于：文中协议选择的加密算法是基于超轻量级的按位运算实现的循环移动与取反运算加密算法，能够极大程度上降低电子标签端的计算量。由图5可以对比得出，当某个时间段内，与读卡器会话的电子标签数量逐渐增多时，文中协议电子标签端计算时间开销优势越明显。

6 结论

在具体分析近些年经典双向认证协议，并指出其不足后，给出一个改进的协议。先创新型的自定义一种循环移动与取反运算，并给出循环移动与取反运算具体实现过程，然后文中协议采用自定义的循环移动与取反运算完成信息的加密。循环移动与取反运算基于循环移动及取反操作实现。循环移动与取反运算同时结合加密参数汉明重量值不同进行不同方向的循环移动，并对移动结果再次进行对奇数位或偶数位的取反运算，增加循环移动与取反运算破解难度，确保协议的安全性。通过仿真实验表明文中协议具备良好的安全性及适用于低成本系统。