View source for V4:Tutorial B6 Breaking AES (Manual CPA Attack)

{{Infobox tutorial
|name                   = B6: Breaking AES (Manual CPA Attack)
|image                  = 
|caption                = 
|software versions      =
|capture hardware       = CW-Lite, CW-Lite 2-Part, CW-Pro
|Target Device          = 
|Target Architecture    = XMEGA/Arm/Other
|Hardware Crypto        = No
|Purchase Hardware      = 
}}

This tutorial will demonstrate how to perform a CPA attack using a simple Python script. This will bring you through an entire CPA attack ''without'' using the ChipWhisperer Analyzer program, which will greatly improve your understanding of the actual attack method.

== The CPA Attack Theory ==

As a background on the CPA attack, please see the section [[Correlation Power Analysis]]. It's assumed you've read that section and come back to this. Ok, you've done that? Good let's continue.

Assuming you ''actually'' read that, it should be apparent that there is a few things we need to accomplish:

# Reading the data, which consists of the analog waveform (trace) and input text sent to the encryption core
# Making the power leakage model, where it takes a known input text along with a guess of the key byte
# Implementing the correlation equation, and then looping through all the traces
# Ranking the output of the correlation equation to determine the most likely key

== Setting Up the Project ==

It is assumed you are experienced with Python development, or have at least run a Python program! If you are on Windows you'll probably use IDLE as a code editor, although you can use any code editor you wish.

Initially, we'll be using Python interactively. This means to just run <code>python</code> at the command prompt, and enter commands into the window. Later we'll move onto writing a simple script which executes these commands.

Note if you want to use matplotlib, and are running a native Python installation, you may need to install that package. If the <code>import matplotlib</code> command listed in the next section fails, you'll need to install these, which again for Windows you can get from the [http://www.lfd.uci.edu/~gohlke/pythonlibs/#pyparsing Pre-Built Windows Binaries]

== Exploring the Trace Data ==

The next step is to read the trace data. If you don't have any data yet, you should follow the steps in [[Tutorial B5 Breaking AES (Straightforward)]] to record some traces. 

You need to find the source trace files, which have a <code>.npy</code> extension. You can follow the path of a <code>.cwp</code> (ChipWhisperer Project) file to find the associated trace <code>.cfg</code> file. The same directory as the <code>.cfg</code> file will have the <code>.npy</code> files. As an example, say that our <code>.cwp</code> file contains this line:

<pre>[Trace Management]
tracefile0 = default-data-dir\traces\config_2013.11.18-16.40.58_.cfg</pre>

Opening the <code>.cfg</code> file shows the <code>prefix=</code> line, which tells us the name of the data files:

<pre>[Trace Config]
numTraces = 50
format = native
numPoints = 3000
prefix = 2013.11.18-16.40.58_</pre>
This means our trace file is in <code>default-data-dir\traces\2013.11.18-16.40.58_traces.npy</code> and the plaintext is in <code>default-data-dir\traces\2013.11.18-16.40.58_textin.npy</code>.

Using default installs, this directory will be <code>C:\chipwhisperer\software\chipwhisperer\capture\default-data-dir\traces</code>. Let's assume you've run a capture and have 50 traces of our usual AVR target.

To read them, first import NumPy to your Python console, and optionally matplotlib (not needed but useful to visualize):

<pre>
>>> import numpy as np
>>> import matplotlib.pyplot as plt</pre>
Then use <code>np.load</code> as such (note: the '''r''' infront of the string means you don't need to escape slahes

<pre>
>>> traces = np.load(r'C:chipwhisperersoftwarechipwhisperercapturedefault-data-dirtraces2013.11.18-16.40.58_traces.npy') 
>>> pt = np.load(r'C:chipwhisperersoftwarechipwhisperercapturedefault-data-dirtraces2013.11.18-16.40.58_textin.npy')
</pre>
You can print, for example, the first plaintext sent to the device:

<pre>>>> pt[0]
array([ 63,   3,  80, 100,  21, 236,  26,  68,  88, 177, 135, 226, 198, 205,  26, 133], dtype=uint8)</pre>
Or check the size of the power traces:

<pre>>>> np.shape(traces)
(51, 3000)
>>> np.shape(traces[0])
(3000,)</pre>
And finally plot a single power trace:

<pre>>>> plt.plot(traces[0])
[<matplotlib.lines.Line2D object at 0x05EF3CF0>]
>>> plt.show()</pre>
After executing <code>plt.show()</code> you should get a window to pop up with the single power trace.

== Reading the Trace Data in a Script ==

Enough fooling around. Now let's make a script that loads the trace and tries to step through them. Make a new file called for example <code>simplecpa.py</code>, starting with this simple example:

<pre>import numpy as np

traces = np.load(r'C:\chipwhisperer\software\chipwhisperer\capture\default-data-dir\traces\2013.11.18-16.40.58_traces.npy')
pt = np.load(r'C:\chipwhisperer\software\chipwhisperer\capture\default-data-dir\traces\2013.11.18-16.40.58_textin.npy')

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

#Use less than the maximum traces by setting numtraces to something
#numtraces = 15

#Set 16 to something lower (like 1) to only go through a single subkey
for bnum in range(0, 16):
    for tnum in range(0, numtraces):
        print &quot;Subkey %d, trace %d&quot;%(bnum, tnum)</pre>
If you run this script, it will generate the following output:

<pre>Subkey 0, trace 0
Subkey 0, trace 1
Subkey 0, trace 2
Subkey 0, trace 3
Subkey 0, trace 4
Subkey 0, trace 5
Subkey 0, trace 6
Subkey 0, trace 7
Subkey 0, trace 8
Subkey 0, trace 9
Subkey 0, trace 10
    ... tons more lines ...
Subkey 15, trace 45
Subkey 15, trace 46
Subkey 15, trace 47
Subkey 15, trace 48
Subkey 15, trace 49
Subkey 15, trace 50 </pre>
It's looping through a single subkey at a time, then looping through every trace. Let's limit it to break a single subkey. Do this by changing the line <code>for bnum in range(0, 16):</code> to <code>for bnum in range(0, 1):</code>. We'll go back later to breaking the whole thing. That part of the file now looks like:

<pre>#Set 16 to something lower (like 1) to only go through a single subkey
for bnum in range(0, 1):
    for tnum in range(0, numtraces):
        print &quot;Subkey %d, trace %d&quot;%(bnum, tnum)</pre>
== Performing the Guess ==

Next, we need to guess every possibility for the subkey. This is done with another loop - we'll first ''remove'' the loop going through each trace, and simply loop through each hypothetical value for each subkey:

<pre>#Set 16 to something lower (like 1) to only go through a single subkey
for bnum in range(0, 16):
    cpaoutput = [0]*256
    for kguess in range(0, 256):
        print &quot;Subkey %d, hyp = %02x&quot;%(bnum, kguess)            </pre>
Note if you want to simplify your life, you can guess only keys around the known answer initially. For example if we know the first byte of the key is 0x2B, we can do:

<pre>for kguess in range(0x26, 0x2F):
        print &quot;Subkey %d, hyp = %02x&quot;%(bnum, kguess)</pre>
Note that in Python we can specify hex constants directly! Now the system will only be searching from 0x26 - 0x2F for the correct key. Once we have a guess, we need to calculate the intermediate value corresponding to the guess.

Looking way back to how AES works, remember we are effectively attemping to target the position at the bottom of this figure:

<blockquote>[[File:Sbox_cpa_detail.png|frame|none|alt=|The AES algorithm involves a number of rounds, this is a detail from the first round of operation. Each input byte is XOR'd with a byte of the (unknown) secret key. This is passed through an S-Box, which is simply a look-up table. The output of this S-Box is what we'll use to 'check' our guessed value of the key.]]
</blockquote>
The objective is thus to determine the output of the S-Box, where the S-Box is defined as follows:

<pre>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)</pre>
Thus we need to write a function taking a single byte of input, a single byte of the guessed key, and return the output of the S-Box:

<pre>def intermediate(pt, keyguess):
    return sbox[pt ^ keyguess]</pre>
Finally, remember we want the ''Hamming Weight'' of the guess. Our assumption is that the system is leaking the Hamming Weight of the output of that S-Box. As a dumb solution, we could first convert every number to binary and count the 1's:

<pre>>>> bin(0x1F)
'0b11111'
>>> bin(0x1F).count('1')
5</pre>
This will ultimately be fairly slow. Instead we make a lookup table using this idea:

<pre>>>> HW = [bin(n).count(&quot;1&quot;) for n in range(0,256)]
>>> HW
[0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8]</pre>
And finally can create our complete intermediate value and power model functions:

<pre>HW = [bin(n).count(&quot;1&quot;) 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]</pre>
Which we can insert into the guessing routine, such that our complete file now looks like this:

<pre>import numpy as np

HW = [bin(n).count(&quot;1&quot;) 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(r'C:\chipwhisperer\software\chipwhisperer\capture\default-data-dir\traces\2013.11.18-16.40.58_traces.npy')
pt = np.load(r'C:\chipwhisperer\software\chipwhisperer\capture\default-data-dir\traces\2013.11.18-16.40.58_textin.npy')

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

#Use less than the maximum traces by setting numtraces to something
#numtraces = 15

for bnum in range(0, 16):
    cpaoutput = [0]*256
    for kguess in range(0, 256):
        print &quot;Subkey %d, hyp = %02x&quot;%(bnum, kguess)

        for tnum in range(0, numtraces):
            hypint = HW[intermediate(pt[tnum][bnum], kguess)]</pre>

== Performing the Check ==

Remember the objective is to calculate the following:

<math>{r_{i,j}} = \frac{{\sum\nolimits_{d = 1}^D {\left[ {\left( {{h_{d,i}} - \overline {{h_i}} } \right)\left( {{t_{d,j}} - \overline {{t_j}} } \right)} \right]} }}{{\sqrt {\sum\nolimits_{d = 1}^D {{{\left( {{h_{d,i}} - \overline {{h_i}} } \right)}^2}} \sum\nolimits_{d = 1}^D {{{\left( {{t_{d,j}} - \overline {{t_j}} } \right)}^2}} } }}</math>

Where the following is the association between variable names in the equation and our python script:

{|
! Equation
! Python Variable
|-
| d
| tnum
|-
| i
| kguess
|-
| j
| j index trace point, e.g.: traces[tnum][j]
|-
| h
| hypint
|-
| t
| traces
|}

It can be noticed there is effectively three sums, all sums are done over all traces. For this initial implementation we'll be explicitly calculating some of these sums, although it's faster to use NumPy to calculate across large arrays. We'll convert the equation into this format:

<math>{r_{i,j}} = \frac{sumnum}{\sqrt{sumden1 \times sumden2}}</math>

Let's go ahead an implement this in Python. To begin with, we initialize those three sums to zero:

<pre>#Initialize arrays &amp; variables to zero
sumnum = np.zeros(numpoint)
sumden1 = np.zeros(numpoint)
sumden2 = np.zeros(numpoint)</pre>
Next, let's save those hypothetical values for ''each'' associated plaintext with the current guess. Remember we are going to compare every guess to ''all'' traces. We modify our loop-over-every-trace syntax from before to append these values to a new list:

<pre>hyp = np.zeros(numtraces)
for tnum in range(0, numtraces):
    hyp[tnum] = HW[intermediate(pt[tnum][bnum], kguess)]</pre>
Next, we need to calculate the mean of the hypothesis, <math>\overline {{h_i}}</math>. This is done via NumPy:

<pre>#Mean of hypothesis
meanh = np.mean(hyp, dtype=np.float64)</pre>
Similiarly for the mean of all traces, <math>\overline {{t_j}}</math>. Remember we want the output to be a '''1 x numpoint''' size array:

<pre>#Mean of all points in trace
meant = np.mean(traces, axis=0, dtype=np.float64)</pre>
Next, let's again consider the three sums to be implemented:

<math>sumnum = {\sum\nolimits_{d = 1}^D {\left[ {\left( {{h_{d,i}} - \overline {{h_i}} } \right)\left( {{t_{d,j}} - \overline {{t_j}} } \right)} \right]} }</math>

<math>sumdem1 = \sum\nolimits_{d = 1}^D {{{\left( {{h_{d,i}} - \overline {{h_i}} } \right)}^2}}</math>

<math>sumdem2 = \sum\nolimits_{d = 1}^D {{{\left( {{t_{d,j}} - \overline {{t_j}} } \right)}^2}}</math>

Note there is some common terms in all three of these, along with a common summation index. We can thus implement them as follows:

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

    sumnum = sumnum + (hdiff*tdiff)
    sumden1 = sumden1 + hdiff*hdiff 
    sumden2 = sumden2 + tdiff*tdiff</pre>
The size of sumnum, sumden1, and sumden2 are all '''1 x numpoints''', meaning an output is generated for each point of the input. Note each of these is calculated independantly, thus we simply avoid looping through every point by using the vector notation of NumPy. Finally, we calculate the single output vector &amp; save it as a specific key guess:

<pre>cpaoutput[kguess] = sumnum / np.sqrt( sumden1 * sumden2 )</pre>
Tying it all together, we end up with the following:

<pre>import numpy as np

HW = [bin(n).count(&quot;1&quot;) 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(r'C:\chipwhisperer\software\chipwhisperer\capture\default-data-dir\traces\2013.11.18-16.40.58_traces.npy')
pt = np.load(r'C:\chipwhisperer\software\chipwhisperer\capture\default-data-dir\traces\2013.11.18-16.40.58_textin.npy')

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

#Use less than the maximum traces by setting numtraces to something
#numtraces = 15

bestguess = [0]*16
#Set 16 to something lower (like 1) to only go through a single subkey &amp; save time!
for bnum in range(0, 16):
    cpaoutput = [0]*256
    maxcpa = [0]*256
    for kguess in range(0, 256):
        print &quot;Subkey %2d, hyp = %02x: &quot;%(bnum, kguess),


        #Initialize arrays &amp; 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]))

        print maxcpa[kguess]

    #Find maximum value of key
    bestguess[bnum] = np.argmax(maxcpa)

print &quot;Best Key Guess: &quot;
for b in bestguess: print &quot;%02x &quot;%b,</pre>
The maxcpa is stored as an ''absolute'' value, since we may end up with positive or negative correlation. We only care about absolute value (e.g. there is a linear correlation), not sign. We also store only the maximum cpa across ''all'' points in the trace. Typically only a few points in the trace are correlating, and it's the maximum across the entire trace we are concerned with. This is done via this line of code:

<pre>maxcpa[kguess] = max(abs(cpaoutput[kguess]))</pre>
The <code>argmax()</code> function is used to find the maximum for ''all'' subkey candidates {0,1,2,...,255}, and which key candidate caused that maximum. The <code>argmax()</code> simply finds the indicie of the maximum value, and in this code the indicie corresponds to the subkey candidate.

When running this code, it's suggest to change the following:

<pre>for bnum in range(0, 16):</pre>
To only attack a single subkey, otherwise there is too much output:

<pre>for bnum in range(0, 1):</pre>
Assuming you've used the usual '''2B 7E ...''' encryption key in your traces, running it would produce the following output:

<pre>Subkey  0, hyp = 00:  0.485067679972
Subkey  0, hyp = 01:  0.452597478584
 ... bunch more lines ...
Subkey  0, hyp = 29:  0.524796414777
Subkey  0, hyp = 2a:  0.429701324
Subkey  0, hyp = 2b:  0.971303850401
Subkey  0, hyp = 2c:  0.404439421891
Subkey  0, hyp = 2d:  0.429089006754
 ... bunch more lines ...
Subkey  0, hyp = ff:  0.449003229759
Best Key Guess: 
2b  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00 </pre>

== Calculating The PGE ==

The Partial Guessing Entropy (PGE) is a useful metric of where the correct answer is ranked. This requires us to know the actual encryption key used during operation. If you've recorded traces with the regular ChipWhisperer system, this is stored alongside the traces &amp; textin file. Check if you have a file called either <code>_knownkey.npy</code> or <code>_keylist.npy</code>. The knownkey file contains a single line, and the keylist contains a list of the encryption key corresponding with every input.

Certain attacks will use different keys during the acqusition period, meaning the keylist.npy file is required since there isn't a constant key. In our case we can load and print the key with:

<pre>>>> knownkey = np.load(r'C:\chipwhisperer\software\chipwhisperer\capture\default-data-dir\traces\2013.11.18-16.40.58_knownkey.npy')
>>> knownkey
array([ 43, 126,  21,  22,  40, 174, 210, 166, 171, 247,  21, 136,   9, 207,  79,  60], dtype=uint8)
>>> [&quot;%02x &quot;%k for k in knownkey]
['2b ', '7e ', '15 ', '16 ', '28 ', 'ae ', 'd2 ', 'a6 ', 'ab ', 'f7 ', '15 ', '88 ', '09 ', 'cf ', '4f ', '3c ']
>>> &quot;&quot;.join([&quot;%02x &quot;%k for k in knownkey])
'2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3c '</pre>
Previously, we simply printed the maximum output for each subkey as follows:

<pre>#Find maximum value of key
bestguess[bnum] = np.argmax(maxcpa)</pre>
To sort the list of CPA output's, we'll use the <code>argsort()</code> function from NumPy. This will output a list where the first element is the index of the lowest value, next element is the index of the next-highest element, etc. Because in our input list the <code>maxcpa</code> vector's indexes correspond to the key guess, this allows us to know where the keys are. We reverse that sorted list to put the first element as the maximum CPA output:

<pre>cparefs = np.argsort(maxcpa)[::-1]</pre>
Finally, the Partial Guessing Entropy is simply the location of the known correct key byte inside that array. We can find that with the <code>.index()</code> function:

<pre>print cparefs.index(0x2B)</pre>
Where the correct key should of course come from our <code>knownkey</code> variable instead of being hard-coded. Pulling it all together:

<pre>....
#Find maximum value of key
bestguess[bnum] = np.argmax(maxcpa)

cparefs = np.argsort(maxcpa)[::-1]

#Find PGE
pge[bnum] = list(cparefs).index(knownkey[bnum])
....</pre>
Where at the beginning of the file we have to open the knownkey:

<pre>....
pt = np.load(r'C:\chipwhisperer\software\chipwhisperer\capture\default-data-dir\traces\2013.11.18-16.40.58_textin.npy')
knownkey = np.load(r'C:\chipwhisperer\software\chipwhisperer\capture\default-data-dir\traces\2013.11.18-16.40.58_knownkey.npy')
....</pre>
Along with initilizing the pge[] array:

<pre>bestguess = [0]*16
pge = [0]*16
for bnum in range(0, 1):
    ....</pre>
Finally, you probably want to print the entire PGE:

<pre>....
print "Best Key Guess: ",
for b in bestguess: print "%02x "%b,

print ""
print "PGE: ",
for b in pge: print "%02d "%b,</pre>
When running the program, uncomment the <code>#numtraces = 10</code> line and set the traces to something lower than the full file. You should see the PGE increase when you don't use all possible traces. You may also wish to comment out the printing of data for every guess, as this slows down the program.

== Future Changes ==

The implementation of the correlation function runs as a loop over all traces. Ideally we'd like to implement this as a 'online' calculation; that is, we can add a trace in, observe the output, add another trace in, observe the output, etc. When generating plots of the Partial Guessing Entropy (PGE) vs. number of traces this is greatly preferred, since otherwise we need to run the loop many times!

We can use an alternate form of the correlation equation, which explicitly stores sums of the variables. This is easier to perform online calculation with, since when adding a new trace it's simple to update these sums. This form of the equation looks like:

<math>r_{i,j} = \frac{D \sum_{d=1}^D h_{d,i}t_{d,j} - \sum_{d=1}^D h_{d,i} \sum_{d=1}^D t_{d,j}}{\sqrt{\Big(\big(\sum_{d=1}^D h_{d,i}\big)^2 - D\sum_{d=1}^D h_{d,i}^2\Big)\Big(\big(\sum_{d=1}^D t_{d,j}\big)^2 - D\sum_{d=1}^D t_{d,j}^2\Big)}}</math>

<blockquote></blockquote>

== Complete Program ==

For reference here is the complete program. Before running you might want to make a few adjustments:

# Uncomment the <code>numtraces = 10</code> line to use less traces
# Comment out the <code>print "Subkey ..."</code> line to avoid printing every value
# Only run over a single subkey by adjusting the larger index in <code>for bnum in range(0, 16)</code>

Here is the code:

<syntaxhighlight lang="python">
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(r'C:\chipwhisperer\software\chipwhisperer\capture\default-data-dir\traces\2013.11.18-16.40.58_traces.npy')
pt = np.load(r'C:\chipwhisperer\software\chipwhisperer\capture\default-data-dir\traces\2013.11.18-16.40.58_textin.npy')
knownkey = np.load(r'C:\chipwhisperer\software\chipwhisperer\capture\default-data-dir\traces\2013.11.18-16.40.58_knownkey.npy')
numtraces = np.shape(traces)[0]-1
numpoint = np.shape(traces)[1]

#Use less than the maximum traces by setting numtraces to something
#numtraces = 10

#Set 16 to something lower (like 1) to only go through a single subkey
bestguess = [0]*16
pge = [256]*16
for bnum in range(0, 16):
    cpaoutput = [0]*256
    maxcpa = [0]*256
    for kguess in range(0, 256):
        print "Subkey %2d, hyp = %02x: "%(bnum, kguess),


        #Initialize arrays &amp; 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]))

        print maxcpa[kguess]

    bestguess[bnum] = np.argmax(maxcpa)

    cparefs = np.argsort(maxcpa)[::-1]

    #Find PGE
    pge[bnum] = list(cparefs).index(knownkey[bnum])

print "Best Key Guess: ",
for b in bestguess: print "%02x "%b,

print ""
print "PGE: ",
for b in pge: print "%02d "%b,

</syntaxhighlight>


== Conversion of Correlation Equation ==

The following shows the derivation of the online correlation equation from the original form:

[[File:Rij_conversion.png]]

== Links ==

{{Template:Tutorials}}
[[Category:Tutorials]]