← 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 at | 1979 (Merkle's Ph.D. thesis describes the construction) |
| born precision | year; earlier one-way-function ideas not read |
| boundary | Inside: 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 level | A 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. |
| scale | technological |
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 rounds | 1600 bits, 24 rounds bits / rounds |
| digest lengths in FIPS 180-4 | 160-512 bits |
| generic collision resistance strength | n/2 bits for an n-bit digest (birthday bound) |
| first SHA-1 collision computation | about 2^63.1 SHA-1 compressions; about 6,500 CPU years and 100 GPU years compressions / years |
| SHA-1 chosen-prefix collision cost | US$45k (identical-prefix US$11k); two months on 900 GTX 1060 GPUs US dollars (rented GPUs, 2020) |
| SHA-1 theory-to-practice lag | 2004 to 2017 years |
| rogue CA collision hardware | more than 200 PlayStation 3 consoles |
| Hashcash work per stamp | 2^19 tries on average for 20 zero bits of SHA-1 hash evaluations |
| Bitcoin proof-of-work electricity | 60-125 TWh per year (2020 bounds) |
| Bitcoin block clock | 10 minutes per block (the paper's assumption) |
| SHA-3 competition entries | 64 submitted; 51, 14, 5 by round; 1 chosen candidates |
| password guessing rate on graphics processors | billions per second (encyclopedia); order of 100 billion tests per second on high-end GPUs guesses per second |
| NIST iteration count for password KDFs | 10,000 or more iterations |
| human fingerprint comparison misses (hexadecimal) | 10.1 % of attacks not detected (1,047 participants) |
| human fingerprint comparison, numeric | 93.57% detection, 10.6 s mean % / seconds |
| quantum collision search | O(cube root of N/r) expected evaluations for an r-to-one function |
| Merkle proof size | proportional to log of the number of leaves hashes |
Open contentions (3) open contention
Where sources or readings disagree. Both stay on the map.
- C-578 Do living things actually run algorithms?
booked: The map treats biological processes as examples of algorithm-like behaviour and as inspiration for algorithms, not as algorithms themselves, and keeps the other view alongside.
the other reading: they run hashing algorithms (Dasgupta 2017 calls the fly's circuit a variant of locality-sensitive hashing) - C-736 When a system first throws away its excess energy and later learns to store it for reuse, is that one process that grew or two separate ones?
booked: The map keeps both readings side by side and rules neither. A few examples fit the 'one process that grew' reading, but it hasn't been tested.
the other reading: one Function before and after a fold (Jerry's reading, labelled his); two separate things that look alike - C-1324 Does a hash that resists collisions also resist being reversed?
booked: The map follows the finding that it depends on how the properties are defined and how much the hash compresses, and keeps the simpler textbook statements alongside.
the other reading: the textbook statements as written: collision resistance implies second-preimage resistance and does not guarantee preimage resistance (the Handbook's Fact and Note as quoted by Rogaway-Shrimpton; the encyclopedia's 'Collision resistance implies second pre-image resistance but does not imply pre-image resistance')
Partners and parts published science
Built from / builds (9)
- Cryptography
- Padding (length padding)
- One-way compression function
- Keccak-p permutation
- Initial value and round constants
- Domain extender (mode)
- Digital signatures and certificates
- Hash designers and cryptanalysts competing over a hash's security margin
- Digital forensics
Sits inside / holds (3)
- Algorithm (the practice of step-by-step procedures and the structure they compute)
- Cryptography
- Computer security
Trades with (valence) (16)
- Entropy via sys:thermal-energy · Cryptographic hash function mixed
- Cryptography via sys:written-record · Cryptographic hash function gain
- Human (Homo sapiens) via sys:sensory-environment · Cryptographic hash function gain
- Bitcoin (cryptocurrency) via sys:written-record · Cryptographic hash function gain
- Computer via sys:electromagnetic-field · Cryptographic hash function gain
- Cryptanalysis (the attack side of the practice) via sys:written-record · Cryptographic hash function loss
- Digital signatures and certificates via sys:written-record · Cryptographic hash function gain
- Git (version control) via sys:written-record · Cryptographic hash function gain
- Quantum computer via sys:written-record · Cryptographic hash function loss
- Computer security via sys:written-record · Cryptographic hash function gain
- Public-key cryptography via sys:written-record · Cryptographic hash function gain
- Authentication via sys:written-record · Cryptographic hash function gain
- Database via sys:written-record · Cryptographic hash function even
- Digital forensics via sys:written-record · Cryptographic hash function even
- Digital identity via sys:human-society · Cryptographic hash function gain
- Data structure via sys:written-record · Cryptographic hash function even
expressed by (12)
- Recombination/Composition
- Templating / Standardization
- Quality Improvement/Refinement
- Interoperability/Transduction (Bridging)
- Encapsulation & Modularity (Abstraction)
- Evolvability/Plasticity Engineering (Design for Future Variation)
- Physical/Virtual Barrier
- Delay/Redirection Tactics
- Validation of Identity/Intention
- Redundancy & Diversity
- Deterrence
- Quality Control & Error Correction
floor filled by (21)
- Entropy
- Human (Homo sapiens)
- Bitcoin (cryptocurrency)
- Computer
- Cryptography
- Padding (length padding)
- One-way compression function
- Keccak-p permutation
- Domain extender (mode)
- Keyed hash (HMAC, MAC)
- Password hash / key derivation function (PBKDF2, bcrypt, scrypt, Argon2)
- Sponge construction
- Merkle tree (hash tree)
- Cryptanalysis (the attack side of the practice)
- Digital signatures and certificates
- Git (version control)
- Bit string
- NIST (standards body)
- Authentication
- Database
- Digital forensics
Kinds (11)
- MD5
- SHA-1
- SHA-2 (SHA-224/256/384/512)
- SHA-3 (Keccak) and SHAKE
- RIPEMD-160
- BLAKE, BLAKE2, BLAKE3
- Whirlpool
- Keyed hash (HMAC, MAC)
- Password hash / key derivation function (PBKDF2, bcrypt, scrypt, Argon2)
- National hashes (SM3, Streebog, GOST R 34.11-94, LSH, Kupyna)
- Message authentication code
wired (1)
Notes published science
- SHA-256's 64 secret-looking constants are nothing up anyone's sleeve: they are the first 32 bits of the fractional parts of the cube roots of the first 64 prime numbers (src:nist-fips-180-4).
- In 2008 researchers used more than 200 PlayStation 3 consoles to forge an MD5 certificate authority that every common browser trusted, letting them in principle impersonate any website (src:sotirov-2008-rogue-ca).
- When people compare security fingerprints by eye in hexadecimal, they miss about one crafted fake in ten (10.1%); plain numbers or generated sentences do better (src:dechand-2016).
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)
- L1: Data in the world: files, documents, passwords, transactions, public keys
- L2: A bit string of any length; the output a fixed-length bit string
- L3: Preprocessing: padding with the length, parsing into blocks, setting the initial value
- 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
- L5: The mode: Merkle-Damgard chaining, the sponge, or a tree, ending in the final hash value
- L6: The promise: preimage, second-preimage and collision resistance, and the analysis that tests it
- L7: Uses back on the world: integrity checks, signatures, MACs, password verification, proof of work, content addresses, commitments
the boardroom (shared floors)
- 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
- 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
- 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
- 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)
- L1: A secret shared key, or a large random non-secret salt stored with the password hash
- L2: Combined with the message: the salt hashed with the password; the key XORed with ipad and opad
- L3: The key padded with zeros to the block length B
way in: Chosen parameters: output length, work factor, memory
- 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
- 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
- L1: Electricity and hardware (CPUs, GPUs, dedicated circuits)
- L2: Word operations the processor offers: 32- and 64-bit additions, rotations, XOR (ARX) or plain bit operations
- L3: The implementation: software-oriented (SHA-2, BLAKE, Skein) or hardware-oriented (Keccak)
way in: Cryptanalysis: attacks and their published results
- L1: Published attacks and colliding messages (SHAttered PDFs; chosen-prefix PGP keys)
- L2: The cost counted in compression-function calls and money
- L4: Differential paths through the compression function's steps
- L5: Near-collision blocks chained through the iteration so the collision holds for any suffix
way in: Fixed constants and the initial value
- L1: Numbers fixed once in the standard: SHA-256's constants from the cube roots of the first 64 primes; Keccak's round constants
- L2: Written as 32-bit words in hex
- L3: The initial value sets the starting chaining value; round constants enter each round
way in: The message: the data to be hashed
- L1: Data in the world: a downloaded file, a document, a password, a block of transactions, a public key
- L2: A bit string of any length (the message)
- L3: Padded (length appended) and parsed into fixed blocks
way out: A fingerprint rendered for a person to compare
- L1: Text on a screen (Human sight) or spoken over a phone (Human hearing)
- L7: The digest encoded for people: hexadecimal, numbers, words or sentences
way out: Heat: the work of hashing dissipated
- L1: Electricity turned into heat: 60 to 125 TWh a year for Bitcoin (2020 bounds)
- L7: Proof-of-work: hashing on purpose, at scale
way out: Standards, deprecations and transitions
- L1: New defaults in software (Git picks SHA-256)
- L6: A hash judged broken or weak
- L7: A competition or a transition plan picks a successor
way out: The digest written out
- L1: Stored in a password file, put in a block header, posted next to a download
- L2: The digest: 160 to 512 bits depending on the algorithm
- L5: The final hash value of the iteration
Sources (28) published science
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)
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)
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)