基于DoS攻击的随机数据包标记源跟踪算法

作者:饥饿加菲猫(QQ120474)

iojhgfti@hotmail.com

摘要: 针对互联网上日益猖獗的拒绝服务攻击(DoS),分析了传统的随机数据包标记算法的性能缺陷,提出一种新的基于散列消息鉴别码的返回跟踪算法HPPM,通过分析其性能指标,说明该算法提高了返回跟踪DoS攻击的效率和准确性。

感谢帮过我的几个高手袁哥[nsfocus], sunwear[E.S.T] , isno[xfocus] , scz[nsfocus]

1.引言

拒绝服务攻击,简称DoS(Denial-of-Service),是一种常见的黑客攻击行为。这种攻击行为通过发送带有虚假源地址的数据包请求,使网络服务器充斥大量等待回复的信息,消耗网络带宽或系统资源,使网络或系统服务负载过重,服务质量下降,直至瘫痪而停止正常的服务。有时,黑客为了提高攻击的效果,往往会联合多个攻击站点向受害者发动进攻。由于DoS攻击易于实施、难于防御,而且很难返回跟踪攻击源,使之成为一个严重侵扰网络服务提供商、政府机关和金融证券等机构正常运作的安全问题。

2.IP返回跟踪相关技术

为了彻底消除DoS攻击,必须追根溯源,找到真正的攻击机器或攻击者。这种方法被称为IP返回追踪技术(IP Traceback)。由于DoS攻击者在发送攻击数据包时往往会伪造源地址,使得IP返回追踪的难度很大。常用的IP返回追踪方法有:入口过滤(Ingress Filtering)、连接测试(Link Testing)、ICMP追踪[7]、登录分析(Logging)、源路径隔离引擎(SPIE)、IPSec追踪,以及随机数据包标记追踪(PPM)[2]。各种追踪技术之间的性能比较,如表1所示。

管理负担     网络负担     路由器负担     分布式能力     事后追踪能力     预防/反应

进入过滤     中等     低     中等     N/A     N/A     预防

输入调试     高     低     高     好     差     反应

控制流     低     高     低     差     差     反应

登陆分析     高     低     高     极好     极好     反应

ICMP追踪     低     低     低     好     极好     反应

数据包标记     低     低     低     好     极好     反应

表1 几种IP返回追踪技术的性能比较[2]

3.HPPM IP返回跟踪算法

3.1     PPM算法(Probabilistic Packet Marking)

随机数据包标记算法PPM的主要原理如下:路由器以一定的概率p(通常是1/25)[2],用其IP地址或IP地址的一部分随机标记经过它的数据包。当发生DoS攻击时,受害者根据其收到的攻击数据包中的标记信息,重建攻击路径。使用PPM算法,路由器负担较小,采用标记边压缩和分片技术大大降低了额外的网络流量。而且,该方法可以在攻击结束以后对攻击源进行追踪。PPM对单源DoS攻击,有较好的追踪效果。

但是,由于其自身缺陷,PPM算法无法很好地返回跟踪DDoS攻击(Distributed–Denial–of–Service)。首先,由于路由器以概率p随机标记数据包,就给攻击者以可乘之机,将伪造的标记信息写入攻击数据包的报头中(一般是Identifier字段),只要该数据包一直不被其经过的路由器标记,直至目标主机,就能在攻击路径中伪造一条边路径,阻止受害者跟踪真正的攻击源。其次,为了节省存储空间,减小网络负担,PPM采用了边标记压缩和分片存储技术。但是,分片存储可能导致受害者将本不属于同一数据包的分片组合在一起,从而生成错误的边路径。而标记的边压缩方法主要依据(a○+b)○+b=a(a、b分别是攻击路径上相邻两个路由器的IP地址),将显著加剧这一效果,进一步生成错误的攻击路径。当发生DDoS攻击时,由于同一距离存在多个攻击者,而产生爆炸效果,影响将更加严重[2]。

3.2     HPPM算法

针对PPM算法的上述缺陷,我们提出了一种基于散列消息鉴别码HMAC的数据包标记算法HPPM,并采用新的标记重叠分片策略,以提高IP返回跟踪DoS攻击(特别是DDoS攻击)的性能。

在该算法中,路由器Ri以概率p随机对经过它的数据包进行标记,标记信息包括Ri的IP地址和下一跳路由器Rj的IP地址,总共64位。为了节省标记存储空间,不给用户带来过多影响,算法使用IPv4首部中的16位标识符字段(Identifier),1位闲置的标志位(Flags)[1]和13位片位移字段(据统计,目前少于0.25%的数据包需要分片[2]),以及一般很少使用的8位TOS字段(Type-of-Service)[1],总共38位,来存储标记分片信息。64位标记信息被分成k=8片,每片占用8位,分片偏移值占log2k=3位,Ri到目标主机的距离值占5位(25-1=31跳,适用于目前绝大多数网络[2]),用于验证的HMAC值占22位。

散列消息鉴别码,简称HMAC,是一种基于消息鉴别码MAC(Message Authentication Code)的鉴别机制。使用HMAC时,消息通讯的双方,通过验证消息中加入的鉴别密钥K来鉴别消息的真伪;HMAC还引人了一个散列函数H,对消息进行加密,进一步确保消息鉴别的安全性和有效性。HMAC的具体计算方法如下:

HMAC(M,K) = H(K○+opad, H(K○+ipad, M ))

其中,ipad = 字0x36重复B次,opad = 字0x5C重复B次,M = 待加密的消息字符串,B = 消息字符串的字长。关于HMAC更详细的内容,请参考文献RFC 2104[6]。

在HPPM算法中,我们采用一次性口令机制OTP(One-Time Password)[4][5],先让每个路由器Ri生成一组私有密钥序列{Kij}(j=0、1、2……)。这组私有密钥序列通过单向散列函数f生成,并具有以下规则:Kij-1 =f(Kij)。由于函数f是单向的,所以由最新的密钥Kij可以依次推出在它以前生成的所有Kij-1、Kij-2……Ki0,但根据已有的密钥却推不出下一个密钥,这就确保了他人无法伪造Ri的密钥。路由器Ri每经过一段固定的时间间隔,就根据上述方法更换一次私有密钥Ki,然后将刚刚停止使用的密钥通过可靠的方式发布出去。当数据包P通过Ri时,Ri 使用HMAC函数H和当前私有密钥Ki,对Ri 的IP地址和P的目的地址进行加密,即:H(M,Ki),其中,M = IP(Ri)+IP(destination)。具体的标记步骤如下:

Marking procedure at router Ri:

let m be the marking massage ip(Ri) + ip(Rj)

let k be the number of fragments in m

let H be the HMAC function

let Ki be the private key of Ri at current time interval

for each packet w

let x be a random number from [0..1)

if x < p then

let hmac be the HMAC value of IP(Ri)+IP(w.destination)

hmac := H( IP(Ri)+IP(w.destination), Ki)

let o be a random integer from [0..k-1]

let f be the fragment of m at offset o

write f into w.frag

write 0 into w.distance

write o into w.offset

write hmac into w.hmac

else

increment w.distance

以下将讨论受害者重建攻击路径的过程。当受到DoS攻击时,受害者开始收集标记分片,并记录其到达时间。我们假设攻击者发送大量的攻击数据包,那么受害者就能收集到足够多的标记分片,然后根据分片的偏移值,将具有相同攻击距离d和hmac值的分片重组,生成边路径,进而生成整个攻击路径。由于攻击者可能伪造标记数据包,干扰返回跟踪过程,因此需要对生成的边路径鉴别真伪。具体鉴别方法是:受害者与路由器Ri(服务提供商)联系,取得Ri最新的私有密钥K,然后根据K和数据包P到达时间(需要考虑延时),使用相同散列函数f计算出Ri标记P时使用的私有密钥Ki;再根据Ri和自身的IP地址,以及Ki,计算出HMAC值与标记数据包中的HMAC值进行比较,一致则说明该边路径有效,否则将其丢弃。重建攻击路径的具体过程如下:

Path reconstruction procedure at victim v:

let FragTbl be a table of tuples (frag, offset, distance, hmac, time)

let G be a tree with root v

let edges in G be tuples (start,end,distance,hmac,time)

let maxd := 0

let last := v

for each packet w from attacker

let rectime be the time when v receives the packet w

FragTbl.Insert(w.frag,w.offset,w.distance,w.hmac,rectime)

if w.distance > maxd then

maxd := w.distance

for d := 0 to maxd

for all ordered combinations of fragments having the same hmac value at distance d

construct edge z( IP(Ri), IP(Rj), w.distance, w.hmac, rectime)

// Start of HMAC authentication

let K be the private key of Ri at current time interval

let Ki be the private key of Ri at the time interval when Ri marked the packet w

let f be the function to get Ki according to K and rectime

Ki := f(K, rectime)

if w.hmac = H(IP(Ri)+IP(v), Ki)

insert edge z( IP(Ri), IP(Rj), w.distance) into G

// End of HMAC authentication

remove any edge (x,y,d,hmac,time) with d ≠ distance from x to v in G

extract path (Ri..Rj ) by enumerating acyclic paths in G

4.HPPM算法性能分析

4.1     攻击收敛包数

根据[2],受害者收到距离为d的路径上最远处路由器发来的标记数据包的概率是:p(1-p)d-1。保守假设受害者收到该路径上任一路由器发来标记数据包的概率都与最远距离d处相同,并且相互独立,因此受害者收到的任一数据包被该数据包途经路径上某些路由器标记过的概率,将具有期望值:1/dp(1-p)d-1。

根据coupon-collector问题[8],受害者收到的从距离为d的路径上发来的数据包中,包括所有d个路由器中每个路由器发出的至少一个标记数据包,所需要接收的数据包数,具有以下期望值:1+d/(d-1)+d/(d-2)+……+d/2+d = d(ln(d)+O(1))。考虑到每个标记数据包被分成k片,总共有kd片,则上述值为kd(ln(kd)+O(1))。因此,重建距离为d(包含d个路由器)的攻击路径所需要的数据包数N,具有期望值:

E(N)<kd(ln(kd)+O(1))

1/dp(1-p)d-1≈k

ln(kd)/p(1-p)d-1

因此,该算法攻击收敛包数与PPM边标记算法相同[2]。

4.2     健壮性

在PPM算法[2]中,对于输出长度为h的散列随机函数,受害者接受任一候选边路径的概率是1/2h。假设有m个攻击者,则在一定距离d处,最坏情况下将有m个独立的路由器。因此,在距离受害者d处,本不在实际攻击路径中的任意候选边路径被受害者接受(即:产生了正误差[3])的最大概率将是:1-(1-1/2h)n(其中n=mk)[2]。因为,最坏情况下,距离d处将有mk个标记分片。当k值或m值很大时,这一概率也将变得很大。而HPPM算法使用的HMAC鉴别机制,可以十分有效地鉴别攻击者伪造的边路径,将伪造的边路径从候选边路径中过滤掉,从而充分减小了算法产生的正误差,提高了返回跟踪的准确性。

4.3     路由器负担

由于采用HMAC和一次性口令机制来加密攻击数据包中的边标记,因此中间路由器无须承担PPM算法中每个路由器对其IP地址和已有边标记进行的异或运算(a○+b)○+b。而HMAC的计算过程简单,扩展性也很好,当发现或需要运算速度更快或更安全的散列函数时,几乎不用修改,就可以很容易地实现底层散列函数的替换,参阅文献[6]。为了使数据包标记过程更加安全,路由器需要周期性更换其用于加密边标记的私有密钥。这个周期需要进行适当选择,周期太短将给路由器带来额外负担,且不利于与受害者的同步,周期太长又影响算法安全性,可以考虑把10秒作为其数量级[3]。

4.4     受害者负担

由于使用了一次性口令机制,受害者需要获取上游路由器加密边标记时使用的私有密钥。一种可行的方法是,上游路由器将最新密钥通过可信渠道发布(如:发布在网站上),受害者鉴别边标记真伪时,只需下载该路由器的最新密钥,根据最新密钥就能推算出该路由器以前加密边标记时使用的所有密钥。这一过程可以在常数时间内完成。

4.5     算法局限性

HPPM算法,要求受害者掌握网络拓扑结构,具有其上游路由器的地图,这在一定程度上限制了算法的发展。受害者与中间路由器关于密钥的同步过程还需要进一步考虑。

5.总结及未来工作

本文描述了一种新的基于散列消息鉴别码HMAC的随机数据包标记算法HPPM,该算法用于返回跟踪DoS攻击的攻击源,能够充分减小由于攻击者伪造数据包标记而带来的误差,提高了返回跟踪的安全性和准确性。然而,该算法还有不完善的地方,比如:与大多数返回跟踪算法一样,HPPM算法是一种反应型跟踪算法,即:只有确实发生了攻击,才能进行跟踪。并且,该算法实际上无法跟踪到真正的攻击源,只能返回跟踪到最接近攻击源的边界路由器。这些问题都有待进一步研究。

参考文献

[1] W.Richard Stevens著,范建华 胥光辉 张涛 等译,谢希仁校,《TCP/IP详解——卷1:协议》[M],第1版,北京:机械工业出版社,2000年4月,第24-27、111-112页.

[2] S.Savage, D.Wetherall, A.Karlin and T.Anderson. Practical network support for IP traceback[C]. In ACM SIGCOMM, Stockholm, Sweden, 2000, 295-306.

[3] D.X.Song and A.Perrig. Advanced and authenticated marking schemes for IP traceback[C]. In IEEE INFOCOMM, April 2001.

[4] N.Haller, The S/KEY One-Time Password System[Z], Internet RFC 1760, February 1995.

[5] N.Haller, A One-Time Password System[Z], Internet RFC 2289, February 1998.

[6] H.Krawczyk, M.Bellare, and R.Canetti, HMAC: Keyed-Hashing for Message Authentication[Z], Internet RFC 2104, February 1997.

[7] S.M.Bellovin. ICMP Traceback Messages[Z]. Internet Draft:draft-bellovin-itrace-00.txt.March 2000.

[8] W.Feller. An Introduction to Probability Theory and Its Applications[M]. 2nd edition, volume 1. Wiley and Sons. 1966.

[9] K.Park, H.Lee. On the Effectiveness of Probabilistic Packet Marking for IP Traceback under Denial

of Service Attack[C]. In IEEE INFOCOM, 2001.

(0)

相关推荐

  • python实现的生成随机迷宫算法核心代码分享(含游戏完整代码)

    完整代码下载:http://xiazai.jb51.net/201407/tools/python-migong.rar 最近研究了下迷宫的生成算法,然后做了个简单的在线迷宫游戏.游戏地址和对应的开源项目地址可以通过上面的链接找到.开源项目中没有包含服务端的代码,因为服务端的代码实在太简单了.下面将简单的介绍下随机迷宫的生成算法.一旦理解后你会发现这个算法到底有多简单. 1.将迷宫地图分成多个房间,每个房间都有四面墙. 2.让"人"从地图任意一点A出发,开始在迷宫里游荡.从A房间的1/

  • asp.net(c#)两种随机数的算法,可用抽考题

    第一种算法,存大一点问题.没有查出来  复制代码 代码如下: static void Main(string[] args)  {  //  // TODO: 在此处添加代码以启动应用程序  int singletitlemeasure=5;  int n=1;//声明一个表示考试类型的int变量  Random ran=new Random(unchecked((int)DateTime.Now.Ticks));  int Int1Random;  switch(n)  {  case 1:/

  • 游戏开发之随机概率的选择算法

    实现代码超简单,具体实现方法如下: 有时候当我们的游戏人物遇敌时,我们需我怪物随机根据概率选择处理方式,如下: 1.50%的机会友好的问候 2.25%的几率走开 3.20%的机会立即攻击 4.5%的机会提供金钱作为礼物 下面的这个算法就是跟据概率数组,返回选择的概率索引号. int Choose(float[] 概率数组) { float total=0; //首先计算出概率的总值,用来计算随机范围 for(int i=0;i<概率数组.length;i++) { total+=概率数组[i];

  • 适用于抽奖程序、随机广告的PHP概率算法实例

    那么我们在程序里必然会设计到算法,即按照一定的概率让用户获得奖品.先来看两个概率算法函数. 算法一 复制代码 代码如下: /** * 全概率计算 * * @param array $p array('a'=>0.5,'b'=>0.2,'c'=>0.4) * @return string 返回上面数组的key */function random($ps){    static $arr = array();    $key = md5(serialize($ps)); if (!isset

  • 史上最全的java随机数生成算法分享

    复制代码 代码如下: String password = RandomUtil.generateString(10); 源码如下: 复制代码 代码如下: package com.javaniu.core.util;import java.util.Random;public class RandomUtil { public static final String ALLCHAR = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRS

  • JS实现随机数生成算法示例代码

    1: 复制代码 代码如下: var MT = []; var index = 0; function initialize_generator(seed) { MT[0] = seed; for (var i = 1; i < 624; i++) { MT[i] = 0xffffffff & (0x6c078965 * (MT[i - 1] ^ (MT[i - 1] >> 30)) + i); } } function generate_numbers() { for (var

  • javascript随机之洗牌算法深入分析

    洗牌算法是我们常见的随机问题,在玩游戏.随机排序时经常会碰到.它可以抽象成这样:得到一个M以内的所有自然数的随机顺序数组. 在百度搜"洗牌算法",第一个结果是<百度文库-洗牌算法>,扫了一下里面的内容,很多内容都容易误导别人走上歧途,包括最后用链表代替数组,也只是一个有限的优化(链表也引入了读取效率的损失). 该文里的第一种方法,可以简单描述成:随机抽牌,放在另一组:再次抽取,抽到空牌则重复抽."抽到空牌则重复抽"这会导致后面抽到空牌的机会越来越大,显然

  • 基于DoS攻击的随机数据包标记源跟踪算法

    作者:饥饿加菲猫(QQ120474) iojhgfti@hotmail.com 摘要: 针对互联网上日益猖獗的拒绝服务攻击(DoS),分析了传统的随机数据包标记算法的性能缺陷,提出一种新的基于散列消息鉴别码的返回跟踪算法HPPM,通过分析其性能指标,说明该算法提高了返回跟踪DoS攻击的效率和准确性. 感谢帮过我的几个高手袁哥[nsfocus], sunwear[E.S.T] , isno[xfocus] , scz[nsfocus] 1.引言 拒绝服务攻击,简称DoS(Denial-of-Ser

  • 基于C语言实现随机点名器(附源码)

    突发奇想写了个随机点名器…以供使用 随机点名器 main函数 #include "myList.h" #define FILENAME "stu.txt" void menu();//画面界面; void userOptions(Node* headNode);//用户选项 int main(void) { SetConsoleTitle(L"随机抽查系统"); Node* List = createrList(); readInfoFromFi

  • Python中使用scapy模拟数据包实现arp攻击、dns放大攻击例子

    scapy是python写的一个功能强大的交互式数据包处理程序,可用来发送.嗅探.解析和伪造网络数据包,常常被用到网络攻击和测试中. 这里就直接用python的scapy搞. 这里是arp的攻击方式,你可以做成arp攻击. 复制代码 代码如下: #!/usr/bin/python """ ARP attack """ import sys, os from scapy.all import * if os.geteuid() != 0:    

  • 三层交换阻击DoS攻击

    尽管全球网络安全专家都在着力开发抗DoS攻击的办法,但收效不大,因为DoS攻击利用了TCP协议本身的弱点.在交换机上进行设置,并安装专门的DoS识别和预防工具,能最大限度地减少DoS攻击造成的损失. 利用三层交换建立全面的网络安全体系,其基础必须是以三层交换和路由为核心的智能型网络,有完善的三层以上的安全策略管理工具.同时,在网络的设计阶段,就应该进行合理布置. 局域网层 在局域网层上,网管员可采取很多预防措施.例如,尽管完全消除IP分组假冒现象几乎不可能,但网管员可构建过滤器,如果数据带有内部

  • 使用C#实现RTP数据包传输 参照RFC3550

    闲暇时折腾IP网络视频监控系统,需要支持视频帧数据包在网络内的传输.未采用H.264或MPEG4等编码压缩方式,直接使用Bitmap图片.由于对帧的准确到达要求不好,所以采用UDP传输.如果发生网络丢包现象则直接将帧丢弃.为了记录数据包的传输顺序和帧的时间戳,所以研究了下RFC3550协议,采用RTP包封装视频帧.并未全面深究,所以未使用SSRC和CSRC,因为不确切了解其用意.不过目前的实现情况已经足够了. 复制代码 代码如下: /// <summary>   /// RTP(RFC3550

  • MySQL基于DOS命令行登录操作实例(图文说明) 原创

    本文实例讲述了MySQL基于DOS命令行登录操作方法.分享给大家供大家参考,具体如下: 常用的MySQL命令行登录语句如下: 复制代码 代码如下: mysql -h localhost -u root -p123456 其中: -h 表示服务器地址,可省略,默认表示本机服务器 -u 表示登录用户,必选,可与用户名连在一起写,如:-uroot -p 表示数据库密码,必选,但这里可不输入密码(注意:命令行中-p与密码之间不能有空格) 因此,上述语句可写成如下几种形式: mysql -u root -

  • Android模拟器接收UDP数据包的若干问题分析

    本文实例分析了Android模拟器接收UDP数据包的若干问题.分享给大家供大家参考,具体如下: android模拟器无法接收UDP数据包 代码如下: DatagramPacket pack = null; DatagramSocket mail_data = null; byte receiver[] = new byte[100]; try { pack = new DatagramPacket(receiver,receiver.length); mail_data = new Datagr

  • 基于java类路径classpath和包的实例讲解

    类路径(classpath) java编译器编译.java文件和java虚拟机执行.class文件时的路径和写法不一样. 在没有设置任何classpath环境变量的情况下,javac可以编译全路径的.java文件.例如: javac d:\myjava\HelloWorld.java 编译后,在.java同路径目录下生成class文件. 默认java虚拟机要从classpath环境变量的路径中搜索class文件去执行,对于java虚拟机来说,这不是类文件,而是类.它只有类路径,而没有文件系统路径

  • 在Linux中使用tcpdump命令捕获与分析数据包详解

    前言 tcpdump 是一个有名的命令行数据包分析工具.我们可以使用 tcpdump 命令捕获实时 TCP/IP 数据包,这些数据包也可以保存到文件中.之后这些捕获的数据包可以通过 tcpdump 命令进行分析.tcpdump 命令在网络层面进行故障排除时变得非常方便. tcpdump 在大多数 Linux 发行版中都能用,对于基于 Debian 的Linux,可以使用 apt 命令安装它. # apt install tcpdump -y 在基于 RPM 的 Linux 操作系统上,可以使用下

  • eBay 打造基于 Apache Druid 的大数据实时监控系统

    首先需要注意的是,本文即将提到的 Druid,并非阿里巴巴的 Druid 数据库连接池,而是另一个大数据场景下的解决方案:Apache Druid. Apache Druid 是一个用于大数据实时查询和分析的高容错.高性能开源分布式时序数据库系统,旨在快速处理大规模的数据,并能够实现快速查询和分析.尤其是当发生代码部署.机器故障以及其他产品系统遇到宕机等情况时,Druid 仍能够保持 100% 正常运行.创建 Druid 的最初意图主要是为了解决查询延迟问题,当时试图使用 Hadoop 来实现交

随机推荐