imported>Antonio.acsj: /* See also */

2025-12-28T20:56:22Z

See also

← Previous revision		Revision as of 20:56, 28 December 2025
Line 8:		Line 8:
	* 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}});		* 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}});
	* a ''second preimage'' resistance strength, with the same expectations, refers to a similar problem of finding a second message that matches the given hash value when one message is already known;		* a ''second preimage'' resistance strength, with the same expectations, refers to a similar problem of finding a second message that matches the given hash value when one message is already known;
	* 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]]).		* 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 because of 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>		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>
Line 31:		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}}		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 [[~~CRC32~~]] 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.		Checksum algorithms, such as [[CRC-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 ===		=== Degree of difficulty ===
Line 41:		Line 41:

	== Illustration ==		== Illustration ==
	An illustration of the potential use of a cryptographic hash is as follows: [[Alice and Bob\|Alice]] poses a tough math problem to [[Alice and Bob\|Bob]] and claims that she has solved it. Bob would like to try it himself, but would yet like to be sure that Alice is not bluffing. Therefore, Alice writes down her solution, computes its hash, and tells Bob the hash value (whilst keeping the solution secret). Then, when Bob comes up with the solution himself a few days later, Alice can prove that she had the solution earlier by revealing it and having Bob hash it and check that it matches the hash value given to him before. (This is an example of a simple [[commitment scheme]]; in actual practice, Alice and Bob will often be computer programs, and the secret would be something less easily spoofed than a claimed puzzle solution.)		An illustration of the potential use of a cryptographic hash is as follows: [[Alice and Bob\|Alice]] poses a tough math problem to [[Alice and Bob\|Bob]] and claims that she has solved it. Bob would like to try it himself, but would yet like to be sure that Alice is not bluffing. Therefore, Alice writes down her solution, computes its hash, and tells Bob the hash value (whilst keeping the solution secret). Then, when Bob comes up with the solution himself a few days later, Alice can prove that she had the solution earlier by revealing it and having Bob hash it and then check that it matches the hash value given to him before. (This is an example of a simple [[commitment scheme]]; in actual practice, Alice and Bob will often be computer programs, and the secret would be something less easily spoofed than a claimed puzzle solution.)

	== Applications ==		== Applications ==
Line 193:		Line 193:
	Passwords may still be retrieved by an attacker from the hashes, because most people choose passwords in predictable ways. Lists of common passwords are widely circulated and many passwords are short enough that even all possible combinations may be tested if calculation of the hash does not take too much time.<ref name="2tECU">{{cite web \| url=https://arstechnica.com/information-technology/2012/12/25-gpu-cluster-cracks-every-standard-windows-password-in-6-hours/ \| title=25-GPU cluster cracks every standard Windows password in <6 hours \| date=2012-12-10 \| first=Dan \| last=Goodin \| publisher=[[Ars Technica]] \| access-date=2020-11-23 \| archive-date=2020-11-21 \| archive-url=https://web.archive.org/web/20201121132005/https://arstechnica.com/information-technology/2012/12/25-gpu-cluster-cracks-every-standard-windows-password-in-6-hours/ \| url-status=live }}</ref>		Passwords may still be retrieved by an attacker from the hashes, because most people choose passwords in predictable ways. Lists of common passwords are widely circulated and many passwords are short enough that even all possible combinations may be tested if calculation of the hash does not take too much time.<ref name="2tECU">{{cite web \| url=https://arstechnica.com/information-technology/2012/12/25-gpu-cluster-cracks-every-standard-windows-password-in-6-hours/ \| title=25-GPU cluster cracks every standard Windows password in <6 hours \| date=2012-12-10 \| first=Dan \| last=Goodin \| publisher=[[Ars Technica]] \| access-date=2020-11-23 \| archive-date=2020-11-21 \| archive-url=https://web.archive.org/web/20201121132005/https://arstechnica.com/information-technology/2012/12/25-gpu-cluster-cracks-every-standard-windows-password-in-6-hours/ \| url-status=live }}</ref>

	The use of [[Salt (cryptography)\|cryptographic salt]] prevents some attacks, such as building files of precomputing hash values, e.g. [[rainbow table]]s. But searches on the order of 100 billion tests per second are possible with high-end [[graphics processor]]s, making direct attacks possible even with salt.<ref name="28vy8">{{Cite web\|url=https://www.theregister.co.uk/2019/02/14/password_length/\|title=Use an 8-char Windows NTLM password? Don't. Every single one can be cracked in under 2.5hrs\|last=Claburn\|first=Thomas\|date=February 14, 2019\|website=The Register\|language=en\|access-date=2020-11-26\|archive-date=2020-04-25\|archive-url=https://web.archive.org/web/20200425091602/https://www.theregister.co.uk/2019/02/14/password_length/\|url-status=live}}</ref>		The use of [[Salt (cryptography)\|cryptographic salt]] prevents some attacks, such as building files of precomputing hash values, e.g. [[rainbow table]]s. But searches on the order of 100 billion tests per second are possible with high-end [[graphics processor]]s, making direct attacks possible even with salt.<ref name="28vy8">{{Cite web\|url=https://www.theregister.co.uk/2019/02/14/password_length/\|title=Use an 8-char Windows NTLM password? Don't. Every single one can be cracked in under 2.5hrs\|last=Claburn\|first=Thomas\|date=February 14, 2019\|website=The Register\|language=en\|access-date=2020-11-26\|archive-date=2020-04-25\|archive-url=https://web.archive.org/web/20200425091602/https://www.theregister.co.uk/2019/02/14/password_length/\|url-status=live}}</ref><ref name="TbJcd">{{cite web\|url=https://improsec.com/tech-blog/mind-blowing-gpu-performance\|title=Mind-blowing development in GPU performance \|publisher=Improsec\|date=January 3, 2020 \|url-status=live \|archive-url=https://web.archive.org/web/20230409171025/https://improsec.com/tech-blog/mind-blowing-gpu-performance \|archive-date= Apr 9, 2023 }}</ref>
	<ref name="TbJcd">{{cite web\|url=https://improsec.com/tech-blog/mind-blowing-gpu-performance\|title=Mind-blowing development in GPU performance \|publisher=Improsec\|date=January 3, 2020 \|url-status=live \|archive-url=https://web.archive.org/web/20230409171025/https://improsec.com/tech-blog/mind-blowing-gpu-performance \|archive-date= Apr 9, 2023 }}</ref>
	The United States [[National Institute of Standards and Technology]] recommends storing passwords using special hashes called [[key derivation function]]s (KDFs) that have been created to slow brute force searches.<ref name="sp800-63B">{{cite book \| title = SP 800-63B-3 – Digital Identity Guidelines, Authentication and Lifecycle Management \| publisher = NIST \| date = June 2017 \| doi=10.6028/NIST.SP.800-63b \| author=Grassi Paul A.}}</ref>{{rp\|5.1.1.2}} Slow hashes include [[pbkdf2]], [[bcrypt]], [[scrypt]], [[argon2]], [[Balloon hashing\|Balloon]] and some recent modes of [[crypt (C)\|Unix crypt]]. For KDFs that perform multiple hashes to slow execution, NIST recommends an iteration count of 10,000 or more.<ref name="sp800-63B" />{{rp\|5.1.1.2}}		The United States [[National Institute of Standards and Technology]] recommends storing passwords using special hashes called [[key derivation function]]s (KDFs) that have been created to slow brute force searches.<ref name="sp800-63B">{{cite book \| title = SP 800-63B-3 – Digital Identity Guidelines, Authentication and Lifecycle Management \| publisher = NIST \| date = June 2017 \| doi=10.6028/NIST.SP.800-63b \| author=Grassi Paul A.}}</ref>{{rp\|5.1.1.2}} Slow hashes include [[pbkdf2]], [[bcrypt]], [[scrypt]], [[argon2]], [[Balloon hashing\|Balloon]] and some recent modes of [[crypt (C)\|Unix crypt]]. For KDFs that perform multiple hashes to slow execution, NIST recommends an iteration count of 10,000 or more.<ref name="sp800-63B" />{{rp\|5.1.1.2}}

Line 216:		Line 215:
	* [[SHA-3]]		* [[SHA-3]]
	* [[Universal one-way hash function]]		* [[Universal one-way hash function]]
			* [[Optimizing performance of hash functions]]
	{{div col end}}		{{div col end}}

imported>Mindmatrix: revert - rm promotional links

2025-05-30T15:10:02Z

revert - rm promotional links

Show changes

Cryptographic hash function - Revision history

imported>Antonio.acsj: /* See also */

imported>Mindmatrix: revert - rm promotional links