Hashing

Image: Jorge Stolfi, Public domain, Wikimedia Commons

In short: A method that deterministically maps data of any size to a value of fixed length (the “hash”) — a one-way street: the original data can’t be recalculated from the hash.

In more detail: Unlike encryption, hashing isn’t reversible. Important properties: the same input always produces the same hash, even a minimal change to the input produces a completely different hash (avalanche effect), and it should be practically impossible to find two different inputs with the same hash (collision resistance). Typical uses: storing passwords (never in plain text, always hashed), checking the integrity of files, data structures such as hash tables. Well-known algorithms: the SHA family, MD5 (outdated, insecure).

In Depth

The avalanche effect

An example shows the avalanche effect impressively — even a single changed character produces a completely different hash:

$ echo -n "Password123" | sha256sum
8f3a2e1d... (example hash)
 
$ echo -n "Password124" | sha256sum
c91b7f4a... (a completely different hash, even though only one digit was changed)

With a good hash function, on average about half of all output bits change if you flip just a single input bit — the output is therefore practically indistinguishable from a genuinely random sequence, even though the process is completely deterministic.

Salting against rainbow tables

When storing passwords securely, pure hashing alone isn’t enough: because the same plain text always produces the same hash, an attacker with a pre-computed table of common passwords and their hashes (a “rainbow table”) could match stolen hash values on a large scale — once computed, such a table works against every database that uses the same hash method without a salt. The solution is a random “salt”: a random value unique per user is appended to the password before hashing, so that even identical passwords of different users produce different hashes and pre-computed tables become useless. The salt itself doesn’t have to be secret — it’s usually stored directly next to the hash in the database; its job is only to make each calculation unique, not to hide it.

Slow hash functions for passwords

For passwords, deliberately SLOW hash algorithms are also used (e.g. bcrypt, scrypt, Argon2) instead of fast general-purpose algorithms such as SHA-256 — an attacker who wants to try millions of passwords per second (brute force) is massively slowed down by the artificial slowness, while a single login for a real user is hardly noticeably slower. For this, bcrypt has an adjustable “cost factor” that increases the computing time exponentially and can regularly be adjusted to faster hardware; Argon2 (winner of the Password Hashing Competition 2015) goes a step further and can additionally be configured to need a lot of memory (memory-hard) — this makes specialised attack hardware such as GPUs or ASICs, which can carry out an extremely large number of operations in parallel but have little memory per core, considerably less effective.

Collision attacks in practice

Cryptographic hash functions (such as SHA-256) differ from simple checksum algorithms (such as CRC32): the former are specifically constructed so that collisions practically can’t be brought about deliberately — checksums are only optimised for random transmission errors, not for attackers who want to construct collisions on purpose. That this difference is real was shown impressively in 2017 by “SHAttered”: Google and CWI Amsterdam published the first practically executed collision for SHA-1 — two different PDF files with an identical SHA-1 hash, calculated with enormous computing effort (the equivalent of tens of thousands of CPU years). The result considerably accelerated the already ongoing switch of many systems (including Git and certificate authorities) from SHA-1 to SHA-256 or newer methods.

Hashing as a basis for data structures

Besides its security application, hashing is also a central concept in computer science generally: hash tables (such as HashMap/HashSet in many programming languages) use a (usually non-cryptographic, but very fast) hash value to find data by a key in almost constant time, instead of having to search a list linearly — here the focus isn’t security but speed and a good distribution of values, in order to keep collisions within the table rare.

See also: SHA-256, Integrity, Key-and-lock principle