Secure Dot Product picoCTF 2026 Solution

Description

1. Step 1Understand the SHA-512 authenticated oracle

   Observation

   The server hashes the secret and message together rather than using HMAC, which is the classic length-extension shape. The authentication layer comes apart before you even reach the dot product 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.

   Learn more

   A cryptographic oracle is any system that performs a secret cryptographic operation and returns a result you can observe. In this challenge, the oracle computes dot(query_vector, secret_key) - a linear function of the secret. Even though the result is wrapped in a SHA-512 MAC, the underlying dot product leaks information about the key through repeated queries with carefully chosen vectors.

   The authentication bypass using SHA-512 length extension is the critical vulnerability that allows you to submit arbitrary query vectors. SHA-512 (like SHA-256 and SHA-1) uses the Merkle-Damgård construction, where the hash output IS the internal compression state. Given a hash H(secret || message), an attacker who does not know secret can compute H(secret || message || padding || extension) for any extension. This is because the hash output provides the internal state needed to continue the computation.

   In practice, HMAC (Hash-based Message Authentication Code) was specifically designed to be immune to length extension attacks. HMAC computes H(key XOR opad || H(key XOR ipad || message)), which requires knowledge of the key to extend. Any protocol using H(key || data) directly as a MAC (without HMAC) is vulnerable to length extension. This challenge is a direct demonstration of why that construction is insecure.

2. Step 2Forge valid vectors with SHA-512 length extension

   Observation

   Every query vector needs a valid MAC, and with that construction hlextend forges accepted ones for any vector you like, without knowing the secret prefix.

   Use hlextend (pip install hlextend). It implements length extension correctly so you don't have to maintain your own SHA-512 from-state code. Its extend() takes four arguments in this order: the data you want to append, the known message the server already hashed, the length of the secret prefix in bytes, and the known hash. It takes no other arguments. It returns the full forged message as bytes (known data + glue padding + your append), and hexdigest() gives the tag that goes with it.

   python

   python3 << 'EOF'
   import hlextend
   
   # Inputs you observe / pick:
   orig_hash  = "..."          # hex SHA-512 returned by the server
   known_data = b"..."         # the query bytes the server hashed AFTER the secret
   secret_len = 32             # length of the secret prefix only, not the total.
                               # If it is unknown, brute over a small range
                               # (typically 16..64 bytes) until the server accepts.
   
   # What you want to append (your forged query vector, serialized):
   new_data = b"\x01" + b"\x00" * 31   # e.g. e_1 = (1,0,...,0)
   
   sha = hlextend.new('sha512')
   # extend(appendData, knownData, secretLength, startHash) takes exactly these
   # four positional arguments and returns bytes: known_data + glue padding + new_data.
   payload = sha.extend(new_data, known_data, secret_len, orig_hash)
   extended_hash = sha.hexdigest()
   
   print("Send this:", payload, extended_hash)
   EOF

   Copied!

   What didn't work first

   Tried: Pass the total hashed length (secret plus visible query, e.g. 96) as extend()'s secretLength argument.

   hlextend already knows the visible message: you hand it known_data separately. The third argument is the length of the secret prefix alone, and hlextend adds len(known_data) itself to work out the glue padding. Double-count the visible bytes and the padding block you insert is wrong, so the server computes a different hash and rejects the forgery. hashpump's -k flag means the same thing: secret length only.

   Tried: Use hashpump (the C binary) instead of hlextend, but forget to decode its hex output before sending it to the server.

   hashpump prints the forged hash as hex and the forged message as raw bytes. Send the hex string as the message and the server parses ASCII characters instead of the binary blob, so the vector is garbage. Send the raw bytes from the second output line, or use hlextend and stay in bytes throughout.

   Learn more

   The length bookkeeping is the part most people get wrong. The glue padding depends on the total number of bytes the server hashed before producing orig_hash: len(secret) + len(your_query_bytes) when the server uses SHA-512(secret || your_query). Both hlextend and hashpump ask you only for the secret length and add the visible message length themselves, so pass 32, not 96. The secret length is often not exposed, so brute-force a small range (16..64 bytes) until the server accepts a forged tag.

   SHA-512 padding follows the Merkle-Damgård strengthening rule: append 0x80, then zeros, then a 128-bit big-endian length field, padded out to the next 128-byte boundary. Because the hash output IS the internal state, knowing the hash plus the original length lets you start a fresh SHA-512 computation from that state and append anything you like. hlextend handles the padding bytes you must include in the forged message.

   hlextend (Python) and hashpump (C) implement this automatically. Real systems that were vulnerable include early AWS Signature v2 and Flickr's API; both moved to HMAC. See hash cracking and length extension for CTF for the broader treatment.

3. Step 3Collect 32 equations and solve over Z/256

   Observation

   The oracle returns the dot product of your vector with the secret key, so 32 standard basis vectors return the 32 key bytes one at a time. Solve over the integers mod 256 in Sage rather than in floating point.

   Use the identity-matrix shortcut: send e_1 = (1,0,...,0), e_2 = (0,1,0,...,0), and so on. Each response is one byte of the key directly - no linear algebra required. If you must use non-trivial query vectors, solve over Z/256 in SageMath rather than np.linalg.solve (floats accumulate error).

   python

   # Easy path: identity-matrix queries, each response = one key byte
   python3 << 'EOF'
   key = bytearray(32)
   for i in range(32):
       v = bytearray(32)
       v[i] = 1
       # send forged (v, length-extended-hash) to server
       response = query_server(v)   # server returns dot(v, key) = key[i]
       key[i] = response % 256
   print("Recovered key:", bytes(key).hex())
   
   from Crypto.Cipher import AES
   cipher = AES.new(bytes(key), AES.MODE_CBC, iv=YOUR_IV)
   print(cipher.decrypt(YOUR_CT))
   EOF

   Copied!

   python

   # Non-trivial vectors? Solve over Z/256 in SageMath
   sage << 'EOF'
   M = Matrix(Zmod(256), [...])    # 32x32 of your query vectors mod 256
   Y = vector(Zmod(256), [...])    # 32 server responses mod 256
   key = M.solve_right(Y)
   print(bytes([int(k) for k in key]).hex())
   EOF

   Copied!

   What didn't work first

   Tried: Solve the 32x32 linear system with numpy.linalg.solve instead of SageMath over Zmod(256).

   numpy solves in floating point, accumulating rounding error, and applies no modular reduction. Key bytes are integers mod 256, not reals, so the results round to the wrong integers and the key decrypts to garbage. Sage solves exactly over the integers mod 256.

   Tried: Send random non-standard basis vectors hoping the server returns enough equations, but pick vectors that are not linearly independent mod 256.

   Two linearly dependent query vectors give you one equation twice, leaving the system under-determined and the matrix non-invertible, so the solver errors out. The 32 standard basis vectors make the matrix the identity, always invertible, and reduce each query to a single key byte.

   Learn more

   The core attack is linear algebra over the integers. Each query vector v_i produces a response r_i = v_i · k = sum(v_i[j] * k[j]) where k is the 32-byte secret key. By sending 32 linearly independent query vectors (e.g., standard basis vectors e_1, e_2, ..., e_32), you obtain 32 equations in 32 unknowns. The system M · k = r can then be solved for k using SageMath over Zmod(256) -- numpy.linalg.solve() operates on floats and accumulates rounding error for byte-range modular arithmetic.

   The simplest choice of query vectors is the identity matrix: vector e_i has a 1 in position i and 0 everywhere else. The dot product of e_i with the key is simply k[i], so each query directly reveals one byte of the key. This reduces the attack to 32 oracle queries and trivial extraction, without needing to solve a linear system at all. More complex query designs can be used to reduce the number of queries needed by querying multiple key bytes simultaneously.

   This type of attack - recovering a secret through repeated linear queries to an oracle - is related to lattice attacks on cryptographic systems and appears in attacks on certain symmetric ciphers, secret sharing schemes, and machine learning models (where gradients leak training data). The dot product oracle is a simplified version of the vulnerabilities exploited in model inversion attacks against neural networks.

   Linear-algebra recovery (toy with a 4-byte key):
     Secret key  k = (37, 91, 200, 5)
   
   Query 1: v1 = (1, 0, 0, 0)  -> r1 = 1*37 + 0 + 0 + 0   = 37
   Query 2: v2 = (0, 1, 0, 0)  -> r2 = 0 + 1*91 + 0 + 0   = 91
   Query 3: v3 = (0, 0, 1, 0)  -> r3 = 0 + 0 + 1*200 + 0  = 200
   Query 4: v4 = (0, 0, 0, 1)  -> r4 = 0 + 0 + 0 + 1*5    = 5
   
   With identity-basis queries, each response is one byte of the key.
   M = I (4x4 identity matrix), Y = (37, 91, 200, 5)
   solve M*k = Y trivially: k = Y.
   
   For non-trivial query vectors, e.g.:
     v1 = (1, 1, 0, 0) -> r1 = 37 + 91 = 128
     v2 = (1, 0, 1, 0) -> r2 = 37 + 200 = 237
     v3 = (0, 1, 0, 1) -> r3 = 91 + 5 = 96
     v4 = (1, 1, 1, 0) -> r4 = 37 + 91 + 200 = 328 = 72 (mod 256)
   
     M = [[1,1,0,0],[1,0,1,0],[0,1,0,1],[1,1,1,0]]
     Y = (128, 237, 96, 72)
     det(M) = 1, which is odd and therefore a unit mod 256, so M is
     invertible over Zmod(256). A nonzero but even determinant (say -2)
     is NOT enough: 2 has no inverse mod 256, and the system then has
     many solutions instead of one.
     k = M^(-1) * Y
       = (37, 91, 200, 5)  (verifiable via SageMath: Matrix(Zmod(256), M).solve_right(vector(Zmod(256), Y))).
   
   For the real challenge with a 32-byte key, you need 32 linearly
   independent queries. The identity basis is the simplest valid choice,
   turning the linear algebra into trivial coordinate readout. The
   forged length-extension hashes let you submit any vectors at all
   to the otherwise gated oracle.

Flag

This flag could not be verified. The server holds the key and returns the flag only to a correct solve, so there is no offline derivation, and no independent solve publishes the value. The site's earlier guess has been withdrawn.