IP チェックサムの秘密

注意

これは、山本和彦が BSD Magazine に掲載した原稿です。BSD Magazine 編集部の許可を得てここに転載します。図はありません。図が欲しい方は、BSD Magazine を買って下さい。:-)

IP チェックサムの秘密

本を読んで勉強しているときには気にもとめないのに、いざ実際にプログラムを作成すると疑問に思うことがある。これはやはり理解しようとする姿勢に差があるからだろう。

TCP/IP の仕様を読んでいるときは、IP チェクサムなんて読み飛ばしてしまう。しかし、カーネルの IP に関する部分をハックしていると、IP チェックサムの仕組みが気になって仕方がなくなった。

疑問に思ったら納得するまで調べる。これがハッカーの基本だ。このコラムは、IP チェックサムにまつわる冒険譚である。

IP チェックサム

IP チェックサムは、IP ヘッダや UDP/TCP データグラムに対し、通信時に起ったエラーを検出するために用意されている。以降では IP チェックサムのことを、単にチェックサムと呼ぶ。

チェックサムは、「対象となるパケットに対し、16ビットごとの 1 の補数和を取り、さらにそれの 1 の補数を取る」ことで計算する。これを単純に「1 の補数和の 1 の補数」と言う。

ここで「1 の補数和」とは何かという疑問が生じる。また、なぜ計算の最後に、わざわざ「1 の補数」を取るのかも不思議だ。

チェクサムは 16 ビットなので、以降では 16 ビットの世界で話を進めていく。しかし、本質は何ビットであっても変わりない。16 進数には 0x を前に付ける。それ以外は 10 進数である。

1 の補数と 2 の補数

まず、1 の補数と 2 の補数の定義を思い出そう。両者はそれぞれ、2 進数における負の数の表し方を定めている。

1 の補数では、負の数を表すために、「正数」表現に対し、単純に否定を取る。つまり、1 を 0 に、0 を 1 に変換する。

-1 を例にとろう。16 進数 4 桁では、1 は 0x0001 だ。これを否定すると、0xFFFE となる。すなわち、1 の補数の世界では、-1 を 0xFFFE と表現する。

2 の補数では、負の数を表すために、「正数」表現に対し、否定を取り、1 を足す。

再び -1 を例にとろう。否定した後、1 を足すのだから、2 の補数の世界では -1 を 0xFFFF と表現する。

16 ビットでは、1 の補数表現では

-32767 〜 32767

2 の補数表現では

-32768 〜 32767 

の数字を表せる。この関係は、次の図を見ると分かりやすいだろう。

「1 の補数」

      -2     -1     -0     +0      1      2
... ---+------+------+------+------+------+-- ...
    0xFFFD 0xFFFE 0xFFFF 0x0000 0x0001 0x0002

「2 の補数」

      -3     -2     -1      0      1      2
... ---+------+------+------+------+------+-- ...
    0xFFFD 0xFFFE 0xFFFF 0x0000 0x0001 0x0002

1 の補数の世界では、0xFFFF と 0x0000 との両方が 0 を表すことに注意。

1 の補数和と 2 の補数和

次に 1 の補数和と 2 の補数和について説明する。

まず、2 の補数和から。2 の補数和とは、2 の補数の世界での足し算だ。これは、2 の補数として表現した数字を単純に足すことを意味している。

たとえば、

10 - 11 = -1

を 2 の補数を使って計算してみよう。左辺は、

10 ＋ (-11)

と解釈できる。10 と -11 はそれぞれ、0x000A と 0xFFF5 である。

0x000A と 0xFFF5 を、正負など気にせずに単純に足せば、0xFFFF となる。これは -1 の 2 の補数表現に他ならない。

このように、2 の補数には、引き算を足し算に変換できるという性質がある。

2 の補数和の計算の際に、桁上がりが生じた場合は、表現範囲に収まらなかったとして、桁上がりを捨てる。

次に 1 の補数和について説明する。1 の補数和とは、1 の補数の世界での足し算だ。2 の補数に慣れている我々には、桁上がりで左にこぼれたビットを、右に足し込むと言えば分かりやすいかもしれない。

例として、0xFFFF と 0x1011 に対する 1 の補数和を取ることを考えよう。2 の補数和では、0x11010 だ。1 の補数和では、桁上がりを戻すので、0x1011 になる。

これは上の図を見ながら、こう考えると分かりやすい。2 の補数は、0xFFFF の次に桁上がりをして、0x0000 に戻る。

これに対し 1 の補数は、0xFFFF の次に桁上がりをして、0x0001 に戻るべきだ。なぜなら、0xFFFF は -0 なのだから、0x0000 の +0 を経由する必要はない。

よって、1 の補数和を、2 の補数和のように計算した場合は、桁上がりの際に 1 つ遅れることになるので、これを修正する必要がある。

なぜ 1 の補数なのか？

これまでに、なぜ 1 の補数なのか、我々が慣れ親しんだ 2 の補数ではだめなのかという疑問を持たれた人もいるだろう。

どうやら昔は、チェックサムに「2 の補数和の 2 の補数」を使っていた形跡がある。RFC 700 "A Protocol Experiment" の 7 章には、「チェックサムとして 『2 の補数和の 2 の補数』を使っているが、『1 の補数和の 1 の補数』の方がよいだろう」とう主旨の文章が載っている。

「1 の補数和の 1 の補数」が、「2 の補数和の 2 の補数」よりもなぜ優れているのか、私には分からない。エラー検出率が高いとすれば、それを理解するには群環論などの知識が必要になるだろう。

実装面から比べると、前者はバイトオーダに依存しないが、後者はバイトオーダを気にしながら計算する必要があるという差がある。

1 の補数和がバイトオーダに依存しない理由は、桁上がりが戻ってくるからだ。右にこぼれても、左にこぼれても、戻ってくれば一緒である。

またこの性質から派生して、コンピュータの自然な整数単位で計算し、16 ビットに変換しても同じ答になるという性質も持っている。

たとえば、32 ビットアーキテクチャのコンピュータでは、32 ビット単位でチェックサムを計算し、最後に上位 16 ビットと下位の 16 ビットを足せば答えが得られる。

2 の補数和には、このような性質はない。

なぜさらに 1 の補数をとるのか？

ではなぜチェックサムは、単純に 「1 の補数和」ではなく、「1 の補数和の 1 の補数」なのだろうか？ 最後にわざわざ否定する必要があるのだろうか？

この疑問には、RFC 1071 "Computing the Internet Checksum" が答えてくれる。理由は、受信者にとってチェックサムの検証が楽になるからだ。

もし仮に、単純な「1 の補数和」だったらどうなるだろう？

送信者がチェックサムを計算する際は、まずチェックサムのフィールドを 0 で埋める。そして、パケット全体の 1 の補数和を取り、それをチェックサムのフィールドに入れる。

受信者が検証する場合は、まずチェックサムの値を何かに記録する。そして、送信者と同様に、チェックサムのフィールドを 0 で埋め、パケット全体の 1 の補数和を取る。最後に、この 2 つの値が一致しているか比べる。

しかし、「1 の補数和の 1 の補数」なら、受信者はなにも気にせずパケット全体の「1 の補数和の 1 の補数」を取り、チェックサムが 0x0000 になるか確かめればよい。

これはどういうことだろう？ 送信者がチェックサムのフィールドを 0 に埋めて計算した 1 の補数和を C とする。実際のチェックサムはこの否定だから、!C になる。

チェックサムのフィールドに !C が埋まったパケット全体の 1 の補数和を取ると 0xFFFF になる。なぜなら、チェックサムのフィールド以外のパケットの 1 の補数和は C なので、C ╋ !C で 0xFFFF だ(╋ は 1 の補数の世界における足し算を表すとする。)。桁上がりは生じないことに注意。0xFFFF の否定は 0x0000 になる。

このように、受信者はチェックサムのフィールドを特別扱いすることなしに、チェックサムを検証できる。

UDP チェックサムの秘密

UDP チェックサムでは、送信者が「1 の補数和の 1 の補数」を計算した結果が 0x0000 になったら、0xFFFF に置き換えろと定義されている。

また、チェックサムのフィールドに 0x0000 の値があれば、それはチェックサムを計算していないこととして扱えとも規定されている。(余談になるが、最近では、UDP チェックサムの計算は必須となっている。)

0x0000 を 0xFFFF に置き換えてしまって、チェックサムの検証はうまくいくのだろうか？

実は 1 の補数和には、単位元が 2 つある。加算の単位元とは、足しても元の値が変化しない値のことだ。

単位元の 1 つが、0x0000 であるのは自明だろう。もう 1 つは、0xFFFF だ。これは、-0 を表すことからも納得できる。

納得できない人は次のように考えればよい。試しに 0x0000 以外の任意の値 X と、0xFFFF の 1 の補数和を取る。

X ╋ 0xFFFF

X を、X より 1 小さい Y を用いて表すと次のようになる。

Y ╋ 0x0001 ╋ 0xFFFF

0x0001 ╋ 0xFFFF は、桁上がりが戻ってくることを考えれば、0x0001 に等しいことが分かる。よって上の式は、

Y ╋ 0x0001

となる。これは、X に他ならない。

X が 0x0000 のときだけは、0xFFFF が単位元にならない。0x0000 と 0xFFFF の 1 の補数和を取ると、0xFFFF となり、値が変わるからだ。

UDP チェックサムに話を戻そう。チェックサムの値が 0x0000 になるのは、どういうときだろうか？

もちろん、チェックサムのフィールドを 0 で埋め、パケット全体の 1 の補数和を取った際に、0xFFFF となっている場合だ。これを A と呼ぼう。

本来チェックサムは 0x0000 となるべきだが、この場合は規定により 0xFFFF を埋める。これを B と呼ぼう。

検証の際は、A と B の「1 の補数和の 1 の補数」を取ることになる。

0xFFFF が 0x0000 以外の値に対し単位元になることに注意すれば、チェックサムの検証結果は次のように 0x0000 になる。

  !(A ╋ B)
= !(0xFFFF ╋ 0xFFFF)
= !0xFFFF
= 0x0000

よって、0x0000 を 0xFFFF にしても、UDP チェックサムはうまく検証できる。

NAT の秘密

もし、パケットの一部を配送中に変更した場合は、チェックサムを再計算する必要がある。たとえば、NAT のように、IP アドレスを変換した場合は、TCP/UDP チェックサムを適切な値に変更しなければならない。

ここでまた大きな疑問が湧く。たとえばもし、UDP パケットが IP レベルで分割されていたとしたら、NAT は UDP チェックサムをどう再計算すればよいのだろう？

NAT が IP パケットを再構成し、パケット全体にアクセスできるようにする必要があるのだろうか？

まず例外として、UDP チェックサムが 0x0000 の場合は、チェックサムは利用されていない。そこで、NAT はチェックサムを再計算する必要はない。

それ以外の場合、つまり UDP チェックサムが利用されている場合は、再計算する必要はなく、値を「補正」できる。

チェックサムは、結局は足し算だから、過不足を補えば十分だ。元のチェックサムの値を S、変更した部分の 1 の補数和の差分を Δ とすると、チェックサムは以下の公式で補正できる。

!(!S ╋ Δ)

ただし、S が 0xFFFF の場合はこれでうまく行くのだろうか？

「(i) 計算の結果 0xFFFF になった場合」と、「(ii) 0x0000 になったので 0xFFFF に変更した場合」 の 2 つについて、検証してみる必要があるだろう。

実際に両方の場合について計算してみよう。

(i) の場合は、

  !(!0xFFFF ╋ Δ)
= !(0x0000 ╋ Δ)
= !Δ

(ii) の場合は、

  !(!0x0000 ╋ Δ)
= !(0xFFFF ╋ Δ)
= !Δ

となり、(ii) を (i) と計算しても結果は同じになる。

鋭い人なら、Δ が 0x0000 のときは違うだろうと思うかもしれない。たしかに、この場合 (i) は 0xFFFF、(ii) は 0x0000 になる。

しかし、そもそも Δ が 0x0000 なら、補正する必要はない。

また (ii) は絶対に起こり得ないケースだ。なぜなら、1 の補数和が 0x0000(計算結果はこれを否定して 0xFFFF) となるのは、入力のビットがすべて 0 の場合に限る。このような UDP パケットは現実的には存在しない。よって、実際に考慮すべきなのは (i) だけだ。

このように、NAT は単純な計算でチェックサムを補正できる。実際の実現方法は、RFC 1631 "The IP Network Address Translator (NAT)" に載っている。

また、チェックサムの補正に関する詳しい考察は、RFC 1624 "Computation of the Internet Checksum via Incremental Update" を参照のこと。

おわりに

チェックサムの冒険譚はいかがだったろうか？ チェックサムのコードは、/usr/src/sys/netinet/in_cksum.c の中の in_cksum() という関数で実現されている。興味があれば、眺めて欲しい。