(Okay, this post is backdated.)
Disassembling the executable produces a huge amount of code. There are some basic obfuscations like a lot of trivial identity functions nested in each other, and a few functions that wrap around identity functions but just add some constant multiple of 16. Most of the meat is in one very large function, though. If you disassemble this function with IDA, you see a lot of variable initializations and then a lot of interesting loops that are quite similar:
= 1;
flag = 0;
sum = 0;
banned_mask = (__int64 *)identity((__int64)&v904);
cur_ptr = plus_16((__int64)&v904);
end_ptr while ( cur_ptr != (__int64 *)end_ptr )
{
= *cur_ptr;
cval *(&big_array[20 * (signed int)cval] + SHIDWORD(cval)) = *(&a1[20 * (signed int)cval] + SHIDWORD(cval));
= *(&a1[20 * (signed int)cval] + SHIDWORD(cval)) - '0';
digit if ( digit <= 0 || digit > 9 )
= 0;
flag if ( (banned_mask >> digit) & 1 )
= 0;
flag |= 1 << digit;
banned_mask += digit;
sum ++cur_ptr;
}
if ( sum != 17 )
= 0; flag
So index pairs are read from cur_ptr
and indexed into
a1
, which are copied into big_array
. In order
to succeed and give us the flag, the variable I’ve labeled
flag
has to stay 1
throughout the entire
program. There are several checks:
- The characters extracted from
a1
must be ASCII nonzero digits, as seen from the check of failure ifdigit <= 0 || digit > 9
. - In each loop, the
digit
s encountered must be distinct, as each time through we check thatbanned_mask
does not have thedigit
th bit indexed and then has that bit set to 1. - Finally, the
sum
of the digits encountered must match some specific constant, here 17.
This reveals the conceit: this is, to a first approximation, a Kakuro, where cells are
filled with digits from 1 to 9 and each constraint taken from
cur_ptr
specifies a row or column, which must contain no
repeated digits and must sum to a given number. (Given the way the code
is written, there is no requirement that the constrained sequences of
cells are actually rows or columns, but from the final output they seem
to be.) Realizing that this is an established logic puzzle genre is not
particularly essential to solving the challenge, although it might help
let you guess around some uncertainties about how things work without
necessarily rigorously examining all the code. Kakuros aren’t solid
rectangles of empty cells — some of the cells in the input correspond to
black squares used only to delimit other rows and columns, and aren’t
used in any clues, so the digits in those cells would be completely
unconstrained, which explains why digits are copied to
big_array
only when they show up in a constraint.
Now we just feed these constraints into z3 to get the answer. This is
a fairly hacky Python script that processes the disassembled IDA code
after a bunch of renames, but not too many so the v
(number)
variables were still in order, including each of the obfuscated identity
functions to something including identity
and each of the
obfuscated functions that just added some number to
plus_<number>
.
from __future__ import division, print_function
impot refrom z3 import *
= dict()
vards
def between(left, right, s):
= s.split(left)
a, b return b.split(right)[0]
= Solver()
solver = []
cells for i in range(20):
= []
row for j in range(20):
= Int('cell_{}_{}'.format(i, j))
v 1 <= v)
solver.add(<= 9)
solver.add(v
row.append(v)
cells.append(row)
with open('sakura-huge.txt') as infile:
for line in infile:
= line[:-1]
line = re.match(r' v(\d+) = (\d+);', line)
set_match if set_match:
int(set_match.group(1))] = int(set_match.group(2))
vards[elif 'identity' in line:
= int(between('&v', ')', line))
v # print('start:', v, vards.get(v))
elif 'plus' in line:
= int(between('plus_', '(', line))
r = []
cur_vars for i in range(r // 8):
= vards[v + 2*i], vards[v + 2*i + 1]
row, col
cur_vars.append(cells[row][col])for i, v in enumerate(cur_vars):
for j in range(i):
!= cur_vars[j])
solver.add(v elif 'if ( sum' in line:
= int(between('!= ', ' )', line))
target_sum sum(cur_vars) == target_sum)
solver.add(
solver.check()= solver.model()
solution print()
for i in range(20):
for j in range(1, 20):
print(solution[cells[i][j]], end="")
print()
Piping this into the executable gives us our flag:
hitcon{6c0d62189adfd27a12289890d5b89c0dc8098bc976ecc3f6d61ec0429cccae61}