要素のセット (順序付けられていないリスト) の sha1 ハッシュを計算したい。各要素の sha1 ハッシュは既に計算済みです。私は2つの解決策を検討しています：
要素をハッシュでソートし、そのようなリストのトップ ハッシュを計算します。
要素ハッシュを 160 ビット整数値として扱い、それらを XOR (ビット演算) して 1 つの 160 ビット ハッシュにします。
安全なハッシュ関数のプロパティに関して、2 番目のソリューションは弱いですか? (プレイメージ耐性、2 番目のプレイメージ耐性、衝突耐性)。
オプション 1 はERSで行われるものです。この標準はハッシュ ツリーを使用します。各ノードには、子ノードからの一連のハッシュ値に対して計算されたハッシュ値が含まれます。ツリーでは順序は重要ではないため、値はハッシュする前に辞書順にソートされます。これは良いことであり、私たちが知る限り安全です。
オプション 2 は非常に安全ではありません。ハッシュ関数の出力が 160 ビットの場合、対応するハッシュ値がベクトル空間GF(2) 160の基礎を構成するように、160 個のランダムな入力を簡単に生成できます。集計ハッシュ値の一致セット。攻撃コストはごくわずかです。
@ paj28 によって提案されたオプション 3 (値をハッシュにソートしてからハッシュする) も、ソートされた値を明確なセパレーターで「連結」する限り、問題ありません。たとえば、「bar」と「foo」を含む文字列のセットをハッシュする場合、「ba」と「rfoo」を含む文字列のセットと同じハッシュ値を取得する必要はありません。ハッシュするすべての値が同じ長さの場合、安全なものを取得する方が簡単です。
したがって、オプション 1 を使用します。セット内の各値をハッシュし、ハッシュ値を辞書順に並べ替え、並べ替えた値のリストを再度ハッシュします。
オプション 2 の攻撃について:これは線形代数です。nビットのk 個のベクトルがあり、そのいずれもk-1 個の他のベクトルの XOR と等しくないとします (それらは線形独立であると言われます)。次に、新しいランダム ベクトルvを考えます。このベクトルがk 個のベクトルのいくつかの XOR に等しい確率は2 k-nに等しくなります。つまり、 k < nである限り小さくなります。新しいベクトルvが実際に既に持っているk 個のベクトルと線形に独立している場合 (したがって、確率1-2 k-n)、それをセットに追加します。これで、k+1 個の線形独立ベクトルができました。
再帰: すぐに、互いに線形に独立したnビットのnベクトルを取得します。ただし、新しいベクトルがn 個の前のベクトルから線形独立である確率が0 に低下したため、これ以上先に進むことはできません。n 個のベクトルは、ベクトル空間の基礎であると言われています。
この場合、ベクトルは単純に値をハッシュすることによって取得されます (ランダム値、または構造を持つ値。ハッシュ関数はランダマイザーとして機能するため、あまり重要ではありません)。
与えられた k 個のベクトルのセットについて、新しいベクトルvがk 個のベクトルと線形独立であるかどうかを判断することは、ガウス消去法を使用して簡単に行うことができます。基底があれば、同じアルゴリズムによって、n 個の基底ベクトルのどれを XOR して任意のベクトルv'を生成するかがわかります。この質問のセットアップでは、これは、 h(m i )が基底を構成するようなn値m iを生成したら、任意のターゲットnビット出力tに対して、ガウスの消去法を使用して、私のh(m i )を一緒に XOR すると、値tが正確に得られます。対応するm i値は、tのプリイメージ セットです。
もう 1 つのオプション (3) は、最初に要素を並べ替えてから、要素の一部として表示できない区切り記号を使用してそれらを 1 つの文字列に結合することです。
これらの可能性のうち、2 が最も懸念されます。どうすれば実際に攻撃できるのか今は考えられませんが、それが最もリスクが高いようです。
したがって、基本的には 1 と 3 で問題ありません。ただし、ハッシュを意図したとおりに使用しているため、3 をお勧めします。