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.