Editorial for DMOJ Capture The Flag '20 R1 - Classic Java


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Ninjaclasher

Looking at the encryption program, the input is broken into chunks of 10 bytes (except the last chunk, which uses whichever characters are left). With each chunk, it randomly determines whether to run subPart1 or subPart2 on that chunk. Then, it runs subPart3, and the result after all of these calls is concatenated to the final string. This final string is then printed out to the user as the encrypted flag.

Let's notice a few things about this problem.

First, subPart1 and subPart2 does not change the length of the chunk it is modifying. Only subPart3 changes the length. Let's see if we can figure out the length of the initial flag with this. If we pass in a string of length 10, we get back a string of length 23. As the encrypted string is 83 bytes, we know there are at least 3 full chunks, plus 14 bytes from the last chunk. We can check that if we pass a string of 7 bytes to subPart3, we get a string of length 14. Thus, this means the unencrypted string is exactly 37 bytes.

Next, since each chunk is handled independently, there are only 2^4 possibilities in whether each chunk used subPart1 or subPart2. Thus, we can try all possibilities. Let's try reversing subPart3 first, as it is needed for the entire string. Since it is recursive, we'll take a look at the first iteration. In the first iteration, the method takes some suffix of the input and appends some prefix of the input. Then, it recursively calls the method again with the first half of the input. Notice that the suffix and the prefix of the input that is concatenated contains all characters in the input, so we can actually ignore all the recursion. Thus, we just need to figure out how the initial string is reordered for the two input lengths given — 7 and 10. Once we do that, we can reverse subPart1 and subPart2.

For subPart1, we can see that the method is a simple XOR, where the i^\text{th} character is XOR'd with all the characters before it. The reverse of this method should be the exact same as the forward method, except we now process the string backwards.

For subPart2, we can see that the method is another XOR, except this time recursive. Notice that this is tail recursion, so we can unroll this into a for loop. If we analyze the first iteration of this loop, we can see that the entire string is XOR'd with the first byte. Then, we call the method again with the newly XORd string without the first byte. The first byte is then appended to the result of this method call. Thus, we know that the last byte of the final string is untouched, the second last byte is XORd with last byte, etc. This should be very simple to reverse, and is left as an exercise for the reader.

Finally, we can try all 2^4 combinations, and see which one returns a string with all printable characters.


Comments

There are no comments at the moment.