Bob wants to draw tons of .png images (http://www.w3.org/TR/PNG/) and send them to Alice. He does not want anyone else to see those pictures. Therefore, he designed the Super Secret Protocol (SSP) and he uses it to communicate with Alice.
Eve wants to destroy their relationship. She bribed their internet providers to slow down their internet so that she could get access to their communication. Now, every message between Bob and Alice travels so slow that Eve can hold it for up to several hours. She has also drawn an evil image, which she wants to deliver to Alice in Bob’s name. Then Alice will break up with Bob for sure (well, with 95 percent confidence).
Unfortunately (for Eve), Eve knows exactly nothing about cryptography. Therefore, she hired IPSC organizers to take care of it. And as they were just preparing this contest, they decided to kill two birds with one stone – and let you do the dirty work for them. The evil images (one for each subproblem, see below) are provided in the respective input files.
SSP protocol specification
Alice has a secret key KA, Bob has a secret key KB. When Bob wants to send a message M of length n to Alice, the following happens:
Notes: ⊕ is bitwise xor. Bob needs exactly six minutes to draw an image. Therefore he will always start sending the next image six minutes after Alice receives the previous one.
Problem specification
Your task is to monitor the messages sent between Alice and Bob and to change some of the messages in such a way that Alice will get the evil image.
In the easy subproblem, you can change any message you want. However, in the hard subproblem, you can only change the messages that go from Alice to Bob.
Note that the hard subproblem uses different secret keys and other messages than the easy subproblem. The protocol remains the same.
Input/output specification
Messages are in binary format, each one has exactly 10000 bytes. The most recently sent message in on the top of the list. If you want to change this message, submit (using the standard submission interface) a binary file containing the new message. If you just wish to deliver it in its original state, submit a text file containing one line with a single word: “forward”.
Valid submissions during the protocol are not counted as incorrect – you will not receive penalty minutes for these submissions.
In the hard subproblem you can only change one message from the protocol, the other ones will be forwarded to their recipient automatically.
In both subproblems, the time between any two submissions in different instances of the protocol has to be at least 6 minutes. In other words, you may not try to submit anything while Bob is drawing the next picture. Submissions that violate this rule will be judged as wrong answers; upon solving the task you will receive penalty minutes for these submissions.
The replaced message always has to have the same size as the original message (otherwise you will get an wrong answer).
At the end of the protocol, if Alice received anything other than the evil image, you will also get a wrong answer. If Alice receives the evil image, you solved the subproblem.
The evil image and all messages sent by Alice or Bob have exactly 10000 bytes. All images are valid PNG images. Alice and Bob have keys of size 50000 bytes.
Past communication between Alice and Bob
The following is a static example of a page the teams saw during the contest. The page contains a list of messages sent between Alice and Bob, along with the modifications already made by the contestants.