It is my Birthday 2 picoCTF 2021 Solution

Description

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

   Observation

   The challenge wants two distinct files with identical SHA-1 hashes, which is exactly what the public SHAttered collision PDFs from 2017 provide. The server also checks that the final 1000 bytes match, so appending the invite.pdf suffix to both files preserves the collision through the Merkle-Damgard construction.

   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 takes roughly 9.2 x 10^18 SHA-1 computations, which no personal hardware will finish in any useful time. The SHAttered PDFs are the readily available precomputed pair, and they are the intended starting point. This challenge is about exploiting an existing collision, not mounting a new one.

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

   Append the suffix to only one file and the digests diverge, because the extra block changes the Merkle-Damgard chain state for that file alone, so the server's equality check fails. Append it identically to both and the internal state differs only at the already-colliding blocks, after which the shared suffix 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 of the same length 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. Equal length matters, because Merkle-Damgard appends the total message length in the final padding block; the two SHAttered PDFs are both 422435 bytes, so that condition holds here. 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 2Upload both PDFs to the challenge server

   Observation

   sha1sum confirms both files produce the same 160-bit digest while differing at the byte level. That satisfies both of the server's conditions, so uploading them is the last step.

   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.