一種安全網(wǎng)絡(luò)路由算法研究

趙巖　周欣欣　徐純森

摘要：路由算法是路由協(xié)議中的重要組成部分，采用何種算法往往決定了最終尋徑結(jié)果的優(yōu)劣。路由算法除了能夠?qū)π畔⑦M(jìn)行正確路由外還應(yīng)使路由器具有抵抗惡意攻擊的能力。文章在介紹了安全的網(wǎng)絡(luò)路由算法的設(shè)計(jì)目標(biāo)以及幾種采用加密技術(shù)的安全網(wǎng)絡(luò)路由算法的基礎(chǔ)上，提出了一種安全網(wǎng)絡(luò)路由算法，該算法通過(guò)公開密鑰機(jī)制，保證了Internet網(wǎng)絡(luò)中擴(kuò)散路由算法的安全性。

關(guān)鍵詞：網(wǎng)絡(luò)；路由算法；安全；加密

在Internet網(wǎng)絡(luò)上需要對(duì)信息進(jìn)行路由，每一個(gè)信息包無(wú)論是經(jīng)過(guò)網(wǎng)絡(luò)還是自治系統(tǒng)都需盡快由源端到達(dá)目的端。因此，目前在Internet上許多路由算法都被設(shè)計(jì)成使信息包通過(guò)網(wǎng)絡(luò)最短的路由算法。OSPF，RIP和IEGP這些網(wǎng)絡(luò)內(nèi)部路由算法都是根據(jù)諸如BGP，EGP的協(xié)議設(shè)計(jì)成。

然而，基于這些協(xié)議的算法都是不安全的。采取這些協(xié)議的路由器對(duì)惡意的攻擊防御能力很脆弱。因此，無(wú)論是否存在惡意攻擊，都需要采用安全的路由算法。

通常情況下，一個(gè)安全的網(wǎng)絡(luò)路由算法應(yīng)該能夠滿足以下目標(biāo)：（1）錯(cuò)誤檢測(cè)：算法應(yīng)該正確運(yùn)行，而且能夠檢測(cè)到危及算法安全的計(jì)算步驟。（2）容錯(cuò)能力：算法應(yīng)該使工作不正確的路由器產(chǎn)生的破壞降到最低限度。（3）鑒別能力：算法應(yīng)該能夠識(shí)別信息是來(lái)自于哪一個(gè)主機(jī)或路由器。（4）數(shù)據(jù)集成：算法應(yīng)該能夠確信接收到的信息與發(fā)出的信息一致。（5）實(shí)時(shí)性：算法應(yīng)該能夠確保所有目前處理的信息在有效時(shí)間范圍內(nèi)，防止重復(fù)攻擊。

當(dāng)然，不一定要求所有的信息都必須是加密的，可以通過(guò)對(duì)信息的敏感內(nèi)容進(jìn)行加密，這一點(diǎn)很容易做到，例如可以對(duì)應(yīng)用層的信息進(jìn)行加密。

1 相關(guān)工作

Perlman最早研究了網(wǎng)絡(luò)的路由安全問(wèn)題，他研究了在不完善的路由器上擴(kuò)散及最短路由算法的安全運(yùn)行問(wèn)題。其基本思想是在路由器中維持一個(gè)表格，表格利用公鑰加密體制，為每一個(gè)路由x分配一個(gè)公鑰/私有密鑰對(duì)，然后對(duì)一個(gè)路由器x發(fā)出的信息加密。這樣，任意路由器y都可鑒別來(lái)自于路由器x的信息。要設(shè)計(jì)一個(gè)安全的擴(kuò)散路由算法，這種基于簽名的方法顯然是可行的。此外，這一方法還可以用來(lái)設(shè)計(jì)一個(gè)安全的距離一向量路由算法。但研究表明，從實(shí)際的觀點(diǎn)來(lái)看，對(duì)所有的信息都加密效率不高。對(duì)一些著名路由算法中的簡(jiǎn)單的表格外觀和計(jì)算步驟進(jìn)行加密和解密既無(wú)必要，且運(yùn)算代價(jià)過(guò)高。

考慮到Perlman算法已具有很高的安全性，全文加密效率又不高。因此，許多其他算法采用散列法和快速加密工具相結(jié)合。此外，由于計(jì)算機(jī)運(yùn)行速度與安全問(wèn)題之間存在自然的平衡，需要考慮算法的實(shí)用性，包括不同的網(wǎng)絡(luò)可能遭到不同的惡意攻擊。

Cheung副采用了單一散列鏈方法以確保路由算法安全，這一方法要求路由器的時(shí)鐘是同步的。但有一個(gè)缺點(diǎn)，其路由器中的密鑰表不是實(shí)時(shí)的，只有在攻擊發(fā)生后才會(huì)探測(cè)到。

Hauser采用了多個(gè)散列鏈以標(biāo)識(shí)在鏈路狀態(tài)路由算法中不同的連接，從而避免了上訴缺陷，但多個(gè)散列鏈要求網(wǎng)絡(luò)中的路由器必須是同步的。文獻(xiàn)總結(jié)了一些靜態(tài)、動(dòng)態(tài)路由算法，并對(duì)其特性進(jìn)行了深入分析。

2 安全擴(kuò)散路由算法

2.1 擴(kuò)散路由算法

本文提出一種安全擴(kuò)散路由算法，其基本思想是通過(guò)公開密鑰體制為每一個(gè)路由器的相鄰節(jié)點(diǎn)分配共享密鑰，每一個(gè)中間節(jié)點(diǎn)在轉(zhuǎn)發(fā)消息的同時(shí)傳遞報(bào)文的加密密鑰達(dá)到鑒別目的。下面先說(shuō)明擴(kuò)散路由算法的具體實(shí)現(xiàn)過(guò)程，然后再提出引入安全策略的安全擴(kuò)散路由算法。

用G（V，E）表示網(wǎng)絡(luò)模型，其中，V代表網(wǎng)絡(luò)中路由器節(jié)點(diǎn)集合，E表示表示路由器節(jié)點(diǎn)之間邊的集合。我們假設(shè)，至少有2臺(tái)路由器同時(shí)受到攻擊時(shí)網(wǎng)絡(luò)才會(huì)癱瘓。網(wǎng)絡(luò)G中的某一臺(tái)路由器v希望向G中的所有其他路由器發(fā)送報(bào)文M，并且，由v對(duì)其所發(fā)送的報(bào)文按時(shí)間順序進(jìn)行編號(hào)，因此，這里以三元組（v，j，M）來(lái)表示一個(gè)報(bào)文，其中，j為報(bào)文編號(hào)。網(wǎng)絡(luò)中的每臺(tái)路由器都需要建立一個(gè)表S_k，用來(lái)記錄網(wǎng)絡(luò)中任一臺(tái)路由器可能發(fā)送的報(bào)文的最大編號(hào)。若某一時(shí)刻路由器k收到相鄰路由器w發(fā)送來(lái)的消息（v，j，M），首先檢查是否小于，如果小于，則記錄，并將消息擴(kuò)散到除路由器w以外的其他路徑上。否則，w認(rèn)為它已處理過(guò)此消息，將其丟棄。

由以上分析可以看出，擴(kuò)散路由算法存在安全隱患，例如某一路由器t可以假冒k發(fā)送消息（v，j，M），若此消息先于正確消息到達(dá)路由器u，則u必然會(huì)丟棄隨后到來(lái)的正確消息。偽裝的路由器甚至可以發(fā)送編號(hào)為j+m的報(bào)文，這樣真正的路由器隨后發(fā)來(lái)的m個(gè)報(bào)文都將被丟棄，顯然，這種安全隱患對(duì)網(wǎng)絡(luò)來(lái)說(shuō)中是致命的。因此，將安全策略引入到擴(kuò)散路由算法中，提出安全擴(kuò)散路由算法。

2.2 安全擴(kuò)散路由算法

首先定義關(guān)于路由器”的鄰居路由器集合N（u），集合N（u）中是由路由器“的鄰居路由器節(jié)點(diǎn)組成，即：N（u）{v|（u，v）∈E，u≠v}，N（u）中的所有路由器共享一個(gè)密鑰k（u），k（u）采用公開密鑰協(xié)議進(jìn)行分配。然后，路由器v可向其鄰居節(jié)點(diǎn)u發(fā)送信息（v，j，M，h（v，j，M，k（x）），0），其中，h為加密方法。v的任意鄰居節(jié)點(diǎn)u都可馬上對(duì)此信息進(jìn)行鑒別。如果路由器u收到其鄰居節(jié)點(diǎn)w的信息（u，j，h₁，h₂），如果w=v，則h₂=0，u可以直接對(duì)此信息鑒別。若h₂≠0，則h₂應(yīng)為h（u，j，M，k（x）），h₁應(yīng)該是來(lái)自路由器w的密文，路由器u仍可通過(guò)鑒別w以獲得k（x）來(lái)達(dá)到鑒別v的目的，前提是失效路由器不超過(guò)1臺(tái)。

2.3 算法優(yōu)點(diǎn)

（1）從安全的角度上來(lái)看，對(duì)密文進(jìn)行破譯計(jì)算量相當(dāng)大，因此，偽裝的路由器如果不知道密鑰就無(wú)法改寫密文。另外，即使某一臺(tái)路由器癱瘓，信息仍可由其他的路由器發(fā)送到目的節(jié)點(diǎn)。

（2）從性能上看，路由器只需對(duì)到達(dá)的擴(kuò)散信息做一次散列計(jì)算，從實(shí)際效果看，要比做全文計(jì)算好得多。

（3）此方法還可發(fā)現(xiàn)工作不正常的路由器，對(duì)任一失常的路由器，其鄰居節(jié)點(diǎn)馬上就會(huì)發(fā)現(xiàn)，并向網(wǎng)絡(luò)管理設(shè)備發(fā)出警告。

3 結(jié)語(yǔ)

在Internet網(wǎng)絡(luò)上實(shí)現(xiàn)消息的安全傳遞是一件十分困難的事情，既需要有足夠高的安全性，又不能給網(wǎng)絡(luò)帶來(lái)太大的負(fù)擔(dān)。本文提出了一種安全擴(kuò)散網(wǎng)絡(luò)算法，通過(guò)將安全策略引入到擴(kuò)散算法中，提高了網(wǎng)絡(luò)路由算法的安全性。