It is my Birthday 2 picoCTF 2021 Solution

Description

1. Step 1

   Obtain the SHA-1 collision PDFs and append the required suffix

   Observation

   I noticed the challenge requires two distinct files with identical SHA-1 hashes, which is exactly the property demonstrated by the publicly known SHAttered collision PDFs from 2017. The server also checks the final 1000 bytes match, so appending the invite.pdf suffix to both collision files exploits the Merkle-Damgard length-extension property to preserve the collision.

   Download the two SHAttered PDFs from shattered.io. Then extract the last 1000 bytes of the challenge's invite.pdf and append that block to both files. Because SHA-1 is a Merkle-Damgard construction, appending the same suffix to two files that already collide produces two new files that still collide.

   bash

   wget https://shattered.io/static/shattered-1.pdf

   Copied!

   bash

   wget https://shattered.io/static/shattered-2.pdf

   Copied!

   bash

   tail -c 1000 invite.pdf > suffix.bin

   Copied!

   bash

   cat shattered-1.pdf suffix.bin > collision1.pdf

   Copied!

   bash

   cat shattered-2.pdf suffix.bin > collision2.pdf

   Copied!

   bash

   sha1sum collision1.pdf collision2.pdf

   Copied!

   Expected output

   e1a8f927ca2e7b49e55e44db9e44f56ae04c96ec  collision1.pdf
   e1a8f927ca2e7b49e55e44db9e44f56ae04c96ec  collision2.pdf

   Both sha1sum outputs should be identical, confirming the collision is preserved after appending the suffix.

   What didn't work first

   Tried: Generate your own SHA-1 collision from scratch instead of using the SHAttered PDFs.

   Reproducing the SHAttered attack requires roughly 9.2 x 10^18 SHA-1 computations, which is infeasible on personal hardware in any reasonable timeframe. The SHAttered PDFs are the only publicly available precomputed SHA-1 collision pair, so they are the intended starting point. The challenge is about exploiting an existing collision, not about mounting a new cryptanalytic attack.

   Tried: Append the suffix to only one of the two PDFs before uploading.

   If only collision1.pdf gets the suffix appended, the two files will have different SHA-1 digests because the extra block changes the final Merkle-Damgard chain state for one file but not the other. The server's check sha1(file1) == sha1(file2) will fail. The suffix must be appended to both files identically so the internal hash state diverges only at the already-colliding blocks, and the identical suffix then drives both chains to the same final digest.

   Learn more

   SHA-1 collision attacks. SHA-1 produces a 160-bit digest. A brute-force collision would require around 2^80 attempts (birthday bound), but cryptographic weaknesses in SHA-1's compression function allow far cheaper attacks. The SHAttered attack (Stevens et al., 2017) found the first practical SHA-1 collision using roughly 9.2 x 10^18 SHA-1 computations - equivalent to about 6,500 years of single-CPU work, but feasible on a GPU cluster.

   Why appending a suffix preserves the collision. SHA-1, like most classical hash functions, uses the Merkle-Damgard construction: the message is processed in fixed-size blocks, each feeding into the next. If two messages A and B collide (SHA-1(A) = SHA-1(B)), then appending any identical suffix C to both gives SHA-1(A + C) = SHA-1(B + C). The internal state after processing A and B is identical, so processing C from that state produces the same final digest. This is why reusing the SHAttered PDFs and appending the invite suffix still satisfies the server's check.

   Real-world impact of SHA-1 collisions. SHA-1 had already been theoretically weakened before the SHAttered demonstration. Git historically used SHA-1 to identify objects, meaning a crafted collision could allow one commit to masquerade as another. Browser and OS vendors had been phasing out SHA-1 certificates since 2016, and the SHAttered result accelerated the final deprecations. For comparison, MD5 (a different, 128-bit algorithm) suffered practical collision attacks even earlier: the 2008 rogue-CA attack and the 2012 Flame malware both exploited MD5 chosen-prefix collisions, not SHA-1.

2. Step 2

   Upload both PDFs to the challenge server

   Observation

   I noticed that sha1sum confirmed both collision files produce the same 160-bit digest while differing at the byte level, which means they satisfy the server's two conditions: file1 != file2 and sha1(file1) == sha1(file2), making the upload the final step to retrieve the flag.

   Submit collision1.pdf and collision2.pdf through the upload form. The server checks that the two files are different (they are, at the byte level) and that their SHA-1 digests match (they do, thanks to the SHAttered collision). Both conditions satisfied, the server returns the flag.

   Learn more

   What the server checks. The gate is: file1 != file2 AND sha1(file1) == sha1(file2). The two PDFs differ byte-for-byte (you can confirm with diff collision1.pdf collision2.pdf or compare their SHA-256 hashes), but produce the same 160-bit SHA-1 digest. Because the server only inspects the SHA-1 digest for equality, both uploads pass as valid distinct documents.

   The challenge illustrates why SHA-1 should not be used for security-critical integrity checks. Any system that accepts "same SHA-1 hash implies same content" is vulnerable to an attacker who can present two different documents as equivalent. Modern systems should use SHA-256 or SHA-3 for integrity verification.

Flag

SHA-1 is cryptographically broken - the 2017 SHAttered attack demonstrated that two distinct files can share the same SHA-1 digest, undermining any security system that relies on SHA-1 for integrity checking.