消失訂正
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/10/12 00:38 UTC 版)
消失訂正(しょうしつていせい、erasure correction)とは、前方誤り訂正において、特に発生した誤りの位置が判明している場合にそれを復元することである。
改竄検出ではない誤り検出訂正符号は、たとえ誤り訂正能力を持たなくともその検出能力内であれば消失訂正が可能である。 また改竄検出であっても、総当たりをすれば消失訂正できる可能性が高い[注釈 1]。
例
消失訂正は一般に、誤り検出訂正の逆算を行なうことを言い、下記の例もそれに従う。が、基本的に消失範囲にあり得る値の全てを試行して符号語に一致する唯一の値を発見することでも可能である。
チェックサム
チェックサムは、各情報の総和を符号語とした誤り検出である。
1,2,3,4を情報とした場合、符号語は1+2+3+4=10となる。この場合、例えば三番目の情報が消失し1,2,X,4となっていた場合、(1+2+X+4)=10→10-(1+2+4)=Xとして消失した情報を得る。
パリティビット
パリティビットは、各ビットの排他的論理和を符号語としたものである。
101101を情報とした場合、排他的論理和を⊕とすると符号語は1⊕0⊕1⊕1⊕0⊕1=0となる。この場合、例えば三番目の情報が消失し10X101となっていた場合、1⊕0⊕X⊕1⊕0⊕1=1→1⊕(1⊕0⊕1⊕0⊕1)=Xとして消失した情報を得る。
応用
一般的に前方誤り訂正が求められる場合には、消失訂正よりも汎用性の高い誤り訂正が用いられる。しかし別途消失箇所を特定する手段がある場合には、汎用性の高い誤り訂正と比較して低コストな誤り検出を使用する消失訂正が用いられる。
RAID
RAIDの5および6では、水平パリティと呼ばれるパリティビット（誤り訂正能力を持たない誤り検出符号）を用いて、読み書きに失敗した[注釈 2]ハードディスクドライブを消失位置として消失訂正を行なうことで耐障害性を高めている。
さらにRAIDの6では、それに加えてQパリティと呼ばれるCRC[注釈 3]を併用することで、単独での消失訂正の他に、水平パリティと組み合わせた連立方程式を解くことで二台のハードディスクドライブが故障しても耐えられる消失訂正を行なっている。
コンピュータウイルス
ファイル圧縮伸長プログラムLHAは、そのアーカイブファイルが通信エラーなどにより破損していないことを確認するためのCRCを用いた検査能力を持っていた。この機能はアーカイブファイルとして自分自身を指定すると自己検査するようになっていた。なのでこれにコンピュータウイルスが感染すると「破損している」と看做されるので手軽に感染が判明した。そのためにコンピュータウイルス配布者はCRC符号を含めて書き換えてから配布するようにしたが、今度はオリジナルのLHAのCRC符号を公開することで対策された。そこでコンピュータウイルスの一部に未使用領域を設け、感染LHAに対して当該未使用領域が消失したものとして消失訂正を行なうことで公開CRC符号と一致する感染LHAを生成した。
これはCRC符号を始めとする誤り検出訂正符号では改竄検出ができないことを示す一例となっている。
また改竄検出であっても、その改竄検出符号ごと差し替えられてしまえば検出はできないことも示している。これを防ぐためには電子署名やメッセージ認証符号などの、単なる検出符号にとどまらない対策が必要となる。
脚注
注釈
出典
関連項目
消失訂正
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/25 05:06 UTC 版)
改竄検出では消失訂正はできないが、それが本当に消失したのであれば、その消失範囲を総当たりで再計算して同じ符号語となるものを探すことで高い確率で消失訂正が行なえる。 しかしそれが行なえることは保証されていない。保証できるような数学的関連性を持っていないことが暗号学的ハッシュ関数の重要な特徴だからである。 同様に、消失範囲を総当たりする場合には「本当に」総当たりをしなければならない。それはその消失範囲の中に同じ符号語となる値が複数含まれていて一つに定まらない可能性があるからである。一つに定まらなかったなら消失訂正に失敗したことになる。この一つに定まらない場合とは単なる衝突のことではないので、誕生日のパラドックスは発生しない。 このため改竄検出符号を用いて消失訂正を行なうことは（特に暗号学的ハッシュ関数の実行が高コストであることから）非現実的であり、自動再送要求などの再送可能な状況下での使用が想定される。もしも前方誤り訂正を必要とする場合には別途誤り訂正符号を設けるのが現実的であるが、この誤り訂正により改竄耐性が失われ大きなセキュリティホールとなる場合があるので併用の際には充分な注意が必要である。その他の攻撃の存在も考え合わせれば、前方誤り訂正をするのではなく、改竄が検出された段階でただちに全てを破棄して切断し、再接続するべきである。
※この「消失訂正」の解説は、「改竄検出」の解説の一部です。
「消失訂正」を含む「改竄検出」の記事については、「改竄検出」の概要を参照ください。
- 消失訂正のページへのリンク
