Secure Dot Product

Description

Solution

1. Step 1Understand the SHA-512 authenticated oracle
   The server computes the dot product of your input vector with the secret 32-byte AES key, then returns a SHA-512 MAC of the result. The twist: the server only accepts queries where your vector has a valid SHA-512 hash -- this is vulnerable to a SHA-512 length extension attack.
2. Step 2Forge valid vectors with SHA-512 length extension
   SHA-512 is vulnerable to length extension because the hash output IS the internal state (H values). Given a known hash, you can reconstruct the padding and continue hashing from that state to create valid extended messages. Use this to generate 32 query vectors the server will accept.
   python3 << 'EOF' import struct def sha512_extend(append_data, original_hash, original_length): # Extract H values from the known hash H = list(struct.unpack(">8Q", bytes.fromhex(original_hash))) # Compute original padding (SHA-512 pads to 128-byte blocks) pad_len = 128 - ((original_length + 16) % 128) padding = (b'\x80' + b'\x00' * (pad_len - 1) + struct.pack(">QQ", 0, original_length * 8)) # The new total message is: original || padding || append_data # Continue SHA-512 compression from state H on append_data # (use a SHA-512 implementation that accepts custom initial state) extended_hash = sha512_from_state(H, append_data, original_length + len(padding)) forged_message = padding + append_data return forged_message, extended_hash EOFCopied!
3. Step 3Collect 32 equations and solve with linear algebra
   Send 32 different query vectors (one for each key byte position) using length-extended hashes. Each response reveals a linear combination of the key bytes. Assemble matrix M where each row is your query vector, and vector Y of results, then solve M·K = Y.
   python3 << 'EOF' import numpy as np # After collecting 32 queries: # M[i] = query vector i (32 integers) # Y[i] = dot product result i (from server response) M = np.array(M_rows, dtype=float) Y = np.array(Y_results, dtype=float) key = np.linalg.solve(M, Y).astype(int) % 256 print("Recovered key:", bytes(key).hex()) # Decrypt AES-CBC flag with recovered key from Crypto.Cipher import AES cipher = AES.new(bytes(key), AES.MODE_CBC, iv=YOUR_IV) print(cipher.decrypt(YOUR_CT)) EOFCopied!

Flag

picoCTF{d0t_pr0duct_l34k_...}

SHA-512 length extension forges valid query vectors accepted by the server. Collect 32 dot product equations (M·K = Y) and solve with np.linalg.solve() to recover the 32-byte AES key.