Defective RAID - CodiSec CodiSec

13 September 2016 Jakub Luczyński — No Comments

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:

no data block missing (trivial, nothing to do)
1 data block missing but P available
1 data block missing but Q available
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:

$ python fix.py

{'failed_1': 13184, 'failed_2': 26112}

$ sudo mount disk_out /mnt/img

$ ls -lha /mnt/img

ls: cannot access '/mnt/img/d3flate': Input/output error

total 506K

drwxr-xr-x 3 root root 16K Jan 1 1970 .

drwxr-xr-x 6 root root 4.0K Sep 3 17:55 ..

d????????? ? ? ? ? ? d3flate

-rwxr-xr-x 1 root root 262K Aug 6 10:23 dog-1194083_1280.jpg

-rwxr-xr-x 1 root root 223K Aug 6 10:23 dog-1210559_1280.jpg

$ file /mnt/img/dog-*

/mnt/img/dog-1194083_1280.jpg: data

/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

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:

def eval_g(block, i):

# todo

pass

def parity2(blocks):

xor(*(eval_g(b, i) for i, b in enumerate(blocks)))

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:

def parity2(blocks)

table = [0, 517762881, 517762881, 593801667]

parity = "".b

(BLOCK_SIZE/4).times do |i|

sum = 0

blocks.each_with_index do |block, j|

puts block[i*4,4].unpack("V")[0]

sum ^= (block[i*4,4].unpack("V")[0] << j)

end

sum = (sum & 0xffffffff) ^ table[sum >> 32]

parity << [sum].pack("V")

end

parity

end

input1 = ["\xff\xff\xff\xff", "\xbe\x90#a", "\xff\xff\xff\xff"]

input2 = ["\xff\xff\xff\xff", "\xff\xff\xff\xff", "\xff\xff\xff\xff"]

BLOCK_SIZE = 4

parity2(input1) == parity2(input2)

=> true

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.

$ python fix.py

{'collisions_1': 4334, 'collisions_2': 19434, 'ok_1': 8850, 'ok_2': 6678}

$ ls img

...

ls: cannot access 'img/?%┤⌡?%┤⌡.?%┤': Input/output error

?%┤⌡?%┤⌡.?%┤ ?%┤⌡?%┤⌡.?%┤ ?%┤⌡?%┤⌡.?%┤ ?%┤⌡?%┤⌡.?%┤ ?%┤⌡?%┤⌡.?%┤

?%┤⌡?%┤⌡.?%┤ ?%┤⌡?%┤⌡.?%┤ ?%┤⌡?%┤⌡.?%┤ ?%┤⌡?%┤⌡.?%┤ d3flate

?%┤⌡?%┤⌡.?%┤ ?%┤⌡?%┤⌡.?%┤ ?%┤⌡?%┤⌡.?%┤ ?%┤⌡?%┤⌡.?%┤ dog-1194083_1280.jpg

?%┤⌡?%┤⌡.?%┤ ?%┤⌡?%┤⌡.?%┤ ?%┤⌡?%┤⌡.?%┤ ?%┤⌡?%┤⌡.?%┤ dog-1210559_1280.jpg

?%┤⌡?%┤⌡.?%┤ ?%┤⌡?%┤⌡.?%┤ ?%┤⌡?%┤⌡.?%┤ ?%┤⌡?%┤⌡.?%┤

$ file /mnt/img/dog-*

/mnt/img/dog-1194083_1280.jpg: JPEG image data, JFIF standard 1.01, aspect ratio, density 1x1, segment length 16

/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

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:

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

import itertools

import pprint

from pwn import *

def idx_dict(l):

out = defaultdict(list)

for i, el in enumerate(l):

out[el].append(i)

return dict(out)

table = [0, 517762881, 517762881, 593801667]

table_idx_dict = idx_dict(table)

def p_column(row):

return -(row + 2) % 5

def q_column(row):

return -(row + 1) % 5

def d_columns(row):

start = -row % 5

out = [x % 5 for x in range(start, start + 3)]

out.sort()

return out

counter = defaultdict(int)

def fill_missing_p(blocks, p):

i = blocks.index(None)

blocks[i] = reduce(operator.xor, (b for b in blocks if b is not None), p)

return blocks[i]

def eval_q(blocks, show=False):

s = 0

for j, block in enumerate(blocks):

s ^= block << j

if show:

print s, s >> 32

return (s & 0xffffffff) ^ table[s >> 32]

def is_string_like(x):

return all(c in string.printable + "0x00" for c in p32(x))

def pick1(candidates):

if 0 in candidates:

return 0

strs = filter(is_string_like, candidates)

if len(strs) > 1:

counter["pick1_str_conflicts"] += 1

if len(strs) > 0:

return strs[0]

return candidates.pop()

def pick2(candidates, k):

missing = range(3)

missing.remove(k)

i, j = missing

for cand in candidates:

if cand[i] == 0 and cand[j] == 0:

return cand

for cand in candidates:

if is_string_like(cand[i]) and is_string_like(cand[j]):

return cand

for cand in candidates:

if cand[i] == 0 or cand[j] == 0:

return cand

for cand in candidates:

if is_string_like(cand[i]) or is_string_like(cand[j]):

return cand

return candidates.pop()

def fill_missing_q(blocks, q):

s = 0

for j, b in enumerate(blocks):

if not b:

continue

s ^= b << j

i = blocks.index(None)

l = 0b11 >> (2 - i)

ok = set()

for t in set(table):

if (s ^ t ^ q) & l == 0:

cand = ((s & 0xffffffff) ^ t ^ q) >> i

assert (s ^ cand << i ^ t) & 0xffffffff == q

for mask in (0b00, 0b11, 0b01, 0b10):

cand2 = cand | mask << 30

if (s ^ cand2 << i ^ t) & 0xffffffff == q and \

(s ^ cand2 << i) >> 32 in table_idx_dict[t]:

ok.add(cand2 & 0xffffffff)

if len(ok) == 0:

counter["failed_1"] += 1

ok.add(0)

elif len(ok) > 1:

counter["collisions_1"] += 1

else:

counter['ok_1'] += 1

# blocks[i] = ok.pop()

# blocks[i] = random.sample(ok, 1)[0]

blocks[i] = pick1(ok)

class NoSolutionException(Exception):

pass

# solution to x ^ x << k = n

def solve(k, n):

if n == 0:

return 0

n_digits = map(int, bin(n)[2:])

l = len(n_digits)

if k >= l:

raise NoSolutionException()

assert 1 <= k < l != 0

out = n_digits[:k]

for i in range(k, l - k):

out.append(out[-k] ^ n_digits[i])

if n_digits[-k:] != out[-k:]:

raise NoSolutionException()

x = int("".join(map(str, out)), 2)

assert x ^ x << k == n

return x

def fill_missing_pq(blocks, p, q):

assert len([b for b in blocks if b is not None]) == 1

ok = set()

i, d = [(i, b) for i, b in enumerate(blocks) if b is not None][0]

x = p ^ d

for m in set(table):

yy = q ^ (d << i & 0xffffffff) ^ m

for b in (0x11, 0x10, 0x01, 0x00):

y = yy | b << 32

try:

if i == 0:

d1 = solve(1, x << 1 ^ y) >> 1

elif i == 1:

d1 = solve(2, x ^ y)

else:

assert i == 2

d1 = solve(1, x ^ y)

except NoSolutionException:

continue

d1 &= 0xffffffff

d2 = d1 ^ x

# order

if i == 0:

cands = [(d, d1, d2), (d, d2, d1)]

elif i == 1:

cands = [(d1, d, d2), (d2, d, d1)]

else:

cands = [(d1, d2, d), (d2, d1, d)]

ok.update(c for c in cands if (eval_q(c) == q and

reduce(operator.xor, c) == p))

if len(ok) == 0:

counter["failed_2"] += 1

ok.add((0, 0, 0))

elif len(ok) > 1:

counter["collisions_2"] += 1

else:

counter['ok_2'] += 1

# out = ok.pop()

# out = random.sample(ok, 1)[0]

out = pick2(ok, i)

for i in xrange(3):

if blocks[i] is None:

blocks[i] = out[i]

def fill_missing(blocks, p=None, q=None):

x = len(filter(lambda el: el is None, blocks))

if x == 1 and p is not None:

fill_missing_p(blocks, p)

elif x == 1 and q is not None:

fill_missing_q(blocks, q)

elif x == 2 and p is not None and q is not None:

fill_missing_pq(blocks, p, q)

else:

print blocks, p, q

assert False

def int32_provider(data, k=None):

if k is None:

k = len(data)

for i in xrange(0, k, 4):

if data:

yield u32(data[i: i + 4])

else:

yield None

def fix():

n = 256 * 1024

k = 512

with open("disk0", "rb") as f0:

with open("disk1", "rb") as f1:

with open("disk4", "rb") as f4:

with open("disk_out", "wb") as f_out:

for row in xrange(n / k):

pc = p_column(row)

qc = q_column(row)

dc = d_columns(row)

assert len(set([pc] + [qc] + dc)) == 5

row_data = (

int32_provider(f0.read(k)),

int32_provider(f1.read(k)),

int32_provider(None, k),

int32_provider(f4.read(k))

)

data = []

for portion in itertools.izip(*row_data):

p = portion[pc]

q = portion[qc]

ds = [portion[i] for i in dc]

if any(d is None for d in ds):

fill_missing(ds, p, q)

data.append(ds)

for block in zip(*data):

f_out.write("".join(map(p32, block)))

if __name__ == "__main__":

fix()

pprint.pprint(dict(counter))

And the result:

$ tree /mnt/img

/mnt/img

├── d3flate

│ ├── d3flate

│ ├── d3flate.c

│ ├── exploit

│ │ └── exploit.py

│ └── Makefile

├── dog-1194083_1280.jpg

└── dog-1210559_1280.jpg

2 directories, 6 files

$ grep -ri /mnt/img -e "flag"

/mnt/img/d3flate/Makefile:CFLAGS = -fstack-protector -funsigned-char -m32 -O2

/mnt/img/d3flate/Makefile:LDFLAGS = -m32

/mnt/img/d3flate/Makefile: $(CC) $(CFLAGS) $(LDFLAGS) -o $@ $< -lz -lcrypto

/mnt/img/d3flate/exploit/exploit.py:# Flag is TWCTF{15264e77bbda63f7f6596cf66c92aa1981e0c07b}

Description

tl;dr

Solution

Leave a Reply Cancel reply

Cookies