Self-Assessment Quiz: Hashing, Checksums, and Error Detection

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+.

Question 1

A hash function $h\colon U \to \{0,\dots,m-1\}$ must be:

A) injective and fast B) deterministic and fast C) surjective and reversible D) collision-free for all inputs

Question 2

The collision theorem (§26.2) says that any hash function with $\lvert U\rvert > m$:

A) can be made collision-free with a clever enough design B) has a collision only if the hash function is poorly chosen C) must map some two distinct keys to the same slot D) maps every key to the same slot

Question 3

In the pigeonhole framing of collisions, the pigeons and holes are, respectively:

A) the slots and the keys B) the keys and the slots C) the bits and the bytes D) the collisions and the keys

Question 4

A hash table has $m = 400$ slots and stores $n = 1000$ keys. The load factor $\alpha$ is:

A) $0.4$ B) $2.5$ C) $400$ D) $600$

Question 5

Under chaining with the uniform-spreading assumption, the expected cost of an unsuccessful lookup is:

A) $O(1)$ regardless of $\alpha$ B) $O(\alpha)$ with no constant term C) $O(1 + \alpha)$ D) $O(n)$ always

Question 6

The chapter prefers a prime table size mainly because:

A) primes make the modulo operation faster B) a prime modulus shares no factor with patterned key steps, so keys don't collapse into a few slots C) primes guarantee zero collisions D) only primes can be used as a modulus

Question 7

Universal hashing defends against an adversary by:

A) using a hash function with no collisions B) choosing a hash function at random from a family, so the adversary can't predict which one is in use C) making the table arbitrarily large D) encrypting every key before hashing

Question 8

A single even parity bit appended to a block detects:

A) any number of bit errors B) exactly the even numbers of bit errors C) exactly the odd numbers of bit errors D) only two-bit errors

Question 9

ISBN-10 uses the modulus 11 rather than 10 specifically so that it also catches:

A) all triple-bit burst errors B) all transpositions of two adjacent digits C) deliberate tampering by an attacker D) errors in the title, not just the number

Question 10

In CRC, appending $r$ zero bits to the message before dividing corresponds, as polynomials, to:

A) adding $r$ to the message value B) multiplying $M(x)$ by $x^r$ (shifting it up by $r$ positions) C) dividing $M(x)$ by $x^r$ D) reducing $M(x)$ modulo $x^r$

Question 11

Over $\mathbb{Z}_2$, subtraction is the same operation as:

A) AND B) OR C) XOR D) NOT

Question 12

An error with error polynomial $E(x)$ goes undetected by a CRC with generator $G(x)$ if and only if:

A) $E(x)$ has even degree B) $G(x) \mid E(x)$ C) $E(x) \mid G(x)$ D) $E(x) = G(x)$

Question 13

A CRC generator of degree $r = 16$ is guaranteed to detect every burst error of length:

A) $\le 8$ B) $\le 15$ C) $\le 16$ D) $\le 32$

Question 14

For a CRC to detect all single-bit errors, the generator $G(x)$ must have:

A) degree at least 32 B) at least two nonzero terms C) the factor $x + 1$ D) an even number of terms

Question 15

The crucial difference between detecting and correcting an error is that correction:

A) is always cheaper than detection B) requires more redundancy and tells you which bit is wrong, not just that something is wrong C) works only for cryptographic hashes D) is impossible for burst errors

Question 16 (True/False, justify)

True or false: Because the pigeonhole principle guarantees a 256-bit cryptographic hash has collisions, the hash is fundamentally insecure. Justify in one sentence.

Question 17 (True/False, justify)

True or false: A CRC-32 checksum published next to a download protects the file against a malicious attacker who replaces it. Justify in one sentence.

Question 18 (True/False, justify)

True or false: If a hash function must be deterministic, then h("Dana") returning a different slot on insert than on lookup is a correctness bug, not a performance issue. Justify in one sentence.

Question 19 (Short answer)

Name the three security properties that distinguish a cryptographic hash function from an ordinary one.

Question 20 (Short answer)

In one sentence each, state what mathematical object each mechanism relies on: (a) the modular hash $h(k) = k \bmod m$; (b) the parity-bit guarantee; (c) the CRC.

Answer Key

Topics to review by question