Cryptographic hash function: Difference between revisions

Revision as of 01:29, 30 May 2025

Latest revision as of 06:42, 21 August 2025

(7 intermediate revisions by 7 users not shown)

Line 4:

{{SHA-box}}

[[Afghanistan|A]] '''cryptographic hash function''' ('''CHF''') is a [[hash algorithm]] (a [[map (mathematics)|map]] of an arbitrary binary string to a binary string with a fixed size of <math>n</math> bits) that has special properties desirable for a [[cryptography|cryptographic]] application:{{sfn|Menezes|van Oorschot|Vanstone|2018|p=33}}

* the probability of a particular <math>n</math>-bit output result ([[hash value]]) for a random input string ("message") is <math>2^{-n}</math> (as for any good hash), so the hash value can be used as a representative of the message;

* finding an input string that matches a given hash value (a ''pre-image'') is infeasible, ''assuming all input strings are equally likely.'' The ''resistance'' to such search is quantified as [[security strength]]: a cryptographic hash with <math>n</math> bits of hash value is expected to have a ''preimage resistance'' strength of <math>n</math> bits, unless the space of possible input values is significantly smaller than <math>2^{n}</math> (a practical example can be found in {{section link||Attacks on hashed passwords}});

Line 31:

In practice, collision resistance is insufficient for many practical uses. In addition to collision resistance, it should be impossible for an adversary to find two messages with substantially similar digests; or to infer any useful information about the data, given only its digest. In particular, a hash function should behave as much as possible like a [[random function]] (often called a [[random oracle]] in proofs of security) while still being deterministic and efficiently computable. This rules out functions like the [[SWIFFT]] function, which can be rigorously proven to be collision-resistant assuming that certain problems on ideal lattices are computationally difficult, but, as a linear function, does not satisfy these additional properties.{{sfn|Lyubashevsky|Micciancio|Peikert|Rosen|2008| pp=54–72}}

Checksum algorithms, such as [[CRC32CRC-32]] and other [[cyclic redundancy check]]s, are designed to meet much weaker requirements and are generally unsuitable as cryptographic hash functions. For example, a CRC was used for message integrity in the [[Wired Equivalent Privacy|WEP]] encryption standard, but an attack was readily discovered, which exploited the linearity of the checksum.

=== Degree of difficulty ===