Attacking TEA with CPA - Revision history

Fheubach at 13:11, 1 May 2018

2018-05-01T13:11:03Z

Coflynn at 18:00, 25 March 2017

2017-03-25T18:00:09Z

Coflynn: Add link to xbox attack

2016-07-05T16:09:58Z

Add link to xbox attack

Gdeon: /* Attacking the Key */

2016-07-05T15:17:40Z

‎Attacking the Key

Show changes

Gdeon: /* Searching for Leakage */

2016-07-05T14:31:16Z

‎Searching for Leakage

Gdeon: /* Capture */

2016-07-05T13:47:14Z

‎Capture

Gdeon at 13:14, 5 July 2016

2016-07-05T13:14:33Z

Gdeon: /* TEA Encryption */

2016-07-04T20:23:11Z

‎TEA Encryption

Gdeon: Created page with "= TEA Encryption = TEA (Tiny Encryption Algorithm) is a simple encryption algorithm that is meant to be simple enough to memorize. It uses a 128 bit key to encrypt 64 bits of..."

2016-07-04T18:58:08Z

Created page with "= TEA Encryption = TEA (Tiny Encryption Algorithm) is a simple encryption algorithm that is meant to be simple enough to memorize. It uses a 128 bit key to encrypt 64 bits of..."

New page

= TEA Encryption =
TEA (Tiny Encryption Algorithm) is a simple encryption algorithm that is meant to be simple enough to memorize. It uses a 128 bit key to encrypt 64 bits of plaintext with the following C code:
<pre>
void tea_encrypt(uint32_t* v, uint32_t* k)
{
uint32_t sum=0, i;
uint32_t delta= 0x9e3779b9;
for (i=0; i < 32; i++) {
sum += delta;
v[0] += ((v[1]<<4) + k[0]) ^ (v[1] + sum) ^ ((v[1]>>5) + k[1]);
v[1] += ((v[0]<<4) + k[2]) ^ (v[0] + sum) ^ ((v[0]>>5) + k[3]);
}
}
</pre>
If you're used to looking at the AES algorithm, this one probably looks extremely simple. However, it is surprisingly secure. As of 2016, very few attacks on TEA are known - the best cryptanalysis results require <math>2^{121.5}</math> guesses against a shortened version of the algorithm! The only real weakness is that every key has three other equivalent keys - that is, there are four different keys that all give the exact same encrypted output. This is not a showstopper because <math>2^{126}</math> keys is still too many to brute-force.

@@ Line 1: / Line 1: @@
-= TEA Encryption =
+== TEA Encryption ==
 TEA (Tiny Encryption Algorithm) is a simple encryption algorithm that is meant to be simple enough to memorize. It uses a 128 bit key to encrypt 64 bits of plaintext with the following C code:
 <pre>
@@ Line 32: / Line 32: @@
 However, this is enough information to recover both of these words. Once we know these 64 bits, the second half of the key can be recovered in exactly the same way.
-= Firmware =
+== Firmware ==
 The AES SimpleSerial target was adapted to use TEA encryption instead of AES. This new target uses the exact same commands as the original SimpleSerial target:
 * <code>kKEY</code> loads KEY as the 128 bit encryption key
@@ Line 39: / Line 39: @@
 This firmware is available in <code>chipwhisperer/hardware/victims/firmware/simpleserial-tea</code>. It uses the same build process as the other targets - simply run <code>make</code> to produce the hex file.
-= Capture =
+== Capture ==
 The setup for this capture routine will be pretty straightforward because the firmware is so close to the SimpleSerial targets we've attacked before. Only a small number of modifications need to be made to adapt the capture script for TEA.
@@ Line 52: / Line 52: @@
 For our analysis, we'll need two sets of data. The first should have random keys and plaintexts, and the second should have a fixed ("secret") key and random plaintexts. For this guide, I'll be using a fixed key of <code>00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F</code>. Capture about 1000 traces for each set and put all of the data files in a convenient place.
-= Analysis =
+== Analysis ==
-== Searching for Leakage ==
+=== Searching for Leakage ===
 Our first step is to look through the traces to see if there's any visible leakage. We can do this by sorting the traces into appropriate groups and comparing the averages of each group. This section will look a lot like [[Tutorial B6 Breaking AES (Manual CPA Attack)]], so you might want to make a copy of this script for a starting point.
@@ Line 146: / Line 146: @@
 Change this <code>s</code> to <code>0</code> and re-make the firmware. Then, repeat the capture setup and record another 2000 traces. Re-run the analysis script and confirm that the leakage is clearly visible.
-== Attacking the Key ==
+=== Attacking the Key ===
 Since we know that our traces show us some leakage, we can complete our attack. We'll start a new script by writing functions to calculate our three attack point values:

← Older revision		Revision as of 18:00, 25 March 2017
Line 346:		Line 346:
	* We had to use a lower optimization level so that we could see the power signature from the sensitive attack points. Can we avoid this? Maybe it's possible to use a different sampling method to find more leakage.		* We had to use a lower optimization level so that we could see the power signature from the sensitive attack points. Can we avoid this? Maybe it's possible to use a different sampling method to find more leakage.
	* A template attack might be a more powerful way to perform this attack. There are several points that we could create a template for, including the three points that we examined in this attack.		* A template attack might be a more powerful way to perform this attack. There are several points that we could create a template for, including the three points that we examined in this attack.
		+
		+
		+	[[Category:Examples]]
		+	[[Category:Half Baked Tutorials]]

@@ Line 13: / Line 13: @@
+}
 </pre>
-If you're used to looking at the AES algorithm, this one probably looks extremely simple. However, it is surprisingly secure. As of 2016, very few attacks on TEA are known - the best cryptanalysis results require <math>2^{121.5}</math> guesses against a shortened version of the algorithm! The only real weakness is that every key has three other equivalent keys - that is, there are four different keys that all give the exact same encrypted output. This is not a showstopper because <math>2^{126}</math> keys is still too many to brute-force.
+If you're used to looking at the AES algorithm, this one probably looks extremely simple. However, it is surprisingly secure. As of 2016, very few attacks on TEA are known - the best cryptanalysis results require <math>2^{121.5}</math> guesses against a shortened version of the algorithm! The only real weakness is that every key has three other equivalent keys - that is, there are four different keys that all give the exact same encrypted output. This is not a showstopper because <math>2^{126}</math> keys is still too many to brute-force (it does mean the algorithm is a poor choice for certain applications such as hashes, something the [https://web.archive.org/web/20090416175601/http://www.xbox-linux.org/wiki/17_Mistakes_Microsoft_Made_in_the_Xbox_Security_System#The_TEA_Hash XBox security missed]).
 In order to complete a CPA attack, we need to find some sensitive points of the algorithm. Breaking up the first round of the one-liner

@@ Line 54: / Line 54: @@
 = Analysis =
 == Searching for Leakage ==
 == Attacking the Key ==

@@ Line 40: / Line 40: @@
 = Capture =
-== Capture Setup ==
+The setup for this capture routine will be pretty straightforward because the firmware is so close to the SimpleSerial targets we've attacked before. Only a small number of modifications need to be made to adapt the capture script for TEA.
-== Sample Outputs ==
 = Analysis =

← Older revision		Revision as of 13:14, 5 July 2016
Line 31:		Line 31:
	# The last XOR combines the first two results, which use both words of the key (<code>k[0]</code> and <code>k[1]</code>). This means that we can only use it if we already know some of the bits in one of these keys (ie: we can only find the first byte of <code>k[0]</code> if we know the first byte of <code>k[1]</code>).		# The last XOR combines the first two results, which use both words of the key (<code>k[0]</code> and <code>k[1]</code>). This means that we can only use it if we already know some of the bits in one of these keys (ie: we can only find the first byte of <code>k[0]</code> if we know the first byte of <code>k[1]</code>).
	However, this is enough information to recover both of these words. Once we know these 64 bits, the second half of the key can be recovered in exactly the same way.		However, this is enough information to recover both of these words. Once we know these 64 bits, the second half of the key can be recovered in exactly the same way.
		+
		+	= Firmware =
		+	The AES SimpleSerial target was adapted to use TEA encryption instead of AES. This new target uses the exact same commands as the original SimpleSerial target:
		+	* <code>kKEY</code> loads KEY as the 128 bit encryption key
		+	* <code>pPLAINTEXT</code> loads PLAINTEXT as the 64 bit plaintext and begins the encryption routine
		+	* <code>rRESPONSE</code> is the reply from the target, where RESPONSE is the 64 bit ciphertext
		+	This firmware is available in <code>chipwhisperer/hardware/victims/firmware/simpleserial-tea</code>. It uses the same build process as the other targets - simply run <code>make</code> to produce the hex file.
		+
		+	= Capture =
		+	== Capture Setup ==
		+	== Sample Outputs ==
		+
		+	= Analysis =
		+	== Searching for Leakage ==
		+	== Attacking the Key ==
		+
		+	= More Ideas =
		+	This guide has walked through a very basic CPA attack on TEA encryption. However, we could take this a lot further...
		+	* This was a very "manual" attack: we had to guide our code through each of the single-byte attacks. It would be good to have a more automatic attack that combines all of the information from all three attack points, rather than picking and choosing bytes to attack.
		+	* We had to use a lower optimization level so that we could see the power signature from the sensitive attack points. Can we avoid this? Maybe it's possible to use a different sampling method to find more leakage.
		+	* A template attack might be a more powerful way to perform this attack. There are several points that we could create a template for, including the three points that we examined in this attack.

← Older revision		Revision as of 20:23, 4 July 2016
Line 14:		Line 14:
	</pre>		</pre>
	If you're used to looking at the AES algorithm, this one probably looks extremely simple. However, it is surprisingly secure. As of 2016, very few attacks on TEA are known - the best cryptanalysis results require <math>2^{121.5}</math> guesses against a shortened version of the algorithm! The only real weakness is that every key has three other equivalent keys - that is, there are four different keys that all give the exact same encrypted output. This is not a showstopper because <math>2^{126}</math> keys is still too many to brute-force.		If you're used to looking at the AES algorithm, this one probably looks extremely simple. However, it is surprisingly secure. As of 2016, very few attacks on TEA are known - the best cryptanalysis results require <math>2^{121.5}</math> guesses against a shortened version of the algorithm! The only real weakness is that every key has three other equivalent keys - that is, there are four different keys that all give the exact same encrypted output. This is not a showstopper because <math>2^{126}</math> keys is still too many to brute-force.
		+
		+	In order to complete a CPA attack, we need to find some sensitive points of the algorithm. Breaking up the first round of the one-liner
		+	<pre>
		+	v[0] += ((v[1]<<4) + k[0]) ^ (v[1] + sum) ^ ((v[1]>>5) + k[1]);
		+	</pre>
		+	gives
		+	<pre>
		+	uint32_t a = (v[1] << 4) + k[0]; // Attack point 1
		+	uint32_t b = v[1] + 0x9e3779b9; //
		+	uint32_t c = (v[1] >> 5) + k[1]; // Attack point 2
		+	v[0] += (a ^ b ^ c); // Attack point 3
		+	</pre>
		+	The three attack points here are good spots to attack because they are non-linear: addition can cause a single changed bit to carry through to several bits of the result. However, all three of these points have limitations.
		+	# This expression includes a left-shift of 4 bits, so we have no control over the bottom 4 bits. This means we cannot use CPA to recover all 32 bits of <code>k[0]</code> - we can only get 28 of them.
		+	# Similarly, this expression includes a right-shift of 5 bits, so we can only get at the bottom 27 bits.
		+	# The last XOR combines the first two results, which use both words of the key (<code>k[0]</code> and <code>k[1]</code>). This means that we can only use it if we already know some of the bits in one of these keys (ie: we can only find the first byte of <code>k[0]</code> if we know the first byte of <code>k[1]</code>).
		+	However, this is enough information to recover both of these words. Once we know these 64 bits, the second half of the key can be recovered in exactly the same way.