SECCON 2018 Quals - Special instructions

reversing

General problem description

We were given a moxie ELF-Binary which was implementing the xorshift32 PRNG algorithm. The flag and some additional random values were hard-coded into the elf.

Solution

Similar to the Special device file challenge the binary took the flag xored with a random value hard-coded into to binary and xored again with a value taken from the xorshift32 algorithm.

The catch was again, that we didn't know the correct configuration of the algorithm only the seed and the first 7 bytes.

Using the Marsaglia [1] paper again, we wrote a script which finds the correct configuration:

``````#!/usr/bin/env python3
from ctypes import *

possible_params = [
( 1, 3,10),( 1, 5,16),( 1, 5,19),( 1, 9,29),( 1,11, 6),( 1,11,16),( 1,19, 3),( 1,21,20),( 1,27,27),
( 2, 5,15),( 2, 5,21),( 2, 7, 7),( 2, 7, 9),( 2, 7,25),( 2, 9,15),( 2,15,17),( 2,15,25),( 2,21, 9),
( 3, 1,14),( 3, 3,26),( 3, 3,28),( 3, 3,29),( 3, 5,20),( 3, 5,22),( 3, 5,25),( 3, 7,29),( 3,13, 7),
( 3,23,25),( 3,25,24),( 3,27,11),( 4, 3,17),( 4, 3,27),( 4, 5,15),( 5, 3,21),( 5, 7,22),( 5, 9,7 ),
( 5, 9,28),( 5, 9,31),( 5,13, 6),( 5,15,17),( 5,17,13),( 5,21,12),( 5,27, 8),( 5,27,21),( 5,27,25),
( 5,27,28),( 6, 1,11),( 6, 3,17),( 6,17, 9),( 6,21, 7),( 6,21,13),( 7, 1, 9),( 7, 1,18),( 7, 1,25),
( 7,13,25),( 7,17,21),( 7,25,12),( 7,25,20),( 8, 7,23),( 8,9,23 ),( 9, 5,1 ),( 9, 5,25),( 9,11,19),
( 9,21,16),(10, 9,21),(10, 9,25),(11, 7,12),(11, 7,16),(11,17,13),(11,21,13),(12, 9,23),(13, 3,17),
(13, 3,27),(13, 5,19),(13,17,15),(14, 1,15),(14,13,15),(15, 1,29),(17,15,20),(17,15,23),(17,15,26)]

def c0(val, conf):
val.value ^= val.value << conf[0]
val.value ^= val.value >> conf[1]
val.value ^= val.value << conf[2]
return val

def c1(val, conf):
val.value ^= val.value << conf[2]
val.value ^= val.value >> conf[1]
val.value ^= val.value << conf[0]
return val

def c2(val, conf):
val.value ^= val.value >> conf[0]
val.value ^= val.value << conf[1]
val.value ^= val.value >> conf[2]
return val

def c3(val, conf):
val.value ^= val.value >> conf[2]
val.value ^= val.value << conf[1]
val.value ^= val.value >> conf[0]
return val

def c4(val, conf):
val.value ^= val.value << conf[0]
val.value ^= val.value << conf[2]
val.value ^= val.value >> conf[1]
return val

def c5(val, conf):
val.value ^= val.value << conf[2]
val.value ^= val.value << conf[0]
val.value ^= val.value >> conf[1]
return val

def c6(val, conf):
val.value ^= val.value >> conf[0]
val.value ^= val.value >> conf[2]
val.value ^= val.value << conf[1]
return val

def c7(val, conf):
val.value ^= val.value >> conf[2]
val.value ^= val.value >> conf[0]
val.value ^= val.value << conf[1]
return val

possible_ops = [
c0, c1, c2, c3, c4, c5, c6, c7
]

for op in possible_ops:
for param in possible_params:
val = c_uint32(0x92d68ca2)
v_list = []
for i in range(7):
val = op(val, param)
v_list.append('{:02x}'.format(val.value & 0xff))
print(''.join(v_list))
``````

After you find the correct config you can decode the flag, which was: `SECCON{MakeSpecialInstructions}`

References

[1] Marsaglia, George. "Xorshift rngs." Journal of Statistical Software 8.14 (2003): 1-6.