一種安全網絡路由算法研究

趙巖　周欣欣　徐純森

摘要：路由算法是路由協議中的重要組成部分，采用何種算法往往決定了最終尋徑結果的優劣。路由算法除了能夠對信息進行正確路由外還應使路由器具有抵抗惡意攻擊的能力。文章在介紹了安全的網絡路由算法的設計目標以及幾種采用加密技術的安全網絡路由算法的基礎上，提出了一種安全網絡路由算法，該算法通過公開密鑰機制，保證了Internet網絡中擴散路由算法的安全性。

關鍵詞：網絡；路由算法；安全；加密

在Internet網絡上需要對信息進行路由，每一個信息包無論是經過網絡還是自治系統都需盡快由源端到達目的端。因此，目前在Internet上許多路由算法都被設計成使信息包通過網絡最短的路由算法。OSPF，RIP和IEGP這些網絡內部路由算法都是根據諸如BGP，EGP的協議設計成。

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

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

當然，不一定要求所有的信息都必須是加密的，可以通過對信息的敏感內容進行加密，這一點很容易做到，例如可以對應用層的信息進行加密。

1 相關工作

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

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

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

Hauser采用了多個散列鏈以標識在鏈路狀態路由算法中不同的連接，從而避免了上訴缺陷，但多個散列鏈要求網絡中的路由器必須是同步的。文獻總結了一些靜態、動態路由算法，并對其特性進行了深入分析。

2 安全擴散路由算法

2.1 擴散路由算法

本文提出一種安全擴散路由算法，其基本思想是通過公開密鑰體制為每一個路由器的相鄰節點分配共享密鑰，每一個中間節點在轉發消息的同時傳遞報文的加密密鑰達到鑒別目的。下面先說明擴散路由算法的具體實現過程，然后再提出引入安全策略的安全擴散路由算法。

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

由以上分析可以看出，擴散路由算法存在安全隱患，例如某一路由器t可以假冒k發送消息（v，j，M），若此消息先于正確消息到達路由器u，則u必然會丟棄隨后到來的正確消息。偽裝的路由器甚至可以發送編號為j+m的報文，這樣真正的路由器隨后發來的m個報文都將被丟棄，顯然，這種安全隱患對網絡來說中是致命的。因此，將安全策略引入到擴散路由算法中，提出安全擴散路由算法。

2.2 安全擴散路由算法

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

2.3 算法優點

（1）從安全的角度上來看，對密文進行破譯計算量相當大，因此，偽裝的路由器如果不知道密鑰就無法改寫密文。另外，即使某一臺路由器癱瘓，信息仍可由其他的路由器發送到目的節點。

（2）從性能上看，路由器只需對到達的擴散信息做一次散列計算，從實際效果看，要比做全文計算好得多。

（3）此方法還可發現工作不正常的路由器，對任一失常的路由器，其鄰居節點馬上就會發現，并向網絡管理設備發出警告。

3 結語

在Internet網絡上實現消息的安全傳遞是一件十分困難的事情，既需要有足夠高的安全性，又不能給網絡帶來太大的負擔。本文提出了一種安全擴散網絡算法，通過將安全策略引入到擴散算法中，提高了網絡路由算法的安全性。