基于分治策略的BGP安全機(jī)制

王濱，安金梁，吳春明，蘭巨龍

（1. 浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310027；2. 浙江工商大學(xué) 信息與電子工程學(xué)院，浙江 杭州 310018；3. 國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002； 4. 河南科技學(xué)院 信息工程學(xué)院，河南 新鄉(xiāng) 453003）

1 引言

域間路由系統(tǒng)作為整個(gè)互聯(lián)網(wǎng)的支柱，其安全性具有重要的戰(zhàn)略意義。作為目前互聯(lián)網(wǎng)唯一的域間路由協(xié)議——BGP(border gateway protocol)協(xié)議[1]在設(shè)計(jì)當(dāng)初并沒有考慮到任何安全因素。由于BGP本身存在著巨大的安全隱患[2]，近年來，很多的域間路由安全事件都是由BGP的安全脆弱性引起的。因此，提高BGP協(xié)議的安全性是解決域間路由安全的重要途徑，也一直是人們研究的熱點(diǎn)問題。

目前，針對(duì) BGP的脆弱性已有不少公司和個(gè)人提出一些安全擴(kuò)展方案。這些方案各有優(yōu)劣，大體可以分為以下2類。

1) 與PKI相關(guān)的方案，即在BGP的基礎(chǔ)上結(jié)合PKI來對(duì)平臺(tái)中的每一個(gè)實(shí)體提供授權(quán)聲明和身份認(rèn)證，其安全能力相對(duì)比較強(qiáng)，但實(shí)現(xiàn)開銷太大、部署困難，如S-BGP[3]和psBGP[4]等。

2) 與PKI無關(guān)的方案，如soBGP[5]和Listen and Whisper機(jī)制[6]等，這些安全機(jī)制的安全性相對(duì)而言較弱，但易于在實(shí)際環(huán)境中部署。

本文在研究了文獻(xiàn)[7]中作者提出的一種新的BGP安全機(jī)制：SE-BGP。通過對(duì)該機(jī)制進(jìn)行形式化描述后進(jìn)行分析，發(fā)現(xiàn)SE-BGP存在明顯的安全漏洞。為了克服SE-BGP存在的安全問題，本文提出了一種基于 RSA順序聚合簽名的算法，該算法可以有效抵抗重放攻擊。最后，使用該簽名算法和基于 AS聯(lián)盟的思想設(shè)計(jì)了一種新的 BGP安全機(jī)制：SA-BGP，該方案可以大規(guī)模地降低單個(gè)節(jié)點(diǎn)的證書存儲(chǔ)規(guī)模，減少路由器處理負(fù)載和傳輸?shù)男畔⒘?，并且該機(jī)制能夠有效地驗(yàn)證AS宣告的NLRI的正確性和AS宣告的路徑屬性的真實(shí)性。

2 SE-BGP概述

文獻(xiàn)[7]中給出了一種新的 BGP安全機(jī)制：SE-BGP，該機(jī)制根據(jù)網(wǎng)絡(luò)中AS節(jié)點(diǎn)總是聚集成不同的集合，集合中的節(jié)點(diǎn)通過少數(shù)高度數(shù)節(jié)點(diǎn)與集合外的節(jié)點(diǎn)相連，并且高度數(shù)節(jié)點(diǎn)之間具有很高的聚集度的特點(diǎn)，生成AS聯(lián)盟并確立聯(lián)盟中的關(guān)鍵節(jié)點(diǎn)，且每個(gè)AS聯(lián)盟內(nèi)都有一個(gè)認(rèn)證中心CA，安全AS聯(lián)盟中關(guān)鍵節(jié)點(diǎn)相連的其他安全AS聯(lián)盟中關(guān)鍵節(jié)點(diǎn)也需要在這個(gè)安全AS聯(lián)盟中進(jìn)行認(rèn)證。本節(jié)將對(duì)SE-BGP機(jī)制中的認(rèn)證算法進(jìn)行簡(jiǎn)單地描述。

2.1 TTM模型

TTM基于分布式的PKI結(jié)構(gòu)。與傳統(tǒng)的網(wǎng)狀結(jié)構(gòu)不同，每個(gè)CA之間并不相互認(rèn)證證書，其信任關(guān)系的傳遞是通過關(guān)鍵節(jié)點(diǎn)的特殊能力實(shí)現(xiàn)的。在如圖1所示的網(wǎng)絡(luò)中假設(shè)AS 聯(lián)盟和關(guān)鍵節(jié)點(diǎn)都已經(jīng)生成完畢，具體如圖1所示。關(guān)鍵節(jié)點(diǎn)1T、2T同時(shí)擁有2套公鑰證書，即1T、2T都具有1SA和2SA 中的公鑰證書。其中，Sk(m) 表示節(jié)點(diǎn)k對(duì)其發(fā)布的信息m進(jìn)行簽名，Vk(S)表示用節(jié)點(diǎn)k的公鑰對(duì)簽名S進(jìn)行驗(yàn)證。

假設(shè) S A2中的節(jié)點(diǎn)c需發(fā)布信息M到 S A1中的節(jié)點(diǎn)b。當(dāng)T2收到c的信息，通過認(rèn)證后，用 S A1中的CA分配的密鑰對(duì)M進(jìn)行簽名，簽名的內(nèi)容記為Mc-T2。當(dāng)T1收到T2傳遞的信息時(shí)，用對(duì)應(yīng)的公鑰驗(yàn)證M，其用T2在 SA1中的公鑰驗(yàn)證M=VT2[ST2(Mc-T2)]，若通過驗(yàn)證，則對(duì)M用自己在 S A1中的私鑰進(jìn)行簽名，簽名的內(nèi)容記為Mc-T1。當(dāng)節(jié)點(diǎn)b收到明文M'和 2個(gè)簽名ST

1(Mc-T1)、ST2(Mc-T2)后，節(jié)點(diǎn)b接受發(fā)布信息M的條件為M' =VT1[ST1(Mc-T1)]=VT2[ST2(Mc-T2)]。

圖1 AS聯(lián)盟連接

2.2 SE-BGP新增的屬性

SE-BGP需要增加2個(gè)屬性。

1) AS_Security_Source用于地址源認(rèn)證，用來存放源節(jié)點(diǎn)以及關(guān)鍵節(jié)點(diǎn)對(duì)于地址源信息的簽名，其中最多包含2個(gè)簽名，只有源節(jié)點(diǎn)和關(guān)鍵節(jié)點(diǎn)才會(huì)更新AS_Security_Source。

2) AS_Security_Path用于路徑認(rèn)證，用來存放任何節(jié)點(diǎn)對(duì)于路徑信息的簽名，其需要簽名的路徑信息包括已經(jīng)過的路徑(含本身)、下一節(jié)點(diǎn)和時(shí)間等其他需簽名的信息，任何節(jié)點(diǎn)都會(huì)更新AS_Security_Path。

2.3 SE-BGP認(rèn)證和更新算法

SE-BGP主要解決對(duì)于不同AS 聯(lián)盟之間，如何通過關(guān)鍵節(jié)點(diǎn)來進(jìn)行認(rèn)證。對(duì)于關(guān)鍵節(jié)點(diǎn)，由于其擁有2套以上的公鑰證書，因此其使用的原則為：用來源節(jié)點(diǎn)的AS聯(lián)盟內(nèi)的公鑰證書進(jìn)行認(rèn)證，用目的AS節(jié)點(diǎn)聯(lián)盟內(nèi)的私鑰簽名。

當(dāng)某節(jié)點(diǎn)需要發(fā)布一條UPDATE信息時(shí)，它需要同時(shí)修改AS_Security_Source和AS_Security_Path屬性。當(dāng)節(jié)點(diǎn)收到一條 UPDATE信息時(shí)，首先對(duì)源地址信息和路徑信息進(jìn)行認(rèn)證，然后對(duì) AS_Security_Source和AS_Security_Path屬性做相應(yīng)的修改，并向下傳遞。具體描述如下。

1) 查找AS聯(lián)盟內(nèi)的完整路徑，檢查其狀態(tài)，若不正確，則拋棄該路徑，并結(jié)束算法。

2) 對(duì)地址源信息進(jìn)行認(rèn)證和更新。

① 地址源認(rèn)證：若AS_Security_Source中只有一個(gè)簽名(源節(jié)點(diǎn)簽名)，則檢查證書；若AS_Security_Source中只有 2個(gè)簽名(含源節(jié)點(diǎn)簽名)，則驗(yàn)證簽名是否一致并檢查證書；若AS_Security_Source中只有2個(gè)簽名(不含源節(jié)點(diǎn)簽名)，則驗(yàn)證簽名是否一致。

② 地址源認(rèn)證簽名更新：若目的 AS和來源AS節(jié)點(diǎn)不在同一個(gè) AS聯(lián)盟內(nèi)，則 AS_Security_Source中的簽名隊(duì)列前移，并將自己對(duì)于驗(yàn)證后的地址源信息簽名加入到隊(duì)列中；否則，若簽名隊(duì)列為 1，則隊(duì)列前移，并將自己對(duì)于驗(yàn)證后的地址源信息簽名加入到隊(duì)列尾；若簽名隊(duì)列為 2，則將自己對(duì)于驗(yàn)證后的地址源信息簽名替換隊(duì)列尾；

3) 對(duì)路徑信息進(jìn)行認(rèn)證和更新。

① 對(duì) AS_Security_Path 中的簽名進(jìn)行認(rèn)證，如果不正確，則退出算法。

② 若目的來源AS為相鄰安全AS聯(lián)盟的關(guān)鍵節(jié)點(diǎn)，且目的節(jié)點(diǎn)為本AS聯(lián)盟內(nèi)節(jié)點(diǎn)，則將AS_Security_Source中的簽名隊(duì)列清空，只保留最后一個(gè)元素，將自己對(duì)于驗(yàn)證后的地址源信息簽名并加入到隊(duì)列中；否則，將自己對(duì)于驗(yàn)證后的地址源信息簽名并加入到隊(duì)列中。對(duì)于非關(guān)鍵節(jié)點(diǎn)，由于只有本安全AS 聯(lián)盟內(nèi)的證書和密鑰，因此只需處理本AS聯(lián)盟內(nèi)節(jié)點(diǎn)和相鄰AS聯(lián)盟的關(guān)鍵節(jié)點(diǎn)的認(rèn)證信息。

3 SE-BGP安全性分析

本節(jié)將給出SE-BGP的形式化描述，并基于此形式化描述對(duì)其進(jìn)行安全性分析。

3.1 SE-BGP形式化描述

文獻(xiàn)[7]作者給出的基于TTM模型的認(rèn)證和更新算法的形式化描述如下。假設(shè)關(guān)鍵節(jié)點(diǎn)1T所在的聯(lián)盟中的節(jié)點(diǎn)C需要發(fā)送一個(gè)SE-BGP數(shù)據(jù)分組給關(guān)鍵節(jié)點(diǎn)4T所在的聯(lián)盟中的節(jié)點(diǎn)D，數(shù)據(jù)分組需要依次經(jīng)過關(guān)鍵節(jié)點(diǎn)1T、2T、3T、4T，4個(gè)關(guān)鍵節(jié)點(diǎn)呈串接關(guān)系。則每個(gè)關(guān)鍵節(jié)點(diǎn)分別擁有其相鄰關(guān)鍵節(jié)點(diǎn)所在AS聯(lián)盟內(nèi)的認(rèn)證中心CA頒發(fā)的證書。另外，形式化描述不考慮聯(lián)盟內(nèi)的認(rèn)證，僅僅考慮關(guān)鍵節(jié)點(diǎn)間的認(rèn)證。

相關(guān)符號(hào)說明如下。path：數(shù)據(jù)分組經(jīng)過的路徑；time：發(fā)送數(shù)據(jù)分組時(shí)的時(shí)間；kCAi-T：聯(lián)盟i的 CA為用戶T頒發(fā)證書的公鑰；：聯(lián)盟i的CA為用戶T頒發(fā)證書的私鑰；[M]k：表示對(duì)消息M用密鑰k進(jìn)行加密或簽名運(yùn)算；CrtU：用戶U的數(shù)字證書。

算法的形式化描述如下。

3.2 SE-BGP的安全性分析

SE-BGP存在以下的安全問題。

1) 設(shè)計(jì)的算法中存在冗余。按照文獻(xiàn)中認(rèn)證和更新算法的描述AS_Security_Source中的2個(gè)簽名，其中第一個(gè)簽名：源節(jié)點(diǎn)所在的聯(lián)盟中的關(guān)鍵節(jié)點(diǎn)對(duì)信源地址的簽名，將一直不被替換，但是該簽名在第二跳以后就不具有任何的認(rèn)證作用了，因?yàn)楣?jié)點(diǎn)3T不和1T相連，所以3T得不到用戶C的證書，故無法驗(yàn)證這個(gè)簽名，所以第二跳以后第一個(gè)簽名就成為一個(gè)冗余。

2) 算法基于對(duì)關(guān)鍵節(jié)點(diǎn)的完全信任，所以無法抵御主動(dòng)攻擊敵手發(fā)起的偽造攻擊。

①任何傳輸路徑上的關(guān)鍵節(jié)點(diǎn)都可以篡改或偽造路徑信息；算法協(xié)議中2T發(fā)送給3T的消息應(yīng)該是明文消息M和{[ ,path+但是如果2T是一個(gè)主動(dòng)攻擊者，那么可以隨意地修改路徑信息并對(duì)修改后的信息進(jìn)行簽名得到，由于該簽名的生成者是內(nèi)部攻擊者，其擁有合法的證書，并且下一跳節(jié)點(diǎn)無法驗(yàn)證，所以下一跳節(jié)點(diǎn)將接受該簽名。

②每個(gè)關(guān)鍵節(jié)點(diǎn)都可以任意偽造并發(fā)布虛假的關(guān)于非本AS聯(lián)盟內(nèi)節(jié)點(diǎn)的UPDATE消息；例如圖1中的關(guān)鍵節(jié)點(diǎn)3T可以任意偽造關(guān)于非3SA內(nèi)節(jié)點(diǎn)的虛假的UPDATE消息，進(jìn)行簽名后發(fā)送出去，但是其下一跳節(jié)點(diǎn)假設(shè)為4T，由于它對(duì)節(jié)點(diǎn)3T是完全信任的，所以只要驗(yàn)證這個(gè)消息是不是節(jié)點(diǎn)3T的簽名，如果是，就會(huì)接受并轉(zhuǎn)發(fā)出去。

3.3 總結(jié)

通過上面對(duì)作者提出的算法的安全性分析，可以看到，BGP協(xié)議中使用作者提出的安全機(jī)制后和沒有添加安全機(jī)制的協(xié)議安全性大致相同，SE-BGP僅僅比BGP協(xié)議增加了當(dāng)發(fā)現(xiàn)虛假UPDATE消息后可以進(jìn)行追查是哪個(gè)節(jié)點(diǎn)發(fā)送了虛假信息的功能。但是，就危害程度而言，SE-BGP比不添加任何安全機(jī)制的BGP更大，因?yàn)橹鲃?dòng)攻擊對(duì)協(xié)議來說具有更大的危險(xiǎn)性，在網(wǎng)絡(luò)環(huán)境下，當(dāng)通信各方彼此信賴時(shí)，這種攻擊對(duì)協(xié)議的威脅就顯得更為嚴(yán)重，因?yàn)楣粽呤且粋€(gè)合法用戶。通過以上的分析可以看到，TTM模型不適合用來設(shè)計(jì)安全域間路由協(xié)議。

4 SA-BGP認(rèn)證算法

雖然通過第3節(jié)的分析可以看到，文獻(xiàn)[7]中給出的SE-BGP存在明顯的安全漏洞，但是并不意味著利用AS結(jié)構(gòu)的Rich-Club 特性生成AS聯(lián)盟的不能設(shè)計(jì)出具有較高安全性和減少證書規(guī)模的BGP安全機(jī)制，本節(jié)將利用AS結(jié)構(gòu)的Rich-Club特性生成 AS聯(lián)盟，并設(shè)計(jì)一種新的 BGP安全機(jī)制――SA-BGP (secure aggregation BGP)。

4.1 SA-BGP概述

SA-BGP機(jī)制利用文獻(xiàn)[7]中提出的AS聯(lián)盟生成算法，將網(wǎng)絡(luò)中的AS分成若干的聯(lián)盟，整個(gè)網(wǎng)絡(luò)擁有一個(gè)管理所有關(guān)鍵節(jié)點(diǎn)的中心CA，相關(guān)定義如下。

定義1 AS 聯(lián)盟：所謂 AS 聯(lián)盟指的是一組AS節(jié)點(diǎn)，這組AS節(jié)點(diǎn)只通過少數(shù)的節(jié)點(diǎn)與組外其他節(jié)點(diǎn)相連和轉(zhuǎn)發(fā)流量；這些少數(shù)的節(jié)點(diǎn)也稱為“關(guān)鍵節(jié)點(diǎn)”，每個(gè)AS 聯(lián)盟內(nèi)有一個(gè)獨(dú)立的PKI系統(tǒng)，可以為該聯(lián)盟內(nèi)的節(jié)點(diǎn)頒發(fā)證書，每一個(gè)關(guān)鍵節(jié)點(diǎn)除了擁有自己聯(lián)盟頒發(fā)的證書外還擁有中心CA頒發(fā)的數(shù)字證書。

定義2 中心CA：為所有的關(guān)鍵節(jié)點(diǎn)頒發(fā)證書，所有的關(guān)鍵節(jié)點(diǎn)都可以在其上查詢到其他關(guān)鍵節(jié)點(diǎn)的證書。

定義3AS_Security_Path（ASP）屬性：用于地址源認(rèn)證和路徑認(rèn)證，用來存放所有經(jīng)過路徑上關(guān)鍵節(jié)點(diǎn)相關(guān)信息的簽名，關(guān)鍵節(jié)點(diǎn)需要簽名的信息包括關(guān)鍵節(jié)點(diǎn)的身份信息、下一節(jié)點(diǎn)和時(shí)間戳信息。

4.2 基于RSA算法的聚合簽名算法

S-BGP和SE-BGP均使用DSA算法作為簽名算法，主要原因是 DSA算法產(chǎn)生的簽名短，但是其驗(yàn)證簽名速度慢，而且還需要進(jìn)行多步驟的運(yùn)算，所以 DSA算法不適用于本來收斂速度就緩慢的BGP類協(xié)議，故SA-BGP使用認(rèn)證速度很快RSA算法作為基本簽名算法。

聚合簽名[8]就是一種能夠?qū)個(gè)不同的用戶對(duì)N個(gè)不同的信息進(jìn)行的簽名聚合成一個(gè)短簽名的數(shù)字簽名算法。目前，已經(jīng)有許多的學(xué)者提出了各種不同的聚合簽名算法[8～10]，其中還有學(xué)者將聚合簽名算法應(yīng)用于安全路由[11]。但是這些聚合簽名算法大都是基于雙線性映射，由于雙線性映射要使用對(duì)運(yùn)算[12～14]速度較慢，且理論研究還不是很成熟，所以文獻(xiàn)[15]給出了一種基于RSA算法的多簽名算法，但是其存在安全問題：無法抵御重放攻擊，下面給出一個(gè)可抵御重放攻擊的基于RSA算法的聚合簽名算法。

在基于RSA簽名算法中，假設(shè)每個(gè)用戶U擁有數(shù)字證書CrtU和其對(duì)應(yīng)的公鑰和私鑰算法分為簽名和驗(yàn)證2部分，具體運(yùn)算過程如下。

1) 聚合簽名：假設(shè)用戶T1,T2,… ,Tn分別對(duì)m1,m2,… ,mn進(jìn)行簽名，且假設(shè)信息的發(fā)送過程是從用戶T1到Tn，按序號(hào)依次進(jìn)行，用戶T1為初始簽名者，其首先計(jì)算（其中，r1為用戶生成的時(shí)間戳），并將(σ1，m1，r1)發(fā)送給T2，下面的用戶對(duì)應(yīng)的聚合簽名過程為：當(dāng)用戶Ti收到前面用戶發(fā)送來的σi-1和r1,m1,m2, … ,mi-1時(shí)，計(jì)算然后將{σi，(m1,m2,… ,mi)m1，r1}發(fā)送給用戶Ti+1。

2) 聚合簽名驗(yàn)證：當(dāng)用戶Ti+1收到前面用戶發(fā)送來的σi和r1,m1,m2,… ,mi時(shí)，首先驗(yàn)證時(shí)間戳r1的新鮮性，如果是新鮮的那么接著計(jì)算hi=H(r1,m1,m2,… ,mi)，然后計(jì)算σi-1=hi+ [σi]ki，依次計(jì)算hi-1、σi-2、…、h1、σ1，驗(yàn)證計(jì)算得到的h1是否等于 [σ1]k1，如果相等則接受簽名，否則拒絕該簽名。

該算法在基于 RSA問題的困難性假設(shè)下，可以證明方案在隨機(jī)預(yù)言(RO，random oracle)模型[16]下是安全的，并且可以有效地抵御重放攻擊。

4.3 SA-BGP的認(rèn)證算法

SA-BGP的認(rèn)證算法分為聯(lián)盟內(nèi)節(jié)點(diǎn)間的認(rèn)證和關(guān)鍵節(jié)點(diǎn)間的認(rèn)證，假設(shè)UPDATE數(shù)據(jù)分組為關(guān)鍵節(jié)點(diǎn)1T所在的AS聯(lián)盟中的節(jié)點(diǎn)1N產(chǎn)生，發(fā)送到關(guān)鍵節(jié)點(diǎn)nT所在的 AS聯(lián)盟中的節(jié)點(diǎn) 'lN，數(shù)據(jù)分組需要依次經(jīng)過1T所在的 AS聯(lián)盟內(nèi)的到達(dá)關(guān)鍵節(jié)點(diǎn)T1，然后數(shù)據(jù)分組需要經(jīng)過關(guān)鍵節(jié)點(diǎn)T2,… ,Tn-1到達(dá)目的關(guān)鍵節(jié)點(diǎn)T.n，數(shù)據(jù)分組需要在關(guān)鍵節(jié)點(diǎn)T.n所在的 AS聯(lián)盟內(nèi)依次經(jīng)過N'1, … ,N'l-1到達(dá)目的節(jié)點(diǎn)N'l。

4.3.1 聯(lián)盟內(nèi)節(jié)點(diǎn)之間的認(rèn)證

在同一個(gè)安全AS 聯(lián)盟內(nèi)，聯(lián)盟內(nèi)有可信的認(rèn)證中心 CA，所以聯(lián)盟內(nèi)的任何節(jié)點(diǎn)都可以獲取其他節(jié)點(diǎn)的地址證書和公鑰，具體認(rèn)證過程如下。

1)N1產(chǎn)生UPDATE報(bào)文向N2通告路由，此時(shí)將自己的AS號(hào)碼 A SN1加入到路由的路徑屬性中，這時(shí)AS_PATH= { ASN1}，并同時(shí)生成一個(gè)時(shí)間戳，計(jì)算和修改然后發(fā)送給下一跳關(guān)鍵節(jié)點(diǎn)N2。

2)N2收到N1的通告路由消息后，檢查 ASP屬性中時(shí)間戳r1的新鮮性，如果不新鮮則丟棄該數(shù)據(jù)分組，否則依據(jù)計(jì)算AS_PATH中的消息查找到其中節(jié)點(diǎn) A SN1的證書，并計(jì)算h1=H( ASN1,r1)，和[σ1]k1，看2個(gè)值是否相同，如果不相同拒絕簽名，否則接受簽名并使用自己的 AS號(hào) A SN2計(jì)算，然后修改，并將修改后的路由通告發(fā)送給下一跳節(jié)點(diǎn)N3。

…

i＋1)Ni+1收到Ni的通告路由消息后，檢查ASP屬性中時(shí)間戳r1的新鮮性，如果不新鮮則丟棄該數(shù)據(jù)分組，否則依據(jù)AS_PATH中的消息查找到其中節(jié)點(diǎn) A SN1, ASN2,… ,A SNi的證書，并計(jì)算hi=H(r1,ASN1, ASN2,…,ASNi)，然后計(jì)算σi-1=hi+[σi]ki，然后依次計(jì)算得到hi-1、σi-2、…、h1、σ1，驗(yàn)證計(jì)算得到的h1是否等于 [σ1]k1，如果不相等則拒絕該簽名，否則接受簽名并計(jì)算然后修改，并將修改后的路由通告發(fā)送給下一跳節(jié)點(diǎn)Ni+2；

…

m＋1)T1收到Nm的通告路由消息后，檢查ASP屬性中時(shí)間戳r1的新鮮性，并依據(jù)計(jì)算AS_PATH中的消息查找到其中節(jié)點(diǎn) A SN1, ASN2,… ,A SNm的證書，并按照聚合簽名驗(yàn)證算法的步驟驗(yàn)證簽名的正確性，如果正確，那么T1開始執(zhí)行關(guān)鍵節(jié)點(diǎn)之間的認(rèn)證算法。

4.3.2 關(guān)鍵節(jié)點(diǎn)之間的認(rèn)證

1)T1向T2通告路由，此時(shí)將自己的AS號(hào)碼AST1加入到路由的路徑屬性中，這時(shí)修改路徑屬性為AS_PATH= {path,AST1}，其中，path為數(shù)據(jù)分組在聯(lián)盟內(nèi)所走的路徑，計(jì)算路徑，然后發(fā)送給下一跳關(guān)鍵節(jié)點(diǎn)T2。

2)T2收到T1的通告路由消息后，檢查ASP屬性中時(shí)間戳r1的新鮮性，并依據(jù)計(jì)算AS_PATH中的消息查找到其中關(guān)鍵節(jié)點(diǎn) A ST1和N1的證書，并按照簽名驗(yàn)證算法驗(yàn)證 2個(gè)簽名，如果通過驗(yàn)證計(jì)算修改并將修改后的路由通告發(fā)送給下一跳節(jié)點(diǎn)T3；

…

i＋1)Ti+1收到Ti的通告路由消息后，檢查ASP屬性中時(shí)間戳r1的新鮮性，并依據(jù)AS_PATH中的消息查找到對(duì)應(yīng)關(guān)鍵節(jié)點(diǎn)的證書，按照簽名驗(yàn)證算法驗(yàn)證簽名，如果通過驗(yàn)證計(jì)算h'i+1=H(path,r1,修改，并將修改后的路由通告發(fā)送給下一跳節(jié)點(diǎn)Ti+2；

…

n)Tn收到Tn-1的通告路由消息后，檢查 ASP屬性中時(shí)間戳r1的新鮮性，并依據(jù)計(jì)算AS_PATH中的消息查找到其中節(jié)點(diǎn)的證書，并按照聚合簽名驗(yàn)證算法的步驟驗(yàn)證簽名的正確性，如果正確，那么Tn開始執(zhí)行聯(lián)盟內(nèi)節(jié)點(diǎn)之間的認(rèn)證算法，只是此時(shí)的AS_PATH= {path,path+, AS}，其中，path為數(shù)據(jù)分組在關(guān)鍵節(jié)點(diǎn)

Tn之間所走的路徑。

5 SA-BGP的安全性分析

SA-BGP具有了以下的安全性質(zhì)。

定理1 簽名是可認(rèn)證的。

證明 要證明簽名是可認(rèn)證的，就是證明簽名算法必須要保證合法用戶的正確簽名能夠被驗(yàn)證者認(rèn)證通過，即當(dāng)用戶收到未經(jīng)篡改的ASP={r,σi}和AS_PATH= { AS1,AS2,… ,A Si}，那么通過按照聚合簽名認(rèn)證算法就可以計(jì)算得到h1[σ1]k1。

計(jì)算過程如下。

1) 計(jì)算hi=H(r,AS1, AS2,… ,A Si)，計(jì)算得到[σi]ki=σi-1+hi，可得σi-1，然后進(jìn)行下面的計(jì)算。

2) 計(jì)算hi-1=H(r,AS1,AS2, … ,ASi-1)， 然后可以得到

i-1) 計(jì)算h2=H(r,AS1,AS2)，可得σ2=h2+[σ3]k3；

i) 計(jì)算h1=H(r,AS1)，σ1=h1+[σ2]k2，然后驗(yàn)證 [σ1]k1是否等于h1。

此時(shí)，只要用戶接收到數(shù)據(jù)未經(jīng)修改，那么最后一定可以得到h1= [σ1]k1。

綜上所述，每一個(gè)收到正確簽名的用戶都可以通過對(duì)簽名進(jìn)行認(rèn)證。

定理2 實(shí)現(xiàn)對(duì)數(shù)據(jù)源的安全認(rèn)證。

證明 實(shí)現(xiàn)對(duì)數(shù)據(jù)源的安全認(rèn)證，主要是要確認(rèn)宣告地址前綴的源 AS是否真正擁有該地址前綴，由于AS所擁有的數(shù)字證書對(duì)AS的組織號(hào)和所擁有的IP地址前綴進(jìn)行了綁定，而私鑰是只有合法的AS組織獨(dú)自擁有的，在聯(lián)盟內(nèi)傳輸時(shí)，當(dāng)路由通告到達(dá)關(guān)鍵節(jié)點(diǎn)時(shí)只有通過了關(guān)鍵節(jié)點(diǎn)的認(rèn)證它才會(huì)將該路由通告在關(guān)鍵節(jié)點(diǎn)之間傳輸，而簽名能夠被驗(yàn)證通過意味著該路由通告的發(fā)起者擁有其對(duì)應(yīng)的私鑰，這也就證明了AS的組織號(hào)是所擁有該IP地址前綴的合法用戶，從而實(shí)現(xiàn)了對(duì)數(shù)據(jù)源的安全認(rèn)證。

定理3 實(shí)現(xiàn)對(duì)AS_PATH的真實(shí)性和完整性的安全認(rèn)證。

證明 要證明對(duì) AS_PATH的真實(shí)性和完整性的安全認(rèn)證，即是要證明經(jīng)過惡意的節(jié)點(diǎn)修改或偽造的 AS_PATH，都是不能被下一跳節(jié)點(diǎn)安全認(rèn)證。假設(shè)某個(gè)惡意ASi將AS_PATH={AS1,AS2,… ,A Si}修改為AS_PATH= { AS1,…, AS'l,…,ASi}(l＜i)，那么無論其進(jìn)行簽名時(shí)使用的是修改過的還是沒有修改過的AS_PATH，其簽名均無法被下一跳的節(jié)點(diǎn)安全認(rèn)證。

假設(shè)惡意的節(jié)點(diǎn)簽名使用的是沒有修改過的AS_PATH，此時(shí)用戶接收到如下的簽名消息為ASP={r,σi}，經(jīng)過修改的路經(jīng)屬性為AS_PATH={AS1,…, A S'l,…, A Si}(l＜i)，下面用戶做如下的驗(yàn)證。

計(jì)算h'i=H(r,AS1,… ,AS'l,… ,ASi)，此時(shí)σ'i-1為由于h'i≠hi，所以σ'i-1≠σi-1，那么用戶在余下的步驟中計(jì)算得到σ'i-2≠σi-2、…、σ'1≠σ1，最后計(jì)算得到h1=[σ1]k1，顯然有h1≠[σ'1]k1，從而該簽名無法通過認(rèn)證，說明有人偽造了簽名或者修改了路徑屬性，故拒絕該簽名。從而實(shí)現(xiàn)了對(duì)AS_PATH的真實(shí)性和完整性的安全認(rèn)證。

上面證明了消息無論在關(guān)鍵節(jié)點(diǎn)之間還是在非關(guān)鍵節(jié)點(diǎn)之間的傳遞都是可以保證AS_PATH的真實(shí)性和完整性的安全認(rèn)證，下面考慮消息在第一個(gè)關(guān)鍵節(jié)點(diǎn)和第二個(gè)關(guān)鍵節(jié)點(diǎn)之間進(jìn)行傳遞時(shí)，第一個(gè)關(guān)鍵節(jié)點(diǎn)是否能夠篡改或偽造消息。

T1向T2通告路由時(shí)，傳輸?shù)南锳SP=其中h'1=H(path, AST1,r1)，σ'1=，此時(shí)T2可以驗(yàn)證σ'1和σ1，如果其中一個(gè)無法通過驗(yàn)證那么將會(huì)拒絕該消息，再由簽名的安全性保證了一旦認(rèn)證通過那么消息是真實(shí)的和有效的。

綜上所述，SA-BGP可以保證對(duì)AS_PATH的真實(shí)性和完整性的安全認(rèn)證。

定理4 AS的身份不能被冒充，簽名不可偽造。

證明 攻擊者要想冒充合法AS的身份或偽造其簽名，就必須要獲得合法AS的私鑰。假設(shè)攻擊者無法竊取到用戶私鑰，那么攻擊者要計(jì)算獲得用戶的私鑰這個(gè)問題等價(jià)于計(jì)算大素?cái)?shù)分解問題的難解性問題。

定理5 惡意節(jié)點(diǎn)無法進(jìn)行各種重放攻擊。

證明 由于每個(gè)合法的用戶在做簽名時(shí)都有時(shí)間戳r的參與，如果某惡意節(jié)點(diǎn)想要冒充用戶Ti+1，利用一個(gè)先前的簽名信息ASP={r,σi}和AS_PATH= { AS1, AS2,… ,A Si}發(fā)起重放攻擊，那么由于下一跳節(jié)點(diǎn)在收到該簽名信息后首先要驗(yàn)證時(shí)間戳r的新鮮性，因?yàn)楣粽弑仨氁獙⒃瓉淼臅r(shí)間戳r修改為當(dāng)前的時(shí)間戳r'，但是簽名σi是用時(shí)間戳r計(jì)算得到的，所以下一跳節(jié)點(diǎn)會(huì)通過驗(yàn)證算法最終拒絕該簽名，從而導(dǎo)致重放攻擊失敗。

另外，在時(shí)間戳的有效時(shí)間范圍內(nèi)，如果惡意節(jié)點(diǎn)發(fā)起重放攻擊， 由于惡意節(jié)點(diǎn)無法對(duì)時(shí)間戳及對(duì)應(yīng)的消息進(jìn)行修改(若修改，則修改后的簽名無法通過驗(yàn)證)，所以當(dāng)接受消息的節(jié)點(diǎn)收到之前已經(jīng)收到了帶有相同時(shí)間戳的消息(所有的時(shí)間戳都是不會(huì)相同的)，那么節(jié)點(diǎn)將會(huì)忽略這條消息，由此可見這樣的攻擊不會(huì)對(duì)網(wǎng)絡(luò)造成危害。

表1 SA-BGP 、SE-BGP和S-BGP的證書規(guī)模

綜上所述，惡意節(jié)點(diǎn)無法進(jìn)行重放攻擊。

6 可擴(kuò)展性分析

本節(jié)從使用SA-BGP將會(huì)給網(wǎng)絡(luò)中路由器需要的證書存儲(chǔ)規(guī)模和處理UPDATE成本2個(gè)方面來考察SA-BGP的可擴(kuò)展性。

6.1 路由器需要的證書存儲(chǔ)規(guī)模

對(duì)路由器需要的證書存儲(chǔ)空間的分析，主要考慮3個(gè)指標(biāo)：全網(wǎng)的證書規(guī)模C、單個(gè)AS 節(jié)點(diǎn)所需的證書規(guī)模Cs以及一個(gè)證書改變時(shí)所影響的AS范圍。假設(shè)互聯(lián)網(wǎng)中總的AS 節(jié)點(diǎn)的規(guī)模為N，rich 節(jié)點(diǎn)的范圍為β%。對(duì)于傳統(tǒng)的信任模型，有：C=N2，Cs=N，=N。

表1對(duì)比了SA-BGP、SE-BGP和S-BGP的證書規(guī)模。

通過表1看出，隨著網(wǎng)絡(luò)中AS數(shù)目的增多，采用SA-BGP比采用S-BGP將減少網(wǎng)絡(luò)中證書的規(guī)模，而且其證書規(guī)模和SE-BGP的證書規(guī)模幾乎相等。最關(guān)鍵的是采用SA-BGP將會(huì)大規(guī)模地降低單個(gè)節(jié)點(diǎn)存儲(chǔ)的證書數(shù)量，證書規(guī)模的減小不僅有利于規(guī)模的可擴(kuò)展性，而且會(huì)在很大程度上降低由于帶外控制而帶來的管理開銷。

6.2 仿真實(shí)驗(yàn)

本節(jié)使用SSFNet模擬器[17]在相同的網(wǎng)絡(luò)拓?fù)?、相同的BGP行為設(shè)置的情況下來評(píng)估采用各種安全機(jī)制給網(wǎng)絡(luò)帶來的時(shí)延和網(wǎng)絡(luò)的收斂時(shí)間[18]。在模擬中，采用了110個(gè)自治系統(tǒng)的網(wǎng)絡(luò)拓?fù)?，每個(gè)自治系統(tǒng)都只有一個(gè)邊界路由器構(gòu)成。每一個(gè) BGP發(fā)言者宣告2個(gè)前綴，網(wǎng)絡(luò)拓?fù)涫腔诨ヂ?lián)網(wǎng)路由表生成[19]。因?yàn)镮BSAS是基于聚合算法的，S-BGP基于數(shù)字證書的，而SA-BGP是采用基于數(shù)字證書的聚合簽名算法的，所以實(shí)驗(yàn)中分別模擬IBSAS、S-BGP和SA-BGP 3種安全機(jī)制。

基于相同的安全性仿真實(shí)驗(yàn)顯示，由于SA-BGP隨著參與簽名的節(jié)點(diǎn)數(shù)目的增加，SA-BGP對(duì)網(wǎng)絡(luò)的延時(shí)影響最小，當(dāng)有6個(gè)節(jié)點(diǎn)簽名時(shí)，SA-BGP密碼操作帶來的網(wǎng)絡(luò)延時(shí)僅為 S-BGP的 1/3，IBSAS的1/5。

圖2中比較了網(wǎng)絡(luò)中最大連接數(shù)節(jié)點(diǎn)從網(wǎng)絡(luò)中斷開，然后再重新連接到網(wǎng)絡(luò)中，網(wǎng)絡(luò)所需的平均收斂時(shí)間。

圖2 收斂時(shí)間

從以上的分析可以看出，隨著互聯(lián)網(wǎng)AS 規(guī)模的不斷擴(kuò)展，SA-BGP 的全網(wǎng)證書規(guī)模、單個(gè) AS節(jié)點(diǎn)所需的證書規(guī)模、造成的延時(shí)、處理開銷以及收斂時(shí)間都小于現(xiàn)有的相同安全級(jí)別的安全機(jī)制。因此，SA-BGP具有良好的規(guī)?？蓴U(kuò)展性。

7 結(jié)束語

本文研究了文獻(xiàn)[7]中提出的一種新的 BGP安全機(jī)制：SE-BGP。該安全機(jī)制利用互聯(lián)網(wǎng)的拓?fù)溥B接規(guī)律，采用局部PKI的認(rèn)證機(jī)制，雖然SE-BGP避免了全局集中式認(rèn)證所帶來的負(fù)面影響，大規(guī)模地降低了網(wǎng)絡(luò)中節(jié)點(diǎn)的證書存儲(chǔ)規(guī)模，但是由于其提出的TTM模型存在安全缺陷，所以使用TTM模型設(shè)計(jì)的安全路由機(jī)制也存在明顯的安全漏洞。

為了克服SE-BGP存在的安全漏洞，基于文獻(xiàn)[7]中提出的AS聯(lián)盟的思想，提出了一種基于RSA的聚合簽名算法，并使用該算法設(shè)計(jì)了一種新的BGP安全機(jī)制：SA-BGP，通過分析可以看到，SA-BGP導(dǎo)致的網(wǎng)絡(luò)中節(jié)點(diǎn)存儲(chǔ)的證書數(shù)量大致相同，但是其可以有效地驗(yàn)證AS宣告的網(wǎng)絡(luò)層可達(dá)信息(NLRI)的正確性和AS宣告的路徑屬性的真實(shí)性。最后通過仿真與現(xiàn)有的 BGP安全機(jī)制 IBSAS和S-BGP進(jìn)行比較，可以看到SA-BGP給網(wǎng)絡(luò)造成延時(shí)和傳輸信息量的增加比現(xiàn)有的安全機(jī)制都要小。

[1] REKHTER Y, LI T. A border gateway protocol 4 (BGP-4)[EB/OL].http://datatracker.ietf.org/doc/rfc4271/,2006.

[2] MURPHY S. BGP security vulnerabilities analysis[EB/OL]. http://datatracker.ietf.org/doc/rfc4272/,2006.

[3] KENT S, LYNN C, SEO K. Secure border gateway protocol(S-BGP)[J]. IEEE Journal on Selected Areas in Communications,2000, 18(4): 582-592.

[4] KRANAKIS E, OORSCHOT C. On inter-domain routing security and pretty secure BGP (psBGP)[J]. ACM Trans on Information and System Security, 2007,10(3):11.

[5] WHITE R. Securing BGP through secure origin BGP (soBGP)[J]. The Internet Protocol Journal, 2003,6(3):15-22.

[6] SNBRAMANIAN L, ROTH V, STOICA L,et al.Listen and whisper:security mechanisms for BGP[A]. Proc of the 1st Symposium on Networked Systems Design and Implementation[C]. San Francisco, CA,USA,2004.

[7] 胡湘江, 朱培棟, 龔正虎. SE-BGP:一種 BGP安全機(jī)制[J].軟件學(xué)報(bào),2008,19(1):167-176.HU X J, ZHU P D, GONG Z H. SE-BGP: an security[J]. Journal of Software, 2008, 19(1):167-176.

[8] BONEH D, GENTRY C, LYNN B,et al.Aggregate and verifiably encrypted signatures from bilinear maps[A]. EUROCRYPT 2003, volume 2656 of Lecture Notes in Computer Science[C]. Springer-Verlag,2003.416-423.

[9] GENTRY C, RAMZAN Z. Identity-based aggregate signatures[A].PKC 2006: 9th International Conference on Theory and Practice of Public Key Cryptography[C]. Springer-Verlag, 2006.257-273.

[10] LU S, OSTROVSKY R, SAHAI A,et al. Sequential aggregate signatures and multisignatures without random oracles[A]. EUROCRYPT 2006[C]. Springer-Verlag, 2006.465-485.

[11] BOLDYREVA A, GENTRY C, O’NEILL A,et al. Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing[A]. ACM CCS 07: 14th Conference on Computer and Communications Security[C]. 2007.276-285.

[12] KERINS T, MARNANE W P, POPOVICI E M,et al. Efficient hardware for the Tate pairing calculation in characteristic three[A]. Workshop on Cryptographic Hardware and Embedded Systems 2005(CHES 2005)[C]. Edinburgh, Scotland, 2005. 412-426.

[13] SCOTT M. Computing the tate pairing[A]. Proceedings of the RSA Conference: Topics in Cryptology-the Cryptographers' Track(CT-RSA 2005)[C]. Springer-Verlag, 2005.293-304.

[14] SCOTT M, BARRETO P S L M. Compressed pairings[A]. Proceedings of CRYPTO 2004[C]. Springer-Verlag, 2004.140-156.

[15] BONEH D, GENTRY C, LYNN B,et al. A survey of two signature aggregation techniques[J]. RSA Crypto Bytes, 2003, 6(2):1-10.

[16] BELLARE M, ROGAWAY P. Random oracles are practical: a paradigm for designing efficient protocols[A]. The 1st ACM Conference on Computer and Communications Security[C]. 1993.62-73.

[17] The SSFnet project[EB/OL]. http://www.ssfnet.org/homepage.html, 2006.

[18] 趙金晶,朱培棟,盧錫城. BGP收斂性及其對(duì)網(wǎng)絡(luò)性能影響的定量分析[J].通信學(xué)報(bào), 2007,28(8):24-33.ZHAO J J, ZHU P D, LU X C. Quantitative analysis of BGP convergence and its influence on network performance[J]. Journal on Communications, 2007,28(8):24-33.

[19] Multi-AS topologies from BGP routing tables[EB/OL]. http://www.ssfnet.org/Exchange/gallery/asgraph/index.html,2006.