Rating:
The big trick: Each byte of the flag was padded with 3 bytes of random data before going through the cipher.
But, the last 2 bytes of each input (aka, a random byte + flag byte) completely determine the last 2 bytes of each output.
All you need to do is build a table of all possible a random byte + flag byte combinations, and their cyphertexts.