This problem deals with some of the modern cryptographical concepts. Fans of pen-and-paper cryptography should check out problem E.
During the investigation of a very complicated case of computer crime, it was discovered that the culprit had been encrypting all his data in a quite sophisticated way. He bought one of the STOP-U (Security Through Obscurity Pluggable USB) devices which are plugged into a standard USB port. The encryption software installed on the machine takes the password – a large number – given by the user, sends this number to the STOP-U device, and receives back the encryption key.
Documentation of the STOP-U device states that:
h1.in.
Any input not in that range produces an error message.
The password used by the culprit has already been obtained, it was X = 31415926535897932384626433. Unfortunately, one of the investigators was a bit clumsy and accidentally short-circuited three of the input contacts on the device. As a result, the lowest three bits of the input are always re-set to zeroes. For example, if you enter the number 22 (binary 10110), the device will read the number 16 (binary 11000). In other words, the password is useless... or is it?
Find the output which WOULD be produced by the device, if it hadn't been damaged by the clumsy guy. In other words, find the number S the original (not damaged) device outputs for the culprit's password X.
Your submission may have one of two different formats:
The result of a submission of the first type will be the output of the damaged device for your input. These submissions count as wrong submissions, i.e., each of them will cost you 10 penalty minutes if you solve the task.
The result of a submission of the second type will be either OK or Wrong answer.
T: 271828182845904523536
The story continues...
One of the directories found on the suspect's harddisk contained two strange files. Although they were different, the disk-imaging software the investigators had been using kept claiming they are the same – and copied only one of them...
After contacting the authors of the software it was found that the file-compare routine used by the software works by comparing the MD5 checksums (hashes) of the files, instead of their complete contents. It's much faster, especially if there are many duplicate files. And, after all, such a method is absolutely reliable for "normal" files, isn't it?
Fortunately, a young investigator, Villiam Mlastik, knew that the answer is "NO, IT IS NOT RELIABLE!". His computer is broken, though, so he'd like to ask you to help him prove his point by creating two different files with the same MD5 checksum. In order to make them more visually-appealing to the authors of the software, the files have to be valid PostScript files and their header has to show that the files had been created by him.
Find two distinct valid PostScript files. Both must start
with the header provided in file h2.in. In addition,
both files must have the same MD5 checksum.
When viewed / printed, one of the files should display the text
"(your team name) are mighty hackers!"
and the other one should show "IPSC rulez!".
Submit a .zip, a .tar.gz, or a .tar.bz2
archive containing both your files. Name the files h2a.ps
and h2b.ps.
The definition and sample implementation of the MD5 hashing algorithm can be found in RFC1321. Most decent programming languages do have a library function to compute the MD5 checksum of given data.
We will use our eyes, our hands,
and md5sum from GNU Text Utilities
to check the correctness of your submissions.
Credits:
Problemsetter(s): MisoF
Contest-related materials: g00ber, MisoF
Acknowledgements: Vlastimil Klima, Magnus Daum, and Stefan Lucks for their contributions to
the area of MD5 collisions.