リンク先のブログで書かれているコリジョンの確率の数字って、誕生日コリジョンは考慮されてないんですね。ブログに対するコメントのほうで書かれてますけど。 まあ、それでも普通のデータ量なら心配しなくていいほどに2^256は広い空間だし、どうしても心配な人は zfs set dedup=verify tank すればいいのか。
設定で zfs set dedup=verify tank とすれば、「ハッシュ値が同じ」だけでなくちゃんとビットイメージまで等しいかをチェックしてくれるので、心配性な人はそれを利用すればいいですよ、とブログにはあります。 実際にコリジョンがあった場合にどうなるのかは分かりません。記録できないのかな？
>設定で zfs set dedup=verify tank とすれば、「ハッシュ値が同じ」だけでなくちゃんとビットイメージまで等しいかをチェックしてくれるので、心配性な人はそれを利用すればいいですよ、とブログにはあります。 >実際にコリジョンがあった場合にどうなるのかは分かりません。記録できないのかな？ ハッシュ値が同じならdiff取ると言うことであれば、同じ／違うの区別は明確にできると思うので大丈夫じゃない？ #それ否定されたらオイラが昔MD5で作った仕組み否定されかねない、業務の主目的じゃなかったから無くても支障無いはずだけど（笑）
衝突の確率はもっと高いような気がするです (スコア:3, 興味深い)
リンク先のブログで書かれているコリジョンの確率の数字って、誕生日コリジョンは考慮されてないんですね。ブログに対するコメントのほうで書かれてますけど。
まあ、それでも普通のデータ量なら心配しなくていいほどに2^256は広い空間だし、どうしても心配な人は zfs set dedup=verify tank すればいいのか。
# SHA256ってまだコリジョン見つかってないんでしたっけ。
Re:衝突の確率はもっと高いような気がするです (スコア:1)
Re:衝突の確率はもっと高いような気がするです (スコア:3, 参考になる)
すいません、「誕生日のパラドックス [wikipedia.org]」「誕生日問題」のほうが一般的な呼び方でした。（攻撃に使う場合は「誕生日攻撃」）
リンク先のブログのコメント欄では、birthday problem なんて書かれています。しかし、これ計算が間違っていそう。
Re:衝突の確率はもっと高いような気がするです (スコア:4, 興味深い)
# 書き忘れました。
リンク先のブログだと、「SHA256のようなセキュアなハッシュを使うときは、コリジョンの可能性は 1/2^256 または 1/10^77 」と書かれています。恐ろしく小さな確率で安全、安心。
が、任意のデータとなにか他のデータのハッシュ値が一致（衝突、コリジョン）してしまう確率としてはそれは正しいですが、ここではZFSで大量に扱う全てのデータどうしでコリジョンしないことが求められるので、正しくは誕生日問題のほうの確率でみないといけないんじゃない？ …と、いう話です。で、そのあたりもブログに対するコメントで既出なのですが、そこにある計算は間違っていそうです。
Wikipediaの表 [wikipedia.org]の値は正しそうです。この表をみると、データ個数が 4.8*10^32 でもどれか1つのデータでコリジョンが起こる確率が 10^-12 ですから、まあいずれにしても問題にならないような数字ですけど。
設定で zfs set dedup=verify tank とすれば、「ハッシュ値が同じ」だけでなくちゃんとビットイメージまで等しいかをチェックしてくれるので、心配性な人はそれを利用すればいいですよ、とブログにはあります。
実際にコリジョンがあった場合にどうなるのかは分かりません。記録できないのかな？
Re: (スコア:0)
>設定で zfs set dedup=verify tank とすれば、「ハッシュ値が同じ」だけでなくちゃんとビットイメージまで等しいかをチェックしてくれるので、心配性な人はそれを利用すればいいですよ、とブログにはあります。
>実際にコリジョンがあった場合にどうなるのかは分かりません。記録できないのかな？
ハッシュ値が同じならdiff取ると言うことであれば、同じ／違うの区別は明確にできると思うので大丈夫じゃない？
#それ否定されたらオイラが昔MD5で作った仕組み否定されかねない、業務の主目的じゃなかったから無くても支障無いはずだけど（笑）
Re:衝突の確率はもっと高いような気がするです (スコア:2)
だとすると、衝突フラグみたいなものをキーに含めておく、というところですかねえ。
いや、なんでこんなに気にしているかというと、私もSHA256で同じようなことやっているからです。（ブロック単位はやりたいけど重過ぎるので、ファイル単位）
もちろんコリジョンにはノーガード戦法ですよー。（・∀・）
Re:衝突の確率はもっと高いような気がするです (スコア:1)
ファイル単位で処理してると、「ファイルサイズ」もキーにすれば、もうちょっと衝突確率は減るんじゃないでしょうか。
まあ、ファイルサイズなんてせいぜい32bitで、256bit→288bitになる程度ですが…
私の自作バックアップソフトでは、リネームしたファイル検出のために、
ファイルサイズをキーにしたstd::map内に、MD5をキーにしたstd::mapを入れてました。
32bitの数値比較で先に絞り込んだ方が検索が速いって理由だったかな。←そういや、4GB超のファイルのことは考えてなかったなぁ…
あと、ファイル冒頭の何バイトかについても比較対象のキーにするとか。
ファイルサイズが小さいときには、ダイジェストを計算するよりも最初から全文比較の方が速いし。
#ちょっとプアな環境だったので、rsync を使ったら、最初のファイル一覧作成段階でタイムアウトしてしまうという…
#で、やむを得ず自作する羽目になったという。今はunison使ってます。
#帯域的にできるだけムダを減らしたかったんですが、最近はぶろーどばんどな感じなので、ムダな転送が出ても気にしなくなりました。
Re: (スコア:0)
Re: (スコア:0)
・ファイルの冒頭24kバイト(だっけ？)のCRC32
・ファイル全体のMD5
の二段構えにしてましたね。
# 32kバイトとかの「キリのいい」値ではないのは、CRC32を計算するコードも含めてCPUのキャッシュに載せるのを意図してたんだと思う。
Re:衝突の確率はもっと高いような気がするです (スコア:3, 興味深い)
うふふ。皆さん同じところで悩んで、同じような解決方法に…。
はい、減ると思います。まあ、セキュアなハッシュはハッシュ空間の中に均等にばら撒かれるのに対して、ファイルサイズの値は（4GBまでだとして）32ビット内で均等にばら撒かれているわけではないので、ハッシュ32ビット分の効果はなさそうですが、サイズはすぐに判別できるので速くて便利だし、32ビットは扱いやすくておいしい。
# SHA1だと32ビットファイルサイズを加えるとちょうどいい塩梅のサイズ（192ビット）になるんですが。
あと、「MD5なら、DB上は64ビット数値2列で管理できるのにー」と思いつつSHA256を使うとか、「SHA256でコリジョンチェックするにしてもテストデータがなっしんぐ(笑)」とか、いろいろと悩みがつきません。ああ楽しい！
Re:衝突の確率はもっと高いような気がするです (スコア:1)
ZFS 的には 32bit なんてファイルサイズを前提にするのは極めて「おいしくない」と思うんですが……。
下位 32bit だけってことでしょうか。今時 OS の DVD ISO イメージでも 4GB 超とか普通にあったりすると思うんですけど。
Re: (スコア:0)
恐らくブロック単位で重複排除のアプローチを採ってますから、プログラム的にファイルのレングスをその下位レイヤーのブロックコントロールで制御するコーディングが煩雑でいやだったんでしょうね。
皆さん知らないようですが
ハッシュのコリジョンは、同じハッシュ値の桁数でも、異なる演算方法のハッシュ関数を組み合わせて生成した方が確率は低くなるという論文が出ています。
ＳＨＡ１とＭＤ５の両方で同じ値となる元データ、
もうデータのライト機構のエラー発生確立よりも小さいので、無視すべきと考えます
それで十分ではないでしょうか？
Re:衝突の確率はもっと高いような気がするです (スコア:2)
これが一般的に成り立つとは、にわかには信じがたいです。これが成り立たないケースが容易にありえそうなので。
ある特定のハッシュの方式では、というような前提条件はないのでしょうか。たとえば、SHA256 + MD5 (384bit) は、SHA384 よりも意図して衝突を引き起こすことは難しい、といったような。
よろしければ、その論文を教えていただけませんか。