Question 1 – The Birthday Paradox Attack [50%]
This exercise illustrates the birthday paradox in the context of hash collisions, using a simple toy “hash” function based on bitwise XOR. You will write a Python program to demonstrate how collisions can occur much more easily than intuition may suggest.
Instructions
Write a Python program that performs the following steps:
1. Generate XOR “hashes” for prime sets.
o Randomly generate 16 sets of three distinct prime numbers, all less than 256 (28).
o Compute the hash of each set by taking the bitwise XOR of the three integers:
Store these 16 hash values as your reference set.
2. Search for a matching composite set.
o Repeatedly generate random sets of three distinct composite numbers less than 256.
o Compute the XOR hash for each composite set and compare it to the 16 prime-set hashes in your reference set.
o Stop as soon as you find a composite set whose hash matches one of the prime-set hashes in your reference set.
3. Output and submission format.
o Your submitted Python file must include, as commented output at the end of the file:
The 16 prime sets and their XOR hashes.
The matching composite set (if found) and its hash.
The total number of composite sets tested before a match occurred.
The random seed used (e.g., random.seed(2025)).
o If no match was found within a reasonable number of attempts, state that clearly.
o Do not submit screenshots; include all output and explanations as comments within your .py file.
4. Conceptual check.
o Briefly note in comments how this toy example relates to the birthday paradox; that is, why collisions become likely once the number of
generated hashes approaches roughly the square root of the hash space size.
Additional Requirements
• Each “set” must be an unordered collection of three distinct numbers (no
repetitions). For example, {5, 11, 5} is invalid, and {2, 7, 19} is the same as {19, 2, 7}.
• Use a fixed random seed to ensure reproducibility.
• The XOR hash should be computed directly using Python’s bitwise XOR operator (^).
• Keep your code well commented and clear.
Expected Results
Because XOR outputs very small integer values (only a few bits when numbers < 28), collisions should appear quickly—often after testing only a few dozen composite sets.
This models the birthday paradox: the probability of two values colliding rises sharply once you generate roughly √N distinct hashes, where Nis the number of possible outputs.
Question 2 – Attempting a Birthday Attack on SHA-256 [50%]
This question extends Question 1 (The Birthday Paradox Attack) by replacing the simple XOR operation with a cryptographically secure hash function (SHA-256). The goal is to empirically show how unlikely it is to find a hash collision when using a modern cryptographic hash function.
Instructions
Write a Python program using the cryptography library (see the documentation at https://cryptography.io/en/latest/hazmat/primitives/cryptographic-hashes.html) that performs the following experiment:
1. Generate SHA-256 digests of prime sets.
o Randomly generate 16 sets of three distinct prime numbers, all less than 256.
o For each set {p1, p2, p3}, compute the SHA-256 digest of the concatenation of their ASCII decimal representations (e.g., b"251", b"157", b"191").
o Store these 16 hash values as your reference digests.
2. Generate SHA-256 digests of composite sets.
o Generate 1,000 sets of three distinct composite numbers, all less than 256.
o Compute their SHA-256 digests in exactly the same format as in Step 1.
o For each composite digest, check whether it matches any of the 16 prime digests. Stop early if a collision is found.
3. Output and submission format.
o Your submitted Python code must include the following as commented output at the end of the file:
The 16 prime sets of your reference set (and their corresponding digests).
Up to 10 composite attempts (with their sets and digests).
The final result, clearly stating whether a collision was found or not.
The fixed random seed used (e.g., random.seed(2025)).
o Do not submit screenshots. All results and explanations must appear as comments within your code file.
4. Explanation (as comments in the code).
o After your code, include a short 1–3 paragraph explanation (as a comment block) describing:
Why a collision is extremely unlikely with SHA-256.
How this relates to the birthday paradox, specifically that a 256-bit hash requires roughly 2128 attempts on average to find a collision.
Why your 1,000-trial experiment will almost certainly yield no matches.
Additional Requirements
• Treat each set as an unordered collection of distinct elements (no repetitions, and order does not matter). For example, {5, 11, 5} is invalid, and {2, 41, 227} is the same as {41, 227, 2}.
• Use a fixed random seed so results are reproducible.
• Verify that all composite numbers are indeed non-prime and greater than 1.
• To avoid accidental false collisions:
o Do not use bytes(n) directly, as it produces a sequence of null bytes (\x00) that can unintentionally overlap between inputs.
o Avoid ambiguous string concatenations such as "2" + "41" + "227" and "24" + "12" + "27", which both yield "241227".
o Instead, include delimiters (e.g., b':') or use separate digest.update(b"...") calls.
Expected Results
You are not expected to find a real collision. Even if you computed all possible sets of three composite numbers less than 256, a true collision with SHA-256 would still be astronomically unlikely, requiring roughly 2128 trials on average. For perspective, generating 1.39 × 106 SHA-256 hashes takes about 40 seconds on the instructor’s laptop, but 2128 hashes would take ≈ 5.9 × 1025 years. This is far longer than the expected lifetime of our galaxy, the Milky Way.
If, after verifying your code, you genuinely find a collision, document it carefully in your output comments, and you will receive full marks for this assignment regardless of other results.