Cryptographic hash function: Difference between revisions

Revision as of 13:18, 14 January 2025

Latest revision as of 06:42, 21 August 2025

(17 intermediate revisions by 17 users not shown)

Line 10:

* finding any pair of different messages that yield the same hash value (a ''collision'') is also infeasible: a cryptographic hash is expected to have a ''collision resistance'' strength of <math>n/2</math> bits (lower due to the [[birthday paradox]]).

Cryptographic hash functions have many [[information security|information-security]] applications, notably in [[digital signature]]s, [[message authentication code]]s (MACs), and other forms of [[authentication]]. They can also be used as ordinary [[hash function]]s, to index data in [[hash table]]s, for [[fingerprint (computing)|fingerprinting]], to detect duplicate data or uniquely identify files, and as [[checksum]]s to detect accidental data corruption. Indeed, in information-security contexts, cryptographic hash values are sometimes called (''digital'') ''fingerprints'', ''checksums'', (''message'') ''digests'',<ref>{{cite web |url=https://csrc.nist.gov/glossary/term/message_digest |title=message digest |publisher=[[NIST]] |website=Computer Security Resource Center - Glossary}}</ref> or just ''hash values'', even though all these terms stand for more general functions with rather different properties and purposes.<ref name="wjryW">{{cite web|last1=Schneier|first1=Bruce|author-link1=Bruce Schneier|title=Cryptanalysis of MD5 and SHA: Time for a New Standard|url=https://www.schneier.com/essays/archives/2004/08/cryptanalysis_of_md5.html|url-status=dead|archive-url=https://web.archive.org/web/20160316114109/https://www.schneier.com/essays/archives/2004/08/cryptanalysis_of_md5.html|archive-date=2016-03-16|access-date=2016-04-20|website=Computerworld|quote=Much more than encryption algorithms, one-way hash functions are the workhorses of modern cryptography.}}</ref>

[[Non-cryptographic hash function]]s are used in [[hash table]]s and to detect accidental errors; their constructions frequently provide no resistance to a deliberate attack. For example, a [[denial-of-service attack]] on hash tables is possible if the collisions are easy to find, as in the case of linear [[cyclic redundancy check]] (CRC) functions.{{sfn|Aumasson|2017|p=106}}

{Crazy_vibes114}

== Properties ==

Line 32 ⟶ 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 ===

Line 78 ⟶ 77:

One of the main applications of a [[hash function]] is to allow the fast look-up of data in a [[hash table]]. Being hash functions of a particular kind, cryptographic hash functions lend themselves well to this application too.

However, compared with standard hash functions, cryptographic hash functions tend to be much more expensive computationally. For this reason, they tend to be used in contexts where it is necessary for users to protect themselves against the possibility of forgery (the creation of data with the same digest as the expected data) by potentially malicious participants, such as open source applications with multiple sources of download, where malicious files could be substituted in with the same appearance to the user, or an authentic file is modified to contain malicious data.<ref>{{citationCite web needed|title=File Hashing |url=https://www.cisa.gov/sites/default/files/FactSheets/NCCIC%20ICS_Factsheet_File_Hashing_S508C.pdf |url-status=live |archive-url=https://web.archive.org/web/20250202100840/https://www.cisa.gov/sites/default/files/FactSheets/NCCIC%20ICS_Factsheet_File_Hashing_S508C.pdf |archive-date=MayFebruary 20232, 2025 |access-date=March 10, 2025 |website=CYBERSECURITY & INFRASTRUCTURE SECURITY AGENCY |format=PDF}}</ref>

==== Content-addressable storage ====