+があるので以下の Huffman 木の形に決まる(右の木を優先して作成する)。
+
+ .
+ / \
+ . . -- 階層1
+ / \
+ . . -- 階層2
+ / \
+ . . -- 階層3
+
+そして各階層毎に文字をコード順に割り当てると
+
+ .
+ / \
+ b . -- 階層1
+ / \
+ a . -- 階層2
+ / \
+ c d -- 階層3
+
+
+と一意に定まることとなる。(「階層毎のコード順」の意味が正確に伝わるよう
+あえて、b と a を逆にしてみた。)
+
+なお、{p,c,t}_len の値はある文字の階層の位置を示すが、これはつまりある
+文字を Huffman 符号化したときの符号長(bit 長)を示していることになる。以
+降、{p,c,t}_len は添え字が復号語、値が符号長を表す配列であるものとして
+説明を行う。この配列のサイズは圧縮対象の文字集合の要素数であり、各要素
+は 0..16 の値を持つ。(LHA の Huffman 木のルールで木の階層は 16 までとなっ
+ている)そして、値 0 はその文字が平文に現れないことを示す。
+
+----------------------------------------------------------------------------
+ Huffman 木 要素数 値の範囲 要素数のビット長
+ (配列) (符号長)
+ p_len np 0..16 pbit
+ c_len NC 0..16 CBIT
+ t_len NT 0..16 TBIT
+
+ 要素数は圧縮対象の文字集合の数
+ c_len[x]=0 の場合、文字 x は複合した結果に現れない
+ 要素数のビット長は要素数を表現するのに必要なビット
+ 長(この後で出てくる)
+----------------------------------------------------------------------------
+
+では、Huffman 木の情報の出力形式について整理しよう。
+
+まず、p_len[] の出力フォーマットを下記に示す。
+
+----------------------------------------------------------------------------
+< p_len[] の出力フォーマット >
+
+ 0 pbit{4 or 5}
+ +-------+-----------+-----------+-- --+-----------+
+ | n | p_len[0] | p_len[1] | ... p_len[n-1]|
+ +-------+-----------+-----------+-- --+-----------+
+
+p_len[i] <= 6 の場合
+
+ 0 3bit
+ +-----+
+ p_len[i] | | | |
+ +-----+
+
+p_len[i] >= 7 の場合
+
+ 0 p_len[i] - 3
+ +----------------+
+ p_len[i] |1 1 1 1 ... 1 0 |
+ +----------------+
+
+p_len[n...np] は、0 となる。
+
+----------------------------------------------------------------------------
+
+先にも書いた通り p_len は位置の値の必要ビット長を Huffman 符号化したと
+きの木の情報である。スライド辞書のサイズは dicsiz であり -lh7- の場合で
+16 bit で位置を指すことができるから、p_len は位置のビット長 0 .. 16 の
+17個(np個)の値を Huffman 符号化した結果(の符号長)である。
+
+そして p_len 自体の出力については、0 .. 6 の値(Huffman 符号長)について
+は 3 bit で、それ以上の値については 0 が現れるまでのビット数で表すよう
+になっている。
+
+なお p_len は np 個の固定長配列だが、出力形式としては先頭に pbit 幅
+の p_len の要素数を出力している。これはなぜかというと p_len の後方の値
+(p_len[n...np])が 0 である場合にその要素を出力しないで済むようにするた
+めである。これは他の Huffman 符号についても同様である。
+
+# なぜ、このような形式になっているか考えてみた。
+#
+# p_len の値の範囲は、0 .. 16 であるから 1 要素は 6 bit で表現可能であり、
+# 単純に出力した場合を考えると 6 * 17 = 102 bit で表現可能である。
+#
+# 一方、p_len の出力形式の場合、LHA の Huffman 木の階層は最大 16 階層であ
+# ることから、最悪すべての p_len[] についてビット数の形式(p_len[] >= 7)
+# が使われた場合 1 つの p_len[] に 16-3 bit * 17 = 221 bit 使うことにな
+# り最悪の使用領域は大きくなってしまうように思えてしまう。
+#
+# しかし、実際にはそうはならない。というのも np が 17 であるから
+# Huffman 木の葉の数は最大でも 17 にしかならない。そして葉の数が np で
+# 最も Huffman 木が深くなるのは
+#
+# .
+# / \
+# . . -- 1 階層目
+# / \
+# . . -- 2 階層目
+# / \
+# . . -- 3 階層目
+# :
+# .
+# / \
+# . . -- 16 階層目
+#
+# となる場合で、この場合の p_len の出力ビット長は
+#
+# 2*(16-3) + (15-3) + ... (7-3) + 6*3
+# = 2*13 + 12 + ... 4 + 18
+# = 167 bit
+#
+# である。単純に出力する場合に比べると 65 bit 増える。また、1 階層減ら
+# した場合は、
+#
+# .
+# / \
+# . . -- 1 階層目
+# / \
+# . . -- 2 階層目
+# / \
+# . . -- 3 階層目
+# :
+# / \
+# . . -- 13 階層目
+# / \
+# . .
+# / \ / \
+# . . . . -- 15 階層目
+#
+# 4*(15-3) + (13-3) + ... (7-3) + 6*3
+# = 4*12 + 10 + ... 4 + 18
+# = 115 bit
+#
+# である。なお、この木の場合も葉は np 個ある。もう 1 階層減らしてみよう。
+#
+# .
+# / \
+# . . -- 1 階層目
+# / \
+# . . -- 2 階層目
+# / \
+# . . -- 3 階層目
+# :
+# / \
+# . . -- 12 階層目
+# / \ / \
+# . . . . -- 13 階層目
+# / \ / \
+# . . . . -- 14 階層目
+#
+#
+# 4*(14-3) + 2*(13-3) + (11-3) + ... + (7-3) + 6*3
+# = 4*11 + 2*10 + 8 + ... 4 + 18
+# = 112 bit
+#
+# この調子で、さらに減らすと
+#
+# 13 階層
+# 4*(13-3) + 2*(12-3) + (10-3) + ... + (7-3) + 6*3
+# = 4*10 + 2*9 + 7 + ... + 4 + 18
+# = 98
+#
+# 13 階層目で単純に出力するよりも小さくなった。感覚的には、あまり効果は
+# 期待できないように見える。これは恐らくは p_len については符号長が 6
+# 以下になる場合が多いのであろう(すべてが 6 以下であれば、3 * 17 = 51
+# bit であり 51 bit 削減できる)。階層が 6 である Huffman 木の葉の数は最
+# 大 2^6 {64} であるから NP{17} 種類の平文を格納する率が高いのであろう。
+
+続いて c_len[] の出力フォーマットを示す。
+
+----------------------------------------------------------------------------
+< c_len[] の出力フォーマット >
+
+ 0 CBIT{9}
+ +-------+-----------+-----------+-- --+-----------+
+ | n | c_len[0] | c_len[1] | ... c_len[n-1]|
+ +-------+-----------+-----------+-- --+-----------+
+
+c_len[i] == 0 の場合
+
+ 0 が続く数を count とすると、
+
+ count == 1 の場合
+
+ t_len[0]
+ <---------->
+ +------------+
+ | t_code[0] |
+ +------------+
+
+ count == 2 の場合
+
+ t_len[0] t_len[0]
+ <----------> <---------->
+ +------------+------------+
+ | t_code[0] | t_code[0] |
+ +------------+------------+
+
+ count == 3..18 の場合
+
+ t_len[1] 4 bit
+ <----------> <------>
+ +------------+-------+
+ | t_code[1] |count-3|
+ +------------+-------+
+
+ count == 19 の場合
+
+ t_len[0] t_len[1] 4 bit
+ <----------> <----------> <------>
+ +------------+------------+-------+
+ | t_code[0] | t_code[1] |count-3|
+ +------------+------------+-------+
+
+ count >= 20 の場合
+
+ t_len[2] CBIT{9}
+ <----------> <------>
+ +------------+--------+
+ | t_code[2] |count-20|
+ +------------+--------+
+
+c_len[i] > 0 の場合
+
+ t_len[c_len[i]+2]
+ <----------------->
+ +-------------------+
+ | t_code[c_len[i]+2]|
+ +-------------------+
+
+c_len[n...NC] は、0 となる。
+
+----------------------------------------------------------------------------
+
+c_len[] の値はある程度 0 が連続する場合が多いことが期待できる。
+c_len[i]=0 の場合というのはその文字(i)が平文に現れない場合を示す。
+ASCII テキストファイルの圧縮なら 0..127 の範囲のコードしか使われないた
+めそれ以外は 0 になるなどである。そして c_len を単純に出力することを考
+えたとき c_len[i]=0 である情報を多数出力することになり領域が無駄である
+(c_len は NC{255+256+2-3=510} 個の要素を持ちその中で未使用文字や未使用
+長が多数あることを想定している)。そこで 0 が連続して現れる特徴を生かし
+
+ o c_len[]=0 が連続で1個
+ o c_len が連続で 3〜18 個
+ o c_len が連続で20個以上(20〜NC{510})
+
+をそれぞれ一つの文字と見なして Huffman 符号化することで c_len 自体の出
+力サイズを小さくしている。これは 0 の出現頻度を単純に Huffman 符号化す
+るよりも効果が期待できる。
+
+上図で t_code は c_len を Huffman 符号化したときの符号表を示しており
+
+ o t_code[0] ... c_len[i] は 0 が 1 個
+ o t_code[1] ... c_len[i] は 0 が 3〜18 個(続く4 ビットのビット列で
+ 個数がわかる)
+ o t_code[2] ... c_len[i] は 0 が 20〜NC-1個(続く CBIT ビットのビット
+ 列で個数がわかる)
+ o t_code[x] ... c_len[i]=x-2 (x>2)
+
+と復号することになる。c_len[i] = 0 が 2 個あるいは 19 個続く場合は
+
+ t_code[0] が 2 個
+ t_code[0] と t_code[1] が 1 個ずつ
+
+で出力されている。
+
+最後に、t_len[] の出力フォーマットを示す。
+
+----------------------------------------------------------------------------
+< t_len[] の出力フォーマット >
+
+ 2 bit
+ 0 TBIT{5} |--|
+ +-------+----------+----------+----------+--+----------+- -+-----------+
+ | n | t_len[0] | t_len[1] | t_len[2] | x|t_len[x+3]| ... | t_len[n-1]|
+ +-------+----------+----------+----------+--+----------+- -+-----------+
+
+t_len[i] <= 6 の場合
+
+ 0 3bit
+ +-----+
+ t_len[i] | | | |
+ +-----+
+
+t_len[i] >= 7 の場合
+
+ 0 t_len[i] - 3
+ +----------------+
+ t_len[i] |1 1 1 1 ... 1 0 |
+ +----------------+
+
+t_len[2] の直後は 2 bit の情報が付加される。この値を x{0..3} とすると、
+t_len[3 .. x+2] の範囲で 0 が続くことを意味し、この 2 bit 以降は、
+t_len[x+3] が続くことになる。x が 0 の場合は、t_len[3] は 0 ではない。
+
+t_len[n...NT] は、0 となる。
+
+----------------------------------------------------------------------------
+
+基本的な考えは p_len[] の場合と同じである(t_len[] の要素数 NT は 19)。
+ただし t_len[3..5] について特別扱いされている。
+
+まず、t_len[] と c_len[x] の値の対応を以下に整理し直す。
+
+ t_len[0] c_len[x]=0 1 つを 1 文字とみなす
+ t_len[1] c_len[x]=0 が 3〜18 個連続している塊を 1 文字とみなす
+ t_len[2] c_len[x]=0 が 20〜NC{510} 個連続している塊を 1 文字とみなす
+ t_len[3] c_len[x]=1
+ t_len[4] c_len[x]=2
+ t_len[5] c_len[x]=3
+ t_len[6] c_len[x]=4
+ :
+ t_len[18] c_len[x]=16
+
+t_len[3..5] の特別扱いについて考えると t_len[3..5] の範囲で 0 が連続す
+る場合に、2 ビットでそのことを表している。これはつまりこのような場合が
+多いのであろう。上で対応関係を示したとおり、t_len[3..5] が 0 である場合
+というのは、つまりビット長 c_len[x] が 1..3 の範囲の値を持たない場合を
+示す。
+
+# c_len[x] が 1..3 の値を持つ場合というのは Huffman 木においてある 3 文字
+# の出現頻度が極端に多い場合を示す。このような場合はあまりないであると想
+# 定しているのだろう。
+#
+# .
+# / \
+# a .
+# / \
+# b .
+# / \
+# c .
+# / \
+# . .
+# / \ / \
+
+以上で LHA ファイルの構造についてひととおり説明したことになる。ただし、
+復号処理を考える場合に注意事項がある。これはこの後で説明しよう。
+
+\f
+セキュリティバグの考察
+----------------------
+
+2006年8月 LHA の復号処理にセキュリティバグ(CVE-2006-4335,4337,4338)が発
+見された。この問題は LHA の実装において符号化については当然あらゆる入力
+ファイルを想定した処理となっているが復号については圧縮ファイルが正しい
+構造、値で作成されていることしか想定せずに処理が作られていたためである。
+つまり、不正な圧縮ファイルが与えられた場合の動作が不定だったのだ。
+
+ここでは、LHA の復号において注意すべき点について考察する。また、ここま
+でに解読した LHa for UNIX ver.1.14i のソースはこのセキュリティバグが
+残っていたものなので、セキュリティバグの対策を行ったソースについても後
+で解析を行うこととする。
+
+以下、LHA の構造を再掲し、各復号処理で注意すべき点を確認しよう。
+以降の説明では注意点毎に (1) (2) のように番号を振っている。最終的に
+全チェックポイントをチェックするように修正したソースを載せ、この番号で
+紐付けを行うこととする。
+
+----------------------------------------------------------------------------
+< LHA ファイルの構造(1 ブロック分) >
+
+ +-----------+
+ | blocksize |
+ +-----------+
+ 16bit
+
+ ハフマン木
+ +-----------+-----------+-----------+
+ | t_len | c_len | p_len |
+ +-----------+-----------+-----------+
+
+ 圧縮文(文字と長さ、位置のビット長のハフマン符号と位置の値)
+ +---------------------+
+ | 圧縮文 |
+ +---------------------+
+
+----------------------------------------------------------------------------
+
+(1)
+blocksize の読み込みについてこの値は 1〜0xffff については正しいが 0 に
+なることはあり得ないので 0 の場合に不正と判断してもよいと思われる。
+
+(2)
+「圧縮文」自体については、blocksize 数を頼りに読み込むので blocksize を
+越えて圧縮文が存在しても次の block として読まれるだけである。blocksize
+に満たない場合は、EOF を検知して早期に不正と判断するように処理した方が
+よいだろう。
+
+圧縮文中の文字と長さについては
+
+ 復号した1文字 >= 256 の場合
+ 長さを示す。(そしてその直後に位置の Huffman 符号がある)
+
+ 復号した1文字 < 256 の場合
+ 文字を示す。
+
+であり、文字としては 0 .. 255 すべてについて正しい値なので問題はない。
+
+(3)
+長さは 256 ... NC{256+maxmatch-3+1} の範囲の値を取るのでこれを超える値
+を返す場合は不正と判断してもよい。ただし、この判定自体は c_len を読み込
+み Huffman 木を構築するときに行うこともできる。(実際、実装では
+Huffman 木にこの範囲内の復号語しか割り当てないのでバグでない限りは発生
+しないだろう)
+
+位置については下図の通り位置のビット長の Huffman 符号と位置の値が書かれ
+ている。
+
+ +------------------------------+----------+
+ | 位置のビット長の Huffman 符号| 位置の値 |
+ +------------------------------+----------+
+
+(4)
+位置の値としては 0 ... 2^dicbit の範囲の値を持つので Huffman 符号の復号
+結果が 0 ... np{dicbit+1} の範囲であれば位置の値部分についてチェックす
+る必要はない。従って、c_len と同じくハフマン木の構築の段階で不正な復号
+語を返さないようにしていればよい。
+
+では、t_len について見てみる。
+
+----------------------------------------------------------------------------
+< t_len[] の出力フォーマット >
+
+ 2 bit
+ 0 TBIT{5} |--|
+ +-------+----------+----------+----------+--+----------+- -+-----------+
+ | n | t_len[0] | t_len[1] | t_len[2] | x|t_len[x+3]| ... | t_len[n-1]|
+ +-------+----------+----------+----------+--+----------+- -+-----------+
+
+t_len[i] <= 6 の場合
+
+ 0 3bit
+ +-----+
+ t_len[i] | | | |
+ +-----+
+
+t_len[i] >= 7 の場合
+
+ 0 t_len[i] - 3
+ +----------------+
+ t_len[i] |1 1 1 1 ... 1 0 |
+ +----------------+
+
+t_len[2] の直後は 2 bit の情報が付加される。この値を x{0..3} とすると、
+t_len[3 .. x+2] の範囲で 0 が続くことを意味し、この 2 bit 以降は、
+t_len[x+3] が続くことになる。x が 0 の場合は、t_len[3] は 0 ではない。
+
+t_len[n...NT] は、0 となる。
+
+----------------------------------------------------------------------------
+
+(5)
+t_len の出力フォーマットの先頭 TBIT{5} は 0 ... 2^5{32} の範囲の値を格
+納できるが t_len の領域サイズは NT{19} なので 0..19 の範囲を超える場合
+は不正と判断しなければならない。
+
+(6)
+また、t_len[i] >= 7 の場合の形式は bit 0 を検出するまでのビット長が値と
+なるが t_len[i] の値はハフマン符号長なので 0 .. 16 の範囲でなければなら
+ない。t_len[i] >= 7 の形式の具体的な値の対応は
+
+ 7: 1110
+ 8: 1111 0
+ :
+ 15: 1111 1111 1110
+ 16: 1111 1111 1111 0
+
+となっているので、16 の場合のビット長(1 が 12 bit 続く)よりビット長が長
+い場合は不正である。(最大 12 ビットまでしか見ないとすることも考えられるが、
+LHA の圧縮処理は上の例のように 16 の場合でもビット 0 を出力するので、そ
+のような読み方をすると正常な圧縮文を復号できなくなる。)
+
+(7)
+さらに、t_len を読み込んだ後に構築した Huffman 木は Huffman 木として整合
+性が保たれなければならない。
+たとえば、LHA における Huffman 木は以下の性質が守られなければならないは
+ずだ。
+
+ o t_len[x] <= 16 (LHA の Huffman 木の階層は 16 までである)
+
+ o 各階層の葉の数は整合性が保たれなければならない。例えば、1 階層目の
+ 葉の数は最大 2 であり、このとき下位の階層の葉の数は 0 である。各節
+ は必ず節か葉を持つ。など。
+
+後で処理を解析する際にこの辺りを確認しよう。
+なお、1 点目については前述の通り t_len の読み込み時にチェックできる。
+2 点目については実装では非常にうまい方法でチェックしている。
+
+続いて c_len[] の出力フォーマットについて考える。
+
+----------------------------------------------------------------------------
+< c_len[] の出力フォーマット >
+
+ 0 CBIT{9}
+ +-------+-----------+-----------+-- --+-----------+
+ | n | c_len[0] | c_len[1] | ... c_len[n-1]|
+ +-------+-----------+-----------+-- --+-----------+
+
+c_len[i] == 0 の場合
+
+ 0 が続く数を count とすると、
+
+ count == 1 の場合
+
+ t_len[0]
+ <---------->
+ +------------+
+ | t_code[0] |
+ +------------+
+
+ count == 2 の場合
+
+ t_len[0] t_len[0]
+ <----------> <---------->
+ +------------+------------+
+ | t_code[0] | t_code[0] |
+ +------------+------------+
+
+ count == 3..18 の場合
+
+ t_len[1] 4 bit
+ <----------> <------>
+ +------------+-------+
+ | t_code[1] |count-3|
+ +------------+-------+
+
+ count == 19 の場合
+
+ t_len[0] t_len[1] 4 bit
+ <----------> <----------> <------>
+ +------------+------------+-------+
+ | t_code[0] | t_code[1] |count-3|
+ +------------+------------+-------+
+
+ count >= 20 の場合
+
+ t_len[2] CBIT{9}
+ <----------> <------>
+ +------------+--------+
+ | t_code[2] |count-20|
+ +------------+--------+
+
+c_len[i] > 0 の場合
+
+ t_len[c_len[i]+2]
+ <----------------->
+ +-------------------+
+ | t_code[c_len[i]+2]|
+ +-------------------+
+
+c_len[n...NC] は、0 となる。
+
+----------------------------------------------------------------------------
+
+(8)
+c_len の出力フォーマットの先頭 CBIT{9} は 0 ... 2^9(512) の範囲の値を
+格納できるが c_len の領域サイズは NC{510} なので 0..510 の範囲を超える
+場合は 不正と判断しなければならない。
+
+(9)
+また、
+ count >= 20 の場合
+ count == 3..18 の場合
+
+のそれぞれの形式において count の数だけ c_len[i] は 0 が続くがこれが
+c_len の*残り*サイズを越える場合も不正である。
+
+(10)
+さらに、c_len[i] > 0 の場合の形式において、t_len[x] を復号した結果が
+c_len[i]{x}+2 の値でありc_len[i] の値はハフマン符号長なので 0 .. 16 の
+範囲でなければならない。これは、c_len, p_len と同じく t_len のハフマン
+木の構築の段階で不正な復号語を返さないようにしていればよい。
+
+(11)
+もちろん、t_len のときと同様 c_len を読み込んだ後に構築した Huffman 木
+は Huffman 木として整合性が保たれなければならない。
+
+続いて p_len[] の出力フォーマットについて考える。
+
+----------------------------------------------------------------------------
+< p_len[] の出力フォーマット >
+
+ 0 pbit{4 or 5}
+ +-------+-----------+-----------+-- --+-----------+
+ | n | p_len[0] | p_len[1] | ... p_len[n-1]|
+ +-------+-----------+-----------+-- --+-----------+
+
+p_len[i] <= 6 の場合
+
+ 0 3bit
+ +-----+
+ p_len[i] | | | |
+ +-----+
+
+p_len[i] >= 7 の場合
+
+ 0 p_len[i] - 3
+ +----------------+
+ p_len[i] |1 1 1 1 ... 1 0 |
+ +----------------+
+
+p_len[n...np] は、0 となる。
+
+----------------------------------------------------------------------------
+
+(12)
+p_len の出力フォーマットの先頭 pbit{4 or 5} は 0 ... 2^4{16} or
+2^5{32} の範囲の値を格納できるが p_len の領域サイズは np{14..17} なので
+0..np の範囲を超える場合は不正と判断しなければならない。
+
+ところで復習になるが np は、各圧縮メソッドの辞書のサイズで決まる。対応
+を以下に再掲するので確認してほしい。(-lh4- の場合の np はなぜか 13 では
+なく14 となっている。おそらく、LHA が実装された当時 -lh6-, -lh7- は存在
+せず np や pbit は固定値(定数 NP, PBIT)であったため、-lh4-, -lh5- の両
+方に対応できるよう変数の領域サイズを合わせただけであると思う。つまり、
+圧縮処理においては、-lh4- の np を 13 と想定しても問題は発生しないと思
+われる。逆に復号処理においては、(gzip のように)圧縮 method の情報が渡さ
+れない場合は np を 14 とするしかない。なお、このような(gzip のような)
+場合 -lh6,7- への対応はできない。最初の pbit 分の要素数の読み込みで 4
+ビット読めばよいのか 5 ビット読めばよいのかがわからないからである)
+
+ method maxmatch dicsiz dicbit np(dicbit+1) pbit
+ -----------------------------------------------------------
+ -lh4- 256 2^12 12 14 (or 13?) 4 (14<2^4)
+ -lh5- 256 2^13 13 14 4 (14<2^4)
+ -lh6- 256 2^15 15 16 5 (16<2^5)
+ -lh7- 256 2^16 16 17 5 (17<2^5)
+
+(13)
+また、t_len と同様に、p_len[i] >= 7 の形式では、1 が 12 bit より多く連
+続した場合に不正である。
+
+(14)
+もちろん、p_len[] を読み込んだ後に構築した Huffman 木の整合性が保たれな
+ければならない点は他の Huffman 木と同じだ。
+
+では、実際に復号処理のセキュリティ対応を行ったソースを基に実装を確認しよう。
+
+\f
+以下は、
+
+ https://bugzilla.redhat.com/show_bug.cgi?id=204676
+
+にて掲載されたパッチある。このパッチは gzip 用のパッチであったが内容は
+ほとんど同じである。(gzip は LHA とほとんど同じ復号処理のソースを含んで
+おり、LHA の圧縮形式を復号することができる。ただ、LHA ヘッダを読むこと
+はできないため lzh ファイルを展開できるわけではない。見たところ
+-lh4,lh5- にのみ対応している。)
+
+diff -ru gzip-1.3.5.orig/unlzh.c gzip-1.3.5/unlzh.c
+--- gzip-1.3.5.orig/unlzh.c 1999-10-06 06:00:00.000000000 +0100
++++ gzip-1.3.5/unlzh.c 2006-08-18 22:56:19.446997000 +0100
+@@ -149,13 +149,17 @@
+ unsigned i, k, len, ch, jutbits, avail, nextcode, mask;
+
+ for (i = 1; i <= 16; i++) count[i] = 0;
+- for (i = 0; i < (unsigned)nchar; i++) count[bitlen[i]]++;
++ for (i = 0; i < (unsigned)nchar; i++) {
++ if (bitlen[i] > 16)
++ error("Bad table (case a)\n");
++ else count[bitlen[i]]++;
++ }
+
+bitlen は、c_len, p_len, t_len であり、いずれの Huffman 木も最大の階層
+は 16 までであるからその範囲を超えたものがないかチェックしている。これ
+は、セキュリティバグの重要な改修点の1点目である。
+
+ start[1] = 0;
+ for (i = 1; i <= 16; i++)
+ start[i + 1] = start[i] + (count[i] << (16 - i));
+- if ((start[17] & 0xffff) != 0)
+- error("Bad table\n");
++ if ((start[17] & 0xffff) != 0 || tablebits > 16) /* 16 for weight below */
++ error("Bad table (case b)\n");
+
+ jutbits = 16 - tablebits;
+ for (i = 1; i <= (unsigned)tablebits; i++) {
+
+tablebits は、make_table() を呼び出すときに指定する引数で以下の通り固定
+値(8 or 12)である。従って必ずしも必要ではない。(あえてチェックするなら
+Bad table でなく Bug と表示するべきだろう)
+
+ make_table(nn, pt_len, 8, pt_table);
+ make_table(NC, c_len, 12, c_table);
+
+total & 0xffff はどの程度の不正テーブルを検出するのだろうか?
+該当の処理を以下に示そう。
+
+ for (i = 1; i <= 16; i++) count[i] = 0;
+ for (i = 0; i < (unsigned)nchar; i++) count[bitlen[i]]++;
+
+ start[1] = 0;
+ for (i = 1; i <= 16; i++)
+ start[i + 1] = start[i] + (count[i] << (16 - i));
+ if ((start[17] & 0xffff) != 0)
+ error("Bad table\n");
+
+これは、LHa for UNIX で以下のように書かれていた部分であり、ロジックとし
+てはまったく一緒である。
+
+ /* (A) */
+ avail = nchar;
+
+ /* initialize */
+ for (i = 1; i <= 16; i++) {
+ count[i] = 0;
+ weight[i] = 1 << (16 - i);
+ }
+
+ /* (B) */
+ /* count */
+ for (i = 0; i < nchar; i++)
+ count[bitlen[i]]++;
+
+ /* (C) */
+ /* calculate first code */
+ total = 0;
+ for (i = 1; i <= 16; i++) {
+ start[i] = total;
+ total += weight[i] * count[i];
+ }
+ if ((total & 0xffff) != 0)
+ error("make_table()", "Bad table (5)\n");
+
+例えば、以下の Huffman 木では各階層の重み weight の値(gzip のソースで、
+(16 - i)の値)は
+
+ /\
+ a /\ weight[1] = 0x8000
+ b c weight[2] = 0x4000
+
+であり、葉の数に重みをかけた値の総和は
+
+0x10000
+
+となる。これは正しい Huffman 木について必ず成り立たなければならない必要
+十分条件である。
+
+しかし、既存の処理では例えば 1 階層目の葉の数が 4 である場合に total が
+0x20000 となり 0xffff との論理積では異常を検知できない。
+
+ここは、以下のようにするべきであろう(以下は、LHa for UNIXのソース)。
+
+ /* (C) */
+ /* calculate first code */
+ total = 0;
+ for (i = 1; i <= 16; i++) {
+ start[i] = total;
+ total += weight[i] * count[i];
+ if (total > 0x10000)
+ error("make_table()", "Bad table\n");
+ }
+ if (total != 0x10000)
+ error("make_table()", "Bad table (5)\n");
+
+ループの中に total のチェックを入れているのは念のためである。もちろん、
+total の変数のサイズは 16 bit では足りないので 32 bit 整数にする必要が
+ある。(gzip のソースでは、total 変数の代わりに start[17] が使われている
+ので、LHa for UNIX のように total 変数にするか、start[] 自体を 32 bit
+整数に変える必要がある。)
+
+なお、32 bit 整数にした場合でも、count[1] が 0x20000 の値以上であるとき
+total がオーバーフローする恐れがあるが以下の処理より count[] がnchar よ
+り大きくなることはない。
+
+ /* (B) */
+ /* count */
+ for (i = 0; i < nchar; i++)
+ count[bitlen[i]]++;
+
+そして、要素数が最も大きい c_len の場合で nchar は NC{510} であるから
+32 bit 整数の範囲をオーバーすることはないだろう。このことがはっきりして
+いればループ中に入れた
+
+ if (total > 0x10000)
+ error("make_table()", "Bad table (5)\n");
+
+は必ずしも必要ではない。あるいは、階層 n の葉の数が 2^n を越えないことの
+チェックに変えても良いだろう。
+
+ /* (C) */
+ /* calculate first code */
+ total = 0;
+ for (i = 1; i <= 16; i++) {
+ if (count[i] > (1<<i))
+ error("make_table()", "Bad table\n");
+ start[i] = total;
+ total += weight[i] * count[i];
+ }
+ if (total != 0x10000)
+ error("make_table()", "Bad table (5)\n");
+
+これならば、total は最大でも 16 * 0x10000 = 0x100000 にしかならないこと
+が保証される。
+
+@@ -169,15 +173,15 @@
+
+ i = start[tablebits + 1] >> jutbits;
+ if (i != 0) {
+- k = 1 << tablebits;
+- while (i != k) table[i++] = 0;
++ k = MIN(1 << tablebits, DIST_BUFSIZE);
++ while (i < k) table[i++] = 0;
+ }
+
+tablebits は固定値なので、必ずしもこのチェックは必要ではない。
+
+ avail = nchar;
+ mask = (unsigned) 1 << (15 - tablebits);
+ for (ch = 0; ch < (unsigned)nchar; ch++) {
+ if ((len = bitlen[ch]) == 0) continue;
+- nextcode = start[len] + weight[len];
++ nextcode = MIN(start[len] + weight[len], DIST_BUFSIZE);
+ if (len <= (unsigned)tablebits) {
+ for (i = start[len]; i < nextcode; i++) table[i] = ch;
+ } else {
+
+DIST_BUFSIZE は、c_table[] のバッファサイズで 1<<12 である。nextcode は、
+LHa for UNIX での該当変数は l で、Huffman 符号の(先頭 tablebits ビット
+の)取り得る最大値である。これは、理論上
+
+ tablebits 最大の Huffman 符号 m
+ c_len 12 1111 1111 1111{4095} 4
+ p_len 8 1111 1111{255} 8
+ t_len 8 1111 1111{255} 8
+
+であり、ループ脱出条件が不正でない限り、このチェックは不要であると思わ
+れる。(そもそも、念のためという意味でチェックしているのなら c_len の場
+合だけしか考慮してないのも変である)
+
+ただし、先ほどの total チェックが不完全なままだと start[] の値が
+不正になりうるため、話が変わってくる。
+そういうわけで、これはセキュリティバグの重要な改修点の2点目となるが、
+本当は total のチェックの方が重要である。
+
+さらに、木の形が正しくても
+
+ 復号語の種類数 < 葉の数
+
+である場合、葉に値が割り当てられない枝が発生してしまう。これもチェック
+しておいた方が良いだろう。復号語の数は nchar で葉の数は count[] の総和
+であるから
+
+ /* (B) */
+ /* count */
+ for (i = 0; i < nchar; i++)
+ count[bitlen[i]]++;
+
+より、このことは保証されているようだ(i >= nchar である bitlen[i] が設定
+されていても使われない。もちろん設定された時点で、エラーを検出する方が
+望ましいとは思う)
+
+@@ -218,7 +222,7 @@
+ for (i = 0; i < 256; i++) pt_table[i] = c;
+ } else {
+ i = 0;
+- while (i < n) {
++ while (i < MIN(n,NPT)) {
+ c = bitbuf >> (BITBUFSIZ - 3);
+ if (c == 7) {
+ mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);
+
+n が t_len、p_len の領域の範囲内の値とは限らないのでそのチェックを行っ
+ている。これは、セキュリティバグの重要な改修点の3点目である。
+
+気になるのは、
+
+・p_len, t_len の論理的な領域サイズでなく実装上の pt_len の領域サイズで
+ チェックしている。そのため、バッファオーバーフローのセキュリティ対策
+ としては十分だがエラーチェックとしては不完全である(エラーの検出が遅延
+ される)。
+
+・不正な値をエラーとせず。処理を最大値で継続している。そのため、以下同文。
+
+@@ -228,7 +232,7 @@
+ pt_len[i++] = c;
+ if (i == i_special) {
+ c = getbits(2);
+- while (--c >= 0) pt_len[i++] = 0;
++ while (--c >= 0 && i < NPT) pt_len[i++] = 0;
+ }
+ }
+ while (i < nn) pt_len[i++] = 0;
+
+i_special は 3 固定なので、このチェックは必ずしも必要というわけではない。
+(厳密には、実装上 i_special が -1 である場合があるが i が -1 になった時
+点でバグであり、その心配はなさそうだ)
+
+@@ -248,7 +252,7 @@
+ for (i = 0; i < 4096; i++) c_table[i] = c;
+ } else {
+ i = 0;
+- while (i < n) {
++ while (i < MIN(n,NC)) {
+ c = pt_table[bitbuf >> (BITBUFSIZ - 8)];
+ if (c >= NT) {
+ mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
+
+n が c_len の領域の範囲内の値とは限らないので、同上。
+
+@@ -256,14 +260,14 @@
+ if (bitbuf & mask) c = right[c];
+ else c = left [c];
+ mask >>= 1;
+- } while (c >= NT);
++ } while (c >= NT && (mask || c != left[c]));
+ }
+
+このループ部分の全体はパッチ前だと、
+
+ c = pt_table[bitbuf >> (BITBUFSIZ - 8)];
+ if (c >= NT) {
+ mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
+ do {
+ if (bitbuf & mask) c = right[c];
+ else c = left [c];
+ mask >>= 1;
+ } while (c >= NT);
+ }
+ fillbuf((int) pt_len[c]);
+
+となっており、
+
+ mask == 0 && c == left[c]
+
+の条件を満たしてしまうような不正な木が構築されていると c の値は変化せず
+いつまでもループし続けることになってしまう。そこで、この条件が発生した
+ときにすぐにループを脱出するようその条件の否定である
+
+ !(mask == 0 && c == left[c])
+
+つまりは、
+
+ (mask || c != left[c])
+
+をループ継続の while 条件に加えているようだ。しかし、mask の初期値は
+
+ 1 << (BITBUFSIZ{16} - 1 - 8) {0000 0000 1000 0000}
+
+でありループ毎に
+
+ mask >>= 1;
+
+しているのだから、mask == 0 になった時点で、8 bit(最初の表引きと合わせ
+て 16 bit)の Huffman 符号を読み込んでおり(くどいかも知れないが LHA にお
+ける Huffman 木の階層は最大 16)、mask == 0 を脱出条件に加えるだけで良い
+と思う。
+
+もちろん、17 bit の符号を読み込んだ時点で不正なのだから
+
+ mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
+ do {
+ if (mask == 0) error("....");
+
+ if (bitbuf & mask) c = right[c];
+ else c = left [c];
+ mask >>= 1;
+ } while (c >= NT);
+
+と異常終了しても問題ないと思う。以下のように for で書くこともできるがま
+あ結局は同じことだ。(こうすると見やすいだろうか?と考えてみただけである
+が、特に効果はないようだ。)
+
+ for (mask = 1 <<(BITBUFSIZ-1-8); mask != 0; mask >>= 1) {
+ if (bitbuf & mask) c = right[c];
+ else c = left[c];
+
+ if (c < NT) break;
+ }
+ if (mask == 0) error(...);
+
+しかし c の値と left[], right[] の領域サイズとの比較は良いのだろうか?
+(理論上は Huffman 木の構築時にチェックされていれば問題ないので、私は問
+題ないと思うのだが、それを言うとそもそも無限ループのチェックも不要であ
+ると思う。)
+
+ fillbuf((int) pt_len[c]);
+ if (c <= 2) {
+ if (c == 0) c = 1;
+ else if (c == 1) c = getbits(4) + 3;
+ else c = getbits(CBIT) + 20;
+- while (--c >= 0) c_len[i++] = 0;
++ while (--c >= 0 && i < NC) c_len[i++] = 0;
+ } else c_len[i++] = c - 2;
+ }
+ while (i < NC) c_len[i++] = 0;
+
+c_len[] の範囲外の領域に値が設定されないようチェックしている。しかし、
+やはりエラーとして検出せずに処理を続行している。
+
+@@ -292,7 +296,7 @@
+ if (bitbuf & mask) j = right[j];
+ else j = left [j];
+ mask >>= 1;
+- } while (j >= NC);
++ } while (j >= NC && (mask || j != left[j]));
+ }
+ fillbuf((int) c_len[j]);
+ return j;
+
+同上。
+
+@@ -309,7 +313,7 @@
+ if (bitbuf & mask) j = right[j];
+ else j = left [j];
+ mask >>= 1;
+- } while (j >= NP);
++ } while (j >= NP && (mask || j != left[j]));
+ }
+ fillbuf((int) pt_len[j]);
+ if (j != 0) j = ((unsigned) 1 << (j - 1)) + getbits((int) (j - 1));
+
+同上。
+
+@@ -356,7 +360,7 @@
+ while (--j >= 0) {
+ buffer[r] = buffer[i];
+ i = (i + 1) & (DICSIZ - 1);
+- if (++r == count) return r;
++ if (++r >= count) return r;
+ }
+ for ( ; ; ) {
+ c = decode_c();
+@@ -366,14 +370,14 @@
+ }
+ if (c <= UCHAR_MAX) {
+ buffer[r] = c;
+- if (++r == count) return r;
++ if (++r >= count) return r;
+ } else {
+ j = c - (UCHAR_MAX + 1 - THRESHOLD);
+ i = (r - decode_p() - 1) & (DICSIZ - 1);
+ while (--j >= 0) {
+ buffer[r] = buffer[i];
+ i = (i + 1) & (DICSIZ - 1);
+- if (++r == count) return r;
++ if (++r >= count) return r;
+ }
+ }
+ }
+
+\f
+さて、これらセキュリティ対策は具体的にどのような場合を想定しているのだ
+ろう?
+
+https://bugzilla.redhat.com/show_bug.cgi?id=204676
+
+には、木の構築が不正になるシナリオとして以下が書かれている。
+
+> * Construct a pt_len[] such that pt_len[n] is 0.
+> * Construct a pt_table[] such that pt_table[(code buffer) >> 16 - 8]
+is n (where n>2)
+> * Now c_len[] is filled with (n-2), generating exceptionally high values in
+> count[n-2].
+
+しかし、これを読んでもよくわからなかったので一緒に掲載されていたサンプ
+ルの不正な符号を読んでみた。
+
+> perl -e 'print "\x1f\xa0","\xab\xcd","\xf6\x40\x01\xc2\xcc\x36\x0c\x92\x00\x00\x00\x00","\xc8","\x00"x"2048"' | gzip -d
+
+\x1f\xa0 はマジックナンバーで、gzip における LHA の圧縮形式を示す。そし
+て、LHA フォーマットは、\xab\xcd から始まる。これは、blocksize である。
+
+ blocksize = Oxabcd
+
+そして、t_len の出力形式が続く。2 進数と合わせて下記に示す。
+
+ f6 40 01 c2 cc 36
+ 1111 0110 0100 0000 0000 0001 1100 0010 1100 1100 0011 0110
+ <---->
+ size of t_len
+
+ 0c 92 00 00 00 00
+ 0000 1100 1001 0010 0000 0000 0000 0000 0000 0000 0000 0000,
+
+ c8 00
+ 1100 1000, 0000 * 2048
+
+いきなり、t_len のサイズが不正(1111 0=0x1e(30) > NT{19})である。そして、各
+t_len[] を読み込むと以下のようになる
+
+ t_len[ 0] = 110 :6
+ t_len[ 1] = 010 :2
+ t_len[ 2] = 0 00 :0
+ 00
+ t_len[ 3] = 000 :0
+ t_len[ 4] = 0 00 :0
+ t_len[ 5] = 01 1 :3
+ t_len[ 6] = 100 :4
+ t_len[ 7] = 001 :1
+ t_len[ 8] = 0 11 :3
+ t_len[ 9] = 00 1 :1
+ t_len[10] = 100 :4
+ t_len[11] = 001 :1
+ t_len[12] = 1 01 :5
+ t_len[13] = 10 0 :4
+ t_len[14] = 000 :0
+ t_len[15] = 110 :6
+ t_len[16] = 0 10 :2
+ t_len[17] = 01 0 :2
+ t_len[18] = 010 :2
+ t_len[19] = 000 :0
+ t_len[20] = 0 00 :0
+ t_len[21] = 00 0 :0
+ t_len[22] = 000 :0
+ t_len[23] = 000 :0
+ t_len[24] = 0 00 :0
+ t_len[25] = 00 0 :0
+ t_len[26] = 000 :0
+ t_len[27] = 000 :0
+ t_len[28] = 0 00 :0
+ t_len[29] = 00, 1 :1
+
+この t_len から Huffman 木の階層の葉の数は、以下の通りとなり
+
+ count[1] = 3
+ count[2] = 4
+ count[3] = 2
+ count[4] = 3
+ count[5] = 1
+ count[6] = 2
+
+以下のような木の形になるので、不正である(図中 X は、count の値が不正な
+ために余計に出来た葉を示す)。
+
+ .
+ / / \
+ X . . - 1 階層目
+ / \ / \
+ . .. . - 2 階層目
+ / \
+ . .
+ \ / \
+ X. .
+ / \
+ . .
+ / \
+ . . - 6 階層目
+
+結果的に、c_len[] はというとこちらは gzip のソースを修正して実際に値を
+出力させてみたところ以下の通りすべての値が 5 になった。これはやはり不正
+である。(階層 5 の葉の数が 288 個ある)
+
+ size of c_len: 100 1000, 0 0x120(288)
+
+ c_len[0] = 5
+ c_len[1] = 5
+ :
+ c_len[287] = 5
+
+
+ところで、本当はこうしたかったのではないだろうか?
+
+perl -e 'print "\x1f\xa0","\xab\xcd","\x9e\x40\x01\xc2\xcc\x36\x0c\x92","\xc8","\x00"x"2048"' | gzip -d
+
+これならば、t_len[] の領域サイズは超えないので、このチェックにはかから
+ない。
+
+ blocksize: 0xabcd
+
+ size of t_len: 0x13(19)
+
+ t_len[ 0]: 6
+ t_len[ 1]: 2
+ t_len[ 2]: 0
+ t_len[ 3]: 0
+ t_len[ 4]: 0
+ t_len[ 5]: 3
+ t_len[ 6]: 4
+ t_len[ 7]: 1
+ t_len[ 8]: 3
+ t_len[ 9]: 1
+ t_len[10]: 4
+ t_len[11]: 1
+ t_len[12]: 5
+ t_len[13]: 4
+ t_len[14]: 0
+ t_len[15]: 6
+ t_len[16]: 2
+ t_len[17]: 2
+ t_len[18]: 2
+
+そして、先ほどと同じ count[] の結果となり不正な木ができる。
+
+ count[1] = 3
+ count[2] = 4
+ count[3] = 2
+ count[4] = 3
+ count[5] = 1
+ count[6] = 2
+
+結果、c_len[] が不正となる。
+
+ size of c_len: 0x190 (400)
+
+ c_len[0] = 5
+ c_len[1] = 5
+ :
+
+結局、この問題は木の形の不正を検出できてないために発生している。調べて
+みたところ、この例では total が 0x30000 になるために、
+
+ (total & 0xffff) != 0
+
+で検出できていないようである。従って、先に示したとおり total を 32 bit
+変数にして、この条件を
+
+ (total != 0x10000)
+
+とすることで解決できるように思う。
+
+# ちなみに、この条件は「クラフトの不等式」を整数に変形したものであるらしい。
+# 階層 16 以下のハフマン木であれば、
+#
+# total == 2^16(0x10000)
+#
+# は必ず成り立ち、また、
+#
+# total < 2^16
+#
+# であれば、この木は冗長な符号を割り当てていることを示すそうだ。そして、
+#
+# total > 2^16
+#
+# は、一意な復号ができないことを示す。
+
+念を押しておくが、セキュリティパッチが間違っているわけではない。セキュ
+リティパッチとしてはバッファオーバフローを防げば良いので単にそのための
+チェックを入れただけである。ただし、プログラマの立場としてはセキュリティ
+パッチは対症療法な修正でしかなく、根本的な問題点を解決していない場合が
+あるということを覚えておく必要がある。と思う。
+
+\f
+このセキュリティバグの報告を受けて、gzip としてどのように修正しているか
+を確認してみた。以下は、問題が発見された gzip-1.3.5 とその修正が行われ
+た gzip-1.3.6 との差分(unlzh.c のみ)である。
+
+--- gzip-1.3.5/unlzh.c 1999-10-06 14:00:00.000000000 +0900
++++ gzip-1.3.6/unlzh.c 2006-11-20 17:40:34.000000000 +0900
+@@ -4,7 +4,7 @@
+ */
+
+ #ifdef RCSID
+-static char rcsid[] = "$Id: unlzh.c,v 1.2 1993/06/24 10:59:01 jloup Exp $";
++static char rcsid[] = "$Id: unlzh.c,v 1.4 2006/11/20 08:40:34 eggert Exp $";
+ #endif
+
+ #include <config.h>
+@@ -69,11 +69,7 @@ local void make_table OF((int nchar, uch
+ #define NT (CODE_BIT + 3)
+ #define PBIT 4 /* smallest integer such that (1U << PBIT) > NP */
+ #define TBIT 5 /* smallest integer such that (1U << TBIT) > NT */
+-#if NT > NP
+-# define NPT NT
+-#else
+-# define NPT NP
+-#endif
++#define NPT (1 << TBIT)
+
+
+恐らく、NT を超える値が圧縮文に埋め込まれてもバッファオーバーフローしな
+いようにするために pt_len のバッファサイズを大きくしたのだろう(重要な改
+修点の3点目を別な方法で解決している。個人的にはこのような対処は好みで
+ない。意図がわかりにくいからだ)
+
+c_len の領域サイズ(NC)はというと、gzip では元々 c_len のバッファサイズ
+は NC よりも大きい(8192 or 16384)。どうやら他の変数を使い回ししているた
+めにこのようになっているようだ。
+
+ /* local ush left[2 * NC - 1]; */
+ /* local ush right[2 * NC - 1]; */
+@@ -155,7 +151,7 @@ local void make_table(nchar, bitlen, tab
+ for (i = 1; i <= 16; i++)
+ start[i + 1] = start[i] + (count[i] << (16 - i));
+ if ((start[17] & 0xffff) != 0)
+- error("Bad table\n");
++ gzip_error ("Bad table\n");
+
+ここの判定(木の構築が正しいかどうか)は変えなかったようだ。
+
+ jutbits = 16 - tablebits;
+ for (i = 1; i <= (unsigned)tablebits; i++) {
+@@ -179,6 +175,8 @@ local void make_table(nchar, bitlen, tab
+ if ((len = bitlen[ch]) == 0) continue;
+ nextcode = start[len] + weight[len];
+ if (len <= (unsigned)tablebits) {
++ if ((unsigned) 1 << tablebits < nextcode)
++ gzip_error ("Bad table\n");
+ for (i = start[len]; i < nextcode; i++) table[i] = ch;
+ } else {
+ k = start[len];
+
+代わりに、table[] の領域範囲を超える符号が現れた場合にエラーになるよう
+にしている(重要な改修点の2点目。ちゃんと、c_len だけでなく、pt_len の
+場合もチェックされることになる)。
+
+@@ -223,6 +221,8 @@ local void read_pt_len(nn, nbit, i_speci
+ if (c == 7) {
+ mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);
+ while (mask & bitbuf) { mask >>= 1; c++; }
++ if (16 < c)
++ gzip_error ("Bad table\n");
+ }
+ fillbuf((c < 7) ? 3 : c - 3);
+ pt_len[i++] = c;
+
+p_len, t_len について Huffman 符号長より大きい値が復号語となる場合にエ
+ラーとしている。(重要な改修点の1点目)
+
+パッチでは、make_table() 内でチェックしていたところを実際に値を読み込む
+箇所に移したのだろう。そして、c_len の場合は、t_len の復号で木の構築
+チェックにてエラーが検出されなければ問題ないとみなしているのだろうと思
+う。
+
+どうやら方針としては最低限のチェックで済ませているらしい。さすがにアル
+ゴリズムを熟知した上での修正のように見えるが、これで良いのかいまひとつ
+確信が持てない。まあ、gzip についてはこれ以上は触れないでおこう。
+
+\f