[Crypto] SquareCtf 2018 - C4: leaky power

Crypto aes, cpa, power_analysis Comments

C4: leaky power
222

C4 is a very advanced AES based defensive system. You are able to monitor the power lines. Is that enough?

You’re given three files:

powertraces.npy: Measurements (over time) of power consumption of a chip while performing AES encryption
#: Corresponding plaintext inputs that were encrypted
instructions.jwe: File encrypted using the same key as plaintexts.npy.

note: The first two files are NumPy arrays.

note: there’s a mistake in the way instructions.jwe was created (the algorithm is A128GCM, not A256GCM).

The encryption used is AES, from reading the challenge description we know we eventually were able to monitor the powerlines having some power traces on powertraces.npy and the corresponding plaintexts used on plaintexts.npy, the ciphertext we want to decrypt is located at instructions.jwe.

We have some power traces so we will need to use some kind of side-channel analysis:

In CPA (Correlation power analysis) the goal is to accurately produce a power model of the device under attack. During an attack, the aim is to find Correlation between a predicted output and the actual power output of a device. If the power model is accurate then a strong correlation should be demonstrated between the predicted output and actual output. If this correlation is found then, gathering a large number of traces will enable one to show that the correctly predicted cipher key will demonstrate the highest level of correlation.

One power model which may be used is the Hamming Weight Power Model. Traditionally, the Hamming weight of a value is the number of non-zeroes. For example, in the binary number 1100 0010 the Hamming weight would be 3. The assumption in using the Hamming Weight Power Model in power analysis attacks is that the number of bits set to 0 or 1 of an output is correlated with the power consumption of a device. The Hamming weight itself is then used as an arbitrary unit to model the consumption of power in a device. Hamming weight units can then be compared to the actual voltage levels of power traces captured when a device was performing cryptographic operations. This act of comparison is the process of finding correlation between the modelled power unit values and the actual power consumed.

One technique to calculate correlation between the power model and the actual power consumption is to use Pearson correlation coefficient equation. In essence, this equation will take two sets data (X and Y) and calculate whether there is a linear (positive or negative) correlation between the two sets of values. We may use this equation to find significance in our power traces since the assumption with the Hamming Weight Power Model is that as the number of 1’s increase in our predicted output, so too does the power consumption increase in the actual output (and vice versa).

_Figure 1 - Pearson correlation coefficient equation_

AES

At the start of encryption, the plaintext values (the data to be encrypted) and the cipher key values (the key used for encryption and decryption purposes) will be each arranged into a 4×4 matrix in the positions as shown in Figure 2. Each value in this matrix holds 1 byte of data. During the AddRoundKey step, each plaintext value is XOR’d with a cipher key value at a matching position in the 4×4 matrix.

_Figure 2. Plaintext and cipher key arrangement._

After AddRoundKey, the SubBytes step will use the result produced by Pi⊕ Ki as a lookup for a value stored in the Rijndael S-box. The S-box output will replace Pi⊕ Ki. The S-box is a 16×16 matrix of values which remains constant for all AES implementations. Each position in the 16×16 matrix will hold 1 byte of data.

_Figure 3 - Rijndael S-box_

For example if the result of Pi ⊕ Ki is c5 then we look for in the sbox table for the line c and the column 5 and we obtain the value a6.

In the context of CPA attack implemented aim to exploit the fact that information may be leaked if one was to monitor the power consumption of a cryptographic device during the point in which the S-box lookup is carried out.

Writing Python Script of CPA

Both this files are numpy arrays, they can be loaded into python by using the numpy.load function:

1
2
3
import numpy as np
traces = np.load('powertraces.npy')
pt = np.load('plaintexts.npy')

Now for each we want to create some hypothesis, the range is between 0x0 to 0xff (all possible bytes), this hypothesis are key guesses in which we will Xor them between with the plaintexts used and calculated it’s Hamming Weight : 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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)

def intermediate(pt, keyguess):
    return sbox[pt ^ keyguess]

HW = [bin(n).count("1") for n in range(0,256)]

# Aes key is 16 bytes so for each best guess
for bnum in range(0, 16):
        cpaoutput = [0]*256
        maxcpa = [0]*256
        # for each keyguess
        for kguess in range(0, 256):
            print "Subkey %2d, hyp = %02x: "%(bnum, kguess),


            #Initialize arrays & variables to zero
            sumnum = np.zeros(numpoint)
            sumden1 = np.zeros(numpoint)
            sumden2 = np.zeros(numpoint)

            hyp = np.zeros(numtraces)
            # calculate every hamming distance for all the traces for this key guess
            for tnum in range(0, numtraces):
                hyp[tnum] = HW[intermediate(pt[tnum][bnum], kguess)]

Now still in the same loop we want to calculate the means of the hypothesis and the points of the trace, this comes from the correlation formula in Figure 2.
We can say that the two aleatory variable X and Y where X is the hamming distance of the key hypothesis for every character of plaintext tested and Y for every points power consumption points in every trace. So concluding the Xi in the formula is the first HW[intermediate(plaintext[x0][k0], kguess)] and yi is all the points in the power consumption trace, while x̅ is the mean of variable X and ȳ is the respective mean of variable Y.

Calculation the means:

1
2
3
4
5
#Mean of hypothesis
meanh = np.mean(hyp, dtype=np.float64)

#Mean of all points in trace
meant = np.mean(traces, axis=0, dtype=np.float64)

Now calculating the summations in the formula and performing the square root:

1
2
3
4
5
6
7
8
9
10
11
#For each trace, do the following
for tnum in range(0, numtraces):
    hdiff = (hyp[tnum] - meanh)
    tdiff = traces[tnum,:] - meant

    sumnum = sumnum + (hdiff*tdiff)
    sumden1 = sumden1 + hdiff*hdiff 
    sumden2 = sumden2 + tdiff*tdiff

cpaoutput[kguess] = sumnum / np.sqrt( sumden1 * sumden2 )
maxcpa[kguess] = max(abs(cpaoutput[kguess]))

So after calculating the correlation for every key guess the best guess key is the one with highest value of correlation:

1
bestguess[bnum] = np.argmax(maxcpa)

In the end we get the complete key used in the encryption, the full script:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import numpy as np

HW = [bin(n).count("1") for n in range(0,256)]

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)

def intermediate(pt, keyguess):
    return sbox[pt ^ keyguess]

traces = np.load('powertraces.npy')
pt = np.load('plaintexts.npy')

bestguess = []
if bestguess == []:

    numtraces = np.shape(traces)[0]-1
    numpoint = np.shape(traces)[1]

    bestguess = [0]*16
    
    for bnum in range(0, 16):
        cpaoutput = [0]*256
        maxcpa = [0]*256
        for kguess in range(0, 256):
            #Initialize arrays & variables to zero
            sumnum = np.zeros(numpoint)
            sumden1 = np.zeros(numpoint)
            sumden2 = np.zeros(numpoint)

            hyp = np.zeros(numtraces)
            for tnum in range(0, numtraces):
                hyp[tnum] = HW[intermediate(pt[tnum][bnum], kguess)]


            #Mean of hypothesis
            meanh = np.mean(hyp, dtype=np.float64)

            #Mean of all points in trace
            meant = np.mean(traces, axis=0, dtype=np.float64)

            #For each trace, do the following
            for tnum in range(0, numtraces):
                hdiff = (hyp[tnum] - meanh)
                tdiff = traces[tnum,:] - meant

                sumnum = sumnum + (hdiff*tdiff)
                sumden1 = sumden1 + hdiff*hdiff 
                sumden2 = sumden2 + tdiff*tdiff

            cpaoutput[kguess] = sumnum / np.sqrt( sumden1 * sumden2 )
            maxcpa[kguess] = max(abs(cpaoutput[kguess]))


        bestguess[bnum] = np.argmax(maxcpa)

    key = ''
    for b in bestguess: 
        key += "%02x"%b
    print "Best Key Guess: %s" % key

Running it : 

1
2
$ python leak_power.py
Best Key Guess: d2dea057d1145f456796966024a703b2

The key is d2dea057d1145f456796966024a703b2 now that we have the key we can decrypt the cyphertext, we can do this ith a few lines of go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package main
import (
	"fmt"
	"io/ioutil"
	"os"
	"gopkg.in/square/go-jose.v2"
	)

// Read input from file
func readInput(path string) []byte {
	var bytes []byte
	var err error
	bytes, err = ioutil.ReadFile(path)
	exitOnError(err, "unable to read input")
	return bytes
}

// Exit and print error message if we encountered a problem
func exitOnError(err error, msg string) {
	if err != nil {
		fmt.Fprintf(os.Stderr, "%s: %s\n", msg, err)
		os.Exit(1)
	}
}

func main() {
	obj, err := jose.ParseEncrypted(string(readInput("instructions_corrected.jwe")))
	exitOnError(err, "unable to parse message")
	plaintext, err := obj.Decrypt("\xd2\xde\xa0\x57\xd1\x14\x5f\x45\x67\x96\x96\x60\x24\xa7\x03\xb2")
	exitOnError(err, "unable to decrypt message")
	fmt.Print(string(plaintext))
}

Running it we get the flag:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
$ go get gopkg.in/square/go-jose.v2
$ go run aes_dec.go
CONFIDENTIAL

To disable C4, you will need:
- 6 bits of Dragon Sumac
- 1 nibble of Winter Spice
- 1 byte of Drake Cardamom
- 1 flag with value flag-e2f27bac480a7857de45
- 2 diskfulls of Tundra Chives
- 5 forks

Grind the Dragon Sumac in a cup, making sure you don't break the cup as it's probably a delicate cup. Add a sprinkle of
liquid ice to turn it into a cream-like paste, then add the Winter Spice, first almost everything, then the last tiny
remnants.

Fill a pan with elemental water, add the mixture and cool it down with how cool you are, then bring the mixture
to a boil. Let it cool down to the body temperature of a reptile before adding the Drake Cardamom and Tundra Chives,
all at once of one, then half at a time of the other.

Bring everything back to a boil, turn of the heat, mix with the forks and let everything cool down. If you
touch the liquid and it burns you, it hasn't cooled down enough.

Whisk the mixture heavily to aerate it. Stop when it's frothy.

Drinking the potion will disable C4.

note: A small, but very cold amount is needed for the potion to be effective. Mixing it in a milkshake could work, but
be wary of brain freeze.

The flag was flag-e2f27bac480a7857de45

References

TeamRocketISTCTF Team

Portuguese Computer Science Students