Chapter 7 — Probability and statistics
Lesson map
Lesson 07 published. Map, example, EX019.
flowchart TD
N0["Learning outcomes"]
N1["7.1 The birthday problem"]
N2["Lab — Collision probability"]
N3["7.2 Reading the results"]
N4["7.3 Interpreting probability claims"]
N5["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5
N5 --> EX["Worked example"]
EX --> Q["Exercise EX019"]
Logical drawing
flowchart LR
N0["Learning outcomes"]
N1["7.1 The birthday problem"]
N2["Lab — Collision probability"]
N3["7.2 Reading the results"]
N4["7.3 Interpreting probability claims"]
N5["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX019"]
[Learning outcomes]
|
v
[7.1 The birthday problem]
|
v
[Lab — Collision probability]
|
v
[7.2 Reading the results]
|
v
[7.3 Interpreting probability claims]
|
v
[Synthesis]
|
v
[Worked example] --> [Exercise EX019]
Learning outcomes
You will (1) apply the birthday bound to collisions; (2) choose tag and identifier lengths from collision targets; (3) interpret probability claims in standards.
7.1 The birthday problem
In a room of 23 people, the chance that two share a birthday exceeds one half, though there are 365 days. The reason is that the number of pairs grows with the square of the number of people. For random values from a space of size N, collisions become likely after about the square root of N draws. For an n-bit value, that is about 2^(n/2). Katz and Lindell use this bound to explain why a hash function with n-bit output offers only about n/2 bits of collision resistance, which is why SHA-256 is described as giving 128-bit collision security.
Lab — Collision probability
"""Birthday bound: chance two of k random n-bit tags collide (approximation)."""
import math
def p(k, bits):
return -math.expm1(-k * (k - 1) / 2 ** (bits + 1))
def main():
for bits in (32, 64, 128):
k = 2 ** (bits // 2)
print(f"{bits:>3}-bit tags, k=2^{bits // 2}: P(collision) = {p(k, bits):.3f}")
print(f"meters 50,000 with 32-bit ids: P = {p(50_000, 32):.3f}")
if __name__ == "__main__":
main()
Run with python3 lab_birthday.py. Verified output:
32-bit tags, k=2^16: P(collision) = 0.393
64-bit tags, k=2^32: P(collision) = 0.393
128-bit tags, k=2^64: P(collision) = 0.393
meters 50,000 with 32-bit ids: P = 0.253
7.2 Reading the results
For each tag length, drawing 2^(n/2) random values gives a collision probability of about 0.393, the same for 32, 64 and 128 bits. That constant shows the square-root rule exactly. More practically, giving 50,000 meters random 32-bit identifiers produces about a 25 percent chance that two share an identifier. Aiyana recommends that Ridgeway assign identifiers sequentially from a registry instead of randomly, and that any random value whose uniqueness matters, such as a nonce, use at least 96 bits as GCM does, with counting and rotation as SP 800-38D requires.
7.3 Interpreting probability claims
Standards often state security as a probability bound for an attacker making a certain number of queries. Aiyana learns to ask three questions of any such claim: what the attacker is allowed to do, how many operations are counted, and what event counts as failure. A claim of 2^-32 failure after 2^32 messages is very different from 2^-32 per message. She also learns that statistics of real systems rarely match ideal randomness, so engineers measure, for instance by checking production logs for duplicate nonces, rather than relying on the theoretical bound alone.
Worked example
Aiyana computes a 25 percent collision chance for 50,000 random 32-bit meter identifiers and recommends registry-assigned identifiers and 96-bit counted nonces.
Synthetic case. The fleet size is invented; SP 800-38D is real.
Errors and limits
The birthday bound assumes uniform randomness; biased generators collide sooner. Probability bounds depend on the counted unit, so read them carefully.
Exercises
- EX019 — Square-root rule. After roughly how many draws do n-bit random values start colliding? Rubric: 3 = about 2^(n/2);; 2 = square root stated;; 1 = 2^n;; 0 = none.
- EX020 — Meter identifiers. What collision chance did the lab give for 50,000 meters with 32-bit identifiers, and what fix followed? Rubric: 3 = about 0.253; registry-assigned identifiers;; 2 = number only;; 1 = fix only;; 0 = none.
- EX021 — Reading a bound. Name the three questions Aiyana asks of a probability claim. Rubric: 3 = attacker capabilities, operations counted, failure event;; 2 = two;; 1 = one;; 0 = none.
Synthesis
The birthday bound turns collision risk into bit-length requirements, and careful reading of probability claims prevents false comfort.
Continue studying — chapter 07 of 50
← Chapter 06 (draft) · Course chapter index · Chapter 08 (draft) →