博士

ロボ子、今日はツリーハッシュの話をするのじゃ。

ロボ子

ツリーハッシュですか。どのようなものなのでしょう？

博士

ツリーハッシュは、データをハッシュ化して木構造でまとめる方法じゃ。でも、単純に作るとセキュリティ的に問題があるらしいぞ。

ロボ子

問題、ですか？具体的にはどのような？

博士

例えば、SHA-3を使った単純な再帰的ツリーハッシュは、衝突耐性とか長さ拡張攻撃に弱いらしいのじゃ。

ロボ子

衝突耐性というのは、異なるデータが同じハッシュ値になることですね。長さ拡張攻撃は？

博士

長さ拡張攻撃は、秘密のデータのハッシュから、それに追加したデータのハッシュを計算できちゃうことじゃ。これはマズイぞ。

ロボ子

なぜそのような脆弱性が生まれるのでしょう？

博士

原因は、SHA-3への入力が、ツリーの違う場所で同じになっちゃうことじゃ。親ノードのバイトがリーフノードのバイトと同じになったり、ツリー内部のハッシュとルートのハッシュが区別できなかったり。

ロボ子

なるほど。では、安全なツリーハッシュを作るにはどうすれば良いのでしょう？

博士

安全なツリーハッシュのためのルールは2つ！まず、リーフハッシュと親ハッシュは絶対に同じにしちゃダメ。それから、ルートハッシュと非ルートハッシュも絶対に同じにしちゃダメなのじゃ！

ロボ子

具体的にはどうすれば？

博士

簡単なのは、すべてのSHA-3入力にプレフィックスかサフィックスを付けることじゃ。こうすることで、ハッシュ値が同じになるのを防げるのじゃ。

ロボ子

プレフィックスやサフィックスを付けることで、入力が区別されるようになるんですね。

博士

そういうことじゃ！これらのルールの正式な定義と証明は、Keccak/SHA-3チームの論文に書いてあるらしいぞ。「Sufficient conditions for sound tree and sequential hashing modes」っていうタイトルじゃ。

ロボ子

勉強になります。ツリーハッシュ、奥が深いですね。

博士

じゃろ？ところでロボ子、ツリーハッシュって、なんだかクリスマスツリーみたいじゃな。頂点にプレゼントが隠されてそうじゃ！

ロボ子

博士、それはちょっと無理があります…。