DDOS终极加速列车算法
文章作者：ZV(zvrop_at_163_dot_com)
信息来源：邪恶八进制信息安全团队（www.eviloctal.com）
注意：文章首发Zerg Hole和网络技术论坛后，由原创作者友情提交到邪恶八进制讨论组。
很久没来了,因为毕业了…事情太多了…
本文产生与前两天群里讨论现在什么DDOS软件最快,然后看到某个软件打出了相当嚣张的简介,为此,我花了两天时间,研究了一下DDOS算法究竟有没有的提升的空间.以此挑战一下最快的DDOS软件的速度.效果还是不错的.
本文原是分两天写的两个部分,现整理一下发到xfocus上来.
先来段代码:
USHORT checksum(USHORT *buffer, int size)
{
unsigned long cksum=0;
while(size >1){
printf("%04X\r\n",*buffer);
cksum+=*buffer++;
size -=sizeof(USHORT);
}
if(size ){
cksum += *(UCHAR*)buffer;
}
cksum = (cksum >> 16) + (cksum & 0xffff);
cksum += (cksum >>16);
return (USHORT)(~cksum);
}
这个是大多数正常的效验和算法,主要是把数据(buffer)当成一个个16位的数值,挨个相加,最后求反码后返回.这个算法速度非常快,以现代的编译器能力来看,没有可能用汇编来加速.不过就算法本身来说不怎么好,毕竟是只加法.还是有值得研究的地方.
因为原先进来计算的数据中包含的效验和是0,所以计算过后把值(反码)放入0的位置.这样,数据包到达目的地的时候,只要再进行一次同样的效验和计算,就能得出结果是0xffff,因为将0改成了整个效验和的和的反码,再次计算的时候,等于将上次计算的结果再加它的反码,所以结果是0xffff(举个例子: 比如0x7878+0x8787 = 0xffff).然后对0xffff又求反码后返回,所以是0.只要目的端计算出的是0,说明途中没有出错.
嗯….其实上面说的都是废话,为了让大家对效验和有个直观的了解,下面说重点:
我们都知道,每个tcp包,是由IP包+tcp包组成的.这样里面就有两个效验和,一个是IP包的,一个是TCP包的,对于TCP包的加速算法,将在下面部分给出,前面部分的加速算法只针对IP包.
参与TCP包计算效验和的包括两个部分,一个是伪首部(本文中是暂称tsd首部),一个是TCP首部.分别是这样的:
typedef struct tsd_hdr //定义TCP伪首部
{
unsigned long saddr; //源地址
unsigned long daddr; //目的地址
char mbz;
char ptcl; //协议类型
unsigned short tcpl; //TCP长度
}PSDHEADER;
typedef struct tcp_hdr //定义TCP首部
{
USHORT th_sport; //16位源端口
USHORT th_dport; //16位目的端口
unsigned int th_seq; //32位序列号
unsigned int th_ack; //32位确认号
unsigned char th_lenres; //4位首部长度/6位保留字
unsigned char th_flag; //6位标志位
USHORT th_win; //16位窗口大小
USHORT th_sum; //16位校验和
USHORT th_urp; //16位紧急数据偏移量
}TCPHEADER;
参与IP包计算效验和也有两个部分,一个是IP首部,一个是TCP首部.分别是这样的:
typedef struct ip_hdr //定义IP首部
{
unsigned char h_verlen; //4位首部长度,4位IP版本号
unsigned char tos; //8位服务类型TOS
unsigned short total_len; //16位总长度（字节）
unsigned short ident; //16位标识
unsigned short frag_and_flags; //3位标志位
unsigned char ttl; //8位生存时间 TTL
unsigned char proto; //8位协议 (TCP, UDP 或其他)
unsigned short checksum; //16位IP首部校验和
unsigned int sourceIP; //32位源IP地址
unsigned int destIP; //32位目的IP地址
}IPHEADER;
typedef struct tcp_hdr //定义TCP首部
{
USHORT th_sport; //16位源端口
USHORT th_dport; //16位目的端口
unsigned int th_seq; //32位序列号
unsigned int th_ack; //32位确认号
unsigned char th_lenres; //4位首部长度/6位保留字
unsigned char th_flag; //6位标志位
USHORT th_win; //16位窗口大小
USHORT th_sum; //16位校验和
USHORT th_urp; //16位紧急数据偏移量
}TCPHEADER;
可见两个效验和计算的时候,TCP首部都有参与.根据算法原理,这个是可以被中和的.现在好玩的来了.
因为TCP效验和是先于IP效验和开始计算的(因为IP效验和需要包括TCP首部,而TCP首部这个时候需要先计算完成),TCP首部计算过后,它的效验和已经放入自己的效验和字段.如果再次计算tcp的效验和,因为已经加入了tcp效验和的反码也参与计算.所以最终计算结果为0.
那么计算IP+TCP的效验和的时候,将整个已经计算过效验和的TCP首部加入进来,岂不是白做工?
不,不是,因为TCP计算效验和的时候还参与了TCP伪首部.所以TCP首部中的效验和不是只有它一个部分,还有另外一个部分,TCP伪首部(TSD首部).
那么有没有办法中和这个伪首部呢?如果能综合这个伪首部,使得它也失去计算效果……
答案是肯定的,方法是通过IP首部.
仔细看上面的TCP伪首部和IP首部.仔细分析他们的区别.
因为效验和终归来讲是对数值进行加法计算.如果我们能用IP首部中的某些字段,巧妙的代替了TSD首部中的某些字段,将他们计算的结果综合,那么整个计算过程就相当简单了.
分析的结果大为让人吃惊,TCP伪首部和IP首部中竟然都有目的IP,源IP字段……意思也就是说,这两个字段如果改变的话,对于IP效验和的计算结果丝毫没有任何影响….我想到了可怕的DDOS程序,你呢?
经过一番筛选和精简,得出了一个可怕结论.下面先来个结构,这是我自己分析出的:
#pragma pack(1)
typedef struct _PackStk{
unsigned char h_verlen; //4位首部长度,4位IP版本号
unsigned char tos; //8位服务类型TOS
unsigned short ident; //16位标识
unsigned char ttl; //8位生存时间 TTL
unsigned char frag_and_flags; //3位标志位
unsigned short checksum; //16位IP首部校验和
}PackStk;
唯一注意的地方是,这个结构的顺序不能变,且内存对其应该为1.
然后我们只要设置这个报文的字段,计算之效验和后,所有不改变PackStk中字段的IP报文(其他字段可任意改变,包括IP),均不用重新计算IP效验和.大大的节省了时间.不,应该说根本不用花时间.
IP效验和加速到此结束,加速成果:100%
前面说到tcp包中的IP包的效验和可以省略的办法,本次再来说说还剩下的一个效验和也就是tcp效验和的加速方法.由于IP效验和被完全取消,所以这个速度理论上可以提升一倍,而接下来的tcp效验和经过加速之后可以提升90甚至更多,所以最终的效果是将DDOS程序的算法提升了5-6倍.是不是很夸张? 是的,我先这么和你说,你才会吧这个文章看完.呵呵…
好了,到了这里我也不想隐瞒什么了,我确实在写ddos程序.不过需要澄清一点,我只是为了研究,为了实现加速算法,不会发布的这个程序或者是公开代码,因为这个做法实在太危险了.
下面开始正文.
首先说说我的想法,DDOS程序中对于效验和要反复计算的原因,在于其伪造的IP需要不停的更变,于是每次IP更变之后,都要对整个数据包(IP+TCP)进行效验和,否则发不出去.
在前次的文章中(见我的实验一),我用综合Tsd首部和IP首部的办法,成功的分离出一个packstk首部,于是只要计算这个首部,即可完成IP效验和的计算,并且从此不再需要改变(相信很多人写ddos的时候都会发现这点,更改了ip首部中的ip地址之后,重新计算ip首部,效验和不变).
(对于前次文章,还有个补遗,就是packstk首部中的len字段,不是ip首部+tcp首部的长度,而是单独的ip首部中len的长度,减去Tsd首部中len的长度)
那么剩下的这个tcp首部的效验和计算方法是:计算Tsd首部和tcp首部的和.
关键的来了,大家知道ttl的,当一个数据包经过一个路由的时候,就会将数据包中的ttl值减去1,那么这个时候路由一定需要重新计算效验和,不然数据包到了下个路由就会被丢弃.
路由器真的重新计算这个效验和了吗?
答案是否定的,路由器使用了一个弥补算法,对效验和进行简单的更新之后,就发了出去,这种简单的算法和完全计算效验和计算之后的值是一样的.我们姑且称之为"路由效验和算法".
有文档可查,在rfc1141上.看这里看这里:http://www.faqs.org/rfcs/rfc1141.html
公式是:~C' = ~(C + (-m) + m') = ~C + (m – m') = ~C + m + ~m'
代码:
UpdateTTL(iph,n)
struct ip_hdr *ipptr;
unsigned char n;
{
unsigned long sum;
unsigned short old;
old = ntohs(*(unsigned short *)&ipptr->ttl);
ipptr->ttl -= n;
sum = old + (~ntohs(*(unsigned short *)&ipptr->ttl) & 0xffff);
sum += ntohs(ipptr->Checksum);
sum = (sum & 0xffff) + (sum>>16);
ipptr->Checksum = htons(sum + (sum>>16));
}
不过非常遗憾的是,这个算法经过我的测试,效率只提高了30%-50%,离我预期的90%有相当一段距离.于是我对这段算法进行了更改.
整体上对效验和进行更新的实现不变,新算法采用这样的公式:
C = ~(~C + ∑[所有更改的位i]Gray_Code[i])
抱歉这里不好打求和符号,大概意思就是,效验和新值 = 原始效验和求反,加上所有改变位的格雷码异或位的和,再求反.
这个算法是速度比重新计算效验和快了90%,而且可以改变多个byte的值(原先算法只针对ttl这个byte).因为格雷码可以查表得到,这仅仅是一个内存复制的过程,如果你每次只更改1个IP段(IP有4个段不用我说吧),那么每次只要加上一个格雷码异或位即可.然而实际应用中需要加两个,因为端口也需要改变.
好了,什么是Gray_Code,这个我不想解释了,去看wiki吧.然而我这里用到的Gray_Code是我自己生成的一个表.下面这样的:
unsigned char gray_code[256][2] = {
{0x00,0x80},{0x01,0x01},{0x03,0x02},{0x02,0x01},{0x06,0x04},{0x07,0x01},{0x05,0x02},{0x04,0x01},
{0x0C,0x08},{0x0D,0x01},{0x0F,0x02},{0x0E,0x01},{0x0A,0x04},{0x0B,0x01},{0x09,0x02},{0x08,0x01},
{0x18,0x10},{0x19,0x01},{0x1B,0x02},{0x1A,0x01},{0x1E,0x04},{0x1F,0x01},{0x1D,0x02},{0x1C,0x01},
{0x14,0x08},{0x15,0x01},{0x17,0x02},{0x16,0x01},{0x12,0x04},{0x13,0x01},{0x11,0x02},{0x10,0x01},
{0x30,0x20},{0x31,0x01},{0x33,0x02},{0x32,0x01},{0x36,0x04},{0x37,0x01},{0x35,0x02},{0x34,0x01},
{0x3C,0x08},{0x3D,0x01},{0x3F,0x02},{0x3E,0x01},{0x3A,0x04},{0x3B,0x01},{0x39,0x02},{0x38,0x01},
{0x28,0x10},{0x29,0x01},{0x2B,0x02},{0x2A,0x01},{0x2E,0x04},{0x2F,0x01},{0x2D,0x02},{0x2C,0x01},
{0x24,0x08},{0x25,0x01},{0x27,0x02},{0x26,0x01},{0x22,0x04},{0x23,0x01},{0x21,0x02},{0x20,0x01},
{0x60,0x40},{0x61,0x01},{0x63,0x02},{0x62,0x01},{0x66,0x04},{0x67,0x01},{0x65,0x02},{0x64,0x01},
{0x6C,0x08},{0x6D,0x01},{0x6F,0x02},{0x6E,0x01},{0x6A,0x04},{0x6B,0x01},{0x69,0x02},{0x68,0x01},
{0x78,0x10},{0x79,0x01},{0x7B,0x02},{0x7A,0x01},{0x7E,0x04},{0x7F,0x01},{0x7D,0x02},{0x7C,0x01},
{0x74,0x08},{0x75,0x01},{0x77,0x02},{0x76,0x01},{0x72,0x04},{0x73,0x01},{0x71,0x02},{0x70,0x01},
{0x50,0x20},{0x51,0x01},{0x53,0x02},{0x52,0x01},{0x56,0x04},{0x57,0x01},{0x55,0x02},{0x54,0x01},
{0x5C,0x08},{0x5D,0x01},{0x5F,0x02},{0x5E,0x01},{0x5A,0x04},{0x5B,0x01},{0x59,0x02},{0x58,0x01},
{0x48,0x10},{0x49,0x01},{0x4B,0x02},{0x4A,0x01},{0x4E,0x04},{0x4F,0x01},{0x4D,0x02},{0x4C,0x01},
{0x44,0x08},{0x45,0x01},{0x47,0x02},{0x46,0x01},{0x42,0x04},{0x43,0x01},{0x41,0x02},{0x40,0x01},
{0xC0,0x80},{0xC1,0x01},{0xC3,0x02},{0xC2,0x01},{0xC6,0x04},{0xC7,0x01},{0xC5,0x02},{0xC4,0x01},
{0xCC,0x08},{0xCD,0x01},{0xCF,0x02},{0xCE,0x01},{0xCA,0x04},{0xCB,0x01},{0xC9,0x02},{0xC8,0x01},
{0xD8,0x10},{0xD9,0x01},{0xDB,0x02},{0xDA,0x01},{0xDE,0x04},{0xDF,0x01},{0xDD,0x02},{0xDC,0x01},
{0xD4,0x08},{0xD5,0x01},{0xD7,0x02},{0xD6,0x01},{0xD2,0x04},{0xD3,0x01},{0xD1,0x02},{0xD0,0x01},
{0xF0,0x20},{0xF1,0x01},{0xF3,0x02},{0xF2,0x01},{0xF6,0x04},{0xF7,0x01},{0xF5,0x02},{0xF4,0x01},
{0xFC,0x08},{0xFD,0x01},{0xFF,0x02},{0xFE,0x01},{0xFA,0x04},{0xFB,0x01},{0xF9,0x02},{0xF8,0x01},
{0xE8,0x10},{0xE9,0x01},{0xEB,0x02},{0xEA,0x01},{0xEE,0x04},{0xEF,0x01},{0xED,0x02},{0xEC,0x01},
{0xE4,0x08},{0xE5,0x01},{0xE7,0x02},{0xE6,0x01},{0xE2,0x04},{0xE3,0x01},{0xE1,0x02},{0xE0,0x01},
{0xA0,0x40},{0xA1,0x01},{0xA3,0x02},{0xA2,0x01},{0xA6,0x04},{0xA7,0x01},{0xA5,0x02},{0xA4,0x01},
{0xAC,0x08},{0xAD,0x01},{0xAF,0x02},{0xAE,0x01},{0xAA,0x04},{0xAB,0x01},{0xA9,0x02},{0xA8,0x01},
{0xB8,0x10},{0xB9,0x01},{0xBB,0x02},{0xBA,0x01},{0xBE,0x04},{0xBF,0x01},{0xBD,0x02},{0xBC,0x01},
{0xB4,0x08},{0xB5,0x01},{0xB7,0x02},{0xB6,0x01},{0xB2,0x04},{0xB3,0x01},{0xB1,0x02},{0xB0,0x01},
{0x90,0x20},{0x91,0x01},{0x93,0x02},{0x92,0x01},{0x96,0x04},{0x97,0x01},{0x95,0x02},{0x94,0x01},
{0x9C,0x08},{0x9D,0x01},{0x9F,0x02},{0x9E,0x01},{0x9A,0x04},{0x9B,0x01},{0x99,0x02},{0x98,0x01},
{0x88,0x10},{0x89,0x01},{0x8B,0x02},{0x8A,0x01},{0x8E,0x04},{0x8F,0x01},{0x8D,0x02},{0x8C,0x01},
{0x84,0x08},{0x85,0x01},{0x87,0x02},{0x86,0x01},{0x82,0x04},{0x83,0x01},{0x81,0x02},{0x80,0x01}
};
比较乱,没办法,这里有255个组,每组的第一位是这个组的值,第二位是异或位.
记住,格雷码的好处是,每个相邻变化,在二进制中仅仅有一位改变.我用格雷码的最初原因是因为只更新IP的一个byte情况下较为简单,而选择格雷码表就简单很多,仅仅需要加一次.如果用递增方式更新IP,会产生多个bit位的改变(比如5[0101]->6[0110],这里同时改变了两个bit) 对于加法不利.后来因为需要多个位的改变(同时更新IP和端口),使得判断bit位变得很复杂.所以权衡了一下,还是选择了递增方式更新IP的做法(虽然此法要比最快的单格雷码变化要慢上一倍,不过更加适用于实际).
异或位表还是采用的格雷码表,便于定位是哪个位需要更新.因为效验和计算的时候,是按16位为单位计算的,所以可以分析出:
例如
IP:1.2.3.4
端口:0x0506
那么计算时候是这样的
0x0201
+
0x0403
+
0x0506
+
…..
那么02所在的位,04所在的位,端口05所在的位如果更新了,加上的格雷码异或位需要左移八个位置.
好了,下面这个是算法:
sip = 0; sport = 0;
psip = (unsigned char*) & sip;
psport = (unsigned char*) & sport;
stt2 = (unsigned char*) & tt2;
ft_cc[5] = psport[1];
ft_cc[4] = psport[0];
ft_cc[3] = psip[3];//01
ft_cc[2] = psip[2];//02
ft_cc[1] = psip[1];//03
ft_cc[0] = psip[0];//04
{
sip ++;
sport ++; //更新ip和端口
tmp_sum = 0;
//判断是否和上次的IP值不一样,大于则加,小于则减
//if(gray_code[psip[0]][0] != gray_code[ft_cc[0]][0]){
if(psip[0] != ft_cc[0]){
if(gray_code[psip[0]][0] > gray_code[ft_cc[0]][0]){
tmp_sum += ((unsigned short)gray_code[psip[0]][1] << 8 | 0x00);
}else{
tmp_sum -= ((unsigned short)gray_code[psip[0]][1] << 8 | 0x00);
}
ft_cc[0] = psip[0];
//if(gray_code[psip[1]][0] != gray_code[ft_cc[1]][0]){
if(psip[1] != ft_cc[1]){
if(gray_code[psip[1]][0] > gray_code[ft_cc[1]][0]){
tmp_sum += (unsigned short)gray_code[psip[1]][1];
}else{
tmp_sum -= (unsigned short)gray_code[psip[1]][1];
}
ft_cc[1] = psip[1];
//if(gray_code[psip[2]][0] != gray_code[ft_cc[2]][0]){
if(psip[2] != ft_cc[2]){
if(gray_code[psip[2]][0] > gray_code[ft_cc[2]][0]){
tmp_sum += ((unsigned short)gray_code[psip[2]][1] << 8 | 0x00);
}else{
tmp_sum -= ((unsigned short)gray_code[psip[2]][1] << 8 | 0x00);
}
ft_cc[2] = psip[2];
//if(gray_code[psip[3]][0] != gray_code[ft_cc[3]][0]){
if(psip[3] != ft_cc[3]){
if(gray_code[psip[3]][0] > gray_code[ft_cc[3]][0]){
tmp_sum += (unsigned short)gray_code[psip[3]][1];
}else{
tmp_sum -= (unsigned short)gray_code[psip[3]][1];
}
ft_cc[3] = psip[3];
}
}
}
}
//判断是否和上次的端口值不一样,大于则加,小于则减
//if(gray_code[psport[0]][0] != gray_code[ft_cc[4]][0]){
if(psport[0] != ft_cc[4]){
if(gray_code[psport[0]][0] > gray_code[ft_cc[4]][0]){
tmp_sum += ((unsigned short)gray_code[psport[0]][1] << 8 | 0x00);
}else{
tmp_sum -= ((unsigned short)gray_code[psport[0]][1] << 8 | 0x00);
}
ft_cc[4] = psport[0];
//if(gray_code[psport[1]][0] != gray_code[ft_cc[5]][0]){
if(psport[1] != ft_cc[5]){
if(gray_code[psport[1]][0] > gray_code[ft_cc[5]][0]){
tmp_sum += (unsigned short)gray_code[psport[1]][1];
}else{
tmp_sum -= (unsigned short)gray_code[psport[1]][1];
}
ft_cc[5] = psport[1];
}
}
tpt2 = (unsigned short)~tt2 + tmp_sum;
tpt2 = (tpt2 >> 16) + (tpt2 & 0xffff);
tt2 = (unsigned short)(~tpt2);
}
这个算法可以更新IP和port,并更新的效验和使其有效,下面这个部分的
tpt2 = (unsigned short)~tt2 + tmp_sum;
tpt2 = (tpt2 >> 16) + (tpt2 & 0xffff);
tt2 = (unsigned short)(~tpt2);
tmp_sum就是格雷码异或位的和值.然后经过高位相加,最后存入效验和.这样更新出来的效验和与重新计算过后的是一样的.
到这里.基本上该说的都说完了,应该来说不是那么详细.
测试中1000万个效验和,只改变1byte(ip单位变化)的计算时间是230ms,同时改变3个byte(ip多位变化+端口)以上的计算时间只要600ms,而用正常方法计算得2800ms.
效验和计算是达到12倍的速度.经过发包测试(这个时候主要的瓶颈就在于sendto函数了),采用缓存池并发线程(一个线程专门负责计算效验和,另外开3 -n个线程用于发包),在我机器上可以满负荷运行,效率是目前最快的算法的程序的3-6倍,如果网络环境允许,可以达到10倍以上.
不要向我要求代码,有编程能力和数学能力的,看完我这篇垃圾的文章,应该就可以写出这样的算法.最后感谢这两天编写过程中给于我支持和一直帮我测试的朋友,有花须酌酒,LK007(小金).谢谢.好像没什么好说的了,我不善于写文章,也不知道大家看的懂不懂,细节也没说清楚,因为被DDOS的开发者拿去了,这个危害也就大了.另外请大家有什么问题可以给我来信(zvrop_at_163_dot_com)
