ハッシュ 関数 セキュリティ プロパティ
Preimage, second-preimage, および collision resistance definitions および その implications.
Three Core Properties
A cryptographic hash function aims to satisfy three distinct resistance properties. Preimage resistance means given a hash output, finding any input that maps to it is infeasible. Second-preimage resistance means given an input, finding a different input with the same hash is infeasible. Collision resistance means finding any two distinct inputs with the same hash is infeasible. Collision resistance implies second-preimage resistance but not the reverse.
- preimage
- Given H(x), hard to find any x
- second-preimage
- Given x, hard to find x' != x with H(x')=H(x)
- collision
- Hard to find any x, x' with H(x)=H(x')
one-waytamper resistancestrongest propertyBirthday Bound
Collision resistance is bounded by the birthday paradox: with 2 to the n/2 random inputs, a collision is likely for an n-bit hash. This is why a 256-bit hash provides only 128-bit collision security. Preimage and second-preimage resistance retain the full n-bit security level. Protocols that rely on collision resistance therefore need double the output length compared to those relying on preimage resistance.
Construction Weaknesses
Merkle-Damgard constructions like SHA-256 are vulnerable to length extension attacks, where an attacker who knows H(m) can compute H(m || padding || extension) without knowing m. This is exploited in naive MAC constructions, which is why HMAC was designed to avoid it. Sponge constructions like SHA-3 are not vulnerable to length extension. Understanding the construction helps choose the right hash for each protocol role.