计算机系统应用  2022, Vol. 31 Issue (5): 254-261   PDF    
抗BGP中间人攻击的无证书签名方法
韩增杰, 胡杨, 姚志强     
福建师范大学 计算机与网络空间安全学院, 福州 350117
摘要:边界网关协议用于自治域之间交换网络可达信息, 但面临中间人攻击威胁, 因此提出一种改进的无证书多重签名方案并将其应用于边界网关协议. 在该方案中域间路由须按照路由传递顺序对其进行签名, 自治系统对多重签名验证成功才可接收路由, 且自治系统的公私钥与可信中心交互生成, 签名消息的长度固定, 计算高效. 通过安全性分析, 证明基于无证书的有序多重签名方案在随机预言机模型下具有不可伪造性, 将其应用到边界网关协议中可以抵抗中间人攻击.
关键词: 无证书签名    多重签名    中间人攻击    前缀劫持    边界网关协议    签名方案    
Prevention of Man-in-the-middle Attacks on BGP Using Certificateless Signatures
HAN Zeng-Jie, HU Yang, YAO Zhi-Qiang     
College of Computer and Cyber Security, Fujian Normal University, Fuzhou 350117, China
Abstract: The border gateway protocol (BGP) is used to exchange network reachability information between autonomous systems, but it is threatened by man-in-the-middle attacks. Therefore, an improved certificateless multi-signature scheme is proposed and applied to BGP. The inter-domain routing must be signed according to the route delivery order, and the autonomous systems can receive the route only after the multi-signatures are verified successfully. The public and private keys to the autonomous systems are generated interactively with the trusted center with a fixed length of the signature message and efficient calculations. The security analysis proves that the proposed scheme cannot be fabricated under the random oracle model and is valid for resisting the man-in-the-middle attacks on BGP.
Key words: certificateless signature     multi-signature     man-in-the-middle attack     prefix hijacking     border gateway protocol (BGP)     signature scheme    

边界网关协议(border gateway protocol, BGP)的作用是在不同的自治系统之间传递路由, 通过BGP提供的各种路由属性为自治系统通信提供最佳路径. 由于BGP协议的通信双方无条件信任彼此, 自治系统不验证路由信息的有效性, 因此容易受到中间人攻击[1]. BGP的中间人攻击主要包括前缀劫持攻击和路径伪造攻击. 中间人可以宣布自己为目标前缀的起源, 通告一个比目标前缀更长的虚假路由, 其余的BGP路由器在接收到这些虚假的通告后将其放到路由表中传送数据. 如果中间人将劫持的路由信息丢弃, 则通信双方不可达, 产生路由黑洞; 如果中间人把自己作为中转中心, 将受害者路径重定向到目标网络, 原始路径依旧可达, 恶意的中间人可以随时窃听双方的通信, 导致消息泄露. 中间人攻击能够得逞的原因是由于缺少对路由消息来源以及对AS-PATH路径的认证, 目前针对中间人攻击的研究方案主要分为两大类, 一类是以S-BGP为代表的安全扩展技术, 另一类是当发生中间人攻击时及时响应的异常检测技术. 在使用证书的BGP安全扩展方案中, 证书的颁布和撤销都是复杂的过程, 而无证书方法只需要引入可信的第三方与用户交互生成公私钥即可, 不需要引入证书, 因此本文提出无证书的签名方法来防止中间人攻击.

1 相关研究

针对BGP的中间人攻击, S-BGP[2]通过公钥基础设施为每个AS颁发证书来验证路由的起始源, 通过签名的方式使得攻击者无法劫持, 但由于S-BGP采用基于证书的安全扩展方案来防御中间人攻击, 在域间路由验证时会产生较大的计算开销和存储代价, 难以实施. 文献[3]提出一种改进的BGP路由源认证方案. 将从RP获取的ROA 证书附加到更新报文中, 接收端从RP申请可信的ROA证书公钥并进行解密, 通过与更新报文比较从而验证路由源的真实性. 文献[4]针对路由传输路径上的负载变化提出了前缀劫持检测系统LDC, 攻击者发动前缀劫持后流量负载会发生异常. 文献[5]根据BGP在受到中间人攻击时路由控制平面路径和真实转发路径不一致的特征, 提出一种针对中间人攻击的实时检测系统, 但该方案无法检测延长距离为1的中间人攻击. 文献[6]提出了一种实时检测与缓解系统ARTEMIS, 由AS本身检测和自动缓解针对其自身前缀的劫持, 该方案利用控制面板监视的最新进展实时检测前缀劫持, 并且会进行自动缓解. Li等人[7]提出了针对BGP的特殊中间人攻击Tiger攻击, Tiger攻击不会破坏路由在控制平面和数据平面一致性, 因此可以规避现有的检测方案. Alkadi等人[8]针对前缀劫持提出了一种实时处理方法OGI, 通过AS本身来检测由被劫持节点引起的可疑传输自治系统. 邓海莲等人[9]从Route Views系统获取路由信息, 根据路由变化的幂律性建立正常域间路由模型, 从而检测前缀劫持和路径篡改等异常行为. 大多数针对BGP的中间人攻击检测系统通常是在前缀劫持发生后进行的检测机制, 因此无法从根本上解决BGP的中间人攻击.

为解决基于身份的密码体制中私钥生成中心(PKG)可能造成的伪造签名攻击, Al-Riyami等人[10]提出了无证书公钥密码体制. 该体制通过引入可信中心KGC来产生用户的部分私钥, 用户根据随机生成的秘密值产生另一部分私钥, 完整私钥由用户自己保存. 陈亚萌等人[11]提出的基于双线性对的无证书签名方案成员交互次数过多, 效率较低. 刘帅等人[12]提出的基于椭圆曲线的无证书签名方案在计算效率上有一定的提升, 但是签名长度不固定, 会随着签名人数的增加而改变.

将无证书公钥密码体制和有序多重签名结合构造成无证书的有序多重签名, 既可以解决传统签名方案中公钥合法性和私钥托管问题, 又可以解决签名时多个签名人无法有序验证的问题. 罗文俊等人[13]提出一种不含双线性对运算的无证书签名方案, 计算效率较高, 但是该方案的签名长度不固定, 且签名人数越多, 通信效率越低. 秦艳琳等人[14]提出的无证书有序多重签名方案被许艳等人[15]通过安全性分析证明其无法抵抗伪造攻击, 许艳等人对方案进行改进从而使其能够抵抗伪造攻击. 但是杜红珍等人[16]提出许艳等人的方案存在不足, 并且通过修改后发现其验证过程需要n+1个双线性对计算, 计算效率大大降低. 孙玉等人[17]提出的多重签名方案没有验证签名者的顺序, 各个签名成员可以私自改变签名顺序从而伪造签名.

为了从根本上解决BGP协议中存在的中间人攻击, 本文从有序多重签名出发, 结合无证书签名方案的优势, 在路由传递过程中源AS和传播AS需要按序对路由信息进行多重签名, 路由信息接收者通过正确的签名顺序对其进行验证, 从而解决域间路由在传递过程中的路径认证问题. 该方案不仅解决了传统公钥密码体制中存在的证书管理问题和基于身份的密码体制中秘钥生成中心伪造签名的问题, 同时能够抵抗边界网关路由协议的中间人攻击.

2 无证书有序多重签名方案

无证书多重签名方案通常是以双线性对为工具构造的, 也有研究人员提出不含双线性对的无证书有序多重签名方案, 本文采用基于双线性对的多重数字签名方案, 其安全性是基于离散对数和计算性Diffie-Hellman问题, 这里不再赘述双线性对和困难问题定义.

无证书有序多重签名方案的步骤如下:

(1)初始化系统参数: KGC生成参数params、系统主密钥和系统公钥, 将params对用户公开.

(2)生成秘密值: 用户Ni随机生成秘密值, 并根据参数params生成部分公钥.

(3)生成部分私钥: KGC验证用户的身份, 并根据参数params生成对应的部分私钥发送给用户Ni.

(4)生成完整公私钥: 用户Ni通过参数params验证部分私钥, 生成完整公钥和完整私钥.

(5)用户签名: 输入消息mparams生成部分签名 $ {\sigma _i} $ , 并将部分签名发送给后续签名成员.

(6)验证签名: 验证上一个签名成员的签名结果 $ {\sigma _i} $ 是否正确. 若正确, 则继续签名, 否则停止签名.

为简述方便, 将方案中使用的符号和含义列于表1. 无证书有序多重签名方案主要包括注册阶段、签名阶段和整体验证阶段, 其中注册阶段包括KGC初始化系统参数及用户公私钥的生成; 签名阶段包括每个用户的部分签名; 整体验证阶段是对生成的完整签名进行验证. 下面详述无证书有序多重签名方案的具体过程:

(1)注册阶段

1)初始化系统参数: KGC选择椭圆曲线上的点构成阶为q的循环群GGT, 其中, q为大素数, G为加法循环群, 记为(G, +), GT为乘法循环群, 记为(GT, ·), 双线性映射e: G×GGT. 选择两个安全的哈希函数H1H2, 其中, H1:{0, 1}*×G×G $ Z_q^ * $ , H2:{0, 1}* $ Z_q^ * $ . KGC随机选择 $ s \in Z_q^ * $ , 计算P0=sP, 其中, P为群G的一个生成元, s为系统主密钥由KGC安全保存, P0为系统公钥, 将参数params={G, GT, q, e, P, P0, H1, H2}对用户公开.

2)生成用户部分公钥: 用户Ni将自己的用户身份IDi发给KGC, 随机选择 $ {x_i} \in Z_q^ * $ 作为秘密值, 生成用户的部分公钥Pi, 将部分公钥发送给KGC.

$ {P_i} = {x_i}P $ (1)

3) KGC为用户生成部分私钥: KGC验证用户Ni的身份IDi, 为用户生成 $ {r_i} \in Z_q^ * $ , 计算RiQizi, 通过安全信道将(Ri, zi)发送给用户Ni.

$\left\{ { \begin{split} &{R_i} = {r_i}P\\ &{Q_i} = {H_1}\left( {I{D_i}, {R_i}, {P_i}} \right)\\ &{{\textit{z}}_i} = {r_i} + {Q_i}s \end{split} } \right. $ (2)

4)用户生成完整公私钥: 用户收到(Ri, zi)后, 计算Zi, 验证Zi=Ri+H1(IDi, Ri, Pi)P0是否成立, 若不成立, 则返回到第2步重新计算; 若成立, 则用户的完整公钥为(Pi, Ri, Zi), 计算wi, 用户的完整私钥为(xi, wi).

$\left\{ { \begin{split} &{Z_i} = {{\textit{z}}_i}P\\ &{w_i} = {\left( {{{\textit{z}}_i} + {x_i}{H_1}\left( {I{D_i}, {R_i}, {P_i}} \right)} \right)^{ - 1}} \end{split} } \right.$ (3)
表 1 符号说明

(2)签名阶段

1)第一个签名用户对消息m进行部分签名:

① 选择随机数 $ {d_1} \in Z_q^ * $ , 计算D1:

$ {D_1} = {d_1}P $ (4)

② 计算V1, 其中, Sn个签名者的身份集合, 记为S={ID1, ID2, …, IDi, …, IDn}, Ti是长度为n的{0,1}n字符串, 其中, 第ni+1位为1, 其余位为0.

$ {V_1} = {H_2}\left( {m\parallel {P_1}\parallel {Z_1}\parallel {P_0}\parallel S\parallel {T_1}\parallel {D_1}} \right) $ (5)

③ 用户N1对消息m的部分签名结果为 ${\textit{Sign}}_1$ , 令 ${\sigma _1} = {\textit{Sign}}_1$ , 用户N1将部分签名结果 $ (m, {\sigma _1}, {D_1}) $ , 发送给下一个待签名用户.

$ {\textit{Sign}}_1 = \left( {{x_1}{H_2}\left( {m\parallel {P_1}\parallel {Z_1}\parallel {P_0}\parallel S\parallel {T_1}\parallel {D_1}} \right) + {d_1}} \right){w_1} $ (6)

2)第i个签名用户Ni收到上一个用户的签名结果 $ (m, {\sigma _{i - 1}}, {D_{i - 1}}) $ , 首先对 $ {\sigma _{i - 1}} $ 进行验证, 若验证不通过, 则停止签名. 无证书有序多重签名的正确性通过双线性对性质计算易得:

$ \prod\limits_{i = 1}^n {e(({D_i} + {V_i}{P_i}){{({R_i} + ({P_0} + {P_i}){Q_i})}^{ - 1}}, P)} = e({\sigma _n}, P) $ (7)

通过上式验证用户的部分签名和完整签名. 验证过程如下:

① 计算QjVj, 其中, 1 ≤ ji–1:

$ \left\{ {\begin{split} &{Q_j} = {H_1}\left( {I{D_j}, {R_j}, {P_j}} \right)\\ &{V_j} = {H_2}\left( {m\parallel {P_j}\parallel {Z_j}\parallel {P_0}\parallel S\parallel {T_j}\parallel {D_j}} \right) \end{split}} \right.$ (8)

② 验证等式:

$ e\left( {{\sigma _{i - 1}}, P} \right) = \prod\limits_{j = 1}^{i - 1} {e(({D_j} + {V_j}{P_j}){{({R_j} + ({P_0} + {P_j}){Q_j})}^{ - 1}}, P)} $ (9)

3)若式(9)成立, 则用户Ni对上一个用户的签名结果进行签名:

① 选择随机数 $ {d_i} \in Z_q^ * $ , 计算Di:

$ {D_i} = {d_i}P $ (10)

② 计算Vi:

$ {V_i} = {H_2}\left( {m\parallel {P_i}\parallel {Z_i}\parallel {P_0}\parallel S\parallel {T_i}\parallel {D_i}} \right) $ (11)

③ 则用户Ni对消息m的部分签名结果为 ${\textit{Sign}}_i = $ $ \left( {{x_i}{V_i} + {d_i}} \right){w_i}$ , 令 ${\sigma _i} = {\textit{Sign}}_i + {\sigma _{i - 1}}$ , 用户Ni将部分签名结果 $ (m, {\sigma _i}, {D_i}) $ , 发送给下一个待签名用户.

(3)整体验证阶段

最终得到完整签名 $ (m, {\sigma _n}, {D_n}) $ , 验证式(12)是否成立:

$ \prod\limits_{i = 1}^n {e(({D_i} + {V_i}{P_i}){{({R_i} + ({P_0} + {P_i}){Q_i})}^{ - 1}}, P)} = e({\sigma _n}, P) $ (12)

其中, 1≤i≤n, 若等式成立, 则签名正确, 否则签名错误.

3 效率分析

为方便计算, 本文将双线性对运算记为BP, 椭圆曲线上的点乘计算记为A, C表示一次模乘运算, D表示一次模逆运算, H表示使用了一次哈希函数, 忽略模加和模减运算, 根据双线性对运算的性质, 验证公式右边可以化简为一个双线性对, 一次签名使用了一次哈希函数. 从表2可以看出在整体验证阶段, 文献[15]的方案需要n+1次双线性对运算, 而本文方案和文献[16]仅需要两个双线性对运算, 且比文献[16]在整体验证时少了n倍的哈希运算.

表 2 与其他方案比较

表2中, 根据文献[18]和文献[19]提供的数据,本文用Tm代表模乘运算所需的计算开销, 则模的取逆运算≈11.60Tm, 椭圆曲线标量乘运算≈29.00Tm, 映射到点的哈希运算≈29.00Tm, 双线性配对运算≈87.00Tm. 设置签名成员n=5, 在I5-4590、16 GB内存和Windows 7操作系统环境下本方案在注册阶段用时为0.63 ms, 签名阶段用时为0.20 ms, 整体验证阶段用时为2.75 ms. 从表3可以看出, 在安全性方面, 文献[13]无法抵抗第2类攻击者且签名长度不固定, 文献[15]提出的方案被杜红珍等人[16]证明无法抵抗第1类攻击者和第2类攻击者, 本文在第5.2节对签名过程进行了详细的分析, 证明本方案能够同时抵抗这两类攻击者的伪造签名攻击. 通过在相同实验环境下分析得出本方案总体计算效率要高于文献[15]和文献[16]: 文献[15]在签名阶段用时0.29 ms, 在整体验证阶段用时4.24 ms; 文献[16]在签名阶段的用时0.29 ms, 在整体验证阶段的用时3.06 ms. 本方案较文献[15]在整体验证效率上提升了约35%, 较文献[16]在注册阶段提升了约31%. 因注册阶段的效率基本相同, 考虑到各成员只进行一次注册阶段, 而签名过程需要多次验证, 因此随着签名人数的增多, 本方案的优势越明显. 同时本方案的签名长度固定, 验证者只需要验证最后产生的完整签名即可, 属于紧凑的有序多重签名.

表 3 安全性对比

4 方案在BGP中的应用 4.1 基于无证书多重签名的BGP方案

基于证书的BGP安全扩展技术存在不足, 因此本文将无证书有序多重签名引入到BGP的路由信息认证中, 解决S-BGP的证书颁发和撤销的复杂问题. 基于无证书多重签名的BGP安全方案主要分为KGC初始化阶段、自治系统注册认证阶段、发布路由阶段和路由传播阶段.

(1) KGC初始化阶段

KGC初始化过程同无证书签名方案一致, 随机选择 $ s \in Z_q^ * $ , 计算P0=sP, 其中, P为群G的一个生成元, s为系统主密钥由KGC安全保存, P0为系统公钥, 将参数params={G, GT, q, e, P, P0 , H1, H2}对用户公开.

(2)自治系统注册认证阶段

自治系统需要向KGC注册, 获得合法成员身份:

1)自治系统ASn将自己的身份信息发给KGC, 随机选择 $ {x_i} \in Z_q^ * $ 作为秘密值, 生成部分公钥Pi=xiP, 将部分公钥发送给KGC.

2) KGC验证自治系统的身份后, 为其生成 $ {r_i} \in Z_q^ * $ , 计算Ri=riPQizi, 通过安全信道将(Ri, zi)发送给自治系统.

$\left\{ { \begin{split} &{Q_i} = {H_1}\left( {I{D_i}, {R_i}, {P_i}} \right)\\ &{{\textit{z}}_i} = {r_i} + {Q_i}s \end{split}} \right.$ (13)

3)自治系统收到(Ri, zi)后, 计算Zi=ziP, 验证Zi=Ri+H1(IDi, Ri, Pi)P0是否成立, 若不成立, 则返回到第2步重新计算; 若成立, 则自治系统的完整公钥为(Pi, Ri, Zi), 计算wi, 自治系统的完整私钥为(xi, wi).

$ {w_i} = {\left( {{{\textit{z}}_i} + {x_i}{H_1}\left( {I{D_i}, {R_i}, {P_i}} \right)} \right)^{ - 1}} $ (14)

(3)发布路由阶段

待发布路由的自治系统发布路由条目, 并且为其签名: 自治系统选择随机数 $ {d_1} \in Z_q^ * $ , 计算D1=d1P, 计算V1, 其中, Sn个传输自治系统的身份集合, 记为S={ID1, ID2, …, IDi, …, IDn}, Ti是长度为n的{0, 1}n字符串, 其中, 第ni+1位为1, 其余位为0. 签名结果为Sign1, 令 $ {\sigma _1} $ = Sign1, 路由发布者将路由信息和签名结果 $ (m, {\sigma _1}, {D_1}) $ 发送给临近的自治系统.

$\left\{ { \begin{split} &{V_1} = {H_2}\left( {m\parallel {P_1}\parallel {Z_1}\parallel {P_0}\parallel S\parallel {T_1}\parallel {D_1}} \right)\\ &Sig{n_1} = \left( {{x_1}{H_2}\left( {m\parallel {P_1}\parallel {Z_1}\parallel {P_0}\parallel S\parallel {T_1}\parallel {D_1}} \right) + {d_1}} \right){w_1} \end{split}} \right.$ (15)

(4)路由传播阶段

当前自治系统收到路由信息时, 需要验证签名结果, 若验证通过则将路由条目添加到路由表, 并将路由信息继续传输, 验证不通过则丢弃路由.

验证过程如下: 计算Qj, Vj, 其中, 1≤ji–1; 验证等式:

$\left\{ { \begin{split} & e\left( {{\sigma _{i - 1}}, P} \right) = \prod\limits_{j = 1}^{i - 1} {e(({D_j} + {V_j}{P_j}){{({R_j} + ({P_0} + {P_j}){Q_j})}^{ - 1}}, P)} \\ & {Q_j} = {H_1}\left( {I{D_j}, {R_j}, {P_j}} \right)\\ & {V_j} = {H_2}\left( {m\parallel {P_j}\parallel {Z_j}\parallel {P_0}\parallel S\parallel {T_j}\parallel {D_j}} \right) \end{split}} \right.$ (16)
4.2 方案分析 4.2.1 抗伪造性

无证书的公钥密码体系中存在两类攻击者: 第1类攻击者A1可以替换签名者的公钥进行签名, 但不知道系统主密钥; 第2类攻击者A2可以获取系统主密钥, 但不能替换签名者的公钥. 本文通过定理1和定理2证明无证书多重签名无法被伪造.

定理1. 在随机预言机模型下, 如果攻击者A1能够以不可忽略的概率伪造出多重签名, 则挑战者D可以通过A1解决CDH问题.

假设攻击者拥有最大优势已经获得n–1个签名者的签名, 即攻击者已经获得了n–1个签名者的私钥, 可以伪造出这n–1个签名者的签名, 为了证明本方案难以抵抗伪造性, 攻击者需要在多项式时间内以一个不可忽略的概率伪造出最后一个签名者的签名. D已知P, X=aP, Y=bP, 如果可以求出abP, 则称D可以通过A1解决CDH问题.

模拟过程如下:

D将结合CDH困难问题模拟本方案, 选择椭圆曲线上的点构成阶为q的循环群GGT, 其中, q为素数, G为加法群, GT为乘法群, 双线性映射e:G×GGT. 选择两个安全的哈希函数H1H2, 其中, H1:{0, 1}*×G×G $ Z_q^ * $ , H2:{0, 1}*→ $ Z_q^ * $ . D设置系统公钥X=xP=P0, 其中, P为群G的一个生成元, 系统主密钥xD未知, D构造询问用户的身份集合S={ID1, ID2, …, IDi, …, IDqc}. D维护4张表: L1对应用户的秘密值询问, L2L4分别对应哈希函数H1H2的询问, L3对应用户的部分私钥询问, 将params={G, GT, q, e, P, P0, H1, H2}发送给A1, A1进行如下询问:

(1)秘密值询问: A1询问IDi的秘密值, 如果L1列表中包含(IDi, xi, Pi), 则Dxi返回给A1, 否则D选择随机数 $ {x_i} \in Z_q^ * $ , 并计算Pi=xiP, 将xi发送给A1, 在L1 列表中记录(IDi, xi, Pi).

(2)公钥替换询问: A1替换用户Ni的公钥, 输入用户的身份IDi和被替换之后的公钥Pi'以及私钥xi', D更新列表L1.

(3) H1询问: A1输入(IDi, Ri, Pi), 如果L2列表中包含(IDi, Ri, Pi, h1i), 则将h1i返回给A1, 如果L2列表中没有相关信息, 则分两种情况讨论:

1)若in, D随机选择 $ {g_i} \in Z_q^ * $ , 计算h1i=giP, 同时在L2列表中记录(IDi, Ri, Pi, h1i).

2)若i=n, D随机选择 $ {g_i} \in Z_q^ * $ A1, 计算h1i=giY, 同时在L2列表中记录(IDi, Ri, Pi, h1i).

(4)部分私钥询问: A1询问用户Ni的部分私钥, 分两种情况讨论:

1)如果i=n, 停止询问, 终止模拟过程;

2)如果in, 随机选择zi, 并计算Zi=ziPRi=ziPh1iP0, 记录到L3表中.

(5)公钥询问: A1询问用户Ni的公钥, 分两种情况讨论:

1)如果in, 查找用户Ni的公钥(Ri, Pi, Zi);

2)如果i=n, D随机选择ri, 计算Ri, 查找Pi, 计算Zi, 同时更新L2表;

(6) H2询问: 输入(m, Pi, Zi, P0, S, Ti, Di), 如果L4列表中包含(m, Pi, Zi, P0, S, Ti, Di, h2i), 则返回h2i, 否则D随机选择h2i $ Z_q^ * $ A1, 同时在L4列表中记录(m, Pi, Zi, P0, S, Ti, Di, h2i).

(7)部分签名询问: A1使用用户身份IDiD询问消息m的签名. 如果i=n, 则停止签名, 停止模拟过程; 如果in, 则D查询L2表和L3表, 计算 $ {w_i} = {\left( {{{\textit{z}}_i} + {x_i}{h_{1i}}} \right)^{ - 1}} $ , 得到用户Ni的完整公私钥, 则用户Ni对消息m的签名为 $ Sig{n_i} = \left( {{x_i}{h_{2i}} + {d_i}} \right){w_i} $ .

(8)伪造签名: 通过上述询问过程得到一个完整签名 $ ({\sigma _n}, {D_n}) $ , D验证式(17)是否成立来判断签名结果:

$\begin{aligned} &e\left( {{\sigma _n}, P} \right) \\&=e(({d_n} + {h_{2n}}{x_n}){({r_n} + s{g_n}Y + {x_n}{h_{1n}})^{ - 1}}, P)\prod\limits_{i = 1}^{n - 1} {e({\sigma _{n - 1}}, P)} \end{aligned}$ (17)

若成立, 则根据分叉引理, 选择不同的哈希函数 $ h_{2n}' $ , 通过重放A1, D可以得到对消息m的另一个有效签名 $ (\sigma _n', {D_n}) $ , 验证式(18)是否成立:

$\begin{aligned} &e\left( {\sigma _n', P} \right) \\ &=e(({d_n} + h_{2n}'{x_n}){({r_n} + s{g_n}Y + {x_n}{h_{1n}})^{ - 1}}, P)\prod\limits_{i = 1}^{n - 1} {e({\sigma _{n - 1}}, P)} \end{aligned}$ (18)

若成立, 则式(17)和式(18)相除可求解sYabP, 从而解决CDH困难问题, 这与定理1矛盾, 因此A1无法伪造签名.

定理2. 在随机预言机模型下, 如果攻击者A2能够以不可忽略的概率伪造出多重签名, 则挑战者D可以通过A2解决ECDLP问题.

假设攻击者拥有最大优势已经获得n–1个签名者的签名, 即攻击者已经获得了n–1签名者的私钥, 可以伪造出这n–1个签名者的签名, 为了证明本方案难以抵抗伪造性, 攻击者需要在多项式时间内以一个不可忽略的概率伪造出最后一个签名者的签名. D已知用户n的公钥UP, 如果可以求出u, 则可以通过A2解决ECDLP问题.

模拟过程如下:

挑战者D选择椭圆曲线上的点构成阶为q的循环群GGT, 其中, q为素数, G为加法群, GT为乘法群, 双线性映射e: G×GGT. 选择两个安全的哈希函数H1H2, 其中, H1: {0, 1}*×G×G $ Z_q^ * $ , H2: {0, 1}*→ $ Z_q^ * $ . D随机选择 $ s \in Z_q^ * $ , 计算P0=sP, 其中, P为群G的一个生成元, s为系统主密钥, P0为系统公钥, D维护4张表: L1对应用户的秘密值询问, L2L4分别对应哈希函数H1H2的询问, L3对应用户的部分私钥询问, 将params={G, GT, q, e, H1, H2, P, P0}和系统主密钥s发送给攻击A2, A2进行如下询问:

(1) H1询问: D构造询问用户的身份集合S={ID1, ID2, …, IDi, …, IDqc}, A2输入(IDi, Ri, Pi), 如果L2列表中包含(IDi, Ri, Pi, h1i), 则Dh1i返回给A2, 如果L2列表中没有相关信息, 则D随机选择h1i $ Z_q^ * $ A2, 同时在L2列表中记录(IDi, Ri, Pi, h1i).

(2)秘密值询问: A2询问IDi的秘密值, 分两种情况讨论:

1)如果in, D选择随机数 $ {x_i} \in Z_q^ * $ , 计算Pi=xiP, 将xi发送给A2, 在L1 列表中记录(IDi, xi, Pi).

2)如果i=n, 令PiU , 将(IDi, $ \bot $ , Pi)记录到表L1中.

(3)部分私钥询问: A2询问IDi的部分私钥zi, D选择两个随机数 $ {a_i}, {b_i} \in Z_q^ * $ , 其中, riai, h1ibi, 计算Ri=riP, 将(IDi, Ri, h1i)记录到表L2中, 计算zi=ri+sh1i, 计算Zi=ziP, 在L3列表中记录 (IDi, zi, Zi).

(4)公钥询问: A2询问IDi的公钥, D查询表L1L2L3, 将完整公钥发给A2.

(5) H2询问: A2输入(m, Pi, Zi, P0, S, Ti, Di), 如果L4列表中包含(m, Pi, Zi, P0, S, Ti, Di, h2i), 则返回h2i, 否则D随机选择h2i $ Z_q^ * $ A2, 同时在L4列表中记录(m, Pi, Zi, P0, S, Ti, Di, h2i).

(6)部分签名询问: A2使用用户身份IDiD询问消息m的签名. 如果i=n, 则停止签名, 停止模拟过程; 如果in, 则D查询L2表和L3表, 计算 $ {w_i} = {\left( {{{\textit{z}}_i} + {x_i}{h_{1i}}} \right)^{ - 1}} $ , 得到用户Ni的完整公私钥, 则用户Ni对消息m的签名为 $ Sig{n_i} = \left( {{x_i}{h_{2i}} + {d_i}} \right){w_i} $ .

(7)伪造签名: 通过上述询问过程得到完整签名 $ ({\sigma _n}, {D_n}) $ , D通过验证式(19)是否成立来判断签名:

$\begin{split} &e\left( {{\sigma _n}, P} \right) \\ & =e(({d_n}P + {h_{2n}}\overline x P){({z_n}P + \overline x P{h_{1n}})^{ - 1}}, P)\prod\limits_{i = 1}^{n - 1} {e({\sigma _{n - 1}}, P)} \end{split}$ (19)

若成立, 则根据分叉引理, 选择不同的哈希函数 $ h_{2n}' $ , 通过重放A2, D可以得到对消息m的另一个有效签名 $ (\sigma _n', {D_n}) $ , 验证式(20)是否成立:

$\begin{split} &e\left( {\sigma _n', P} \right) \\ & =e(({d_n}P + h_{2n}'\overline x P){({{\textit{z}}_n}P + \overline x P{h_{1n}})^{ - 1}}, P)\prod\limits_{i = 1}^{n - 1} {e({\sigma _{n - 1}}, P)} \end{split}$ (20)

若成立, 则式(19)和式(20)相除可求解u的值, 从而解决ECDLP困难问题, 这与定理2矛盾, 因此攻击者A2无法伪造签名.

4.2.2 抗中间人攻击

在BGP中, 恶意的中间人通过伪造路由信息的方式, 使其在控制层面的转发路径和真实传输路径不一致, 导致面临威胁. 本方案中发布或者转发路由信息的自治系统需要向KGC注册身份信息, KGC通过运营商验证自治系统的合法身份后才会向其分配部分私钥和完整的公钥. 其次在路由传递过程中包含了自治系统的身份集合{ID1, ID2, …, IDi, …, IDn}, 恶意的中间人无法伪造身份信息. 当中间人使用新的身份ID进行签名后, 下一个自治系统会通过原始的身份集合进行验证. 由于签名时的随机数发生改变, 根据无证书有序多重签名方案的验证方式, 下一个自治系统将无法验证, 则会停止签名, 并将验证失败的路由条目丢弃. 本方案通过签名的方式确保路由条目没有被篡改, 当攻击者和受害者前缀网络所在的自治系统相邻时同样满足上述的验证过程, 因此本方案也解决文献[5]方案存在的不足. 同时本方案存在用来表明签名顺序的0-1字符串, 每个自治系统都有固定的签名顺序, 各个自治系统不能擅自改变签名顺序来伪造签名.

5 结论

本文针对边界网关路由协议存在的中间人攻击威胁, 将无证书公钥密码体制和有序多重签名结合, 提出一种无证书的有序多重签名方案, 并对私钥生成过程和签名过程进行改进. 与同类型方案相比, 本文提出的签名方案在计算效率上有一定的提升, 同时能够抵抗BGP的中间人攻击.

参考文献
[1]
Conti M, Dragoni N, Lesyk V. A survey of man in the middle attacks. IEEE Communications Surveys & Tutorials, 2016, 18(3): 2027-2051.
[2]
Kent S, Lynn C, Seo K. Secure border gateway protocol (S-BGP). IEEE Journal on Selected Areas in Communications, 2000, 18(4): 582-592. DOI:10.1109/49.839934
[3]
贾佳, 延志伟, 耿光刚, 等. 一种改进的BGP路由源认证机制. 计算机系统应用, 2017, 26(1): 240-245. DOI:10.15888/j.cnki.csa.005541
[4]
Liu YJ, Su JS, Chang RKC. LDC: Detecting BGP prefix hijacking by load distribution change. 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum. Shanghai: IEEE, 2012. 1197–1203.
[5]
黎松, 段海新, 李星. 域间路由中间人攻击的实时检测系统. 清华大学学报(自然科学版), 2015, 55(11): 1229–1234.
[6]
Sermpezis P, Kotronis V, Gigis P, et al. ARTEMIS: Neutralizing BGP hijacking within a minute. IEEE/ACM Transactions on Networking, 2018, 26(6): 2471-2486. DOI:10.1109/TNET.2018.2869798
[7]
Li Q, Zhang XW, Zhang X, et al. Invalidating idealized BGP security proposals and countermeasures. IEEE Transactions on Dependable and Secure Computing, 2015, 12(3): 298-311. DOI:10.1109/TDSC.2014.2345381
[8]
Alkadi OS, Moustafa N, Turnbull B, et al. An ontological graph identification method for improving localization of IP prefix hijacking in network systems. IEEE Transactions on Information Forensics and Security, 2020, 15: 1164-1174. DOI:10.1109/TIFS.2019.2936975
[9]
邓海莲, 刘宇靖, 葛一漩, 等. 域间路由异常检测技术研究. 信息网络安全, 2019(11): 63-70.
[10]
Al-Riyami SS, Paterson KG. Certificateless public key cryptography. 9th International Conference on the Theory and Application of Cryptology and Information Security. Taipei: Springer, 2003. 452–473.
[11]
陈亚萌, 程相国, 王硕, 等. 基于双线性对的无证书群签名方案研究. 信息网络安全, 2017(3): 53-58. DOI:10.3969/j.issn.1671-1122.2017.03.009
[12]
刘帅, 陈建华. 无双线性对的无证书签名方案及其在配电网中的应用. 计算机科学, 2020, 47(9): 304-310. DOI:10.11896/jsjkx.200500002
[13]
罗文俊, 李长英. 一种不含双线性对的无证书有序多重签名方案. 计算机应用研究, 2012, 29(4): 1427-1429. DOI:10.3969/j.issn.1001-3695.2012.04.063
[14]
秦艳琳, 吴晓平. 高效的无证书有序多重签名方案. 通信学报, 2013, 34(7): 105–110.
[15]
许艳, 黄刘生, 田苗苗, 等. 可证安全的高效无证书有序多重签名方案. 通信学报, 2014, 35(11): 126–131.
[16]
杜红珍, 温巧燕. 改进的无证书有序多重签名方案. 通信学报, 2015, 36(10): 56-61. DOI:10.11959/j.issn.1000-436x.2015196
[17]
孙玉, 刘贵全. 安全高效无证书有序多重签名方案. 重庆邮电大学学报(自然科学版), 2016, 28(3): 431-434, 442.
[18]
Karati A, Islam SKH, Biswas GP. A pairing-free and provably secure certificateless signature scheme. Information Sciences, 2018, 450: 378–391.
[19]
He DB, Zeadally S, Xu BW, et al. An efficient identity-based conditional privacy-preserving authentication scheme for vehicular ad hoc networks. IEEE Transactions on Information Forensics and Security, 2015, 10(12): 2681-2691. DOI:10.1109/TIFS.2015.2473820