Hashing Fundamentals

A cryptographic hash function maps input of arbitrary size to a fixed-size output called a digest (or hash). It is deterministic (same input, same output) and designed to be computationally infeasible to reverse.

The digest itself is raw bytes, not text; hex is just the conventional way to print it, two characters per byte:

cat Dockerfile | openssl dgst -sha256 -binary | xxd
## 64 hex characters and 32 bytes (6, v, etc are just bytes to ASCII)
## e.g. `00110110` -> 36 hex -> 6 ASCII
00000000: 366b be1e c476 cec0 41a2 117a 8b38 79de  6k...v..A..z.8y.
00000010: 0e26 a5a8 777d 0db5 1bf2 264d 715b 2637  .&..w}....&Mq[&7

Security properties

Three properties are what make a hash "cryptographic". A cryptographic hash is consider weakened or broken once an attack can violate any of these properties.

• Preimage resistance — having a hash h, finding input m should be almost impossible, so hash(m) = h. Concept related to one-way function.
• Second-preimage resistance — having an input m1, it's extremely difficult to find another input m2, that will give same output - hash(m1) = hash(m2).
• Collision resistance — finding any two inputs with the same hash is extremal difficult. When found it's called hash collision

Collision resistance is the weakest of the three and falls first. MD5 and SHA-1 are both collision-broken while their preimage resistance still holds in practice — a digest still doesn't reveal its input, but an attacker can craft two files that hash the same. That's enough to break signatures and certificates.

Common hash algorithms

Command-line tools: md5sum, sha1sum, sha256sum, sha512sum, b3sum.

SHA-3 is not a successor to SHA-2 — it exists as a structurally different backup in case SHA-2's design ever falls. SHA-2 is still fine.

SHA-512 beats SHA-256 on 64-bit hardware for two reasons: it operates on 64-bit words, so each operation is a single instruction instead of using half the register, and it runs fewer compression rounds per byte (80 rounds over a 128-byte block vs 64 over a 64-byte block).

For storing passwords these are all the wrong choice, as for storing password should be used slower hashing algorithms.

Length extension

MD5, SHA-1 and SHA-2 use the Merkle-Damgard construction, where the digest is the entire internal state at the end of the message. Anyone holding it can resume hashing from that point. So given H(secret || message) and the length of secret — without knowing secret itself — an attacker can compute a valid H(secret || message || padding || anything). This is a length extension attack.

The consequence: H(secret || message) is not a valid message authentication code, even with a strong hash. SHA-3 (a sponge, which never exposes its whole state) and the truncated variants SHA-512/256 and SHA-384 are immune.

HMAC

A Hash-based Message Authentication Code combines a hash function with a secret key, giving integrity and authentication:

HMAC(K, M) = H((K ⊕ opad) || H((K ⊕ ipad) || M))

Only a party holding the key can produce a valid code. The two nested passes with different padding constants are what kills length extension — the outer hash runs over a fixed-size digest, so there is no attacker-controlled tail to extend.

Verifying a code with an ordinary == compares byte by byte and returns early on the first mismatch. That timing difference leaks how many leading bytes were right, which is enough to forge a tag one byte at a time, so comparison has to be constant-time: hmac.Equal in Go.

File integrity verification

sha256sum compares current hashes against previously recorded values:

sha256sum --check checksums.txt

A checksum published on the same server as the download only proves the transfer wasn't corrupted — if the server is compromised, both files change together. A GPG-signed checksum file is what makes it meaningful, since the signing key doesn't live on the mirror.

Properties and limitations

Collisions are inevitable. By the pigeonhole principle, unlimited inputs mapping to a fixed-size output means some distinct inputs must share a hash. A secure hash function just makes finding such a pair computationally infeasible.

Collisions come much cheaper than preimages. Thanks to the birthday attack, finding a collision in an n-bit hash takes about 2^(n/2) work rather than 2^n, so a 256-bit hash gives 128-bit collision resistance. SHA-1's 160 bits meant roughly 2^80 in theory, and cryptanalysis pushed the real 2017 SHAttered collision down to about 2^63.

Avalanche effect. A small change in the input produces a completely different output, so similar inputs don't yield similar hashes.

Hashing is not encryption. There is no key and no way back. Hashing low-entropy input (a PIN, an email address, a phone number) hides nothing, since the whole space can just be enumerated and hashed.

Identifying a hash

Length narrows a raw hex digest down quickly:

Length alone can't separate MD5 from an NT hash — context decides (a 32-hex string out of a Windows SAM dump is NTLM). Many password-hash formats use $-delimited fields and encode the algorithm, parameters, salt, and hash; for example, $2b$ identifies bcrypt.

Where hashes show up

• Content addressing — git names every object by the hash of its contents, so the identifier doubles as an integrity check.
• Merkle trees — one root hash covering a whole dataset, so a single piece can be verified without downloading the rest. Used by git, BitTorrent, ZFS and Certificate Transparency.
• Commitment — publish a hash now, reveal the input later to prove nothing changed in between.

Glossary

Birthday attack

A collision search exploiting the birthday paradox: in a group of 23 people two probably share a birthday, even though there are 365 options. Collisions in an n-bit hash turn up after roughly 2^(n/2) tries rather than 2^n.

Merkle-Damgard construction

The block-by-block design behind MD5, SHA-1 and SHA-2: pad the message, then iterate a compression function over the blocks, carrying an internal state that becomes the digest.

Length extension attack

Continuing a Merkle-Damgard hash from a published digest, producing H(secret || message || more) without knowing the secret.

Merkle tree

A tree where leaves are hashes of data blocks and every parent hashes its children, so one root hash commits to the entire structure.

Reference

Hashcat example hashes