SEED Correlation Power Analysis

This post is not an introduction to the SEED block cipher itself. I assume the reader already knows the 16-round Feistel structure, the round F function, the G function, and the key schedule.

The goal here is narrower: given power traces and known plaintexts from an unprotected SEED implementation, recover enough round-key material with Correlation Power Analysis (CPA), then invert the key schedule to recover the master key.

References:

• SEED specification: KISA SEED document
• SEED reference description: RFC 4269

1. Attack Model

I assume the following setting.

1. The implementation uses a fixed 128-bit SEED key.
2. The plaintext for each encryption trace is known.
3. The traces are roughly aligned.
4. The implementation is not masked or otherwise protected against first-order CPA.

The SEED block is 128 bits. I write the plaintext state as four 32-bit words:

Each round applies the F function to the right half, then XORs the result into the left half and swaps the Feistel sides.

The trace below was collected from a SEED implementation on ChipWhisperer. The optimized SEED encryption itself is short compared with the dummy operation after it.

Zooming into the SEED region, the repeated round activity is visible. This is a useful SPA sanity check before starting CPA.

2. SEED Round Structure

The high-level Feistel movement is important because round 2 CPA needs the state after round 1. The same colored blocks in the diagram represent the same state words moving between rounds.

Inside one round, the right half is split into two 32-bit words. I call them $C$ and $D$ in the F function:

The round key also has two 32-bit words:

The F function mixes them with XOR, modular addition, and the nonlinear G function.

The useful CPA leakage points are the G calls. G is a 32-bit input, 32-bit output transformation built from byte S-box substitutions and linear mixing. We do not need to attack the entire 32-bit output at once; the first substituted bytes are enough to build byte-wise leakage hypotheses.

The compact form is:

For CPA, the important part is the first nonlinear S-box layer. If a byte of the G input is known up to one guessed key byte, we can predict the S-box output, convert it to Hamming weight, and correlate it with the measured traces.

3. Why Four CPA Passes Are Needed

One SEED round key has two 32-bit words, $K_{i,0}$ and $K_{i,1}$. The first G input in the F function is based on:

This simplifies to:

Therefore, the first CPA of a round does not recover $K_{i,0}$ or $K_{i,1}$ directly. It recovers their XOR:

After that, a second CPA target uses the next addition and G call to recover $K_{i,0}$. Once $K_{i,0}$ is known, the other half is immediate:

To recover the first two round keys, I repeat this twice:

1. Round 1 CPA for $K_{1,0} \oplus K_{1,1}$.
2. Round 1 CPA for $K_{1,0}$.
3. Round 2 CPA for $K_{2,0} \oplus K_{2,1}$, after computing the round 1 state.
4. Round 2 CPA for $K_{2,0}$.

Each target is a 32-bit word, but the CPA is done one byte at a time. A direct 32-bit guess would require $2^{32}$ hypotheses. Four independent byte CPA runs require only:

key-byte hypotheses.

4. Round 1 CPA: Recovering $K_{1,0} \oplus K_{1,1}$

For the first round, $C$ and $D$ are known from the plaintext:

The first target is:

where $k$ is a byte guess for $K_{1,0} \oplus K_{1,1}$.

The diagram below shows the first G call in the round 1 F function. That is the attack point for the XOR-combined key.

For byte position $b$, plaintext trace $j$, and key-byte guess $k$, the hypothetical leakage is:

The S-box index $S_b$ depends on the byte position and the implementation’s SEED S-box ordering.

The code shape is the same as the AES CPA post: build a hypothetical leakage vector for each key guess and correlate it against each sample point.

1
for (int byte_pos = 0; byte_pos < 4; byte_pos++) {
2
    for (int key = 0; key < 256; key++) {
3
        for (int trace_idx = 0; trace_idx < trace_count; trace_idx++) {
4
            uint8_t iv = PT[trace_idx][byte_pos + 8]
5
                       ^ PT[trace_idx][byte_pos + 12]
6
                       ^ key;
7

8
            if (byte_pos % 2 == 0) {
9
                iv = S[1][iv];
10
            } else {
11
                iv = S[0][iv];
12
            }
13

14
            predicted_hw[trace_idx] = hamming_weight(iv);
15
        }
16

17
        correlate_against_trace_window(byte_pos, key, predicted_hw, traces);
18
    }
19
}

The correlation peaks are clear.

The recovered 32-bit value is:

This matches the known round-key values:

5. Round 1 CPA: Recovering $K_{1,0}$

The second target is the next G call in the same F function. At this point we already know:

So the first G output can be computed for every trace. The next input is based on:

This gives a leakage model that depends on $K_{1,0}$.

There is one complication: this is a 32-bit modular addition, so carry propagation matters. I recover the bytes from least significant to most significant so that the carry into the next byte can be modeled.

For a byte-wise CPA, the model is:

Then the leakage target is a byte of:

The implementation model looks like this in C-style pseudocode.

1
for (int byte_pos = 3; byte_pos >= 0; byte_pos--) {
2
    for (int key = 0; key < 256; key++) {
3
        for (int trace_idx = 0; trace_idx < trace_count; trace_idx++) {
4
            uint32_t cd_xor = pack_be32(&PT[trace_idx][8])
5
                            ^ pack_be32(&PT[trace_idx][12]);
6

7
            uint32_t first_g = G_Function(cd_xor ^ known_kxor);
8
            uint8_t g_byte = select_byte(first_g, byte_pos);
9
            uint8_t c_byte = PT[trace_idx][byte_pos + 8] ^ key;
10

11
            uint8_t iv = add_with_known_carry(c_byte, g_byte, byte_pos);
12

13
            if (byte_pos % 2 == 0) {
14
                iv = S[1][iv];
15
            } else {
16
                iv = S[0][iv];
17
            }
18

19
            predicted_hw[trace_idx] = hamming_weight(iv);
20
        }
21

22
        correlate_against_trace_window(byte_pos, key, predicted_hw, traces);
23
    }
24
}

The correlations are lower than the first CPA, but still clearly distinguishable from noise.

The recovered left round key is:

Then the right round key is:

6. Round 2 CPA

For round 2, the plaintext alone is no longer enough. We first compute the round 1 output state using the recovered round 1 keys. That gives the round 2 input words $C$ and $D$ for every trace.

Then the same two-step attack applies.

The first round 2 target is:

where $C$ and $D$ are now the round 2 right-half words.

The correlation trace is again strong because this target is the first G call of the round.

The recovered XOR-combined key is:

This matches:

The second round 2 target recovers $K_{2,0}$ from the next addition and G call, just like round 1.

The recovered left round key is:

Then:

7. Interpreting the Correlation Traces

The four CPA traces overlaid on the SEED power trace show where each target leaks.

The combined-key CPA targets, $K_{i,0} \oplus K_{i,1}$, produce stronger correlations around 0.8. The left-key CPA targets are weaker, around 0.5, because the model passes through modular addition and carry handling before the next S-box.

That difference is expected. A lower correlation is not a failure if the correct key still produces a clear peak above the wrong guesses.

At this point the recovered round-key material is:

8. Recovering the Master Key

The remaining step is to invert the SEED key schedule. SEED splits the 128-bit master key into four 32-bit words:

The first two round-key equations are:

For round 2, the key schedule rotates $A \parallel B$ by one byte while $C$ and $D$ remain in place:

The next equations are:

By applying $G^{-1}$ and correcting the round constants, we get:

Because $A' \parallel B'$ is only a one-byte rotation of $A \parallel B$, the system is almost fixed by the first two rounds. In this example, guessing the single byte that crosses the $A/B$ boundary is enough to reconstruct all four master-key words.

The recovered master key is:

00010203 04050607 08090A0B 0C0D0E0F

The important point is that CPA did not directly recover the master key. It recovered early round-key constraints. The SEED key schedule then turned those constraints back into the 128-bit master key.