一种安全网络路由算法研究

摘要：路由算法是路由协议中的重要组成部分，采用何种算法往往决定了最终寻径结果的优劣。路由算法除了能够对信息进行正确路由外还应使路由器具有抵抗恶意攻击的能力。文章在介绍了安全的网络路由算法的设计目标以及几种采用加密技术的安全网络路由算法的基础上，提出了一种安全网络路由算法，该算法通过公开密钥机制，保证了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为报文编号。网络中的每台路由器都需要建立一个表Sk，用来记录网络中任一台路由器可能发送的报文的最大编号。若某一时刻路由器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，h1，h2），如果w=v，则h2=0，u可以直接对此信息鉴别。若h2≠0，则h2应为h（u，j，M，k（x）），h1应该是来自路由器w的密文，路由器u仍可通过鉴别w以获得k（x）来达到鉴别v的目的，前提是失效路由器不超过1台。

2.3 算法优点

（1）从安全的角度上来看，对密文进行破译计算量相当大，因此，伪装的路由器如果不知道密钥就无法改写密文。另外，即使某一台路由器瘫痪，信息仍可由其他的路由器发送到目的节点。

（2）从性能上看，路由器只需对到达的扩散信息做一次散列计算，从实际效果看，要比做全文计算好得多。

（3）此方法还可发现工作不正常的路由器，对任一失常的路由器，其邻居节点马上就会发现，并向网络管理设备发出警告。

3 结语

在Internet网络上实现消息的安全传递是一件十分困难的事情，既需要有足够高的安全性，又不能给网络带来太大的负担。本文提出了一种安全扩散网络算法，通过将安全策略引入到扩散算法中，提高了网络路由算法的安全性。