Parity that collides
Defective RAID: recovering files when two of five disks are gone
Five disk images, two missing, and a Ruby emulator whose second parity is not quite RAID-6. The recovery needs the algebra of the parity code, a collision search and a heuristic for picking the likely candidate.
- 01
Inspect
The Ruby emulator shows rows of 3 data blocks plus P and Q parity, with the parity columns rotating; disks 2 and 3 are the lost ones.
- 02
Hypothesize
P is a plain XOR and easy to invert. Q looks like RAID-6 but uses a lookup table that is not a proper field reduction, so recovery may be ambiguous.
- 03
Test
Reassemble with zeros for unknown blocks, count how many blocks need which repair, and find a concrete pair of inputs with identical Q.
- 04
Solve
Enumerate every valid candidate for each damaged word, pick the one that is zero or printable, and grep the mounted filesystem for the flag.
Defective RAID was a 300-point forensics and programming task in TokyoWesterns/MMA CTF 2nd 2016. The description says the RAID NAS fails after two disks crash and asks to rescue an exploit source file. The package contains five disk images, a Ruby script with an incomplete RAID emulator, and nothing else. Two of the five disks are unreadable, so only disk0, disk1 and disk4 carry data.
Reading the emulator
The Ruby code describes the layout. Each stripe row has five blocks of 512 bytes: three data blocks, a P block and a Q block. The images are 256 KiB, which gives 512 rows per disk. Which column holds P, which holds Q and which three hold data changes with the row, and the Python equivalents of the three position functions are short: P sits in column -(row + 2) % 5, Q in -(row + 1) % 5, and the data columns are three consecutive positions starting at -row % 5, taken modulo 5 and sorted.
That produces four situations per row, depending on which disks are missing:
- All three data blocks survive, so nothing needs to be done.
- One data block is missing and P survives, so XOR repairs it.
- One data block is missing and only Q survives.
- Two data blocks are missing, and P and Q both survive.
The first case is trivial, and the second is the same XOR trick as in a plain RAID-5. The third and fourth cases are the reason the task is worth 300 points.
First attempt and the count of failures
A first reassembly can fill the easy case, write zeros in place of unknown blocks in the harder cases, and count how often each case occurred. The counts came out as 13184 words needing a Q-only repair and 26112 needing a P-and-Q repair. Mounting the result gave a filesystem with two readable JPEG names and one directory, d3flate, that returned an input/output error. One of the pictures was recognized by file, the other only as data. This confirmed the general shape of the layout and also showed that zero-filling was losing real data: the directory entry was damaged.
Why the second parity is not RAID-6
Real RAID-6 computes Q over GF(2^8) with generator powers, and the Linux md code is a well-known reference. The emulator works on 32-bit little-endian words instead. For each word position it builds a 64-bit-wide sum where block j contributes its word shifted left by j bits, XORed together, then reduces the overflow above bit 32 by looking up a four-entry table: [0, 517762881, 517762881, 593801667]. Those constants are related: 593801667 equals 517762881 << 1 ^ 517762881. The first constant, 0x1EDC6F41, is also the polynomial known from CRC-32C, so the table looks like a carry-less multiplication reduction that was written by hand.
A proper field multiplication would be invertible: different inputs always give different outputs. The table-based reduction is not, because the two middle entries of the table are identical, and the index is computed from the overflow bits, which cannot be told apart after the reduction. A collision is easy to demonstrate with a three-block input of one-word blocks. Taking ff ff ff ff, be 90 23 61, ff ff ff ff gives the same Q word as three blocks of ff ff ff ff. In RAID-6 proper this cannot happen. Here it means that Q and P together can describe several different original contents.
Enumerating candidates
The practical response is to find every candidate that satisfies the equations and then choose.
For the case with one data block missing and only Q available, the solver computes the partial sum of the known blocks, then tries each distinct table value t, derives the word that would produce the observed Q, and checks the upper two bits against all four possible masks to see which ones are consistent with the table index. Every consistent value goes into a set. The set size says whether the word was recovered uniquely, ambiguously, or not at all. In a measured run the statistics were 8850 unique and 4334 colliding words for this case.
The two-blocks-missing case is harder. Knowing P gives the XOR of the two lost words, and Q gives a second relation involving shifts. Solving x ^ (x << k) = n for x is a bit-by-bit recurrence, because each output bit depends on the bit k positions earlier. A small solve(k, n) function builds the answer from the top bits down and rejects inputs for which no solution exists. Then it tries both orderings of the two recovered words and keeps those that satisfy both P and Q. This path gave 6678 unique and 19434 colliding words, so more than two thirds of the damaged words had several valid candidates.
Choosing between candidates
Picking at random or taking an arbitrary element of the set still left the filesystem broken: tree looped forever on a corrupted directory and the JPEGs did not decode. The deciding step was to use what the data is likely to contain. FAT tables and directory slack are full of zero words, so a candidate equal to zero wins first. For the rest, a candidate whose four bytes are all printable ASCII beats one that is not, since the target is source code. For the two-word case the order of preference is: both words zero, both printable, at least one zero, at least one printable, and anything otherwise. With these rules in place the remaining damage is confined to the binary files, which are not needed.
The final mount shows the d3flate directory with d3flate.c, a Makefile, a compiled binary and exploit/exploit.py. A recursive grep -ri flag /mnt/img finds the answer in a comment at the top of exploit.py, in the format TWCTF{...}; the Makefile also matches because of CFLAGS, which is a harmless false positive.
What transfers to other challenges
When a recovery problem has an ambiguous solution set, count the ambiguity first: the ratio of unique to colliding words tells whether a heuristic can work. Search for the cheapest tie-break that matches the expected content type, since that matters more than elegant algebra. And read the reference implementation closely, because the lookup table here is the whole puzzle.
For the straightforward version of this problem, see Deadnas. A systematic way to see parity bands and data bands in a disk image is explained in binary data visualization, and compression vs encryption shows why parity looks like noise.
Questions readers ask
What do P and Q mean in RAID-6?
P is the XOR of the data blocks in a stripe row. Q is a second, independent syndrome, normally the sum of the data blocks each multiplied by a different power of a generator in GF(2^8). With both, any two missing blocks of a row can be solved as two equations in two unknowns.
Why do collisions make recovery harder?
If two different data sets produce the same Q, then Q and P together no longer identify the lost blocks uniquely. The solver gets several candidates per damaged word and must choose, so the recovered filesystem can contain wrong bytes unless a good tie-break rule is used.
Why prefer zero and printable bytes when choosing a candidate?
Real disks hold many zero bytes in FAT tables and padding, and source code is mostly printable ASCII. Among equally valid candidates, the one with zeros or printable characters is far more likely to be the original, so the heuristic recovers text files first and leaves binary files damaged.
New to capture the flag? Formats, teams and a first-month plan in one place.
Read the CTF guide