Hash functions

How do you check 700 MB without rereading them?

Awa downloads a 700 MB program. The site says: "SHA-256: ba78…". How can she know the file received is exactly the one published, without comparing it byte by byte with an original she does not have? She computes a digest (also called a hash) of the file received and compares it to the published digest: 64 characters to compare instead of 700 million bytes.

What is a hash function?

A hash function takes data of any size (a sequence of bytes) and returns a value of fixed size. SHA-256, from the SHA-2 family defined by the FIPS 180-4 standard, always returns 256 bits, i.e. 32 bytes. They are written in hexadecimal (base 16: digits 0 to 9 then letters a to f), where each character represents 4 bits: 256 ÷ 4 = 64 characters.

Type abc into the widget below: you should find the second row. A 700 MB file, too, gives 64 characters.

Two families of "hash" functions

In workshop 102, a hash table's hash function serves to spread keys over buckets: it just needs to be fast and well spread. A cryptographic hash function must also resist someone who is actively trying to break it. The first is used for data structures, the second for security. When we say "hash" without qualification in the rest of the curriculum, we mean the second.

A beginner's trap: what you really hash

You hash bytes. For a text, these are the bytes of its encoding (here UTF-8). An extra space or a hidden line break changes the digest:

printf 'hello' | sha256sum
# 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

echo hello | sha256sum
# 5891b5b522d5df086d0ff0b110fbd9d21bb4fc7163af34d08286a2e846f6be03

The second command hashes hello followed by a line break (the echo command adds one). It is not the same data, hence not the same digest. When two people do not find the same digest for "the same text", it is almost always an invisible difference of this kind.

What is a digest for?

• Checking the integrity of a file downloaded or copied (lesson 4).
• Identifying content by its digest: the Git version-control system names each object this way.
• Committing to data without revealing it yet: publish the digest, reveal the data later.
• Linking blocks: each block contains the previous block's digest (lesson 4, then the blockchain workshops).

What this does not guarantee

• A digest alone does not say who produced the file: anyone can compute the SHA-256 of anything. Proving the author takes a signature (workshop 105).
• It does not necessarily hide the data (lesson 3).
• Two files with equal digests are, in practice, identical; the converse "different digests ⇒ different files" is, by contrast, absolutely certain.

Recap

Hash function: bytes of any size → fixed-size digest (SHA-256: 256 bits, 64 hexadecimal characters). It applies to bytes, to the character. The digest identifies content, but does not identify its author.

What should we demand of a good digest?

Suppose Awa uses as her digest "the sum of the letters' codes, modulo 1,000". It is fast, fixed-size… and unusable: "AWA" and "AAW" have the same digest (anagrams), and changing one letter changes the digest by only a few units. The three properties below are the ones this toy lacks.

1. Determinism

The same input always gives the same digest, on any machine, at any time, with no secret key. That is what lets two people who do not know each other compare their results. Determinism comes with a fixed-size output (SHA-256: 256 bits) and a fast computation: hashing a file is nearly instant.

2. The avalanche effect

A tiny change in the input — one character, one bit — changes the digest unpredictably, as if it were entirely new. Compare:

Only the first letter changes (h → H, a single bit apart in the encoding). Yet the digest no longer resembles the other: comparing position by position, 61 of the 64 hexadecimal characters differ. This is no accident: if two hexadecimal strings were independent, each position would coincide with probability 1/16, i.e. 64 ÷ 16 = 4 identical positions on average and about 60 different ones. Seeing about 60 differences, however close the inputs, is exactly what we expect. This corresponds to about half of the bits: a hexadecimal character differs as soon as any one of its 4 bits differs, which happens 15 times out of 16, whereas each bit taken alone differs one time in two. Use the widget to compare two texts one character apart and count the differences.

Avalanche is a design criterion, visible to the eye, that follows from the security requirements; it is not by itself a proof of security. It does explain why you cannot "creep up" on a target digest by small successive tweaks.

3. Collision resistance (and its two cousins)

A collision is a pair of two different inputs that give the same digest. Collisions necessarily exist: there are infinitely many possible inputs and only 2^256 digests (the pigeonhole principle). The property asked for is that finding them is infeasible. Textbooks distinguish three levels:

How many tries? Orders of magnitude

For SHA-256, finding a preimage by blind trial takes on the order of 2^256 ≈ 1.2 × 10^77 tries. For a collision, the birthday paradox shows that one turns up after about the square root of that number, i.e. on the order of 2^128 ≈ 3.4 × 10^38 tries: this is the best generic attack known, and it is why SHA-256 is said to offer about 128 bits of security against collisions. These numbers are beyond the reach of any imaginable hardware.

To feel the principle, truncate the digest to 16 bits (65,536 possible values): by the same reasoning a collision shows up after about √65,536 = 256 inputs, i.e. in moments. The digest length sets the cost of the attack: a short digest is a broken digest.

What this does not guarantee

• "Infeasible" does not mean "impossible": it is a judgement on the current state of computing and cryptanalysis. A function can be weakened: MD5 and SHA-1 are the examples (lesson 4).
• To my knowledge no practical collision on SHA-256 has been published; that may change, which is why standards are reviewed. The figures above are for generic attacks on an ordinary computer; quantum computers, if they ever exist at scale, would lower these generic costs (without making them zero), and standards bodies follow the subject.
• These three properties cover neither secrecy nor authenticity (lesson 3).

Recap

Determinism: same input, same output, fixed size. Avalanche: a small change makes about 60 characters out of 64 differ. Collision resistance: finding two inputs with the same digest is infeasible (about 2^128 tries for SHA-256), although such pairs exist.

"We encrypted the PINs with SHA-256"

A small service keeps, for each customer, the SHA-256 digest of their 4-digit PIN, and says: "the codes are encrypted, nobody can read them". Is that true? The answer means separating two operations that are often confused.

Encrypting and hashing: two different tools

Hashing is one-way for two reasons that add up. First, the function loses information: a 1 GB file gives 32 bytes, and countless inputs give the same digest, so "decrypting" would not even make sense. That is not enough on its own, though (cutting a file after its first 32 bytes also loses information, and is trivially "undone" when the input is short). Second, preimage resistance: finding an input that gives a given digest is believed infeasible… provided the input cannot be guessed.

The trap of guessable inputs

A 4-digit PIN has only 10,000 possible values (0000 to 9999). An attacker who steals the database computes the SHA-256 of those 10,000 candidates and looks each stolen digest up in their list. This takes a fraction of a second on an ordinary computer (a few milliseconds in Python). The SHA-256 of 1234, for example, is 03ac674216f3e15c761ee1a5e255f067953623c8b388b4459e13f978d7c846f4: anyone can compute and recognise it. The digest therefore hides nothing: the security of a hashed secret is the security of how hard it is to guess. The PIN was not protected, only disguised.

Passwords: you need a hash made for the job

A good password hash must be deliberately slow and salted:

• the salt is a random value specific to each user, stored next to the digest and mixed with the password before hashing. Two users with the same password then get different digests, and precomputed digest tables become useless;
• a deliberately slow function (Argon2, scrypt, bcrypt, PBKDF2; Argon2 and scrypt also demand a lot of memory) makes each attacker guess expensive. Plain SHA-256, designed to be fast, is a poor choice here.

None of these precautions is "encryption": the password is never recovered, only compared.

Proving who produced a message: HMAC

A digest alone does not prove the author: an attacker can modify the message and recompute the digest. An HMAC mixes a shared secret key into the message before hashing: only someone who knows the key can produce the right HMAC. The widget below computes an HMAC-SHA256: try it with a fictitious key (for example cle-fictive-de-demonstration), then change one character of the message or the key and observe that the HMAC changes entirely. With an HMAC, the verifier must know the same key as the producer: the proof is shared between two people, not public. Workshop 105's signatures will bring a proof anyone can verify.

What this does not guarantee

• Hashing does not hide guessable data (PIN, first name, phone number): the attacker tries every possibility.
• Equal digests reveal that two pieces of data are equal: useful (spotting a duplicate) but also a leak.
• A digest does not prove origin: anyone can hash anything.

Recap

Encrypting = reversible with a key; hashing = no key, one-way, fixed size. A hashed secret is only protected by how hard it is to guess: PINs and passwords call for a slow, salted hash. HMAC adds a key to authenticate a message between two people who share it.

Verifying a file's digest

On Linux and macOS: sha256sum file (or shasum -a 256 file). On Windows, in PowerShell: Get-FileHash file -Algorithm SHA256. In Python:

import hashlib

def sha256_file(path):
    h = hashlib.sha256()
    with open(path, "rb") as f:
        for chunk in iter(lambda: f.read(65536), b""):
            h.update(chunk)
    return h.hexdigest()

It reads in chunks so as not to load 700 MB into memory; the final digest is the same as if everything had been read at once. Projects often publish a digest file where each line is "digest, two spaces, file name", which sha256sum -c checks automatically.

Reading the result. The two digests are identical to the character, or they are not: there is no "nearly identical". A single difference — even in the last character — means the file is not the one that was published. It may be corruption (interrupted download) or deliberate alteration; either way, do not run it.

Where does the reference digest come from?

Verifying assumes you trust the published digest. If the file and the digest come from the same compromised server, the attacker replaces both and the verification succeeds. A digest therefore protects against accidental corruption, and against an altered file when the digest was obtained through a separate, reliable channel (another official site, a signed announcement). For a proof that holds even if the server is compromised, you need a digital signature (workshop 105).

Chaining blocks by their digests

Workshop 103 ended on a problem: modifying a row of the log left no trace. Here is the idea that solves it. Each block contains its data and the previous block's digest; its own digest is computed over the whole. Our TOY chain, with the convention "number | data | previous digest":

block 1: 1|Awa credit 100|GENESIS
         digest h1 = fa68461319a4bcab4ea332b39bc1d03311f222f813c36432235756047f20c312

block 2: 2|Awa pays Kofi 30|fa68461319a4bcab4ea332b39bc1d03311f222f813c36432235756047f20c312
         digest h2 = fdec2cc6e9c9c0997020c1acc3b3f044ab80cb6fd5a963da3881ac1c035523bd

block 3: 3|Kofi pays Mba 10|fdec2cc6e9c9c0997020c1acc3b3f044ab80cb6fd5a963da3881ac1c035523bd
         digest h3 = eff5f1c07e8133f22ba376f95f24d1692dbcb842b23746824cc84afd1cb10575

You can recompute h1 by typing exactly 1|Awa credit 100|GENESIS into the sha256 widget.

The attack. A fraudster changes, in block 2, "30" to "300". Block 2's digest becomes 2f359f87ad0dcc90… instead of fdec2cc6e9c9c099…. But block 3 still contains the old digest (fdec2cc6…): when recomputing, the verification finds that block 2's digest no longer matches what block 3 announces. The alteration is detected.

To hide it, the fraudster must fix block 3 (putting 2f359f87… in it), which changes block 3's digest, so block 4 must be fixed, and so on to the end of the chain. In a chain of n blocks where block k is modified, all blocks from k + 1 to n must be recomputed. And if someone else kept a copy of the last digest, the rewritten chain will no longer match that copy. The "chain-explorer" widget lets you modify a block and watch the following digests break.

The honest warning

• Chaining detects a modification; it does not prevent it. If nobody keeps the last digest elsewhere, a fraudster who controls the whole chain can rewrite it entirely, cleanly. Having several independent parties keep the same chain is the subject of the consensus workshop.
• It does not say who wrote a block, nor that its content is true: it only guarantees the content has not changed since the digest was computed.
• Our chain convention is a toy. Real chains have a precise format (byte headers, double hashing in Bitcoin), which you will see later.

MD5 and SHA-1: why they are banned

Practical collisions have been published for MD5 (in the 2000s) and for SHA-1 (first public collision in 2017). These functions therefore no longer fulfil collision resistance, and are no longer used for signatures or certificates. MD5 remains fine for spotting accidental corruption, but not against an adversary. See the security exercise.

Recap

Verifying a file = computing its digest and comparing it, character by character, with a reference obtained through a reliable channel. Chaining blocks by their digests makes any modification detectable and forces all following blocks to be recomputed, without making it impossible.