PowerAnalysis: Warmup picoCTF 2023 Solution

Description

1. Step 1Understand the leakage model

   Observation

   The server returns one integer per query rather than a raw power trace. That is a derived statistic from the SubBytes step, and knowing exactly which bits it exposes comes before 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))

   Every term in that sum depends on exactly one plaintext byte and one key byte. Because the plaintext bytes you send are independent of each other, the 15 terms other than i are statistically independent of any prediction you make about byte i: across many random queries they average to a constant offset and act as zero-mean noise rather than bias. That is what lets a correlation on byte i alone pick k[i] out of the scalar total. Fixing the other 15 plaintext bytes to a constant works too and removes the noise entirely, at the cost of a separate collection pass per key byte.

   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 2Collect (plaintext, leakage) pairs from the server

   Observation

   Pearson correlation needs a distribution of input and output pairs before any dependency shows. Automate many queries with pwntools, recording each plaintext alongside its leakage value, before analyzing anything.

   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 is plenty, and one pass covers all 16 key bytes at once because the single scalar each query returns carries a contribution from every key byte.

   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 3Build the prediction matrix and correlate

   Observation

   The leakage formula isolates one key byte at a time, taking a single bit of the S-Box output for that position. Build a 256-row prediction matrix per position and correlate it against the collected leakages to find which guess matches the observations.

   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 15 other terms are independent of your byte-i prediction, so they average out as noise and only byte i's prediction correlates with 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 15 other terms depend on plaintext bytes drawn independently of col, so they average to a constant and contribute only noise to the correlation. Only byte i's contribution tracks col, so with enough samples the correlation peaks sharply at the right guess and stays near zero for wrong ones.

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

4. Step 4Submit the recovered 16-byte key as the flag

   Observation

   The description says the flag is the recovered AES key, and the script already prints it wrapped in picoCTF{}. Submitting those hex-encoded bytes is the last 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.