SequenceHash: 私たちのためのマルチハッシュ

ページコンテンツ マルチハッシュは、それほど深く考えずに済ませがちな暗号タスクの1つです。これは残念なことです。なぜなら、マルチハッシュは、暗号学者がハッシュを使用しようとする際の一般的なつまずきポイントだからです。 「バグではなくソフトウェアを修正する」という目標の一環として、Trail of Bitsは、Keccak以外のハッシュ関数を使用する開発者に安全なマルチハッシュをもたらす、関連するハッシュ構造のペアであるSequenceHashと、その姉妹関数SequenceMACを発表します。SequenceHashとSequenceMACが、曖昧な入力エンコーディングを利用する攻撃を暗号学者が回避するのに役立つことを願っています。仕様はオープンソースであり、現在はCommunity Cryptography Specification Project（C2SP）の一部となっています。 SequenceHashとSequenceMACはNISTのTupleHashと似たように動作しますが、単一のハッシュ関数に縛られないという利点があります。また、開発者がバイトアラインされていない、扱いにくい計算を実装する必要もありません。代わりに、SequenceHashとSequenceMACは、SHA256/384/512、BLAKE、RIPEMDなど、ほとんどのセキュアな暗号ハッシュ関数でそのまま使用できます。SequenceMACは、32バイト以上のキー（${2}^{128}-1$バイトという途方もない制限まで）をサポートしています。 （注記: SequenceHashとSequenceMACは、それ自体のセキュリティのために基盤となるハッシュのセキュリティに依存しています。SequenceHashとSequenceMACは、MD4やSHA0を魔法のように再び安全にすることはできません。このドキュメントの目的では、CRC32ではなくSHA256のような合理的なハッシュ関数を選択したと仮定します。） SequenceHashとSequenceMACを使いやすくするために、Rust、Go、Pythonの3つの初期実装をリリースしています。また、複数のハッシュ関数をカバーし、開発者が実装をデバッグおよび検証するのに役立つ中間値を含む、大規模なテストベクターセットもリリースしています。 待てよ、「マルチハッシュ」？ ええ、奇妙な言葉ですが、その考えは非常にシンプルです。「マルチハッシュ」とは、「たくさんの値を一緒にハッシュすること」を意味します。暗号論文を読んだことがあれば、何かステップで「共有認証子N=Hash(X, Y, Z, A, B)を計算する」と書かれているのを見たことがあるでしょう。それがマルチハッシュです。入力X、Y、Z、A、Bを組み込んだハッシュを作成する必要があります。残念ながら、入力を連結して結果をハッシュするという単純な「解決策」は、深刻なセキュリティ問題につながる可能性があります。 例えば、「生の」SHA256を使用して3つの入力をハッシュした場合に何が起こるかを考えてみましょう。 import hashlib hasher = hashlib.new('sha256') hasher.update(b'Test 0') hasher.update(b'Test 1') hasher.update(b'Test 2') print(hasher.hexdigest()) hasher = hashlib.new('sha256') hasher.update(b'Test 0Test 1') hasher.update(b'Test 2') print(hasher.hexdigest()) hasher = hashlib.new('sha256') hasher.update(b'Test 0') hasher.update(b'') hasher.update(b'Test 1Test 2') print(hasher.hexdigest()) これは次の出力を生成します。 4fce0a9940a42b5c9d1bcbfc9a6ddd6de20d731d584a0acf5bda6de86483641c 4fce0a9940a42b5c9d1bcbfc9a6ddd6de20d731d584a0acf5bda6de86483641c 4fce0a9940a42b5c9d1bcbfc9a6ddd6de20d731d584a0acf5bda6de86483641c 入力は別々の呼び出しでフィードされますが、ハッシュ関数の観点からは区別されません。内部的には、入力は単に連結されます。 暗号学の多くのことと同様に、マルチハッシュはあなたが思うよりも難しいです。これは大きな問題です。なぜなら、マルチハッシュはゼロ知識証明の最も重要なツールの1つであるフィアット・シャミール変換の重要なコンポーネントだからです。マルチハッシュを間違えると、ゼロ知識証明に偽造のリスクをもたらします。ゼロ知識証明が現在、仮想通貨で大きな役割を果たしていることを考えると、そのような間違いは数百万ドルに相当することもあります。 しかし、フィアット・シャミール変換だけがマルチハッシュを使用したい場所ではありません。関連するオブジェクトのコレクションをハッシュする必要があることは珍しくありません。オブジェクトとコレクションの両方が可変サイズである場合です。アーカイブ内のファイルの認証、複数の仮想通貨トランザクションを単一のハッシュにグループ化する、または誰かの名前のような「単純な」ものをハッシュすることを考えてみてください。 マルチハッシュは、値の暗号学的コミットメントを生成する際にも使用されます。一部のプロトコルでは、一方の当事者が秘密の値を使用して計算を実行し、後で検証のために他の当事者に開示する必要があります。多くの場合、これは秘密の値とランダムな「ブラインディング」値を一緒にハッシュし、その結果をコミットメントとして他の当事者にブロードキャストすることによって行われます。秘密の値とブラインディング値の境界が不明確な場合、「コミットメント」は複数の異なる方法で開かれることがあります。 残念ながら、誰もこの問題に対する一貫した標準的な解決策にたどり着いていないようです。代わりに、オープンソースエコシステム全体や私たちのプライベート監査で、開発者が問題をまったく異なる方法で解決しているのを見かけます。これらの解決策の中には、入力にも現れる可能性のある区切り文字文字を使用するなど、安全でないものもあります。他のものは、区切り文字を曖昧にしないようにデータをエンコードしますが、エンコーディングは不必要に複雑で、微妙なタイミングリスクをもたらします。Base64でバイト文字列をエンコードし、結果をドル記号で区切るようなものを考えてみてください。一部のハッシュ入力は長さエンコードされていますが、すべてではないという状況をよく目にします。そこはワイルドウェストです。 フィアット・シャミール変換に特化したツール（Merlinや私たち自身のdecreeなど）はありますが、一般的なマルチハッシュにはあまり適していません。 マルチハッシュの最も広く知られている標準はTupleHashであり、NIST SP 800-185で定義されています。はっきり言っておくと、TupleHashは素晴らしいです。それは単純な方法（長さプレフィックスエンコーディング）でマルチハッシュ問題を解決し、実質的に無制限のサイズの入力（もしあなたが${2}^{2040}-1$ビット以上の入力を定期的にハッシュしているなら、Trail of Bitsはあなたと物理学への無謀さを祝いたいでしょう）を処理します。ボーナスとして、それは自然にXOFとして機能します。TupleHashが利用可能であれば、それは素晴らしいツールです。 しかし、TupleHashには欠点があります。それはKeccak（SHA3の基盤となる関数）でのみ動作するように定義されています。Keccakを別のハッシュ関数に置き換えると、長さ拡張抵抗のような重要なセキュリティ機能のいくつかが失われる可能性があります。Keccak実装を手元に持っていない場合、運が悪いです。SHA3とKeccakの採用が過去10年間であまり芳しくなかったことを考えると、それは多くの暗号学者が取り残されていることを意味します。これは、CNSA 2.0がほぼすべてのものにSHA384とSHA512を義務付けている政府契約部門では特にそうです。 これは標準化された解決策を強く求める問題です。完全な仕様を要求します。複数の言語で利用可能なすぐに使える実装を求めます。 Enter SequenceHash SequenceHashは、HMACがハッシュアグノスティックなMAC構造であるのと同様に、ハッシュアグノスティックなマルチハッシュ構造です。SequenceHashは、SHA2ファミリー全体、BLAKE、RIPEMDなど、お気に入りのハッシュ関数で使用できます。 SequenceHashが提供するもの SequenceHashは、ハッシュ値がコンテキスト間で混同、拡張、または再利用されないようにする4つの主要な機能を提供します。 曖昧さのない入力エンコーディング 2つの入力（A, B）に対して、任意の長さtの他の入力シーケンス（I1, ..., It）が存在せず、基盤となるハッシュ関数に同じ入力をもたらすことが保証されます。 言い換えれば、ハッシュされる値は「意味論的に区別可能」であることが保証されます。入力の開始と終了でゲームをプレイする余地はなく、Aの一部とB、またはその逆を混同する機会もありません。 SequenceHashは、暗号学者がホートン原則に従うのに役立ちます。つまり、あなたが意図したものをハッシュし、ハッシュしたものを意図するということです。 長さ拡張防止 SHA256やSHA512を含むいくつかの一般的なハッシュ関数は、長さ拡張攻撃に対して脆弱です。アリスが秘密の値Aを持ち、H(A)をボブに送信した場合、ボブはBという値を構築して、Aを知らなくてもH(A||B)を計算できます。