Template Attacks - Revision history

Fheubach: Change header levels

2018-05-01T13:44:35Z

Change header levels

Coflynn at 20:42, 25 March 2017

2017-03-25T20:42:39Z

Gdeon: /* Picking POIs */ Added section

2016-05-25T18:39:04Z

‎Picking POIs: Added section

Gdeon: /* Creating the Template */ There aren't 16 bits in a byte, Greg.

2016-05-25T14:52:34Z

‎Creating the Template: There aren't 16 bits in a byte, Greg.

Gdeon: /* Using the Template */ Described attack method

2016-05-25T14:18:53Z

‎Using the Template: Described attack method

Gdeon: /* Using the Template */ Added information on attack quality

2016-05-25T13:32:34Z

‎Using the Template: Added information on attack quality

Gdeon: /* Analyzing the Data */ Added section

2016-05-25T13:23:13Z

‎Analyzing the Data: Added section

Gdeon: /* Creating the Template */ Added info on number of traces and POIs

2016-05-25T12:50:50Z

‎Creating the Template: Added info on number of traces and POIs

Gdeon: Wrote out remaining sections

2016-05-25T12:22:00Z

Wrote out remaining sections

Gdeon: /* Multivariate Statistics */ Added basics of multivariate stats.

2016-05-25T12:13:57Z

‎Multivariate Statistics: Added basics of multivariate stats.

@@ Line 9: / Line 9: @@
 # Apply the template to the attack traces. For each subkey, track which value is most likely to be the correct subkey. Continue until the key has been recovered.
-= Signals, Noise, and Statistics =
+== Signals, Noise, and Statistics ==
 Before looking at the details of the template attack, it is important to understand the statistics concepts that are involved. A template is effectively a multivariate distribution that describes several key samples in the power traces. This section will describe what a multivariate distribution is and how it can be used in this context.
-== Noise Distributions ==
+=== Noise Distributions ===
 Electrical signals are inherently noisy. Any time we take a voltage measurement, we don't expect to see a perfect, constant level. For example, if we attached a multimeter to a 5 V source and took 4 measurements, we might expect to see a data set like (4.95, 5.01, 5.06, 4.98). One way of modelling this voltage source is
@@ Line 43: / Line 43: @@
 so we're very unlikely to see a reading of 7 V. We'll use this to our advantage in this attack: if <math>f(x)</math> is very small for one of our subkey guesses, it's probably a wrong guess.
-== Multivariate Statistics ==
+=== Multivariate Statistics ===
 The 1-variable Gaussian distribution works well for one measurement. What if we're working with more than one random variable?
@@ Line 80: / Line 80: @@
 Don't worry if this looks crazy - the SciPy package in Python will do all the heavy lifting for us. As with the single-variable distributions, we're going to use this to find how likely a certain observation is. In other words, if we put <math>k</math> points of our power trace into <math>\mathbf{x}</math> and we find that <math>f(\mathbf{x})</math> is very high, then we've probably found a good guess.
-= Creating the Template =
+== Creating the Template ==
 A template is a set of probability distributions that describe what the power traces look like for many different keys. Effectively, a template says: "If you're going to use key <math>k</math>, your power trace will look like the distribution <math>f_k(\mathbf{x})</math>". We can use this information to find subtle differences between power traces and to make very good key guesses for a single power trace.
-== Number of Traces ==
+=== Number of Traces ===
 One of the downsides of template attacks is that they require a great number of traces to be preprocessed before the attack can begin. This is mainly for statistical reasons. In order to come up with a good distribution to model the power traces for ''every key'', we need a large number of traces for ''every key''. For example, if we're going to attack a single subkey of AES-128, then we need to create 256 power consumption models (one for every number from 0 to 255). In order to get enough data to make good models, we need tens of thousands of traces.
 Note that we don't have to model every single key. One good alternative is to model a sensitive part of the algorithm, like the substitution box in AES. We can get away with a much smaller number of traces here; if we make a model for every possible Hamming weight, then we would end up with 9 models, which is an order of magnitude smaller. However, then we can't recover the key from a single attack trace - we need more information to recover the secret key.
-== Points of Interest ==
+=== Points of Interest ===
 Our goal is to create a multivariate probability describing the power traces for every possible key. If we modeled the entire power trace this way (with, say, 3000 samples), then we would need a 3000-dimension distribution. This is insane, so we'll find an alternative.
@@ Line 96: / Line 96: @@
 These two points mean that we can usually live with a handful (3-5) of ''points of interest''. If we can pick out good points and write down a model using these samples, then we can use a 3D or 5D distribution - a great improvement over the original 3000D model.
-=== Picking POIs ===
+==== Picking POIs ====
 There are several ways to pick the most important points in each of the traces. Generally, the aim is to find points that vary strongly between different operations (subkeys or Hamming weights). The simplest method -- the one that we'll use here -- is the ''sum of differences'' method.
@@ Line 121: / Line 121: @@
 # Repeat until enough POIs have been selected.
-== Analyzing the Data ==
+=== Analyzing the Data ===
 Suppose that we've picked <math>I</math> points of interest, which are at samples <math>s_i</math> (<math>0 \le i < I</math>). Then, our goal is to find a mean and covariance matrix for every operation (every choice of subkey or intermediate Hamming weight). Let's say that there are <math>K</math> of these operations (maybe 256 subkeys or 9 possible Hamming weights).
@@ Line 168: / Line 168: @@
 These steps must be done for every operation <math>k</math>. At the end of this preprocessing, we'll have <math>K</math> mean and covariance matrices, modelling each of the <math>K</math> different operations that the target can do.
-= Using the Template =
+== Using the Template ==
 With a template in hand, we can finish our attack. For the attack, we need a smaller number of traces - we'll say that we have <math>A</math> traces. The sample values will be labeled <math>a_{j, s_i}</math> (<math>1 \le j \le A</math>).
-== Applying the Template ==
+=== Applying the Template ===
 First, let's apply the template to a single trace. Our job is to decide how likely all of our key guesses are. We need to do the following:
 * Put our trace values at the POIs into a vector. This vector will be
@@ Line 195: / Line 195: @@
 This process gives us an array of <math>p_{k, j}</math>, which says: "Looking at trace <math>j</math>, how likely is it that key <math>k</math> is the correct one?"
-== Combining the Results ==
+=== Combining the Results ===
 The very last step is to combine our <math>p_{k, j}</math> values to decide which key is the best fit. The easiest way to do this is to combine them as
@@ Line 212: / Line 212: @@
 Comparing these logarithms will give us the same results without the precision issues.
-== Attack Time ==
+=== Attack Time ===
 The number of attack traces required to complete a template attack can vary wildly depending on the quality of the preprocessing. As described in the original papers on template attacks (Chari, Rao, and Rohatgi), when using high-quality templates made from many traces, it is possible to attack a system with a single trace. In the ChipWhisperer tutorials, we'll save ourselves a bit of processing time and only record a few thousand traces for generating the templates, meaning that we'll need more attack traces to recover the key from the victim.

← Older revision		Revision as of 20:42, 25 March 2017
Line 216:		Line 216:

	It may be interesting to experiment with different amounts of processing. Can you break AES in one trace? How many template traces does it take?		It may be interesting to experiment with different amounts of processing. Can you break AES in one trace? How many template traces does it take?
		+
		+	[[Category:Theory]]

@@ Line 97: / Line 97: @@
 === Picking POIs ===
-''TODO; want to write tutorial first''
+There are several ways to pick the most important points in each of the traces. Generally, the aim is to find points that vary strongly between different operations (subkeys or Hamming weights). The simplest method -- the one that we'll use here -- is the ''sum of differences'' method.
 == Analyzing the Data ==

@@ Line 86: / Line 86: @@
 One of the downsides of template attacks is that they require a great number of traces to be preprocessed before the attack can begin. This is mainly for statistical reasons. In order to come up with a good distribution to model the power traces for ''every key'', we need a large number of traces for ''every key''. For example, if we're going to attack a single subkey of AES-128, then we need to create 256 power consumption models (one for every number from 0 to 255). In order to get enough data to make good models, we need tens of thousands of traces.
-Note that we don't have to model every single key. One good alternative is to model a sensitive part of the algorithm, like the substitution box in AES. We can get away with a much smaller number of traces here; if we make a model for every possible Hamming weight, then we would end up with 17 models, which is an order of magnitude smaller. However, then we can't recover the key from a single attack trace - we need more information to recover the secret key.
+Note that we don't have to model every single key. One good alternative is to model a sensitive part of the algorithm, like the substitution box in AES. We can get away with a much smaller number of traces here; if we make a model for every possible Hamming weight, then we would end up with 9 models, which is an order of magnitude smaller. However, then we can't recover the key from a single attack trace - we need more information to recover the secret key.
 == Points of Interest ==
@@ Line 100: / Line 100: @@
 == Analyzing the Data ==
-Suppose that we've picked <math>I</math> points of interest, which are at samples <math>s_i</math> (<math>0 \le i < I</math>). Then, our goal is to find a mean and covariance matrix for every operation (every choice of subkey or intermediate Hamming weight). Let's say that there are <math>K</math> of these operations (maybe 256 subkeys or 17 possible Hamming weights).
+Suppose that we've picked <math>I</math> points of interest, which are at samples <math>s_i</math> (<math>0 \le i < I</math>). Then, our goal is to find a mean and covariance matrix for every operation (every choice of subkey or intermediate Hamming weight). Let's say that there are <math>K</math> of these operations (maybe 256 subkeys or 9 possible Hamming weights).
 For now, we'll look at a single operation <math>k</math> (<math>0 \le k < K</math>). The steps are:

@@ Line 147: / Line 147: @@
 = Using the Template =
-Apply the template by measuring more traces
+With a template in hand, we can finish our attack. For the attack, we need a smaller number of traces - we'll say that we have <math>A</math> traces. The sample values will be labeled <math>a_{j, s_i}</math> (<math>1 \le j \le A</math>).
-== Finding the Key ==
+== Applying the Template ==
-How to use the template to narrow down the possibilities
+First, let's apply the template to a single trace. Our job is to decide how likely all of our key guesses are. We need to do the following:
 == Attack Time ==

← Older revision		Revision as of 13:32, 25 May 2016
Line 153:		Line 153:

	== Attack Time ==		== Attack Time ==
−	~~Shouldn't take long~~ to attack	+	The number of attack traces required to complete a template attack can vary wildly depending on the quality of the preprocessing. As described in the original papers on template attacks (Chari, Rao, and Rohatgi), when using high-quality templates made from many traces, it is possible to attack a system with a single trace. In the ChipWhisperer tutorials, we'll save ourselves a bit of processing time and only record a few thousand traces for generating the templates, meaning that we'll need more attack traces to recover the key from the victim.
		+
		+	It may be interesting to experiment with different amounts of processing. Can you break AES in one trace? How many template traces does it take?

@@ Line 44: / Line 44: @@
 == Multivariate Statistics ==
-''TODO: basics of multivariable stats''
+The 1-variable Gaussian distribution works well for one measurement. What if we're working with more than one random variable?
 = Profiling a Device =