IP校驗和詳解

      IP校驗和主要是用來保證資料（IP標頭）的完整性，就是反碼求和校驗.需要注意的是反碼求和又叫1的補碼(one's complement),而2的補碼就是我們通常說的補碼求和了.校驗算法具體如下.

1、發送方

  i)将校驗和字段置為0,然後将IP標頭按16比特分成多個單元,如標頭長度不是16比特的倍數,則用0比特填充到16比特的倍數;

!U#M^ATX

 ii)對各個單元采用反碼加法運算(即高位溢出位會加到低位,通常的補碼運算是直接丢掉溢出的高位),将得到的和的反碼填入校驗和字段;

iii)發送資料包;

2、接收方

  i)将IP標頭按16比特分成多個單元,如標頭長度不是16比特的倍數,則用0比特填充到16比特的倍數;

  ii)對各個單元采用反碼加法運算,檢查得到的和是否符合是全1(有的實作可能對得到的和會取反碼,然後判斷最終值是不是全0);

  iii)如果是全1則進行下步處理,否則意味着包已變化進而丢棄之.

   需要強調的是反碼和是采用高位溢出加到低位的,如3比特的反碼和算:100b+101b=010b(因為100b+101b=1001b,高位溢出1,其應該加到低位,即001b+1b(高位溢出位)=010b)

網上流傳多組實作,常見的有如下兩種(如追求效率可改寫為彙編代碼):

 1、RFC1071源碼

unsigned short csum(unsigned char *addr, int count)

{

/* Compute Internet Checksum for "count" */

* beginning at location "addr". */

register long sum = 0;

while( count > 1 )

{

/* This is the inner loop */

sum += * (unsigned short) addr++;

count -= 2;

}

/* Add left-over byte, if any */

if( count > 0 )

sum += * (unsigned char *) addr;

/* Fold 32-bit sum to 16 bits */

while (sum>>16)

sum = (sum & 0xffff) + (sum >> 16);

return ~sum;

}

   這個實作與前面的一個的最大的不同是對資料的長度沒什麼限制了,因為它在第一個循環的加法運算中實時檢測sum的高位的值,一旦發現其有溢出的危險,就及時運用等價運算關系消除了這個危險

    第一個while循環是做普通加法(2進制補碼加法),因為IP標頭和TCP整個封包段比較短(沒達到2^17數量級),是以不可能導緻4位元組的sum溢出(unsigned long 一般至少為4位元組)). 

    緊接着的一個判斷語句是為了能處理輸入資料是奇數個位元組的這種情況.  再接着的資料循環是實作反碼算法(在前面的普通加法得到的資料的基礎上),由反碼和的高位溢出加到低位的性質,可得到"32位的資料的高位比特移位16比特,再加上原來的低16比特,不影響最終結果"這個等價運算,因為sum的最初值(剛開始循環時)可能很大,是以這個等價運算需循環進行,直到sum的高比特(16比特以上)全為0.對于32位的sum,事實上這個運算循環至多隻有兩輪,是以也有程式直接用兩條"sum = (sum & 0xffff) + (sum >> 16);"代替了整個循環.

    最後,對和取反傳回.

2、對資料長度沒限制的實作

unsigned short cksum (struct ip *ip, int len)

{

long sum = 0; /* assume 32 bit long, 16 bit short */b

while ( len >1 )

{

sum += *((unsigned short *) ip)++;

if (sum & 8x00000000) /* if high-order bit set, fold */

sum = (sum & 0xFFFF) + (sum>> 16) ;

len -= 2;

}

if ( len ) /* take care of left over byte */

sum += ( unsigned short ) * (unsignedl char *) ip;

while ( sum >> 16)

sum =(sum & 0xFFFF) + (sum>> 16);

return ~sum;

}

 3、資料部分改變時的重校驗

   考慮這樣的應用場景:路由器轉發IP封包時,有可能隻更改了IP資料標頭的部分内容(如更改了TTL,分片了或SNAT更改了源IP等~~~),卻需要重校驗的問題.為提高轉發效率,要求重校驗算法盡可能快,故出現了如下所示的重校驗算法（隻是一個簡單的示例）:

 UpdateTTL(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));

}

算法的實作依據是這樣的.假設標頭原校驗和為~C,改變的字段的原始值是m,更改後的值是m',設~C'為重校驗和,則有 ~C' = ~(C+(-m)+m') = ~C+(m-m') = ~C+m+~m'  等價關系的成立基于反碼的運算性質:取反運算滿足結合律,按位取反運算與符号取反(及相反數)是等價的(即~C=-C).

)[email protected]+hL

   如果有多個字段改變，隻是上面的公式中的m和m'有多個而已，直接用反碼加法搞定即可。

2、為什麼采用反碼和運算

 IP資料包校驗要求速度快,是以隻采用了簡單的和校驗,為什麼采用反碼和而不是補碼和呢?

   i)反碼和的溢出有後效性(蔓延性)

    反碼和将高位溢出加到低位,導緻這個溢出會對後面操作有永久影響,有後效性;而補碼和直接将高位和溢出,導緻這個溢出對後面的操作再無影響,是以無後效性

   ii)反碼校驗無需考慮位元組序

    正因為反碼和的溢出有後效性,導緻大端位元組序(big-endian)和小端位元組序(little-endian)對同一資料序列(如兩個16比特的序列)産生的校驗和也隻是位元組序相反，而補碼和因為将溢出丢掉了,不同位元組序之間的校驗大不相同且沒什麼聯系.

   基于以上的理由，校驗和運算既可選擇在資料被轉換成網絡位元組序前，也可選擇在之後。（這其實可以看作是負負得正，計算校驗和與位元組序有關，然後寫校驗和字段與位元組序有關，然後直接計算校驗和再寫校驗和字段則與位元組序無關了~~）