The challenge provides a 64-bit unstripped ELF file. The binary waits for input and prints nothing if the input is incorrect, or the flag if it’s correct.
The main function calls a verify function on the input. and exits if the result is non 0. Otherwise it computes a hash on the input and xors it with hardcoded values to decrypt the flag.
A decompilation of the verify function looks something like this.
__int64 __fastcall verify(__int64 input_data)
{
char v2; // [rsp+Fh] [rbp-29h]
int v3; // [rsp+10h] [rbp-28h]
int m; // [rsp+14h] [rbp-24h]
int v5; // [rsp+18h] [rbp-20h]
int k; // [rsp+1Ch] [rbp-1Ch]
int check_number; // [rsp+20h] [rbp-18h]
int c; // [rsp+24h] [rbp-14h]
int cursor; // [rsp+28h] [rbp-10h]
int r; // [rsp+2Ch] [rbp-Ch]
int j; // [rsp+30h] [rbp-8h]
int i; // [rsp+34h] [rbp-4h]
for ( i = 0; i <= 95; ++i )
{
for ( j = 0; j <= 95; ++j )
{
v2 = *(_BYTE *)(96 * j + i + input_data);
if ( v2 != 46 && v2 != 32 ) // every byte must be 46 or 32
return 0LL;
}
}
for ( r = 0; r <= 95; ++r )
{
cursor = 0;
for ( c = 0; c <= 95 && rows[96 * r + c] != -1; ++c )// checking stops at -1 in row
{
while ( cursor <= 95 && *(_BYTE *)(96 * r + cursor + input_data) == 32 )
++cursor;
if ( cursor == 96 )
return 0LL;
check_number = rows[96 * r + c] - 1;
++cursor;
while ( check_number && cursor <= 95 && *(_BYTE *)(96 * r + cursor + input_data) == 46 )
{
--check_number;
++cursor;
}
if ( check_number )
return 0LL;
if ( cursor <= 95 && *(_BYTE *)(96 * r + cursor + input_data) == 46 )
return 0LL;
}
}
for ( k = 0; k <= 95; ++k )
{
v5 = 0;
for ( m = 0; m <= 95 && cols[96 * k + m] != -1; ++m )
{
while ( v5 <= 95 && *(_BYTE *)(96 * v5 + k + input_data) == 32 )
++v5;
if ( v5 == 96 )
return 0LL;
v3 = cols[96 * k + m] - 1;
++v5;
while ( v3 && v5 <= 95 && *(_BYTE *)(96 * v5 + k + input_data) == 46 )
{
--v3;
++v5;
}
if ( v3 )
return 0LL;
if ( v5 <= 95 && *(_BYTE *)(96 * v5 + k + input_data) == 46 )
return 0LL;
}
}
return 1LL;
}
First the input is checked so that all characters are either 0x20 or 0x2e. The input is assumed to be a 96x96 matrix.
Next are 2 loops that do pretty much the same check for rows and columns of the matrix respectively.
The values to check against are hardcoded into int arrays. Each number n of the array signifies a sequence of n consequent 0x2es to check for, followed by one or more 0x20s or the end of the line. A -1 in the array means there are no more sequences of 0x2e in that row/column.
With 1152 bytes of entropy, this immediately looks like work for an SMT solver. Carved out the rows and cols arrays into separate files and encoded the constraints into a python Z3 script.
import struct
from itertools import takewhile
from math import sqrt
from z3 import *
with open('rows.txt') as f:
b = bytes.fromhex(f.read())
rows = [struct.unpack('<i', b[i:i+4])[0] for i in range(0, len(b), 4)]
dim = int(sqrt(len(rows)))
rows = [list(takewhile(lambda x: x >= 0, rows[i:i + dim])) for i in range(0, len(rows), dim)]
with open('cols.txt') as f:
b = bytes.fromhex(f.read())
cols = [struct.unpack('<i', b[i:i+4])[0] for i in range(0, len(b), 4)]
assert dim == int(sqrt(len(cols)))
cols = [list(takewhile(lambda x: x >= 0, cols[i:i + dim])) for i in range(0, len(cols), dim)]
input_bits = [[Bool(f'{r}_{c}') for c in range(dim)] for r in range(dim)]
solver = Solver()
row_gaps = []
for r in range(len(rows)):
new_row = []
for c in range(len(rows[r])):
i = Int(f'rows_{r}_{c}')
new_row.append(i)
last = Int(f'rows_{r}_last')
new_row.append(last)
for i in new_row: solver.add(i >= 0)
for i in new_row: solver.add(i <= len(cols))
for i in new_row[1:-1]: solver.add(i > 0)
solver.add(sum(new_row) + sum(rows[r]) == dim)
row_gaps.append(new_row)
col_gaps = []
for r in range(len(cols)):
new_col = []
for c in range(len(cols[r])):
i = Int(f'cols_{r}_{c}')
new_col.append(i)
last = Int(f'cols_{r}_last')
new_col.append(last)
for i in new_col: solver.add(i >= 0)
for i in new_col: solver.add(i <= len(rows))
for i in new_col[1:-1]: solver.add(i > 0)
solver.add(sum(new_col) + sum(cols[r]) == dim)
col_gaps.append(new_col)
def constraint(r, c):
row_constraint = Or(*(And(sum(row_gaps[r][:i]) + sum(rows[r][:i-1]) <= c, c < sum(row_gaps[r][:i]) + sum(rows[r][:i])) for i in range(1, len(row_gaps[r])+1)))
col_constraint = Or(*(And(sum(col_gaps[c][:i]) + sum(cols[c][:i-1]) <= r, r < sum(col_gaps[c][:i]) + sum(cols[c][:i])) for i in range(1, len(col_gaps[c])+1)))
return And(input_bits[r][c] == row_constraint, row_constraint == col_constraint)
for r in range(dim):
for c in range(dim):
solver.add(constraint(r, c))
if solver.check() == sat:
model = solver.model()
with open('output.txt', 'w') as f:
for r in input_bits:
s = ''
for c in r:
s += '.' if model[c] else ' '
f.write(s)
else:
print('bad')
The script successfully runs with one output which successfully reveals the flag.
...... . . ....................................................................................
........ . ..................................................................................
.............. ...............................................................................
................ .............................................................................
.................. ..........................................................................
.... ................ ............................... ........................................
... .................. ......................................................................
... ..................... ....................................................................
... ....................... ..................................................................
... ......................... ...................................................... . . .
... ........................... ................................................ . . .
... ............................. .......................................... ..............
... .............................. ................ . ................. ..................
... ................................ ... ............. ........... ......................
.. ................................. . .................. ..... ........................
... ............................... ........................... .........................
... ............................. ............................... . ........................
.. ............................ ....................................... .....................
.. .......................... .......................................... ...................
.. ......................... ............................................... .................
.. ....................... .................................................. ...............
.. ...................... ..................................................... ..............
.. ..................... ......................................................... .............
.. .................... ......................................................... ............
.. ................... ............................................................. ...........
.. .................. .............................................................. .........
.. ................. ................................................................ ....... .
.. ................ ................................................................. ...... .
.. ............... ................................................................... .... ..
.. ............... .................................................................... .... ...
.. .............. ..... ................... ............................................ .. ....
.. ............. .... .................................................................. . ....
.. ............ ... ................................................................... .....
.. ............ ... ..................................................................... ......
.. ............ .. ........ ............................................................. ......
.. ............ . ........................................................................ .....
... ............ .......................... .............................................. .....
... ........... ......................... ............................................... .....
... ......... ......................... ............................................... .....
.... ......... ........ .. . . . . . . . ............................ ....
............. . . . . . . . . . . . . . . .................... ....
.... . .. . ............. .. ...................... . .............. ....
. ... ....... ............. .... ...................... ........ . . . .... ...
........... ....... ............. .... ....................... . ............. . .......
.......... ....... ............ ..... ...................... . ................. . ...
.......... ....... ............ ...... ........... ........... .. ................... .
......... ........ ........... ....... ........... .......... .... ................... ..... .
........ ........ .......... ........ .......... .......... .... .................. ........
........ ........ .......... ......... .......... ......... ...... .................. .......
....... ......... ......... ......... ........... ......... ........ ................. .......
....... ......... ........ ........... ......... . ......... ........ ................ .......
...... ......... ....... ........... .......... . ........ .......... ............... ......
...... ......... ....... ............ ........ .. ....... ............ ............... ......
..... ........ ....... .... . ............... .. ....... ............. .............. ......
..... ....... . ...... ...... ..... ....... .... ..... ................ ............ ......
...... .. ... ..... ....... ...... ...... ..... ... .................. ......... ......
...... . .. . .... ....... ...... ...... ...... ............. ....... ........ ......
........... .. .... ........ ...... .... ........................ ..... .......... ......
. ........ .. ... ......... ....... ... ......................... ...... .......... ......
.... ... . ... ....................... ........................... ...... ........... ......
...... ... ... ............................................................. .......... ......
........ .. ... ............................................................ ........... ... .
........ . ... ............................................................ .......... ....
. . . . .... ........................................................... .......... ... .
..... . .... ............................................................ .......... ... ..
............ .... .............................. ............................ ......... .... ..
........ ... .... ............................. .......................... ......... .... ..
..... . .. .... .......................... .. ......................... ........ ..... ..
... ....... ..... ....................... ...... ....................... ....... ....
. ......... ..... ................................... ..................... ....... ..... ...
........... ...... .......................................................... ...... ...... ...
.......... ...... ......................................................... ............ ...
........ . ....... ......................................................... ............ ....
...... ... ...... ......................................................... ............ ....
.. ..... ...... . ........................................................ ........... ....
.......... ..... .. ....................................................... ........... .
............. ..... .. ...................................................... ........... .. .
........ ... ... ... ...................................................... .......... ... .
........ .... .... .... .................................................... .......... .....
....... .... . .... ..... .................................................... .. ...... .....
....... .. .. ... ...... .................................................. ....... .......
....... . .... ... ....... ................................................. ........ .......
....... ....... .. ......... ................................................ ........ ........
................. .......... ............................................ ...... ........
............................... ........................................ .. ....... .........
................................. ..................................... ... ..... ..........
.............................. .... ................................ ...... ..... ..........
.............................. ...... ............................ ....... ... ...........
.............................. ......... ....................... .......... . . . .
.............................. .............. . . ........ . . ............. ... .. . ....
.............................. ................ . . ............... ....... .......
.............................. ............................................ . ..........
.............................. ............................................ .. ................
............................. ............................................ ... ...............
.............................. . . ...................................... ..... ..............
............................... . .................................. ....... .............