2011年8月18日木曜日

IP、TCP/UDP チェックサムについての覚え書き

【目的】
パケットを加工するプログラムを書いている際に、
IPのチェックサム部分のコードの実装を理解できず混乱してしまった。
ネットワークの初心者に戻ったつもりで、この機会にどういう仕組か把握しなおす。



【チェックサムを求める前の予備知識】
IPv4 パケット構造
先頭行はbyte。つまりこの図では一行4byteとして描いている。
 ----------------------------------------------------------------------
|        0        |       1        |        2        |        3        |
|----------------------------------------------------------------------|
| Version | HL※  | ServiceType    | TotalLength                       |
| ---------------------------------------------------------------------|
| Identifier                       | flag   | FragmentOffset           |
|----------------------------------------------------------------------|
| TTL             | Protocol       | CheckSum                          |
|----------------------------------------------------------------------|
| SourceIP                                                             |
|----------------------------------------------------------------------|
| DestIP                                                               |
 ----------------------------------------------------------------------
※HL : HeaderLength


チェックサムとは
チェックサムとはIPヘッダやTCP/UDPデータグラムに対し、
16ビットごとの1の補数和(1の補数の加算)を取り、さらにそれの1の補数を取ることである。

補数という言葉の定義に悩まされるが、
数学的な意味は脇に置き、チェックサムを計算するだけなら簡単にできる。
1の補数和を求めるためには、16ビットごとの値の和を単純に加算し、
オーバーフローしたぶんを足し込み、最後に論理否定を取ればいいのである。
とにもかくにも、実際に計算方法を見れば求め方はすぐに分かるだろう。


(補足)
IPはヘッダだけをチェックサムの対象にしているのにはわけがある。
IPパケットがフラグメント化された場合には、すべてのデータ部分が揃わないので、
チェックサムを計算することができなくなるからである。
フラグメント化されてもIPヘッダはすべてのIPパケットに含まれている。

ところで、TCP/UDPにもデータの中にIPヘッダを含めたチェックサムがある。
※IPアドレスの情報はIPヘッダ中から抜き出してくるだけであり、
当然TCPのパケットにはIP情報は存在しない。

ではIPプロトコルレベルでのチェックは不要なのではないか。
その通りであり、IPv6では廃止されている。
しかし、IPv4のICMPのチェックサムにはIPヘッダの情報は含まれないため、
念のためチェックした方がいいだろう。
ICMPv6ではチェックサムにIPヘッダの情報も含まれる。



【チェックサムを手動で計算】
2つのノード間でpingを打ち、
Wiresharkでそのパケットをダンプした。
その結果を元にIPプロトコルヘッダのチェックサムを計算してみる。










送信側
16ビットデータなので、2バイトの変数で計算をする

Version + HeaderLength + ServiceType : 0x4500
TotalLength                  : 0x003C
Identifier                   : 0xF228
Flag + FragmentOffset        : 0x0000
TTL + Protocol               : 0x8001
CheckSum                     : 0xC1400x0000
SourceIP                     : 0xC0A8
                               0x0303
DestIP                       : 0xC0A8
                               0x0304

1) 16ビットごとに値を加算
送信時の検証時にはチェックサムのフィールドを0で埋める。
0x4500 + 0x003C + 0xF228  + 0x0000 + 0x8001 + 0x0000 +  0xC0A8 + 0x0303 + 0xC0A8 + 0x0304
= 0x33EBC

2) オーバフローした分を足しこみ
16ビットとして桁上がりした分の値が16数で3である。
この桁上がり分を値を加算する。オーバーフローが3周分起きた、ということである。
0x3EBC + 0x3 = 0x3EBF

3) 1の補数
チェックサム通りの値になっているのでパケットは正常である。
~0x3EBC = 0xC140


・受信側
1) 16ビットごとに値を加算
チェックサムも含めて加算する。
0x4500 + 0x003C + 0xF228  + 0x0000 + 0x8001 + 0xC140 + 0xC0A8 + 0x0303 + 0xC0A8 + 0x0304
= 0x3FFFC

2) オーバフローした分を足しこみ
0xFFFC + 0x3 = 0xFFFF

0xFFFFであるのでパケットは正常である。



【疑問】
1の補数をとる理由
桁が上がりオーバフローした17ビット目を右に足し込める。
これによりバイトオーダに依存しないコードが書ける。
ここを参照されたい。


最後にさらに1の補数(否定)をする理由
受信者にとってチェックサムの検証が楽になるというのが答えである。

手動でチェックサムした手順を思い出しながら考えてほしい。

1) 最後に1の補数をとらない場合
(送信時)
チェックサムのフィールドを0にする。
パケット全体の1の補数和を取り(この結果をCとする)、
さらにその否定した値(この結果を!Cとする)を
チェックサムのフィールドに入れる。

(受信時)
受信したパケットのまずチェックサムの値をいったん脇にどける。
チェックサムのフィールドを0にする。
パケット全体の1の補数和を取り、チェックサムのフィールドに入れる。
脇にどけたチェックサムと比較する。

受信時にも送信時と同じ計算をするはめになる。


2) 最後に1の補数をとる場合
(送信時)
上記と同じである。

(受信時)
パケット全体の1の補数和の1の補数を計算する。
チェックサムのフィールドに!Cが埋まっている。


チェックサムのフィールド以外のパケットの1の補数和 = C
チェックサム部分 = !C

チェックサムのフィールドに!Cが埋まったパケット全体の1の補数和
= C + !C
= 0xFFFF



【チェックサムを自動化(プログラム化)】
1) IPプロトコルヘッダチェックサム

u_int16_t checksum(u_char *data, int len) {
  register u_int32_t sum;
  register u_int16_t *ptr;
  register int c;

  sum = 0;
  ptr = (u_int16_t *)data;

  for(c = len; c>1; c -= 2) {
    sum += (*ptr);
    // sumは32bitなので0x80000000を超えるとで
    // 次の足し合わせ時に桁あふれする恐れがある。
    // よってこの段階でオーバーフロー分を加算しておく。
    if(sum&0x80000000) {
      sum = (sum&0xFFFF) + (sum>>16);
    }
    ptr++;
  }

  if(c == 1) {
    u_int16_t val;
    val = 0;
    // 16bitの変数に8bitの値を前方に詰める。
    memcpy(&val, ptr, sizeof(u_int8_t));
    sum += val;
  }

  while(sum>>16) {
    sum = (sum&0xFFFF) + (sum>>16);
  }
  // 下でもよい。
  // sum = (sum&0xffff) + (sum>>16);
  // sum = (sum&0xffff) + (sum>>16);
  // オーバーフロー分を足し合わせる。
  // 足し合わせた結果、 さらにオーバフローする
  // 可能性があるためもう一度行う。

  // この結果が0または0xFFFFであればよい。
  return(~sum);
}



2) TCP/UDPプロトコルデータグラム チェックサム
TCP/UPDプロトコルのデータグラムのチェックサムの計算以外に、
IPプロトコルヘッダにオプションがある場合にも利用する。後から説明する。

u_int16_t checksum2(u_char *data, int len) {
  register u_int32_t sum;
  register u_int16_t *ptr;
  register int c;

  sum = 0;
  ptr=(u_int16_t *)data;

  for(c = len; c>1; c -= 2) {
    sum += (*ptr);
    // sumは32bitなので0x80000000を超えるとで
    // 次の足し合わせ時に桁あふれする恐れがある。
    // よってこの段階でオーバーフロー分を加算しておく。
    if(sum&0x80000000) {
      sum = (sum&0xFFFF) + (sum>>16);
    }
    ptr++;
  }

  if(c == 1) {
    u_int16_t val;
    val = 0;
    // 16bitの変数に8bitの値を前方に詰める。
    memcpy(&val, ptr, sizeof(u_int8_t));
    sum += val;
  }

  while(sum>>16) {
    sum = (sum&0xFFFF) + (sum>>16);
  }
  // 下でもよい。
  // sum = (sum&0xffff) + (sum>>16);
  // sum = (sum&0xffff) + (sum>>16);
  // オーバーフロー分を足し合わせる。
  // 足し合わせた結果、 さらにオーバフローする。
  // 可能性があるためもう一度行う。

  return(~sum);
}

u_int16_t checksum2(u_char *data1, int len1, u_char *data2, int len2) {
  register u_int32_t sum;
  register u_int16_t *ptr;
  register int c;

  sum = 0;
  ptr=(u_int16_t *)data1;

  for(c = len1; c>1; c -= 2) {
    sum += (*ptr);
    if(sum&0x80000000) {
      sum=(sum&0xFFFF) + (sum>>16);
    }
    ptr++;
  }

  if(c == 1) {
    u_int16_t val;
    val = ((*ptr)<<8) + (*data2);
    sum += val;
    if(sum&0x80000000) {
      sum = (sum&0xFFFF) + (sum>>16);
    }
    ptr = (u_int16_t *)(data2 + 1);
    len2--;
  }
  else {
    ptr = (u_int16_t *)data2;
  }

  for(c = len2; c>1; c -= 2) {
    sum += (*ptr);
    if(sum&0x80000000) {
      sum = (sum&0xFFFF) + (sum>>16);
    }
    ptr++;
  }

  if(c == 1) {
    u_int16_t     val;
    val = 0;
    memcpy(&val, ptr, sizeof(u_int8_t));
    sum += val;
  }

  while(sum>>16) {
    sum = (sum&0xFFFF) + (sum>>16);
  }

  return(~sum);
}


3) 使い方例

u_char  *ptr;

ptr = 受信したパケット

ptr += sizeof(struct iphdr);

// ihlは4byte単位である。
// つまり÷4されているので実際にバイト数を求めるに×4をする。
option_length=iphdr->ihl*4-sizeof(struct iphdr);

// IPパケットのオプションの存在を確認する。
if(option_length>0) {
  if(option_length >= 1500) {
    return(-1);
  }
  option = ptr;
  ptr += option_length;
}


// IPヘッダのチェックサムを求める。
if(check_ip(iphdr, option, option_length) == 0) {
  return(-1);
}


// データグラムのチェックサムを求める。
if(iphdr->protocol == IPPROTO_TCP) {
  len = ntohs(iphdr->tot_len)-iphdr->ihl*4;

  if(checksum_data(iphdr, ptr, len) == 0) {
    return(-1);
  }
}


////////////////////////////////////

int checksum_ip(struct iphdr *iphdr, u_char *option, int option_length) {
  unsigned short sum;

  if(option_length == 0) {
    sum = checksum((u_char *)iphdr, sizeof(struct iphdr));
    if(sum == 0 || sum == 0xFFFF) {
      return(1);
    }
    else {
      return(0);
    }
  }
  else{
    sum = checksum2((u_char *)iphdr, sizeof(struct iphdr), option, option_length);
    if(sum == 0 || sum == 0xFFFF) {
      return(1);
    }
    else {
      return(0);
    }
  }
}


////////////////////////////////////

// 疑似ヘッダである
struct pseudo_ip{
  struct in_addr  ip_src;
  struct in_addr  ip_dst;
  unsigned char   dummy;
  unsigned char   ip_p;
  unsigned short  ip_len;
};


int checksum_data(struct iphdr *iphdr, unsigned char *data, int len) {
  struct pseudo_ip p_ip;
  unsigned short sum;

  memset(&p_ip, 0, sizeof(struct pseudo_ip));
  p_ip.ip_src.s_addr = iphdr->saddr;
  p_ip.ip_dst.s_addr = iphdr->daddr;
  p_ip.ip_p = iphdr->protocol;
  p_ip.ip_len = htons(len);

  sum = checksum2((unsigned char *)&p_ip, sizeof(struct pseudo_ip), data, len);
  if(sum == 0 || sum == 0xFFFF) {
    return(1);
  }
  else {
    return(0);
  }
}


参考
http://d.hatena.ne.jp/kingkunikuni/20100116/1263631169
http://4049.nwr.jp/comp/ip_csum.html
http://www.morishima.net/~naoto/fragments/archives/2007/02/19/ip_tcp_udp_checksum/
http://www.mew.org/~kazu/doc/bsdmag/cksum.html



0 件のコメント:

コメントを投稿