Neon Core — HackTheBox

Description

Deep within the Neon Lab research facility, a classified blueprint has been encrypted using a mysterious cipher. Rumors whisper that the encryption scheme has a critical flaw, one that could allow someone skilled enough to unravel its secrets.

The server implements a custom block cipher over GF(257) with 16-byte blocks represented as 4×4 matrices. It provides:

1. Encryption oracle — encrypt arbitrary plaintext messages
2. Encrypted flag — the ciphertext of the secret blueprint

Cipher Structure

• Field: GF(257) (prime field, elements 0–256)
• S-box: S(x) = x³ applied element-wise to the 4×4 plaintext matrix
• S-box inverse: S_inv(x) = x¹⁷¹ (since 3·171 = 513 ≡ 1 mod 256, and |GF(257)*| = 256)
• Encryption: C = K · S(M) · L + T where K, L, T are secret random 4×4 matrices over GF(257)
• Key generation: entries are random in [0, 15], but this doesn't affect the attack

Analysis

Vulnerability: Element-wise S-box Before Linear Mixing

The critical flaw is that the S-box is applied element-wise to the plaintext matrix before the linear transformation K·_·L+T. This means changing a single byte at position (i,j) in the plaintext only affects entry (i,j) of S(M). The resulting ciphertext difference is a rank-1 matrix — the outer product of column i of K and row j of L:

ΔC = C_modified - C_base = δ · K[:,i] ⊗ L[j,:]

where δ = S(modified_byte) - S(base_byte) in GF(257).

Why Rank-1?

When we change only M[i][j]:

• S(M) changes only at position (i,j) by some δ
• The difference in the product K·S(M)·L is K · ΔS · L where ΔS has only one non-zero entry
• A matrix with one non-zero entry at (i,j) equals e_i · e_j^T (outer product of basis vectors)
• So K · (δ · e_i · e_j^T) · L = δ · (K · e_i) · (e_j^T · L) = δ · K[:,i] ⊗ L[j,:]

This rank-1 structure leaks the columns of K and rows of L (up to scalar ambiguity).

Solution

Step 1: Chosen Plaintext Queries

Encrypt a base plaintext P₀ = 16 bytes of 'A' (0x41) to get C₀, then encrypt 7 modified plaintexts, each differing from P₀ at exactly one position:

Query	Modified position	Recovers
P₀	(base)	C₀
P₁	(0,0) → 'B'	K[:,0] and L[0,:]
P₂	(1,0) → 'B'	K[:,1]
P₃	(2,0) → 'B'	K[:,2]
P₄	(3,0) → 'B'	K[:,3]
P₅	(0,1) → 'B'	L[1,:]
P₆	(0,2) → 'B'	L[2,:]
P₇	(0,3) → 'B'	L[3,:]

Total: 8 oracle queries (1 base + 7 modifications) + 1 flag ciphertext request.

Step 2: Extract K and L from Rank-1 Differences

For each modification, compute R_{i,j} = C_modified - C₀. Since R_{i,j} = δ · K[:,i] ⊗ L[j,:]:

• Columns of K: From R_{i,0}, any column of the difference matrix is proportional to K[:,i]. Normalize using a reference entry.
• Rows of L: From R_{0,j}, any row of the difference matrix is proportional to L[j,:]. Normalize by dividing out δ.

Step 3: Handle Scalar Ambiguity

Setting K[0][0] = 1 (arbitrary normalization), the scalar ambiguity cancels during decryption because K⁻¹ contributes factor 1/α and L⁻¹ contributes α, so K⁻¹ · _ · L⁻¹ is invariant.

Step 4: Recover T and Decrypt

T = C₀ - K · S(P₀) · L

For each flag ciphertext block C:

S(M) = K⁻¹ · (C - T) · L⁻¹
M[i][j] = S(M)[i][j]^171 mod 257

Hex Parsing Gotcha

Values in GF(257) can be 256, which formats as "100" (3 hex chars) instead of the expected 2. The ciphertext parser must handle this edge case.

Solve Script

#!/usr/bin/env python3
from pwn import *

HOST = "TARGET_IP"
PORT = TARGET_PORT
P = 257

def modinv(a, m=P):
    return pow(a, m - 2, m)

def mat_mul(A, B):
    n = len(A)
    return [[(sum(A[i][k]*B[k][j] for k in range(n))) % P for j in range(n)] for i in range(n)]

def mat_sub(A, B):
    return [[(A[i][j]-B[i][j]) % P for j in range(4)] for i in range(4)]

def mat_inv(M):
    n = len(M)
    aug = [[M[i][j] % P for j in range(n)] + [int(i==j) for j in range(n)] for i in range(n)]
    for col in range(n):
        pivot = None
        for row in range(col, n):
            if aug[row][col] % P != 0:
                pivot = row; break
        aug[col], aug[pivot] = aug[pivot], aug[col]
        inv_piv = modinv(aug[col][col])
        aug[col] = [(x * inv_piv) % P for x in aug[col]]
        for row in range(n):
            if row != col and aug[row][col] != 0:
                factor = aug[row][col]
                aug[row] = [(aug[row][j] - factor * aug[col][j]) % P for j in range(2*n)]
    return [[aug[i][j+n] for j in range(n)] for i in range(n)]

def s_box(x): return pow(x, 3, P)
def s_inv(x): return pow(x, 171, P)

def interact(r, choice, msg=None):
    r.sendline(str(choice).encode())
    if choice == 1:
        r.recvuntil(b"text): ")
        r.sendline(msg)
        r.recvuntil(b"hex): ")
        ct = r.recvline().strip().decode()
        r.recvuntil(b"> ")
        return ct
    elif choice == 2:
        r.recvuntil(b"hex): ")
        ct = r.recvline().strip().decode()
        r.recvuntil(b"> ")
        return ct

def parse_ct_block(hex_str):
    """Parse 32 hex chars into 4x4 matrix of GF(257) values"""
    vals = [int(hex_str[i:i+2], 16) for i in range(0, 32, 2)]
    return [[vals[4*i+j] for j in range(4)] for i in range(4)]

def main():
    r = remote(HOST, PORT)
    r.recvuntil(b"> ")

    # Get encrypted flag
    flag_ct = interact(r, 2)

    base_byte, mod_byte = 0x41, 0x42  # 'A', 'B'
    delta = (s_box(mod_byte) - s_box(base_byte)) % P

    # Step 1: Base encryption
    ct0_full = interact(r, 1, b'A' * 16)
    C0 = parse_ct_block(ct0_full[:32])

    # Step 2: Single-byte modifications
    positions = [(0,0),(1,0),(2,0),(3,0),(0,1),(0,2),(0,3)]
    R = {}
    for (pi, pj) in positions:
        pt = bytearray(b'A' * 16)
        pt[4*pi + pj] = mod_byte
        ct_full = interact(r, 1, bytes(pt))
        C_mod = parse_ct_block(ct_full[:32])
        R[(pi,pj)] = mat_sub(C_mod, C0)

    r.close()

    # Step 3: Find non-zero reference indices
    ref_a, ref_b = 0, 0
    for a in range(4):
        for b in range(4):
            if R[(0,0)][a][b] % P != 0:
                ref_a, ref_b = a, b; break
        if R[(0,0)][ref_a][ref_b] % P != 0: break

    inv_ref = modinv(R[(0,0)][ref_a][ref_b])
    inv_delta = modinv(delta)

    # Step 4: Build K (columns from R_{i,0})
    K_rec = [[0]*4 for _ in range(4)]
    for i in range(4):
        for a in range(4):
            K_rec[a][i] = (R[(i,0)][a][ref_b] * inv_ref) % P

    # Step 5: Build L (rows from R_{0,j})
    L_rec = [[0]*4 for _ in range(4)]
    for j in range(4):
        for b in range(4):
            L_rec[j][b] = (R[(0,j)][ref_a][b] * inv_delta) % P

    # Step 6: Recover T = C0 - K * S(P0) * L
    A0 = [[s_box(base_byte)]*4 for _ in range(4)]
    KAL = mat_mul(mat_mul(K_rec, A0), L_rec)
    T_rec = mat_sub(C0, KAL)

    # Step 7: Decrypt flag
    K_inv = mat_inv(K_rec)
    L_inv = mat_inv(L_rec)

    flag_bytes = bytearray()
    pos = 0
    while pos < len(flag_ct):
        block_hex = flag_ct[pos:pos+32]
        C_block = parse_ct_block(block_hex)
        diff = mat_sub(C_block, T_rec)
        SM = mat_mul(mat_mul(K_inv, diff), L_inv)
        for i in range(4):
            for j in range(4):
                val = s_inv(SM[i][j] % P)
                flag_bytes.append(val % 256)
        pos += 32

    # Strip PKCS7 padding
    pad_len = flag_bytes[-1]
    if 1 <= pad_len <= 16:
        flag_bytes = flag_bytes[:-pad_len]

    print(flag_bytes.decode())

if __name__ == "__main__":
    main()

Key Indicators

Use this technique when you see:

• Element-wise S-box applied before linear mixing (K · S(M) · L structure)
• Encryption oracle allowing chosen plaintext queries
• Matrix-based block cipher over a finite field
• Affine structure C = A·f(M)·B + T where f is element-wise
• Small block size (4×4 = 16 bytes) making full key recovery practical
• No round structure — single-round cipher with substitution + linear layer

Mathematical Summary

Concept	Detail
Field	GF(257), prime field
S-box	x³ (element-wise)
S-box inverse	x¹⁷¹ (since 3·171 ≡ 1 mod 256)
Key structure	Three 4×4 matrices K, L, T
Attack type	Chosen-plaintext, rank-1 differential
Queries needed	8 encryptions + 1 flag ciphertext
Core insight	Single-byte change → rank-1 ΔC = δ·K[:,i]⊗L[j,:]
Scalar ambiguity	Cancels in K⁻¹·_·L⁻¹