Link: https://score.ctf.westerns.tokyo/problems/38 (only for logged in users)
Points: 300
Category: forensic, PPC

Description

The stupid RAID NAS fails after two disks are crashed.
Please rescue our exploit source code.

Incomplete RAID emulator is attached.

defective-raid.7z

tl;dr

Provided archive contains custom RAID implementation (Ruby) and 5 disk images. 2 disks are crashed. At first, the implementation looks similar to RAID-6 but after some investigation it turns out to be malformed allowing collisions which makes full data rescue difficult.

Solution

I did not manage to finish this task during the contest. Still I did verify the flag after the contest was finished. The full working source code (Python) is at the end. I will try to describe more less how I have came up to this solution.

After reading provided implementation we know that there are 5 blocks in a row: 3 data blocks, P (block with parity1 outcome) and Q (block with parity2 outcome). Blocks are distributed differently in each row and we have 4 different cases:

  1. no data block missing (trivial, nothing to do)
  2. 1 data block missing but P available
  3. 1 data block missing but Q available
  4. 2 data block missing but P and Q available

We can quickly observe that in case 2 we can easily restore missing data block as P is just XOR of all data blocks.

First I just pieced together all data blocks, restoring missing blocks in case 2 (function fill_missing_p) and putting zeros in unknown blocks in case 3 and 4. I counted how many times it was required, failed_1 is case 3 and failed_2 is case 4. I  After mounting the result I got something like:

Not bad but still nothing interesting. At this point I started to read some theory behind the RAID so that I can fix case 3 and 4. I’ve carefully read this and  this wiki articles and compared it with parity2 function. I noticed that 593801667 = 517762881 << 1 ^ 517762881 which was promising. At first I tried to extract g0 g1 and g2 operations so that I could rewrite parity2 to something like:

which would allow me to use the theory behind RAID-6. But after a while I observed that original parity2 function is totally broken and I was able to find the example collision:

In original RAID-6 collisions should not happen. In this particular implementation they occur as it is not always possible to determine which mask (value from table) was used.

My idea to deal with collision at this point was just to find all valid candidates and pick one of them (in some deterministic way or at random). I wanted to check how many collisions would occur on the whole disk and hoped that I will restore enough data to read the flag. I expected that most often the collision will contain only 2 valid candidates.

I started with case 3 (function fill_missing_q). I could not apply the method described on wiki so I just used the simple idea to find all candidates that have the chance of being valid and then to check them one by one.  After I finished I restored data with rate 4334 colliding to 8850 non colliding values. The data was still unreadable so I worked on case 4 (fill_missing_p_q) using similar idea. After I finished the result was still not good.

JPG images were still broken. Folder structure was also broken (tree command produces infinite loop). I tried selecting from valid candidates in random but this did not work any better. At this point I was wandering if I would manage to restore the images. If this was the objective, the solution would probably be worth more then 300 points. I decided that the flag should be in some text file (“Please rescue our exploit source code” is the description).

I worked on some better strategy of picking from valid candidates in case of collision (functions pick1 and pick2). I decided that I prefer 0 as it is more probable to occur (this fixed some junk data in fat tables). I also decided to prefer candidates which contain only printable ASCI characters. This way I reached the final version of the code which solved the problem:

And the result:

 


Leave a Reply

Your email address will not be published. Required fields are marked *

*

Share This