HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

SequenceHash: Multihashing for the rest of us (blog.trailofbits.com)

26 pointsby tob_scott_a0 コメント

要約

Trail of Bitsは、Keccak以外のハッシュ関数でも安全なマルチハッシュを実現するSequenceHashとSequenceMACを発表しました。これらは、入力エンコーディングの曖昧さから生じる攻撃を防ぎ、SHA256、BLAKE、RIPEMDなど、ほとんどのセキュアな暗号ハッシュ関数と互換性があります。Rust、Go、Pythonでの実装も公開されています。

全文翻訳

SequenceHash: 誰でも使えるマルチハッシュ

マルチハッシュは、あまり深く考えずに済ませがちな暗号タスクの一つです。これは残念なことです。なぜなら、マルチハッシュは暗号学者がハッシュを使おうとする際の一般的なつまずきやすい点だからです。

Trail of Bitsは、「バグではなくソフトウェアを修正する」という目標の一環として、Keccak以外のハッシュ関数を使用する開発者に安全なマルチハッシュを提供する、関連するハッシュ構築法のペアであるSequenceHashとSequenceMACを紹介します。SequenceHashとSequenceMACが、曖昧な入力エンコーディングを利用する攻撃を暗号学者が回避するのに役立つことを願っています。仕様はオープンソースであり、現在はコミュニティ暗号仕様プロジェクト(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がありますが、これらは一般的なマルチハッシュにはあまり適していません。

マルチハッシュとして最も広く知られている標準は、NIST SP 800-185で定義されているTupleHashです。はっきり言っておくと、TupleHashは素晴らしいです。マルチハッシュ問題を直接的な方法(長さプレフィックスエンコーディング)で解決し、実質的に無制限のサイズの入力を処理します(もしあなたが${2}^{2040}-1$ビットを超える入力を定期的にハッシュしているなら、Trail of Bitsはあなたとあなたの物理法則への軽視とパーティーをしたいです)。ボーナスとして、それは自然にXOFとして機能します。TupleHashが利用可能であれば、それは素晴らしいツールです。

しかし、TupleHashには欠点があります。それはKeccak、SHA3の基盤となる関数でのみ動作するように定義されています。Keccakを別のハッシュ関数に置き換えると、重要なセキュリティ機能(長さ拡張耐性など)のいくつかが失われる可能性があります。Keccak実装を手元に持っていない場合は、運が悪いです。SHA3とKeccakの採用は過去10年間でかなり低迷していることを考えると、多くの暗号学者は取り残されています。これは特に政府契約部門で顕著です。そこでは、CNSA 2.0がほぼすべてのものにSHA384とSHA512を義務付けています。

これは標準化されたソリューションが切望される問題です。完全な仕様が求められています。複数の言語で利用可能なすぐに使える実装が求められています。

SequenceHashの登場

SequenceHashは、HMACがハッシュ関数に依存しないMAC構築法であるのと同様に、ハッシュ関数に依存しないマルチハッシュ構築法です。SequenceHashは、SHA2ファミリー全体、BLAKE、RIPEMDなど、お気に入りのハッシュ関数で使用できます。

SequenceHashが提供するもの?

SequenceHashは、ハッシュ値を混合、拡張、またはコンテキスト間でリプレイされないようにする4つの主要な機能を提供します。

曖昧さのない入力エンコーディング

2つの入力AとBが与えられた場合、基盤となるハッシュ関数に同じ入力をもたらす、任意の長さtの他の入力シーケンスI_1, ..., I_tが存在しないことが保証されます。

言い換えれば、ハッシュする値は「意味論的に区別可能」であることが保証されます。入力の先頭と末尾でゲームをする余地はなく、Aの一部とBを混同したり、その逆を行ったりする機会もありません。

SequenceHashは、暗号学者がホートン原則に従うのに役立ちます。つまり、あなたが意味するものをハッシュし、ハッシュするものを意味するということです。

長さ拡張の防止

SHA256やSHA512を含むいくつかの一般的なハッシュ関数は、長さ拡張攻撃に対して脆弱です。アリスが秘密の値Aを持っていて、H(A)をボブに送信した場合、ボブはAを知らなくてもH(A||B)を計算できるような値Bを作成できます。

SequenceHashにはその問題はありません。これは、ボブがH(A||B)を計算するために必要な情報を学習できないようにする二重ハッシュ構築法を使用します。

カスタマイズ文字列の組み込み

暗号プロトコルを開発している場合、リプレイ攻撃や値の再利用に関連するその他の問題を防止するために、ハッシュ値を特定のプロトコルのステップや特定のプロトコルのインスタンスにバインドすることがしばしば重要です。

SequenceHashは、組み込みのカスタマイズ文字列でこれを容易にします。良好なハッシュ関数を使用していると仮定すると、異なるカスタマイズ文字列で同じ入力にSequenceHashまたはSequenceMACを適用すると、無関係な出力が得られ、ハッシュを特定の用途に簡単に、予測可能にバインドできます。カスタマイズ文字列が必要ない場合は、心配しないでください。それらは完全にオプションです。

追加のボーナスとして、カスタマイズ文字列は二重ハッシュ構築法の外側のレイヤーにのみ組み込まれます。同じ値を複数のカスタマイズ文字列でハッシュする必要がある場合、内側のハッシュを再利用できます!

MACモード

SequenceHashのもう1つのクールな機能は、キー付きモードであるSequenceMACがあることです。SequenceMACはHMACに構造的に似ており、SequenceHashと同じ機能(曖昧さのないエンコーディング、カスタマイズ文字列、長さ拡張保護)を提供します。また、HMACに存在するキーの疑似衝突問題を防ぐために、キーとカスタマイズ文字列に関するメタデータを組み込んでいます。

SequenceHashはどのように機能しますか?

TupleHashと同様に、SequenceHashは長さエンコーディングを使用して入力を曖昧さなくエンコードします。しかし、SequenceHashはよりシンプルなエンコーディングを使用します。ハッシュされるビット数を可変長整数として書き込む代わりに、SequenceHashはバイト数を固定長128ビット整数にエンコードします。SequenceHashは入力に長さサフィックスエンコーディングを使用します。TupleHashが使用する長さプレフィックスエンコーディングシステムと同様に、長さサフィックスエンコーディングは曖昧さがありません。しかし、サフィックスエンコーディングにより、実装者は事前に長さを知らないデータをハッシュする必要がある場合にストリーミングAPIを開発できます。

実装の容易さ(32ビットおよび64ビットシステムでのゼロパディングが容易)と、${2}^{128}-1$バイトの制限が現在および予見可能な将来の実用的な考慮事項をすべて超えているため、128ビットの長さエンコーディングを選択しました。現在使用されている最も人気のあるハッシュ関数の2つであるSHA256とSHA512は、それぞれ${2}^{61}$バイトと${2}^{125}$バイトの入力を制限しています。これは、${2}^{128}-1$バイトの制限が、いずれにしても最も人気のある基盤となるハッシュ関数の指定された制限を超えていることを意味します。SequenceHashの限界に近づいている場合は、すでにSHA256とSHA512の制限を超えています。

バイト数を単純化のために使用します。今日のハッシュ処理のほとんどは、8ビット、16ビット、32ビット、または64ビット値の文字列に対してソフトウェアで実行されます。バイト長でない文字列を使用するシステムは、現在では非常にまれであり、SequenceHashを使用したい場合は、独自のバイトパディングを提供するべきだと考えています。

HMACと同様に、SequenceHashは長さ拡張攻撃を防ぐために二重ハッシュ構築法を使用します。この構造により、キー付きバリアントであるSequenceMACもサポートできます。これは${2}^{128}-1$バイトまでのキーを受け入れます。

元のHMAC構築法の1つの欠点は、「キー疑似衝突」として知られるものに影響されることです。HMACキーは任意の長さになりますが、特定のカットオフ値(ハッシュに依存)より長い場合、使用前にハッシュされます。これは、すべての「長い」キーが、まったく同じ出力を生成する「短い」表現を持っていることを意味します。プロトコルでキーの長さを指定および強制することに注意すれば、この種の問題から保護できますが、注意しないと、誰かが異なるコンテキストで「同じ」キーの2つのバージョンを提示して、不正行為を行う可能性があります。

もう1つのキー疑似衝突の形態は、キー拡張です。HMACに関しては、8ビットキー0xffは16ビットキー0xff00や128ビットキー0xff000000000000000000000000000000と同じです。キーにゼロを追加しても(少なくともカットオフ長を超えない限り)実際には変更されません。この種の問題は、偶発的に発生する可能性があるため、より巧妙です。意図せずに128ビットキーを256ビットキーの代わりに渡したり、どこかで長さインジケーターを誤って設定したりすることは、それほど難しくありません。

SequenceHashのキー付きバリアントであるSequenceMACは、ハッシュの一部であるヘッダーブロックにキー長を組み込みます。その結果、HMACスタイルのロングキー疑似衝突を見つけるのは困難です。キーをハッシュする必要がある場合、生のキーのハッシュを提供することは、生のキーを提供することと同じではありません。SequenceMACキーの末尾のゼロは意味論的に重要です。

SequenceHashとSequenceMACは、TupleHashのカスタマイズ文字列と同様に、ドメイン分離のためのカスタマイズ文字列をサポートします。カスタマイズ文字列は最大${2}^{128}-1$バイトの長さになり、外側のハッシュ関数にのみ統合されるため、開発者はすべてを再ハッシュすることなく、同じ入力セットから複数のハッシュを派生させることができます。

どうやって使うのですか?

良い質問です!すでに3つの実装が利用可能です:Rust、Go、およびPython。また、C2SPの一部として仕様が利用可能であり、独自の С実装を記述したい場合に備えてテストベクトルも利用可能です。

SequenceHash APIを他のAPIと区別する主な機能は、SequenceHashおよびSequenceMACオブジェクトへのすべての更新がアトミックであることです。つまり、ハッシュオブジェクトに値を書き込むたびに、それは独立した長さエンコードされたオブジェクトとしてハッシュに追加されます。

SequenceHashとSequenceMACのAPIは、各言語の標準APIに似ていますが、同一ではないように努めました。Goの暗号ライブラリのhash.Hashインターフェースはio.Writerインターフェースを組み込んでおり、シーケンスで2つの値を書き込むことはそれらを連結して書き込むことと同じであることを保証します。Pythonのハッシュライブラリは、PEP 247のupdate関数に対しても同様の保証を行っています。

上記の例の値をSequenceHashを使用してハッシュした場合に何が起こるか見てみましょう。

import sequencehash

hasher = sequencehash.SequenceHash.new('sha256')
hasher.add(b'Test 0')
hasher.add(b'Test 1')
hasher.add(b'Test 2')
print(hasher.result().hex())
hasher = sequencehash.SequenceHash.new('sha256')
hasher.add(b'Test 0Test 1Test 2')
print(hasher.result().hex())
hasher = sequencehash.SequenceHash.new('sha256')
hasher.add(b'Test 0')
hasher.add(b'Test 1Test 2')
print(hasher.result().hex())

次の出力を得ます。

6eea7264b266d35bd5e483ef042189d2cebe51f9e8b764b90b0f9c82185de7ca
1469d91e90c1d9c6189f576822e900f5cc8c3cdbd2ec51256df649d37c1688f7
1800a2188e126c79dac8f7cf7e38a66e3f797654c15a5e49248a94d4e99bcaae

3つの出力はすべて無関係です。これは、各入力が長さエンコードされているため、SequenceHashの連続呼び出しにTest 0とTest 1をフィードすることが、単一の呼び出しにTest 0Test 1をフィードすることと同じではないからです。

異なるカスタマイズ文字列で同じ入力をハッシュすることも試すことができます。

import sequencehash

hasher = sequencehash.SequenceHash.new('sha256')
hasher.add(b'Test 0')
print(hasher.result_with_customizer(b'CUST 0').hex())

hasher = sequencehash.SequenceHash.new('sha256')
hasher.add(b'Test 0')
print(hasher.result_with_customizer(b'CUST 1').hex())

hasher = sequencehash.SequenceHash.new('sha256')
hasher.add(b'Test 0')
print(hasher.result_with_customizer(b'CUST 2').hex())

ここでも、3つの無関係な出力があります。

3e54b5cd60ef78773dcf14c5f65ed593726a981f2c80045db7fac03015cc07ad
3c5b12ea6952714fed499796a743b103de97575fc938aab7d154cc6c605984a9
706af798b32b12c9f508c16c3411b594227f79936a3cc521e6e1f362b1ef3a38

SequenceMACについてはどうですか?

SequenceMACはSequenceHashのように動作しますが、32バイト以上のキーが必要です。SequenceHashと同様に、入力間の境界を移動すると異なる結果が得られることがわかります。

import sequencehash

KEY = bytes.fromhex("c5d6670f20adad622292a404dc5496cd6692fee636b5935a18451c985b7277bc9cacbc26e5473f85cfc6a64e96d0b98e7b9b604eaebc8899971e1a97dc3caa3a")

hasher = sequencehash.SequenceMAC.new(KEY, digestmod='sha256')
hasher.add(b'Test 0')
hasher.add(b'Test 1')
print(hasher.result().hex())

hasher = sequencehash.SequenceMAC.new(KEY, digestmod='sha256')
hasher.add(b'Test 0Test 1')
print(hasher.result().hex())

hasher = sequencehash.SequenceMAC.new(KEY, digestmod='sha256')
hasher.add(b'Test 0')
hasher.add(b'')
hasher.add(b'Test 1')
print(hasher.result().hex())

これにより、次の出力が得られます。

9a24e4209dad98d2e1f1eecd62aa2908234f1eed2963395292fd9718129fe258
4e4b71b8bb7b2c80e9f9ca89cb8bff43cd77cc5b530fc5f163069e5dda2876cb
6faf7818842f5a208dc306afe83ed7bea5b3fadc2a617c2208e836709f925889

キーを変更したり、異なるカスタマイズ値でresult_with_customizerを使用したりしても、同様に異なる出力が得られます。

キーサイズに関する注意点

1つの重要な点は、SequenceMACは最小キーサイズが32バイト(256ビット)であるということです。良好な256ビットハッシュ関数と組み合わせると、これは偽造攻撃に対して約128ビットのセキュリティレベルに対応します。HMACと同様に、キーサイズは一般的にハッシュの出力と同じ長さ以上であるべきです。

さらに、SequenceMACは${2}^{128}-1$バイトまでのキーをサポートしますが、「長いキー」が「高いセキュリティ」と同じではないことを覚えておくことが重要です。基盤となるハッシュ関数とキーの前処理ステップ(ハッシュ関数のブロックサイズより長いキーをハッシュする)は、SequenceMACが提供できる総セキュリティにハードキャップを課します。ハッシュ出力の長さよりも長いキーを使用することは、一般的に良い考えではありません。

SHA224やRIPEMD160などの出力が256ビット未満のハッシュ関数の場合、セキュリティレベルは約ハッシュ長の半分(SHA224の場合は112ビット、RIPEMD160の場合は80ビット)であるべきであり、最小キーサイズのセキュリティと一致しません。SequenceMACはこれらのハッシュ関数で使用できますが、SequenceMAC仕様は短いキーを禁止するだけで、短い出力を持つハッシュ関数の使用を強く推奨しません。

拡張可能な出力関数(XOF)についてはどうですか?

素晴らしい質問です!まだ答えはありません!

SequenceXOFは仕様化していませんが、間違いなく検討していることです。現時点では、XOFはハッシュほど広く使用されていないため、APIは少し不安定です。関連するすべてのユースケースを確実にカバーするために、慎重に進めたいと考えています。

独自の С実装を書きたい場合は?

質の高い実装を見るのは大好きです!SequenceHashとSequenceMACが役立つ可能性のある言語はたくさんあり、現在のAPIをニーズに合わせてカスタマイズする方法も確かにあります!

まず、仕様を確認してください。ドキュメントは少し長いですが、構造は直接的です。HMACを実装したことがあるなら、SequenceHashとSequenceMACはそれらの洗練されたバージョンのように感じるでしょう。

次に、ターゲット言語がRust、Go、またはPythonに似ている場合は、初期実装を移植することを検討してください。これらの実装はできるだけクリーンに保つように努めたため、監査が容易であり、他の暗号学者がそれらから学ぶことができます。

最後に、何をするにしても、実装をテストベクトルで確認することを忘れないでください。テストベクトルは単純な既知の回答テストではありません。それらは、実装のデバッグと検証を支援するための中間値を含んでいます。

いくつかの軽微な注意点

SequenceHashは、カスタマイズとドメイン分離、該当する場合の長さ拡張攻撃の防止、そして最も重要なこととして、入力が危険な方法で混同されないようにするという特定のニーズに対応します。それはツールであり、万能薬ではありません。

正しい入力をハッシュしていることを確認する必要があります。値をデコードできるからといって、2つのソフトウェアがその値を同じ方法でエンコードするとは限りません。これは、異なるサーバー、クライアント、ライブラリ間で互換性の問題を引き起こす可能性があります。例えば、JSONとXMLは常にフィールド順序を保証するわけではありません。文字列の場合でさえ、一貫したエンコーディング方法を使用することが重要です(「世界はすべてASCII」は真実ではなく、決してそうではありませんでした)。

フィアット・シャミール変換の場合、すべての入力を含めることには引き続き注意が必要です。シュノール証明には、常にグループ記述子(個々の値または名前付きパラメータセットのいずれか)、ジェネレータ要素などを含める必要があります。出力がある値のモジュロとして解釈されることになっている場合、モジュロバイアスを回避するために十分な出力を持つハッシュを選択することも重要です。暗号学は微妙です。常に考慮すべき複雑さがあります。

それでも、入力の一貫性を保ち、すべての値を確実に含める限り、SequenceHashとSequenceMACを使用すると、誰もあなたの入力が本来意図されているもの以外の意味を持つと偽ることができないことを簡単に保証できます。

仕様はC2SPで公開されており、Rust、Go、Pythonの実装は本日利用可能で、独自の С実装を記述したい場合はテストベクトルも利用可能です。ぜひ試して、ご意見をお聞かせください!