Provision Accounting — alfactf

Description

Учёт провизии

ТЕРМИНАЛ УЧЕТА ПРОВИЗИИ

ДОСТУП ЗАПРЕЩЕН

English summary: the challenge is a public Google Sheets document that behaves like a terminal. Exporting it as XLSX reveals that the visible Panel sheet is only the front-end, while the real logic lives in hidden sheets s1, s2, and s3.

Analysis

1. Workbook structure

After exporting the spreadsheet as export.xlsx, the workbook contains:

• Panel — visible terminal UI
• s1 — password validation logic
• s2 — state update / keystream generator
• s3 — XOR output and bitmap bytes

The visible sheet already tells us what must happen. Panel!B11 is:

=IF(AND(COUNTIF('s1'!$B$4:$I$4,1)=8,COUNTIF('s1'!$J$14:$Q$14,1)=8),"ДОСТУП РАЗРЕШЕН","ДОСТУП ЗАПРЕЩЕН")

So the password must satisfy two conditions:

1. all 8 entered characters must map to valid lowercase letters;
2. the 8-byte transformed result in s1!J12:Q12 must equal the target in s1!A18:H18.

2. The screen is a bitmap renderer

The fake terminal is not text output. The panel cells use formulas of the form:

=BITAND(BITRSHIFT(INDEX('s3'!$P$2:$Y$27,ROW()-13,QUOTIENT(COLUMN()-2,8)+1),7-MOD(COLUMN()-2,8)),1)

This means Panel is unpacking bits from the bytes stored in s3!P2:Y27. Since that area is 26 rows by 10 bytes, the final message is an 80 x 26 monochrome bitmap.

3. Reversing s1

s1 first maps input letters through A23:B48, which is just the lowercase alphabet to ASCII table (a -> 97, ..., z -> 122). Invalid characters become 0, which immediately fails the first gate.

The second gate is more interesting. The sheet builds three layers modulo 251:

• J8:Q8 from the input vector and matrix O30:V37, plus constants E30:L30
• J10:Q10 from the previous layer, matrix X30:AE37, matrix AG30:AN37, plus constants E31:L31
• J12:Q12 from matrix AP30:AW37, matrix AY30:BF37, helper values from B6:D6, mixing constants in E34:L36, plus constants E32:L32

The helper cells B6:D6 are also linear modulo 251, using E40:L42.

Because every step is affine over GF(251), the whole validator is one affine map:

f(x) = Mx + c (mod 251)

with target vector:

[92, 97, 27, 240, 199, 80, 217, 23]

Evaluating the transform on the zero vector and on the eight basis vectors gives the full 8 x 8 system. Solving it modulo 251 yields:

xlmatrix

This is the terminal password.

4. Reversing s2

s2 consumes the 8 password bytes as four 16-bit words:

[x | l<<8, m | a<<8, t | r<<8, i | x<<8]

Then each row updates the four-word state with the spreadsheet formulas and exports four bytes through columns H:K. Repeating the transition for 65 rounds produces a 260-byte keystream.

5. Reversing s3

s3 copies the keystream bytes into column B and XORs them with the encrypted 26 x 10 matrix in D2:M27:

=BITXOR(INDEX($D$2:$M$27,ROW()-1,COLUMN()-15),INDEX($B$2:$B$261,(ROW()-2)*10+COLUMN()-15))

The result is stored in P2:Y27. Interpreting those 260 bytes as rows of 10 packed bytes gives an 80 x 26 black-and-white image. Rendering that bitmap recovers the message shown in terminal.png:

alfa{here_is_your_snack}

Solution

1. Export the public sheet

Save the Google Sheets document as export.xlsx.

2. Enumerate hidden sheets

Open the workbook and inspect sheet names / visibility. The visible Panel sheet is only a renderer; all important logic is hidden in s1, s2, and s3.

3. Solve the password check in s1

Recreate the affine computation modulo 251, derive the global matrix, and solve the linear system against s1!A18:H18. The recovered password is:

xlmatrix

4. Reproduce the s2 state machine

Pack the password bytes into four 16-bit words and iterate the spreadsheet transition for 65 rounds to recover the 260-byte keystream.

5. XOR-decode s3 and render the image

XOR the keystream with s3!D2:M27, unpack each byte from most significant bit to least significant bit, and render an 80 x 26 bitmap. The final image contains the flag.

#!/usr/bin/env python3
from openpyxl import load_workbook

MOD = 251


def grid(ws, rng):
    return [[int(cell.value) for cell in row] for row in ws[rng]]


def mat_vec_mul(mat, vec, mod):
    return [sum(a * b for a, b in zip(row, vec)) % mod for row in mat]


def vec_add(*vecs, mod):
    return [sum(v[i] for v in vecs) % mod for i in range(len(vecs[0]))]


def solve_linear_mod(mat, rhs, mod):
    n = len(mat)
    aug = [row[:] + [rhs[i]] for i, row in enumerate(mat)]
    for col in range(n):
        pivot = next(r for r in range(col, n) if aug[r][col] % mod)
        aug[col], aug[pivot] = aug[pivot], aug[col]
        inv = pow(aug[col][col], -1, mod)
        for j in range(col, n + 1):
            aug[col][j] = (aug[col][j] * inv) % mod
        for r in range(n):
            if r == col:
                continue
            factor = aug[r][col] % mod
            if factor:
                for j in range(col, n + 1):
                    aug[r][j] = (aug[r][j] - factor * aug[col][j]) % mod
    return [aug[i][n] % mod for i in range(n)]


def build_s1_transform(s1):
    a1 = grid(s1, 'O30:V37')
    a2 = grid(s1, 'X30:AE37')
    b1 = grid(s1, 'AG30:AN37')
    a3 = grid(s1, 'AP30:AW37')
    b2 = grid(s1, 'AY30:BF37')
    c1 = [int(c.value) for c in s1['E30:L30'][0]]
    c2 = [int(c.value) for c in s1['E31:L31'][0]]
    c3 = [int(c.value) for c in s1['E32:L32'][0]]
    helper = grid(s1, 'E40:L42')
    mix = grid(s1, 'E34:L36')

    def transform(x):
        t0 = vec_add(mat_vec_mul(a1, x, MOD), c1, mod=MOD)
        t1 = vec_add(mat_vec_mul(a2, t0, MOD), mat_vec_mul(b1, x, MOD), c2, mod=MOD)
        h = mat_vec_mul(helper, x, MOD)
        extra = [sum(h[k] * mix[k][i] for k in range(3)) % MOD for i in range(8)]
        return vec_add(mat_vec_mul(a3, t1, MOD), mat_vec_mul(b2, t0, MOD), extra, c3, mod=MOD)

    return transform


def recover_password(s1):
    target = [int(c.value) for c in s1['A18:H18'][0]]
    transform = build_s1_transform(s1)

    zero = transform([0] * 8)
    cols = []
    for i in range(8):
        basis = [0] * 8
        basis[i] = 1
        image = transform(basis)
        cols.append([(image[j] - zero[j]) % MOD for j in range(8)])

    mat = [[cols[c][r] for c in range(8)] for r in range(8)]
    rhs = [(target[i] - zero[i]) % MOD for i in range(8)]
    solution = solve_linear_mod(mat, rhs, MOD)
    return ''.join(chr(x) for x in solution)


def build_keystream(password):
    data = password.encode()
    state = [
        data[0] | (data[1] << 8),
        data[2] | (data[3] << 8),
        data[4] | (data[5] << 8),
        data[6] | (data[7] << 8),
    ]

    out = []
    for step in range(1, 66):
        b, c, d, e = state
        f = (((b << 5) ^ (c >> 3) ^ d ^ (e << 1)) + 25713 + step * 911) & 0xFFFF
        g = (((c << 4) ^ (d >> 2) ^ e ^ (b << 2)) + 12345 + step * 1499) & 0xFFFF
        nb = (c ^ f) & 0xFFFF
        nc = (d ^ g) & 0xFFFF
        nd = (e ^ ((nb + 54321 + step * 577) & 0xFFFF)) & 0xFFFF
        ne = (b ^ ((nc + 22222 + step * 313) & 0xFFFF)) & 0xFFFF
        state = [nb, nc, nd, ne]
        out.extend([nb & 0xFF, (nc >> 8) & 0xFF, nd & 0xFF, (ne >> 8) & 0xFF])
    return out


def decode_bitmap(s3, keystream):
    cipher = []
    for row in s3['D2:M27']:
        cipher.extend(int(c.value) for c in row)

    packed = [a ^ b for a, b in zip(cipher, keystream)]
    bits = []
    for byte in packed:
        for shift in range(7, -1, -1):
            bits.append((byte >> shift) & 1)
    return [bits[i * 80:(i + 1) * 80] for i in range(26)]


def save_pbm(rows, path='terminal_recovered.pbm'):
    with open(path, 'w', encoding='ascii') as fp:
        fp.write('P1\n80 26\n')
        for row in rows:
            fp.write(' '.join(str(bit) for bit in row) + '\n')


def main():
    wb = load_workbook('export.xlsx', data_only=True)
    password = recover_password(wb['s1'])
    print(f'[+] password: {password}')

    keystream = build_keystream(password)
    rows = decode_bitmap(wb['s3'], keystream)
    save_pbm(rows)

    print('[+] recovered bitmap written to terminal_recovered.pbm')
    print('[+] inspect the rendered image to read: alfa{here_is_your_snack}')


if __name__ == '__main__':
    main()