PowerAnalysis: Warmup picoCTF 2023 Solution

Description

1. Step 1

   Understand the leakage model

   Observation

   I noticed the server returns a single integer per query rather than raw power traces, which suggested the leakage was a derived statistic from the SubBytes step and that understanding exactly which bits it exposed was necessary before attempting any correlation attack.

   The server computes AES and leaks the sum of least-significant bits of all 16 S-box outputs: leakage = sum(SBOX[p[i] XOR k[i]] & 1 for i in 0..15). Because each term depends on exactly one key byte, you can vary one plaintext byte at a time and correlate the observed leakage against every possible key-byte guess.

   Learn more

   AES begins with AddRoundKey (XOR plaintext with key) then SubBytes (S-box lookup). The server exposes the LSB of each S-box output, so the total leakage for a 16-byte plaintext is:

   leakage = sum(SBOX[p[i] ^ k[i]] & 1  for i in range(16))

   When you fix 15 of the 16 plaintext bytes to a constant and vary the remaining one, the contribution from the other 15 bytes is a constant offset that cancels out in correlation. Only the varying byte's term changes, so you isolate key byte k[i] cleanly.

   Collecting ~500 queries is enough for the correlation to peak sharply at the correct key byte. Each query sends a 32-hex-character plaintext and reads back one integer.

2. Step 2

   Collect (plaintext, leakage) pairs from the server

   Observation

   I noticed that Pearson correlation requires a distribution of input/output pairs to find statistical dependencies, which suggested I needed to automate many queries to the server using pwntools and record each (plaintext, leakage) pair before running any analysis.

   Write a script that connects to the server with pwntools, sends random 16-byte plaintexts as hex, and stores each (plaintext_bytes, leakage_int) pair. About 500 pairs per key byte is plenty, but you can collect for all 16 key bytes in a single pass since each query returns the full 16-byte leakage.

   python

   python3 collect.py   # saves pairs to traces.npy / plaintexts.npy

   Copied!

   What didn't work first

   Tried: Send the same plaintext repeatedly to collect more leakage samples for a single key-byte position.

   Repeating an identical plaintext always produces the same leakage value, so you end up with N copies of one point rather than N independent (plaintext, leakage) pairs. Pearson correlation requires variance in both the predictor and the observed values - constant input gives zero variance and makes the correlation undefined or zero for every key-byte guess.

   Tried: Use r.recv() instead of r.recvline() to read the server's leakage integer.

   r.recv() returns whatever bytes are available in the buffer at that moment, which may be a partial line, multiple lines merged together, or the prompt text for the next query. This causes int() conversion to fail or to parse the wrong number. r.recvline() waits for the newline delimiter that the server appends, ensuring you read exactly one complete integer per query.

   Learn more

   Minimal pwntools collection loop:

   from pwn import remote
   import numpy as np, os
   
   HOST, PORT = "saturn.picoctf.net", <PORT_FROM_INSTANCE>
   
   N = 500
   plaintexts = np.frombuffer(os.urandom(N * 16), dtype=np.uint8).reshape(N, 16)
   leakages   = np.zeros(N, dtype=np.int32)
   
   with remote(HOST, PORT) as r:
       r.recvuntil(b"\n")          # consume banner if any
       for i in range(N):
           r.sendline(plaintexts[i].tobytes().hex().encode())
           leakages[i] = int(r.recvline().strip())
   
   np.save("plaintexts.npy", plaintexts)
   np.save("leakages.npy",   leakages)

   The exact banner/prompt text depends on the challenge instance. Adjust recvuntil to match what the server actually sends before it reads input.

3. Step 3

   Build the prediction matrix and correlate

   Observation

   I noticed the leakage formula isolates one key byte at a time via SBOX[p[i] XOR k[i]] & 1, which suggested building a 256-row prediction matrix per key-byte position and using Pearson correlation against the collected leakages to identify which key-byte guess best matches the observed data.

   For each key-byte index i (0 to 15), build a (256, N) matrix of predicted LSB values. Compute Pearson correlation between each row of that matrix and the leakage vector. The row with the highest absolute correlation identifies the correct key byte.

   python

   python3 attack.py

   Copied!

   Expected output

   picoCTF{...}

   What didn't work first

   Tried: Correlate the full raw S-box output value (SBOX[p ^ k]) instead of just its least-significant bit against the leakage vector.

   The server only leaks the LSB of each S-box output, so the leakage model is SBOX[p ^ k] & 1. Using the full byte value introduces a mismatch between predictions and observations - many key-byte guesses will show spuriously high correlation because the full byte partially correlates with the LSB across the 256-value S-box. The correct prediction is the single bit the server actually measures.

   Tried: Run the correlation over all 16 key bytes at once by correlating the full 16-byte leakage vector without isolating individual byte positions.

   The server returns one scalar that sums contributions from all 16 key bytes. Treating that scalar as a single response to attack all 16 bytes simultaneously means each key-byte guess must predict the joint behavior of 256^16 possible full keys, which is computationally infeasible. The attack works by attacking one byte at a time: for position i, the other 15 bytes contribute a roughly constant offset, so only byte i's prediction correlates with the variation in the total leakage.

   Learn more

   The AES S-Box is a fixed 256-byte table. The attack for one key-byte position i:

   import numpy as np
   
   SBOX = [
     0x63,0x7c,0x77,0x7b,0xf2,0x6b,0x6f,0xc5,0x30,0x01,0x67,0x2b,0xfe,0xd7,0xab,0x76,
     0xca,0x82,0xc9,0x7d,0xfa,0x59,0x47,0xf0,0xad,0xd4,0xa2,0xaf,0x9c,0xa4,0x72,0xc0,
     0xb7,0xfd,0x93,0x26,0x36,0x3f,0xf7,0xcc,0x34,0xa5,0xe5,0xf1,0x71,0xd8,0x31,0x15,
     0x04,0xc7,0x23,0xc3,0x18,0x96,0x05,0x9a,0x07,0x12,0x80,0xe2,0xeb,0x27,0xb2,0x75,
     0x09,0x83,0x2c,0x1a,0x1b,0x6e,0x5a,0xa0,0x52,0x3b,0xd6,0xb3,0x29,0xe3,0x2f,0x84,
     0x53,0xd1,0x00,0xed,0x20,0xfc,0xb1,0x5b,0x6a,0xcb,0xbe,0x39,0x4a,0x4c,0x58,0xcf,
     0xd0,0xef,0xaa,0xfb,0x43,0x4d,0x33,0x85,0x45,0xf9,0x02,0x7f,0x50,0x3c,0x9f,0xa8,
     0x51,0xa3,0x40,0x8f,0x92,0x9d,0x38,0xf5,0xbc,0xb6,0xda,0x21,0x10,0xff,0xf3,0xd2,
     0xcd,0x0c,0x13,0xec,0x5f,0x97,0x44,0x17,0xc4,0xa7,0x7e,0x3d,0x64,0x5d,0x19,0x73,
     0x60,0x81,0x4f,0xdc,0x22,0x2a,0x90,0x88,0x46,0xee,0xb8,0x14,0xde,0x5e,0x0b,0xdb,
     0xe0,0x32,0x3a,0x0a,0x49,0x06,0x24,0x5c,0xc2,0xd3,0xac,0x62,0x91,0x95,0xe4,0x79,
     0xe7,0xc8,0x37,0x6d,0x8d,0xd5,0x4e,0xa9,0x6c,0x56,0xf4,0xea,0x65,0x7a,0xae,0x08,
     0xba,0x78,0x25,0x2e,0x1c,0xa6,0xb4,0xc6,0xe8,0xdd,0x74,0x1f,0x4b,0xbd,0x8b,0x8a,
     0x70,0x3e,0xb5,0x66,0x48,0x03,0xf6,0x0e,0x61,0x35,0x57,0xb9,0x86,0xc1,0x1d,0x9e,
     0xe1,0xf8,0x98,0x11,0x69,0xd9,0x8e,0x94,0x9b,0x1e,0x87,0xe9,0xce,0x55,0x28,0xdf,
     0x8c,0xa1,0x89,0x0d,0xbf,0xe6,0x42,0x68,0x41,0x99,0x2d,0x0f,0xb0,0x54,0xbb,0x16,
   ]
   
   plaintexts = np.load("plaintexts.npy")   # shape (N, 16)
   leakages   = np.load("leakages.npy")     # shape (N,)
   
   key = []
   for byte_idx in range(16):
       col = plaintexts[:, byte_idx]        # N plaintext bytes for this position
       # Build (256, N) prediction matrix: predicted LSB of SBOX[p ^ k_guess]
       preds = np.array(
           [[SBOX[int(col[j]) ^ k] & 1 for j in range(len(col))]
            for k in range(256)],
           dtype=np.float32,
       )
       # Pearson correlation between each guess row and the leakage vector
       corrs = np.corrcoef(preds, leakages[np.newaxis, :])[:256, 256]
       best = int(np.argmax(np.abs(corrs)))
       key.append(best)
       print(f"byte {byte_idx:02d}: {best:#04x}  |corr|={abs(corrs[best]):.3f}")
   
   print("Key:", bytes(key).hex())
   print("Flag: picoCTF{" + bytes(key).hex() + "}")

   Why this works: the other 15 key bytes contribute a nearly constant offset to the leakage (since their plaintexts are random but fixed across the correlation). Only byte i's contribution varies with col, so the correlation peaks sharply there and stays near zero for wrong guesses.

   See the Rijndael S-box article to verify the table values.

4. Step 4

   Submit the recovered 16-byte key as the flag

   Observation

   I noticed the challenge description states the flag is the AES key recovered from the attack, and the script already prints it wrapped in picoCTF{}, which confirmed that submitting the hex-encoded key bytes directly was the final step.

   The flag is the 16-byte AES key encoded as 32 lowercase hex characters, wrapped in picoCTF{}. Run the attack script, copy the printed flag, and submit it.

   Learn more

   Power analysis attacks were first published by Paul Kocher in 1999 and remain a serious threat to hardware implementations of cryptography today. Smart cards, HSMs, and embedded cryptographic modules must use countermeasures like randomized masking (blinding intermediates with a random value to break the LSB correlation) and power supply filtering to resist these attacks.

   This warmup uses a scalar LSB leakage rather than a full oscilloscope trace, which actually makes the math simpler: there is no time axis to search over. The harder Power Analysis challenges replace this clean oracle with noisier multi-sample traces, requiring the same correlation framework but over many time points.

Flag

The flag is the secret AES key in hex, which varies per challenge instance. Run the attack script against your assigned server to recover it.