EVOPEDIA

← all systems · see it in The System

Cryptographic hash function

A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for cryptographic applications. Hashing is a one-directional mathematical operation which is quick to calculate, yet hard to reverse.

Properties published scienceour proposal

Sourced fields, and our own readings.

born at1979 (Merkle's Ph.D. thesis describes the construction)
born precisionyear; earlier one-way-function ideas not read
boundaryInside: the function itself (padding, the compression function or permutation, the mode that chains blocks, the fixed constants), the security it promises, and the practice that designs, standardizes, uses, attacks and replaces hash functions. Outside: the data it is applied to, the computers it runs on, the systems built on it (signatures, MACs, password stores, blockchains, version control), and the people who compare its outputs.
nested levelA kind of hash algorithm (itself an algorithm) with properties wanted for cryptography; a primitive of cryptography; runs on computers (rung 12); its structure (a map) booked as a rung-0 role.
scaletechnological

Measures (18) published science

characteristic clock: one compression-function call per message block (SHA-256: 64 steps per 512-bit block)64 steps per block
Keccak-p permutation width and rounds1600 bits, 24 rounds bits / rounds
digest lengths in FIPS 180-4160-512 bits
generic collision resistance strengthn/2 bits for an n-bit digest (birthday bound)
first SHA-1 collision computationabout 2^63.1 SHA-1 compressions; about 6,500 CPU years and 100 GPU years compressions / years
SHA-1 chosen-prefix collision costUS$45k (identical-prefix US$11k); two months on 900 GTX 1060 GPUs US dollars (rented GPUs, 2020)
SHA-1 theory-to-practice lag2004 to 2017 years
rogue CA collision hardwaremore than 200 PlayStation 3 consoles
Hashcash work per stamp2^19 tries on average for 20 zero bits of SHA-1 hash evaluations
Bitcoin proof-of-work electricity60-125 TWh per year (2020 bounds)
Bitcoin block clock10 minutes per block (the paper's assumption)
SHA-3 competition entries64 submitted; 51, 14, 5 by round; 1 chosen candidates
password guessing rate on graphics processorsbillions per second (encyclopedia); order of 100 billion tests per second on high-end GPUs guesses per second
NIST iteration count for password KDFs10,000 or more iterations
human fingerprint comparison misses (hexadecimal)10.1 % of attacks not detected (1,047 participants)
human fingerprint comparison, numeric93.57% detection, 10.6 s mean % / seconds
quantum collision searchO(cube root of N/r) expected evaluations for an r-to-one function
Merkle proof sizeproportional to log of the number of leaves hashes

Open contentions (3) open contention

Where sources or readings disagree. Both stay on the map.

Partners and parts published science

Built from / builds (9)

Sits inside / holds (3)

Trades with (valence) (16)

expressed by (12)

floor filled by (21)

Kinds (11)

wired (1)

Notes published science

Layers

The ways it takes in its world, where they meet, and how it acts back, each from L1 (where it meets the world) up.

a message hashed to a fixed-length digest: data in, blocks compressed and chained, the security it promises, and its uses back on the world (reader's view)

  1. L1: Data in the world: files, documents, passwords, transactions, public keys
  2. L2: A bit string of any length; the output a fixed-length bit string
  3. L3: Preprocessing: padding with the length, parsing into blocks, setting the initial value
  4. L4: The compression function or permutation: rounds of word additions, rotations and XOR (SHA-2) or bit operations (Keccak), mixing so that small changes spread
  5. L5: The mode: Merkle-Damgard chaining, the sponge, or a tree, ending in the final hash value
  6. L6: The promise: preimage, second-preimage and collision resistance, and the analysis that tests it
  7. L7: Uses back on the world: integrity checks, signatures, MACs, password verification, proof of work, content addresses, commitments

the boardroom (shared floors)

  1. L4: The compression function or permutation: rounds that mix the block, the chaining value and the constants (64 steps of ARX in SHA-256; 24 rounds of bit operations in Keccak-p[1600]); where the avalanche happens
  2. L5: The domain extender (mode): Merkle-Damgard chaining one block at a time, the sponge's absorb and squeeze, or a tree; ends in the final hash value
  3. L6: What the digest promises: preimage, second-preimage and collision resistance (n, n and n/2 bits), their seven formal versions and the implications among them, and the analysis that tests them
  4. L7: Uses back on the world: integrity checks, signatures, MACs, password storage, proof of work, content addresses, commitments; and the standards and transitions that decide which hash is used

way in: A secret key (HMAC) or a random salt (password hashing)

  1. L1: A secret shared key, or a large random non-secret salt stored with the password hash
  2. L2: Combined with the message: the salt hashed with the password; the key XORed with ipad and opad
  3. L3: The key padded with zeros to the block length B

way in: Chosen parameters: output length, work factor, memory

  1. L1: The application's demand: a digest length, an extendable output of d bits, a proof-of-work target, an iteration count or memory size
  2. L2: Set as numbers: d; the number of leading zero bits; NIST's 10,000 or more iterations; Argon2's passes over memory

way in: Compute: the processor, its word operations and its power

  1. L1: Electricity and hardware (CPUs, GPUs, dedicated circuits)
  2. L2: Word operations the processor offers: 32- and 64-bit additions, rotations, XOR (ARX) or plain bit operations
  3. L3: The implementation: software-oriented (SHA-2, BLAKE, Skein) or hardware-oriented (Keccak)

way in: Cryptanalysis: attacks and their published results

  1. L1: Published attacks and colliding messages (SHAttered PDFs; chosen-prefix PGP keys)
  2. L2: The cost counted in compression-function calls and money
  3. L4: Differential paths through the compression function's steps
  4. L5: Near-collision blocks chained through the iteration so the collision holds for any suffix

way in: Fixed constants and the initial value

  1. L1: Numbers fixed once in the standard: SHA-256's constants from the cube roots of the first 64 primes; Keccak's round constants
  2. L2: Written as 32-bit words in hex
  3. L3: The initial value sets the starting chaining value; round constants enter each round

way in: The message: the data to be hashed

  1. L1: Data in the world: a downloaded file, a document, a password, a block of transactions, a public key
  2. L2: A bit string of any length (the message)
  3. L3: Padded (length appended) and parsed into fixed blocks

way out: A fingerprint rendered for a person to compare

  1. L1: Text on a screen (Human sight) or spoken over a phone (Human hearing)
  2. L7: The digest encoded for people: hexadecimal, numbers, words or sentences

way out: Heat: the work of hashing dissipated

  1. L1: Electricity turned into heat: 60 to 125 TWh a year for Bitcoin (2020 bounds)
  2. L7: Proof-of-work: hashing on purpose, at scale

way out: Standards, deprecations and transitions

  1. L1: New defaults in software (Git picks SHA-256)
  2. L6: A hash judged broken or weak
  3. L7: A competition or a transition plan picks a successor

way out: The digest written out

  1. L1: Stored in a password file, put in a block header, posted next to a download
  2. L2: The digest: 160 to 512 bits depending on the algorithm
  3. L5: The final hash value of the iteration

Sources (28) published science

Cryptographic hash function (encyclopedia, Wikimedia Enterprise snapshot 2026-11-01)
Chang S-j, Perlner R, Burr WE, Sonmez Turan M, Kelsey JM, Paul S, Bassham LE (2012) Third-Round Report of the SHA-3 Cryptographic Hash Algorithm Competition. NISTIR 7896. doi:10.6028/NIST.IR.7896 (behind its links)
Merkle-Damgard construction (encyclopedia, Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Nakamoto S (2008) Bitcoin: A Peer-to-Peer Electronic Cash System (behind its links)
Dechand S, Schurmann D, Busse K, Acar Y, Fahl S, Smith M (2016) An Empirical Study of Textual Key-Fingerprint Representations. 25th USENIX Security Symposium (open access) (behind its links)
NIST (2015) FIPS PUB 202 SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. doi:10.6028/NIST.FIPS.202 (behind its links)
Cryptography (Wikipedia, via Wikimedia Enterprise snapshot) (behind its links)
NIST (2023) FIPS 186-5: Digital Signature Standard (DSS). doi:10.6028/NIST.FIPS.186-5 (behind its links)
Lyle JR, Guttman B, Butler JM, Sauerwein K, Reed C, Lloyd CE (2022) Digital Investigation Techniques: A NIST Scientific Foundation Review. NIST IR 8354. doi:10.6028/NIST.IR.8354 (behind its links)
NIST (2015) FIPS PUB 180-4 Secure Hash Standard (SHS). doi:10.6028/NIST.FIPS.180-4 (behind its links)
Stevens M, Bursztein E, Karpman P, Albertini A, Markov Y (2017) The first collision for full SHA-1. CRYPTO 2017. doi:10.1007/978-3-319-63688-7_19 (behind its links)
Leurent G, Peyrin T (2020) SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust. 29th USENIX Security Symposium (open access) (behind its links)
Sotirov A, Stevens M, Appelbaum J, Lenstra A, Molnar D, Osvik DA, de Weger B (2008) MD5 considered harmful today: Creating a rogue CA certificate (research project page, TU Eindhoven HashClash) (behind its links)
Sedlmeir J, Buhl HU, Fridgen G, Keller R (2020) The Energy Consumption of Blockchain Technology: Beyond Myth. Bus Inf Syst Eng 62(6):599-608. doi:10.1007/s12599-020-00656-x (open access) (behind its links)
Brassard G, Hoyer P, Tapp A (1997) Quantum Algorithm for the Collision Problem. arXiv:quant-ph/9705002 (behind its links)
Merkle tree (encyclopedia, Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Krawczyk H, Bellare M, Canetti R (1997) HMAC: Keyed-Hashing for Message Authentication. RFC 2104 (behind its links)
Git documentation: hash-function-transition (Git SHA-1 to SHA-256 transition plan) (behind its links)
Turan et al. 2018, NIST SP 800-90B, Recommendation for the entropy sources used for random bit generation (doi:10.6028/NIST.SP.800-90B) (behind its links)
Laurie, Langley and Kasper, Certificate Transparency, RFC 6962, IETF, 2013 (behind its links)
Grassi et al. 2017, NIST SP 800-63B Digital Identity Guidelines: Authentication and Lifecycle Management, doi:10.6028/NIST.SP.800-63b (behind its links)
DeCandia G et al. (2007) Dynamo: Amazon's Highly Available Key-value Store. SOSP 2007. doi:10.1145/1294261.1294281 (behind its links)
Digital identity (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Hash table (encyclopedia, Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Rogaway P, Shrimpton T (2004) Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance. FSE 2004, LNCS 3017 (full version, author copy). doi:10.1007/978-3-540-25937-4_24 (behind its links)
Biryukov A, Dinu D, Khovratovich D, Josefsson S (2021) Argon2 Memory-Hard Function for Password Hashing and Proof-of-Work Applications. RFC 9106 (behind its links)
Dasgupta S, Stevens CF, Navlakha S (2017) A neural algorithm for a fundamental computing problem. Science 358:793-796; bioRxiv preprint doi:10.1101/180471 (Europe PMC PPR21674) (behind its links)
Rolls ET (2013) The mechanisms for pattern completion and pattern separation in the hippocampus. Front Syst Neurosci 7:74. doi:10.3389/fnsys.2013.00074 (PMC3812781, CC BY) (behind its links)