Editorial for DMOJ Capture The Flag '20 F3 - Four Taps


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

In this problem, we are given a broken FLAC file that we must fix. In the statement, there is a hidden span that clarifies that a few bits is actually 4, so we know when we have properly fixed the file. Off the bat, there are already 3 bits that are obviously wrong. The first 4 bytes of a FLAC file should be fLaC, while in our case, it is eLac. After fixing this, we have one bit left that we need to fix. If we read the documentation on the FLAC format, we can see that a FLAC is broken up into 2 sections that we care about, the metadata section and the audio section.

Let us take a look at the metadata section first. After the first 4 bytes (the magic number), we have a block where the first byte is 00000000. This means that this is not the last metadata block and that the block type is STREAMINFO. The next 3 bytes are 000022, which means that the next 0x22 = 34 bytes is the length of the metadata block. Let us skip this data for now. We hit the next block. This next block's first byte is 00000100, which means that this is not the last metadata block and that the block type is VORBIS_COMMENT. The next 3 bytes are 00002e, which means that the next 0x2e = 46 bytes is the metadata. Once again, let us skip this data for now (However, note that this block is actually a comment block, so we can completely ignore it).

We hit the next block. This next block's first byte is 00000001, meaning this is not the last metadata block and that the block type is PADDING. The next 3 bytes are 002000, which means that the next 0x2000 bytes is the metadata. Again, let us skip this data for now (again, we can completely ignore this block because the padding block should be filled with zeroes, and indeed it is).

We hit the next block (promise this is the last block we'll analyze). The first byte is 11111111, meaning that this is the last metadata block, and the block type is ...invalid? The next 3 bytes are f8590c, which means the length of the metadata block is ... 16271628 bytes?! This can't possibly be correct, because the entire file is less than 16271628 bytes. Either we overshot or all 3 of these bytes are wrong. However, since we are off by only 1 bit, all 3 bytes can't be wrong. Thus, we definitely overshot.

Now, let's backtrack. Let's assume that we actually hit the audio data section, which means that the previous block must have been the last metadata block section. Recall that the first bit in the first byte of each metadata section determines if it is the last metadata block — exactly the one bit we are missing. Thus, let's change the 01 in position 0x5c to an 81 to flag it as the last metadata block.

If we try playing the FLAC file now, it works! ... "works". The audio is a bunch of "dots" and "dashes" — morse code. Converting this morse code either manually or with software reveals the flag to us.


Comments

There are no comments at the moment.