2つの異なる文字列S1とS2（S1！= S2）が与えられた場合、次のことが可能です。
SHA1(S1) == SHA1(S2)
本当ですか？
私が達成しようとしている目標は、機密性の高いID文字列（親IDなどの他のフィールドと結合されている可能性があります）をハッシュして、代わりにハッシュ値をIDとして使用できるようにすることです（データベースなど）。
例：
Resource ID: X123
Parent ID: P123
クライアントが「X123-P123」を表示できるように、リソースIDの性質を公開したくありません。
代わりに、新しい列ハッシュ（ "X123-P123"）を作成したいと思います。たとえば、AAAZZZとしましょう。次に、クライアントはID AAAZZZのリソースを要求できますが、私の内部IDなどはわかりません。
あなたが説明するものは衝突と呼ばれます。SHA-1 はより多くの異なるメッセージを入力として受け入れ、異なる出力を生成できるため、衝突は必然的に存在します (SHA-1 は 2^64 ビットまでの任意のビット列を消費する可能性がありますが、出力は 160 ビットのみです。したがって、少なくとも 1 つの出力値が数回ポップアップする必要があります)。この観察は、関数が「適切な」ハッシュ関数であるかどうかに関係なく、入力よりも小さい出力を持つすべての関数に有効です。
SHA-1 が「ランダム オラクル」(基本的にランダムな値を返す概念オブジェクトであり、入力 m で出力v を返すと、その後は常に入力mで vを返さなければならないという唯一の制限付き) のように動作すると仮定すると、 2 つの異なる文字列 S1 と S2 の衝突確率は 2^(-160) である必要があります。SHA-1 がランダムなオラクルのように振る舞うという仮定の下で、多くの入力文字列を収集すると、約 2^80 のそのような文字列を収集した後に衝突が観察され始めます。
(これは 2^160 ではなく 2^80 です。これは、2^80 の文字列を使用すると、約 2^159 ペアの文字列を作成できるためです。これは、衝突に適用されるとほとんどの人が驚くため、「誕生日のパラドックス」と呼ばれることがよくあります。誕生日に関するウィキペディアのページを参照してください。)
ここで、誕生日パラドックス アプローチがランダム オラクルの最適な衝突検索アルゴリズムであるため、SHA-1 が実際にはランダム オラクルのように動作しないことを強く疑っています。それでも、約 2^63 ステップで衝突を検出する攻撃が公開されているため、誕生日パラドックス アルゴリズムよりも 2^17 = 131072 倍高速です。このような攻撃は、真のランダム オラクルでは実行できないはずです。注意してください、この攻撃は実際には完了しておらず、理論的なままです (一部の人々は試みましたが、明らかに十分な CPU パワーを見つけることができませんでした)(更新: 2017 年の初めの時点で、誰かがSHA-1 衝突を計算しました上記の方法で、予測どおりに機能しました）。それでも、理論は健全に見え、SHA-1 はランダムなオラクルではないようです。それに対応して、衝突の確率に関しては、まあ、すべての賭けはオフです。
3 番目の質問について: nビット出力の関数の場合、2^ nを超える個別のメッセージを入力できる場合、つまり最大入力メッセージ長がnより大きい場合、必然的に衝突が発生します。範囲mがnよりも小さい場合、答えはそれほど簡単ではありません。関数がランダム オラクルとして動作する場合、衝突が存在する確率はmとともに低下し、直線的にではなく、m=n/2付近で急激にカットオフします。これは誕生日のパラドックスと同じ分析です。SHA-1 では、これは、m < 80 の場合、衝突が発生しない可能性があり、m > 80であることを意味します。少なくとも 1 つの衝突が存在する可能性が非常に高くなります ( m > 160の場合、これは確実になります)。
「衝突が存在する」と「衝突を見つける」には違いがあることに注意してください。衝突が存在しなければならない場合でも、試行するたびに 2^(-160) の確率があります。前の段落が意味することは、たとえば 80 ビット未満の文字列に制限しているなどの理由で (概念的に) 2^160 ペアの文字列を試すことができない場合、そのような確率はむしろ無意味であるということです。
はい、鳩の穴の原理により可能です。
ほとんどのハッシュ (sha1 も) は出力の長さが固定されていますが、入力は任意のサイズです。したがって、十分に長く試してみると、それらを見つけることができます。
ただし、暗号化ハッシュ関数 (sha ファミリー、md ファミリーなど) は、このような衝突を最小限に抑えるように設計されています。知られている最善の攻撃では、衝突を見つけるのに 2^63 回試行する必要があるため、確率は 2^(-63) であり、実際には 0 です。
ハッシュ関数では、ほぼ常に衝突が発生する可能性があります。SHA1 は、今日まで、予測不可能な衝突の生成においてかなり安全でした。危険なのは、衝突が予測できる場合です。同じハッシュ出力を生成するために元のハッシュ入力を知る必要はありません。
たとえば、MD5 に対する攻撃は、昨年、Security Nowポッドキャスト エピソード 179で例として挙げられたように、SSL サーバー証明書の署名に対して行われました。 . このため、MD5 署名付き証明書を購入しないことを強くお勧めします。
あなたが話していることは、衝突と呼ばれます。SHA1 衝突に関する記事は次のとおりです: http://www.rsa.com/rsalabs/node.asp?id=2927
編集：別の回答者が私を打ち負かして鳩の穴の原則LOLに言及しましたが、これが鳩の穴の原則と呼ばれる理由を明確にするために、伝書鳩が巣を作るためにいくつかの穴が切り取られているが、穴よりも鳩の数が多い場合の場合、一部のハト (入力値) は穴 (出力値) を共有する必要があります。