Link: https:\/\/score.ctf.westerns.tokyo\/problems\/38 (only for logged in users)
\nPoints:\u00a0300
\nCategory: forensic,\u00a0PPC<\/p>\n
The stupid RAID NAS fails after two disks are crashed.
\nPlease rescue our exploit source code.<\/p>\nIncomplete RAID emulator is attached.<\/p>\n
defective-raid.7z<\/a><\/p><\/blockquote>\n
tl;dr<\/h2>\n
Provided archive contains custom RAID implementation (Ruby) and 5 disk images. 2 disks are crashed. At first, the implementation looks similar to\u00a0RAID-6\u00a0but after some investigation\u00a0it turns out to be malformed allowing collisions which makes full data rescue difficult.<\/p>\n
Solution<\/h2>\n
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.<\/p>\n
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:<\/p>\n
\n
- no data block missing (trivial, nothing to do)<\/li>\n
- 1 data block missing but P available<\/li>\n
- 1 data block missing but Q available<\/li>\n
- 2 data block missing but P and Q\u00a0available<\/li>\n<\/ol>\n
We can quickly\u00a0observe that in case 2 we can easily restore missing data block as P is just XOR\u00a0of all data blocks.<\/p>\n
First I just pieced together all\u00a0data\u00a0blocks, 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 \u00a0After mounting the result I got something like:<\/p>\n
$ python fix.py\r\n{'failed_1': 13184, 'failed_2': 26112}\r\n\r\n$ sudo mount disk_out \/mnt\/img\r\n\r\n$ ls -lha \/mnt\/img \r\nls: cannot access '\/mnt\/img\/d3flate': Input\/output error\r\ntotal 506K\r\ndrwxr-xr-x 3 root root 16K Jan 1 1970 .\r\ndrwxr-xr-x 6 root root 4.0K Sep 3 17:55 ..\r\nd????????? ? ? ? ? ? d3flate\r\n-rwxr-xr-x 1 root root 262K Aug 6 10:23 dog-1194083_1280.jpg\r\n-rwxr-xr-x 1 root root 223K Aug 6 10:23 dog-1210559_1280.jpg\r\n\r\n$ file \/mnt\/img\/dog-*\r\n\/mnt\/img\/dog-1194083_1280.jpg: data\r\n\/mnt\/img\/dog-1210559_1280.jpg: JPEG image data, JFIF standard 1.01, aspect ratio, density 1x1, segment length 16, baseline, precision 8, 1280x960, frames 3\r\n<\/pre>\nNot 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<\/a>\u00a0and \u00a0this<\/a>\u00a0wiki articles\u00a0and 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:<\/p>\n
def eval_g(block, i):\r\n # todo\r\n pass\r\n\r\ndef parity2(blocks):\r\n xor(*(eval_g(b, i) for i, b in enumerate(blocks)))<\/pre>\nwhich would allow me to use the\u00a0theory 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:<\/p>\n
def parity2(blocks)\r\n table = [0, 517762881, 517762881, 593801667]\r\n parity = \"\".b\r\n (BLOCK_SIZE\/4).times do |i|\r\n sum = 0\r\n blocks.each_with_index do |block, j|\r\n puts block[i*4,4].unpack(\"V\")[0]\r\n sum ^= (block[i*4,4].unpack(\"V\")[0] << j)\r\n end\r\n sum = (sum & 0xffffffff) ^ table[sum >> 32]\r\n parity << [sum].pack(\"V\")\r\n end\r\n parity\r\nend\r\n\r\ninput1 = [\"\\xff\\xff\\xff\\xff\", \"\\xbe\\x90#a\", \"\\xff\\xff\\xff\\xff\"]\r\ninput2 = [\"\\xff\\xff\\xff\\xff\", \"\\xff\\xff\\xff\\xff\", \"\\xff\\xff\\xff\\xff\"]\r\n\r\nBLOCK_SIZE = 4\r\nparity2(input1) == parity2(input2)\r\n=> true<\/pre>\nIn original RAID-6 collisions should\u00a0not happen. In this particular implementation they occur as it is not always possible to\u00a0determine which mask (value from table) was used.<\/p>\n
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\u00a0occur 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.<\/p>\n
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. \u00a0After I finished I restored data\u00a0with 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.\u00a0After I finished the result was still not good.<\/p>\n
$ python fix.py\r\n{'collisions_1': 4334, 'collisions_2': 19434, 'ok_1': 8850, 'ok_2': 6678}\r\n\r\n$ ls img\r\n...\r\nls: cannot access 'img\/?%\u2524\u2321?%\u2524\u2321.?%\u2524': Input\/output error\r\nls: cannot access 'img\/?%\u2524\u2321?%\u2524\u2321.?%\u2524': Input\/output error\r\nls: cannot access 'img\/?%\u2524\u2321?%\u2524\u2321.?%\u2524': Input\/output error\r\n?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524\r\n?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524\r\n?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524\r\n?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524\r\n?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524\r\n?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524\r\n?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524\r\n?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524\r\n?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 d3flate\r\n?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 dog-1194083_1280.jpg\r\n?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 dog-1210559_1280.jpg\r\n?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524\r\n?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524\r\n?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524 ?%\u2524\u2321?%\u2524\u2321.?%\u2524\r\n\r\n$ file \/mnt\/img\/dog-*\r\n\/mnt\/img\/dog-1194083_1280.jpg: JPEG image data, JFIF standard 1.01, aspect ratio, density 1x1, segment length 16\r\n\/mnt\/img\/dog-1210559_1280.jpg: JPEG image data, JFIF standard 1.01, aspect ratio, density 1x1, segment length 16, baseline, precision 8, 1280x960, frames 3\r\n<\/pre>\nJPG images were\u00a0still broken. Folder structure was\u00a0also broken (tree command produces infinite loop). I tried selecting from valid candidates in random\u00a0but this did not work any better. At this point I was wandering if I would\u00a0manage 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).<\/p>\n
I worked on some better\u00a0strategy of picking from valid candidates in case of collision\u00a0(functions pick1 and pick2).\u00a0I\u00a0decided 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:<\/p>\n
import itertools\r\nimport pprint\r\n\r\nfrom pwn import *\r\n\r\n\r\ndef idx_dict(l):\r\n out = defaultdict(list)\r\n for i, el in enumerate(l):\r\n out[el].append(i)\r\n return dict(out)\r\n\r\n\r\ntable = [0, 517762881, 517762881, 593801667]\r\ntable_idx_dict = idx_dict(table)\r\n\r\n\r\ndef p_column(row):\r\n return -(row + 2) % 5\r\n\r\n\r\ndef q_column(row):\r\n return -(row + 1) % 5\r\n\r\n\r\ndef d_columns(row):\r\n start = -row % 5\r\n out = [x % 5 for x in range(start, start + 3)]\r\n out.sort()\r\n return out\r\n\r\n\r\ncounter = defaultdict(int)\r\n\r\n\r\ndef fill_missing_p(blocks, p):\r\n i = blocks.index(None)\r\n blocks[i] = reduce(operator.xor, (b for b in blocks if b is not None), p)\r\n return blocks[i]\r\n\r\n\r\ndef eval_q(blocks, show=False):\r\n s = 0\r\n for j, block in enumerate(blocks):\r\n s ^= block << j\r\n if show:\r\n print s, s >> 32\r\n return (s & 0xffffffff) ^ table[s >> 32]\r\n\r\n\r\ndef is_string_like(x):\r\n return all(c in string.printable + \"0x00\" for c in p32(x))\r\n\r\n\r\ndef pick1(candidates):\r\n if 0 in candidates:\r\n return 0\r\n strs = filter(is_string_like, candidates)\r\n if len(strs) > 1:\r\n counter[\"pick1_str_conflicts\"] += 1\r\n if len(strs) > 0:\r\n return strs[0]\r\n return candidates.pop()\r\n\r\n\r\ndef pick2(candidates, k):\r\n missing = range(3)\r\n missing.remove(k)\r\n i, j = missing\r\n for cand in candidates:\r\n if cand[i] == 0 and cand[j] == 0:\r\n return cand\r\n\r\n for cand in candidates:\r\n if is_string_like(cand[i]) and is_string_like(cand[j]):\r\n return cand\r\n\r\n for cand in candidates:\r\n if cand[i] == 0 or cand[j] == 0:\r\n return cand\r\n\r\n for cand in candidates:\r\n if is_string_like(cand[i]) or is_string_like(cand[j]):\r\n return cand\r\n\r\n return candidates.pop()\r\n\r\n\r\ndef fill_missing_q(blocks, q):\r\n s = 0\r\n for j, b in enumerate(blocks):\r\n if not b:\r\n continue\r\n s ^= b << j\r\n\r\n i = blocks.index(None)\r\n l = 0b11 >> (2 - i)\r\n\r\n ok = set()\r\n for t in set(table):\r\n if (s ^ t ^ q) & l == 0:\r\n cand = ((s & 0xffffffff) ^ t ^ q) >> i\r\n assert (s ^ cand << i ^ t) & 0xffffffff == q\r\n\r\n for mask in (0b00, 0b11, 0b01, 0b10):\r\n cand2 = cand | mask << 30\r\n if (s ^ cand2 << i ^ t) & 0xffffffff == q and \\\r\n (s ^ cand2 << i) >> 32 in table_idx_dict[t]:\r\n ok.add(cand2 & 0xffffffff)\r\n if len(ok) == 0:\r\n counter[\"failed_1\"] += 1\r\n ok.add(0)\r\n elif len(ok) > 1:\r\n counter[\"collisions_1\"] += 1\r\n else:\r\n counter['ok_1'] += 1\r\n\r\n # blocks[i] = ok.pop()\r\n # blocks[i] = random.sample(ok, 1)[0]\r\n blocks[i] = pick1(ok)\r\n\r\n\r\nclass NoSolutionException(Exception):\r\n pass\r\n\r\n\r\n# solution to x ^ x << k = n\r\ndef solve(k, n):\r\n if n == 0:\r\n return 0\r\n n_digits = map(int, bin(n)[2:])\r\n l = len(n_digits)\r\n\r\n if k >= l:\r\n raise NoSolutionException()\r\n\r\n assert 1 <= k < l != 0\r\n out = n_digits[:k]\r\n for i in range(k, l - k):\r\n out.append(out[-k] ^ n_digits[i])\r\n\r\n if n_digits[-k:] != out[-k:]:\r\n raise NoSolutionException()\r\n x = int(\"\".join(map(str, out)), 2)\r\n assert x ^ x << k == n\r\n return x\r\n\r\n\r\ndef fill_missing_pq(blocks, p, q):\r\n assert len([b for b in blocks if b is not None]) == 1\r\n ok = set()\r\n i, d = [(i, b) for i, b in enumerate(blocks) if b is not None][0]\r\n x = p ^ d\r\n\r\n for m in set(table):\r\n yy = q ^ (d << i & 0xffffffff) ^ m\r\n for b in (0x11, 0x10, 0x01, 0x00):\r\n y = yy | b << 32\r\n\r\n try:\r\n if i == 0:\r\n d1 = solve(1, x << 1 ^ y) >> 1\r\n elif i == 1:\r\n d1 = solve(2, x ^ y)\r\n else:\r\n assert i == 2\r\n d1 = solve(1, x ^ y)\r\n except NoSolutionException:\r\n continue\r\n\r\n d1 &= 0xffffffff\r\n d2 = d1 ^ x\r\n\r\n # order\r\n if i == 0:\r\n cands = [(d, d1, d2), (d, d2, d1)]\r\n elif i == 1:\r\n cands = [(d1, d, d2), (d2, d, d1)]\r\n else:\r\n cands = [(d1, d2, d), (d2, d1, d)]\r\n\r\n ok.update(c for c in cands if (eval_q(c) == q and\r\n reduce(operator.xor, c) == p))\r\n\r\n if len(ok) == 0:\r\n counter[\"failed_2\"] += 1\r\n ok.add((0, 0, 0))\r\n elif len(ok) > 1:\r\n counter[\"collisions_2\"] += 1\r\n else:\r\n counter['ok_2'] += 1\r\n\r\n # out = ok.pop()\r\n # out = random.sample(ok, 1)[0]\r\n out = pick2(ok, i)\r\n\r\n for i in xrange(3):\r\n if blocks[i] is None:\r\n blocks[i] = out[i]\r\n\r\n\r\ndef fill_missing(blocks, p=None, q=None):\r\n x = len(filter(lambda el: el is None, blocks))\r\n if x == 1 and p is not None:\r\n fill_missing_p(blocks, p)\r\n elif x == 1 and q is not None:\r\n fill_missing_q(blocks, q)\r\n elif x == 2 and p is not None and q is not None:\r\n fill_missing_pq(blocks, p, q)\r\n else:\r\n print blocks, p, q\r\n assert False\r\n\r\n\r\ndef int32_provider(data, k=None):\r\n if k is None:\r\n k = len(data)\r\n\r\n for i in xrange(0, k, 4):\r\n if data:\r\n yield u32(data[i: i + 4])\r\n else:\r\n yield None\r\n\r\n\r\ndef fix():\r\n n = 256 * 1024\r\n k = 512\r\n\r\n with open(\"disk0\", \"rb\") as f0:\r\n with open(\"disk1\", \"rb\") as f1:\r\n with open(\"disk4\", \"rb\") as f4:\r\n with open(\"disk_out\", \"wb\") as f_out:\r\n for row in xrange(n \/ k):\r\n pc = p_column(row)\r\n qc = q_column(row)\r\n dc = d_columns(row)\r\n assert len(set([pc] + [qc] + dc)) == 5\r\n\r\n row_data = (\r\n int32_provider(f0.read(k)),\r\n int32_provider(f1.read(k)),\r\n int32_provider(None, k),\r\n int32_provider(None, k),\r\n int32_provider(f4.read(k))\r\n )\r\n\r\n data = []\r\n for portion in itertools.izip(*row_data):\r\n p = portion[pc]\r\n q = portion[qc]\r\n ds = [portion[i] for i in dc]\r\n if any(d is None for d in ds):\r\n fill_missing(ds, p, q)\r\n\r\n data.append(ds)\r\n\r\n for block in zip(*data):\r\n f_out.write(\"\".join(map(p32, block)))\r\n\r\n\r\nif __name__ == \"__main__\":\r\n fix()\r\n pprint.pprint(dict(counter))\r\n<\/pre>\nAnd the result:<\/p>\n
$ tree \/mnt\/img\r\n\/mnt\/img\r\n\u251c\u2500\u2500 d3flate\r\n\u2502 \u251c\u2500\u2500 d3flate\r\n\u2502 \u251c\u2500\u2500 d3flate.c\r\n\u2502 \u251c\u2500\u2500 exploit\r\n\u2502 \u2502 \u2514\u2500\u2500 exploit.py\r\n\u2502 \u2514\u2500\u2500 Makefile\r\n\u251c\u2500\u2500 dog-1194083_1280.jpg\r\n\u2514\u2500\u2500 dog-1210559_1280.jpg\r\n\r\n2 directories, 6 files\r\n\r\n$ grep -ri \/mnt\/img -e \"flag\"\r\n\/mnt\/img\/d3flate\/Makefile:CFLAGS = -fstack-protector -funsigned-char -m32 -O2\r\n\/mnt\/img\/d3flate\/Makefile:LDFLAGS = -m32\r\n\/mnt\/img\/d3flate\/Makefile:\t$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $< -lz -lcrypto\r\n\/mnt\/img\/d3flate\/exploit\/exploit.py:# Flag is TWCTF{15264e77bbda63f7f6596cf66c92aa1981e0c07b}\r\n<\/pre>\n<\/p>\n","protected":false},"excerpt":{"rendered":"
Link: https:\/\/score.ctf.westerns.tokyo\/problems\/38 (only for logged in users) Points:\u00a0300 Category: forensic,\u00a0PPC 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…<\/span> <\/p>\n
Read more ›<\/div>\n<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[3,6],"tags":[],"yoast_head":"\n\n\n\n\n\n\n\n\n\n\n\n\n\t\n