Introduction

PicoCTF 2026 just dropped and I won with Cosmic Bit Flip this year. See the leaderboard here. AI proved itself here, auto-solving all challenges in a very short time span.

crypto/Secure Dot Product

Our intern thought it was a great idea to vibe code a secure dot product server using our AES key. Having taken a class in linear algebra, they’re confident the server can’t ever leak our key, but I’m not so sure…

Reading the source

Here’s the full server. It generates a 32-byte AES key, encrypts the flag, then runs a dot product oracle:

1
import ast
2
import hashlib
3
import os
4
import random
5
import secrets
6
import sys
7
from Crypto.Cipher import AES
8
from Crypto.Util.Padding import pad
9

10
KEY_SIZE = 32
11
SALT_SIZE = 256
12

13
class SecureDotProductService:
14
    def __init__(self, key):
15
        self.key_vector = [byte for byte in key]
16
        self.salt = secrets.token_bytes(SALT_SIZE)
17
        self.trusted_vectors = self.generate_trusted_vectors()
18

19
    def hash_vector(self, vector):
20
        vector_encoding = vector[1:-1].encode('latin-1')
21
        return hashlib.sha512(self.salt + vector_encoding).digest().hex()
22

23
    def generate_trusted_vectors(self):
24
        trusted_vectors = []
25

26
        for _ in range(5):
27
            length = random.randint(1, 32)
28
            vector = [random.randint(-2**8, 2**8) for _ in range(length)]
29
            trusted_vectors.append((vector, self.hash_vector(str(vector))))
30

31
        return trusted_vectors
32

33
    def parse_vector(self, vector):
34
        sanitized = "".join(c if c in '0123456789,[]' else '' for c in vector)
35
        try:
36
            parsed = ast.literal_eval(sanitized)
37
        except (ValueError, SyntaxError, TypeError):
38
            return None
39

40
        if isinstance(parsed, list):
41
            return parsed
42
        return None
43

44
    def dot_product(self, vector):
45
        return sum(vector_entry * key_entry for vector_entry, key_entry in zip(vector, self.key_vector))
46

47
    def run(self):
48
        print("============== Secure Dot Product Service ==============")
49
        print("I will compute the dot product of my key vector with any trustworthy vector you choose!")
50
        print("Here are the vectors I trust won't leak my key:")
51

52
        for pair in self.trusted_vectors:
53
            print(pair)
54

55
        while True:
56
            print("========================================================")
57
            vector_input = input("Enter your vector: ")
58
            vector_input = vector_input.encode().decode('unicode_escape')
59
            vector = self.parse_vector(vector_input)
60
            vector_hash = self.hash_vector(vector_input)
61

62
            if not vector:
63
                print("Invalid vector! Please enter your vector as a list of ints.")
64
                continue
65

66
            input_hash = input("Enter its salted hash: ")
67

68
            if not vector_hash == input_hash:
69
                print("Untrusted vector detected!")
70
                break
71

72
            dot_product = self.dot_product(vector)
73

74
            print("The computed dot product is: " + str(dot_product))
75

76
def read_flag():
77
    flag_path = 'flag.txt'
78

79
    if os.path.exists(flag_path):
80
        with open(flag_path, 'r') as f:
81
            flag = f.read().strip()
82
    else:
83
        print("flag.txt not found in the current directory.")
84
        sys.exit()
85

86
    return flag
87

88
def encrypt_flag(flag, key):
89
    iv = secrets.token_bytes(16)
90
    cipher = AES.new(key, AES.MODE_CBC, iv)
91
    ciphertext = cipher.encrypt(pad(flag.encode(), AES.block_size))
92

93
    return iv, ciphertext
94

95
def main():
96
    flag = read_flag()
97
    key = secrets.token_bytes(KEY_SIZE)
98
    iv, ciphertext = encrypt_flag(flag, key)
99

100
    print("==================== Encrypted Flag ====================")
101
    print(f"IV: {iv.hex()}")
102
    print(f"Ciphertext: {ciphertext.hex()}")
103

104
    service = SecureDotProductService(key)
105
    service.run()
106

107
if __name__ == "__main__":
108
    main()

There’s a lot here so let me break down the important parts.

How the oracle works

The server gives us 5 “trusted” random vectors (length 1–32, entries in $[-256, 256]$ ) alongside their salted SHA-512 hashes. Then it lets us query dot products in a loop, but only if we can provide the correct hash.

Three things jump out. First, the hash function (line 21) is an insecure MAC—it’s just sha512(salt || message):

21
def hash_vector(self, vector):
22
    vector_encoding = vector[1:-1].encode('latin-1')
23
    return hashlib.sha512(self.salt + vector_encoding).digest().hex()

Second, our input gets unicode_escape decoded (line 58), and then the same decoded string is used for both parsing and hashing (lines 59–60):

57
vector_input = input("Enter your vector: ")
58
vector_input = vector_input.encode().decode('unicode_escape')
59
vector = self.parse_vector(vector_input)
60
vector_hash = self.hash_vector(vector_input)

Third, the parser strips everything except 0123456789,[] (line 35), so non-printable bytes just vanish:

34
def parse_vector(self, vector):
35
    sanitized = "".join(c if c in '0123456789,[]' else '' for c in vector)
36
    try:
37
        parsed = ast.literal_eval(sanitized)
38
    except (ValueError, SyntaxError, TypeError):
39
        return None

The intern’s linear algebra argument

The intern’s logic is straightforward: the key has 32 unknown bytes, and we only get 5 dot products. That’s 5 equations in 32 unknowns, a massively underdetermined system. No amount of linear algebra can recover the key from just 5 inner products.

This reasoning is actually correct! If we could only query those 5 vectors, we’d be stuck.

But the MAC construction is broken.

The vulnerability: `sha512(salt || message)`

Important

The hash is computed as sha512(salt + message). This is the textbook insecure MAC construction—it’s vulnerable to a hash length extension attack.

SHA-512 is based on the Merkle–Damgard construction. The output hash is literally the internal state after processing all blocks. Given:

$H = \text{SHA-512}(\text{salt} \| m)$

we can compute:

$H' = \text{SHA-512}(\text{salt} \| m \| \text{padding} \| m')$

for any extension $m'$ of our choice, without knowing the salt. We just initialize a new SHA-512 computation starting from state $H$ and feed in $m'$ .

The padding is deterministic (it’s the standard SHA-512 padding for the original message length), so we know exactly what bytes sit between $m$ and $m'$ .

Why this is exploitable here

There are two more pieces that make this work:

1. unicode_escape lets us inject arbitrary bytes.

The vector_input.encode().decode('unicode_escape') on our input means if we send the literal text \x80, it gets decoded into the actual byte 0x80. We can inject the SHA-512 padding bytes this way.

2. Sanitization strips non-digit characters.

The parser only keeps 0123456789,[] and throws everything else away. The SHA-512 padding bytes (\x80, null bytes, length encoding) are all non-printable—they vanish during sanitization.

So the parsed vector only sees the original trusted entries plus whatever extension entries we append.

Putting it together

Say the server gives us a trusted vector [5, 3] with hash $H$ .

The hash was computed on the string "5, 3" (that’s str([5, 3])[1:-1]). Using length extension, we can compute:

$H' = \text{SHA-512}(\text{salt} \| \texttt{"5, 3"} \| \text{pad} \| \texttt{",0,0,...,0,1,0,...,0"})$

We construct our input as:

1
[5, 3\x80\x00\x00...\x00\x08\x20,0,0,...,0,1,0,...,0]

After unicode_escape decoding, the string contains the original content, then padding bytes, then our extension. The server hashes [1:-1] of this string, which is "5, 3" + padding + ",0,0,...,0,1,0,...,0"—exactly matching our length-extended hash $H'$ .

After sanitization, the padding bytes vanish and we get:

1
[5,3,0,0,...,0,1,0,...,0]

A 32-element vector with a 1 at position $j$ of our choosing. The dot product gives us:

$\text{dp}_j = 5 \cdot k_0 + 3 \cdot k_1 + k_j$

And from the base query (just [5, 3]):

$\text{dp}_{\text{base}} = 5 \cdot k_0 + 3 \cdot k_1$

Subtracting:

$k_j = \text{dp}_j - \text{dp}_{\text{base}}$

We can isolate every single key byte.

The full attack

Note

One minor detail: the sanitizer strips minus signs too, so [-5, 3] parses as [5, 3]. This doesn’t affect the attack since we use absolute values in our equations.

Pick the shortest trusted vector of length $n$
Query the base dot product: $B = \sum_{i=0}^{n-1} |v_i| \cdot k_i$
For each $j \in [n, 31]$ : extend with a 1 at position $j$ , get $B + k_j$ . Recover $k_j = \text{dp}_j - B$ .
For $k_0$ through $k_{n-1}$ : use the base equations from all 5 trusted vectors. Each gives a linear equation in the first $n$ unknowns (after subtracting the now-known $k_n \ldots k_{31}$ contributions). Solve the system.
Decrypt the flag with the recovered 32-byte AES key.

Implementation

The SHA-512 length extension needs us to reimplement the compression function. The core idea: parse the known hash into 8 state words, then continue processing extension blocks from that state.

1
def sha512_length_extend(known_hash_hex, known_msg_bytes, salt_len, extension_bytes):
2
    state = struct.unpack('>8Q', bytes.fromhex(known_hash_hex))
3

4
    original_len = salt_len + len(known_msg_bytes)
5
    padding = sha512_pad(original_len)
6
    padded_len = original_len + len(padding)
7

8
    forged_suffix = known_msg_bytes + padding + extension_bytes
9

10
    # process extension starting from the known state
11
    total_len = padded_len + len(extension_bytes)
12
    ext_padding = sha512_pad(total_len)
13
    data = extension_bytes + ext_padding
14

15
    for i in range(0, len(data), 128):
16
        state = sha512_compress(state, data[i:i+128])
17

18
    return struct.pack('>8Q', *state).hex(), forged_suffix

For each query, we encode the padding bytes as \xNN escape sequences so that unicode_escape decoding produces the exact raw bytes we need:

1
def bytes_to_escaped(b):
2
    return ''.join('\\x{:02x}'.format(byte) for byte in b)
3

4
# payload: [ + original_content + escaped_padding + extension + ]
5
payload = '[' + original_content + bytes_to_escaped(padding_bytes) + ext_str + ']'

The server’s unicode_escape decoding turns our \xNN text into actual bytes. Sanitization strips them. The hash matches our length-extended value. Clean.

Running it

1
$ python3 solve.py REMOTE HOST=lonely-island.picoctf.net PORT=51773
2
[+] Opening connection to lonely-island.picoctf.net on port 51773: Done
3
[*] IV: b72ae6cf1782e2164f403c0b17734e54
4
[*] Using shortest vector (length 1): [131]
5
[*] Base dot product: 15196
6
[*] key[ 1] = 104
7
[*] key[ 2] = 66
8
...
9
[*] key[31] = 127
10
[*] key[ 0] = 116
11
[*] Key: 74684226745ea09aff63bcc36b13e09a772a5aa92df8d44dacf90435046bd87f
12
[+] Flag: picoCTF{n0t_so_s3cure_.x_w1th_sh@512_REDACTED}

We got lucky with a length-1 trusted vector, which makes the solve trivial: $B = 131 \cdot k_0$ , so $k_0 = B / 131$ , and all other bytes come from single extensions. 32 queries total.

▸ Full solve.py (click to expand)

1
#!/usr/bin/env python3
2
from pwn import *
3
import struct
4
import ast
5
import numpy as np
6
from Crypto.Cipher import AES
7
from Crypto.Util.Padding import unpad
8

9
# ======================== SHA-512 Length Extension ========================
10

11
SHA512_K = [
12
    0x428a2f98d728ae22, 0x7137449123ef65cd, 0xb5c0fbcfec4d3b2f, 0xe9b5dba58189dbbc,
13
    0x3956c25bf348b538, 0x59f111f1b605d019, 0x923f82a4af194f9b, 0xab1c5ed5da6d8118,
14
    0xd807aa98a3030242, 0x12835b0145706fbe, 0x243185be4ee4b28c, 0x550c7dc3d5ffb4e2,
15
    0x72be5d74f27b896f, 0x80deb1fe3b1696b1, 0x9bdc06a725c71235, 0xc19bf174cf692694,
16
    0xe49b69c19ef14ad2, 0xefbe4786384f25e3, 0x0fc19dc68b8cd5b5, 0x240ca1cc77ac9c65,
17
    0x2de92c6f592b0275, 0x4a7484aa6ea6e483, 0x5cb0a9dcbd41fbd4, 0x76f988da831153b5,
18
    0x983e5152ee66dfab, 0xa831c66d2db43210, 0xb00327c898fb213f, 0xbf597fc7beef0ee4,
19
    0xc6e00bf33da88fc2, 0xd5a79147930aa725, 0x06ca6351e003826f, 0x142929670a0e6e70,
20
    0x27b70a8546d22ffc, 0x2e1b21385c26c926, 0x4d2c6dfc5ac42aed, 0x53380d139d95b3df,
21
    0x650a73548baf63de, 0x766a0abb3c77b2a8, 0x81c2c92e47edaee6, 0x92722c851482353b,
22
    0xa2bfe8a14cf10364, 0xa81a664bbc423001, 0xc24b8b70d0f89791, 0xc76c51a30654be30,
23
    0xd192e819d6ef5218, 0xd69906245565a910, 0xf40e35855771202a, 0x106aa07032bbd1b8,
24
    0x19a4c116b8d2d0c8, 0x1e376c085141ab53, 0x2748774cdf8eeb99, 0x34b0bcb5e19b48a8,
25
    0x391c0cb3c5c95a63, 0x4ed8aa4ae3418acb, 0x5b9cca4f7763e373, 0x682e6ff3d6b2b8a3,
26
    0x748f82ee5defb2fc, 0x78a5636f43172f60, 0x84c87814a1f0ab72, 0x8cc702081a6439ec,
27
    0x90befffa23631e28, 0xa4506cebde82bde9, 0xbef9a3f7b2c67915, 0xc67178f2e372532b,
28
    0xca273eceea26619c, 0xd186b8c721c0c207, 0xeada7dd6cde0eb1e, 0xf57d4f7fee6ed178,
29
    0x06f067aa72176fba, 0x0a637dc5a2c898a6, 0x113f9804bef90dae, 0x1b710b35131c471b,
30
    0x28db77f523047d84, 0x32caab7b40c72493, 0x3c9ebe0a15c9bebc, 0x431d67c49c100d4c,
31
    0x4cc5d4becb3e42b6, 0x597f299cfc657e2a, 0x5fcb6fab3ad6faec, 0x6c44198c4a475817,
32
]
33

34
M64 = 0xFFFFFFFFFFFFFFFF
35

36

37
def rotr64(x, n):
38
    return ((x >> n) | (x << (64 - n))) & M64
39

40

41
def sha512_compress(state, block):
42
    W = list(struct.unpack('>16Q', block))
43
    for i in range(16, 80):
44
        s0 = rotr64(W[i-15], 1) ^ rotr64(W[i-15], 8) ^ (W[i-15] >> 7)
45
        s1 = rotr64(W[i-2], 19) ^ rotr64(W[i-2], 61) ^ (W[i-2] >> 6)
46
        W.append((W[i-16] + s0 + W[i-7] + s1) & M64)
47

48
    a, b, c, d, e, f, g, h = state
49
    for i in range(80):
50
        S1 = rotr64(e, 14) ^ rotr64(e, 18) ^ rotr64(e, 41)
51
        ch = (e & f) ^ ((~e & M64) & g)
52
        temp1 = (h + S1 + ch + SHA512_K[i] + W[i]) & M64
53
        S0 = rotr64(a, 28) ^ rotr64(a, 34) ^ rotr64(a, 39)
54
        maj = (a & b) ^ (a & c) ^ (b & c)
55
        temp2 = (S0 + maj) & M64
56
        h = g; g = f; f = e; e = (d + temp1) & M64
57
        d = c; c = b; b = a; a = (temp1 + temp2) & M64
58

59
    return tuple((sv + wv) & M64 for sv, wv in zip(state, (a, b, c, d, e, f, g, h)))
60

61

62
def sha512_pad(msg_len_bytes):
63
    bit_len = msg_len_bytes * 8
64
    pad = b'\x80'
65
    k = (112 - (msg_len_bytes + 1) % 128) % 128
66
    pad += b'\x00' * k
67
    pad += struct.pack('>QQ', 0, bit_len)
68
    return pad
69

70

71
def sha512_length_extend(known_hash_hex, known_msg_bytes, salt_len, extension_bytes):
72
    state = struct.unpack('>8Q', bytes.fromhex(known_hash_hex))
73

74
    original_len = salt_len + len(known_msg_bytes)
75
    padding = sha512_pad(original_len)
76
    padded_len = original_len + len(padding)
77

78
    forged_suffix = known_msg_bytes + padding + extension_bytes
79

80
    total_len = padded_len + len(extension_bytes)
81
    ext_padding = sha512_pad(total_len)
82
    data = extension_bytes + ext_padding
83
    assert len(data) % 128 == 0
84

85
    for i in range(0, len(data), 128):
86
        state = sha512_compress(state, data[i:i+128])
87

88
    new_hash = struct.pack('>8Q', *state).hex()
89
    return new_hash, forged_suffix
90

91

92
# ======================== Exploit Logic ========================
93

94
SALT_SIZE = 256
95

96

97
def bytes_to_escaped(b):
98
    return ''.join('\\x{:02x}'.format(byte) for byte in b)
99

100

101
def do_query(p, payload_str, hash_hex):
102
    p.recvuntil(b'Enter your vector: ')
103
    p.sendline(payload_str.encode())
104

105
    resp = p.recvuntil([b'Enter its salted hash: ', b'Invalid vector!'])
106
    if b'Invalid vector!' in resp:
107
        log.error("Server rejected vector as invalid!")
108
        return None
109

110
    p.sendline(hash_hex.encode())
111

112
    resp = p.recvuntil([b'The computed dot product is: ', b'Untrusted vector detected!'])
113
    if b'Untrusted vector' in resp:
114
        log.error("Hash mismatch!")
115
        return None
116

117
    dp = int(p.recvline().strip())
118
    return dp
119

120

121
def query_base(p, vec, hash_val):
122
    return do_query(p, str(vec), hash_val)
123

124

125
def query_extended(p, vec, hash_val, extension_entries):
126
    original_content = str(vec)[1:-1]
127
    original_content_bytes = original_content.encode('latin-1')
128

129
    ext_str = ''.join(f',{e}' for e in extension_entries)
130
    ext_bytes = ext_str.encode('latin-1')
131

132
    new_hash, forged_suffix = sha512_length_extend(
133
        hash_val, original_content_bytes, SALT_SIZE, ext_bytes
134
    )
135

136
    padding_bytes = forged_suffix[len(original_content_bytes):-len(ext_bytes)]
137
    payload = '[' + original_content + bytes_to_escaped(padding_bytes) + ext_str + ']'
138

139
    return do_query(p, payload, new_hash)
140

141

142
def main():
143
    if args.REMOTE:
144
        p = remote(args.HOST or 'lonely-island.picoctf.net', int(args.PORT or 64888))
145
    else:
146
        p = process(['python3', 'remote.py'])
147

148
    # Read encrypted flag
149
    p.recvuntil(b'IV: ')
150
    iv = bytes.fromhex(p.recvline().strip().decode())
151
    p.recvuntil(b'Ciphertext: ')
152
    ct = bytes.fromhex(p.recvline().strip().decode())
153

154
    # Read trusted vectors
155
    p.recvuntil(b"Here are the vectors I trust won't leak my key:\n")
156
    trusted = []
157
    for _ in range(5):
158
        line = p.recvline().strip().decode()
159
        vec, hash_val = ast.literal_eval(line)
160
        trusted.append((vec, hash_val))
161

162
    # Sort by length (shortest first)
163
    trusted.sort(key=lambda x: len(x[0]))
164
    base_vec, base_hash = trusted[0]
165
    n_min = len(base_vec)
166
    log.info(f"Using shortest vector (length {n_min}): {base_vec}")
167

168
    # Step 1: base dot product for shortest vector
169
    base_dp = query_base(p, base_vec, base_hash)
170
    log.info(f"Base dot product: {base_dp}")
171

172
    # Step 2: extract key[n_min..31] via length extension
173
    key = [None] * 32
174
    for j in range(n_min, 32):
175
        ext = [0] * (32 - n_min)
176
        ext[j - n_min] = 1
177
        ext_dp = query_extended(p, base_vec, base_hash, ext)
178
        key[j] = ext_dp - base_dp
179
        log.info(f"key[{j:2d}] = {key[j]}")
180

181
    # Step 3: solve for key[0..n_min-1] using all 5 trusted vectors
182
    if n_min == 1:
183
        key[0] = base_dp // abs(base_vec[0])
184
        log.info(f"key[ 0] = {key[0]}")
185
    else:
186
        equations_A = []
187
        equations_b = []
188

189
        known_sum = sum(abs(base_vec[i]) * key[i] for i in range(n_min, min(len(base_vec), 32)))
190
        equations_A.append([abs(base_vec[i]) for i in range(n_min)])
191
        equations_b.append(base_dp - known_sum)
192

193
        for vec, hash_val in trusted[1:]:
194
            dp = query_base(p, vec, hash_val)
195
            known_sum = sum(abs(vec[i]) * key[i] for i in range(n_min, min(len(vec), 32)))
196
            coeffs = [abs(vec[i]) for i in range(min(n_min, len(vec)))]
197
            coeffs += [0] * (n_min - len(coeffs))
198
            equations_A.append(coeffs)
199
            equations_b.append(dp - known_sum)
200

201
        A_all = np.array(equations_A, dtype=np.float64)
202
        b_all = np.array(equations_b, dtype=np.float64)
203
        n_eq = len(equations_A)
204

205
        if n_eq >= n_min:
206
            x, _, _, _ = np.linalg.lstsq(A_all, b_all, rcond=None)
207
            for i in range(n_min):
208
                key[i] = int(round(x[i]))
209
        else:
210
            n_free = n_min - n_eq
211
            A_pivot = A_all[:, :n_eq]
212
            A_free = A_all[:, n_eq:]
213
            found = False
214
            from itertools import product as iprod
215
            for free_vals in iprod(range(256), repeat=n_free):
216
                free_arr = np.array(free_vals, dtype=np.float64)
217
                rhs = b_all - A_free @ free_arr
218
                try:
219
                    pivot_vals = np.linalg.solve(A_pivot, rhs)
220
                except np.linalg.LinAlgError:
221
                    continue
222
                rounded = [int(round(v)) for v in pivot_vals]
223
                if all(0 <= v <= 255 and abs(v - pv) < 0.01 for v, pv in zip(rounded, pivot_vals)):
224
                    for i in range(n_eq):
225
                        key[i] = rounded[i]
226
                    for i in range(n_free):
227
                        key[n_eq + i] = free_vals[i]
228
                    test_key = bytes(key)
229
                    try:
230
                        test_cipher = AES.new(test_key, AES.MODE_CBC, iv)
231
                        test_flag = unpad(test_cipher.decrypt(ct), AES.block_size)
232
                        test_flag.decode()
233
                        found = True
234
                        break
235
                    except Exception:
236
                        continue
237
            if not found:
238
                log.error("Brute force failed!")
239
                p.close()
240
                return
241

242
    key_bytes = bytes(key)
243
    log.info(f"Key: {key_bytes.hex()}")
244
    cipher = AES.new(key_bytes, AES.MODE_CBC, iv)
245
    try:
246
        flag = unpad(cipher.decrypt(ct), AES.block_size)
247
        log.success(f"Flag: {flag.decode()}")
248
    except ValueError as e:
249
        log.error(f"Decryption failed: {e}")
250

251
    p.close()
252

253

254
if __name__ == '__main__':
255
    main()

Takeaway

The intern’s linear algebra argument was solid—5 equations in 32 unknowns really can’t leak a key. The problem was the MAC. Using sha512(secret || message) instead of HMAC let us forge hashes for arbitrary extended vectors, turning 5 trusted vectors into as many as we want.

picoCTF{n0t_so_s3cure_.x_w1th_sh@512_REDACTED}

PicoCTF 2026