Editorial for DMOJ Capture The Flag '20 C4 - Larger Encryption


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

This problem is very strange. Instead of the flag as the text to be encrypted, it is actually the key used for encrypting. As such, we know nothing about the data (except that maybe all the characters are printable?). Looking closely at the encryption system, we can see that the first BLOCK_SIZE characters remain completely untouched after encrypting. This reveals a lot of information. For one, the first few bytes do not match any common magic number, so the text is most likely printable characters or some weird format. Let us not assume anything for now.

The second thing we can notice is that for each block of data, only one byte of the key is used. Once again, we can brute force this one byte and check all 256 outputs. Remember that the second block is XOR'd with the first block, so remember to reverse that first. If we go through all 256 outputs, exactly one of them contains all printable characters, not to mention that it forms English words. Thus, we can somewhat safely assume that all the characters are printable characters (we can check thoroughly after if we need to). Checking a few more blocks, we can see all of them return valid English words. In fact, some might realize this text is a section of one of Shakespeare's plays. In theory, you could simply copy the text from an unencrypted version of the play, but you never know if the problem author is messing with you and changed a few bytes. As such, we will not rely on external sources to decrypt the rest of the text.

As there are more than 80 blocks to decrypt, we can write a script to decrypt them automatically. Remember to store this key somewhere as we will need it later to retrieve the flag. For each block, we'll need to check if there is exactly one key byte that returns printable characters (if not, then our initial assumption that all the bytes are printable is wrong). It turns out that this initial assumption is indeed correct, as all blocks return only one valid key byte.

Next, we notice that the key is actually "encrypted" with the plaintext. We will need to "decrypt" the key. Notice that the plaintext is padded, but this padding happens after we "encrypt" the key. As such, we will need to strip away the padding, which is all the @ characters at the end of the plaintext. Once we've done this, we can simply remove the i^\text{th} character for all i in the Counter dictionary. Remember to do this backwards (in descending array order), since characters were added in the ascending array.

Notice that the secrets.choice used for expanding the key only appends to the key, which means we don't care about the added values and can safely ignore them. Finally, we know that the flag is 37 bytes (from the 2nd line of the encrypted text), so we can take the first 37 bytes from this half-decrypted key. This is the flag.


Comments

There are no comments at the moment.