Changes

== TEA Encryption ==

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]).

== Firmware ==

== Capture ==

== Analysis == === Searching for Leakage ===

=== 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: <pre>def intermediate_1(v, k): v1 = ( v[4] << 24 | v[5] << 16 | v[6] << 8 | v[7]) k0 = ( k[0] << 24 | k[1] << 16 | k[2] << 8 | k[3]) return ((v1 << 4) + k0) & 0xffffffff def intermediate_2(v, k): v1 = ( v[4] << 24 | v[5] << 16 | v[6] << 8 | v[7]) k1 = ( k[4] << 24 | k[5] << 16 | k[6] << 8 | k[7]) return ((v1 >> 5) + k1) & 0xffffffff def intermediate_3(v, k): v0 = ( v[0] << 24 | v[1] << 16 | v[2] << 8 | v[3]) v1 = ( v[4] << 24 | v[5] << 16 | v[6] << 8 | v[7]) k0 = ( k[0] << 24 | k[1] << 16 | k[2] << 8 | k[3]) k1 = ( k[4] << 24 | k[5] << 16 | k[6] << 8 | k[7]) int1 = ((v1 << 4) + k0) & 0xffffffff int2 = (v1 + 0x9e3779b9) & 0xffffffff int3 = ((v1 >> 5) + k1) & 0xffffffff return v0 + (int1 ^ int2 ^ int3)</pre> Then, we'll copy in the CPA attack script from Tutorial B6 and make some modifications. The full script for the TEA attack is:<pre>traces = np.load('traces/O0_rand_traces.npy')pt = np.load('traces/O0_rand_textin.npy')knownkey = np.load('traces/O0_rand_keylist.npy')#print knownkeynumtraces = np.shape(traces)[0]numpoint = np.shape(traces)[1] # Use less than the maximum traces by setting numtraces to something smallernumtraces = 1000bestguess = 0 cpaoutput = [0]*256maxcpa = [0]*256for kguess in range(0, 256): print "Key = %02x: "%(kguess), # Build our key guess k = [0, 0, 0, kguess, 0, 0, 0, 0]  #Initialize arrays and variables to zero sumnum = np.zeros(numpoint) sumden1 = np.zeros(numpoint) sumden2 = np.zeros(numpoint)  # Calculate hypothesis = Hamming weight of intermediate values hyp = np.zeros(numtraces) for tnum in range(0, numtraces): int = (intermediate_1(pt[tnum], k) >> 0) & 0xff hyp[tnum] = HW[int]  #Means of hypothesis and traces meanh = np.mean(hyp, dtype=np.float64) meant = np.mean(traces, axis=0, dtype=np.float64)  #For each trace, calculate correlation 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 = np.argmax(maxcpa)cparefs = np.argsort(maxcpa)[::-1] print "Best Key Guess: %02x"%(bestguess)print [hex(c) for c in cparefs]</pre> There's one line of this script that we'll need to change a few times. In the key-guessing loop, we build the key by writing<pre>k = [0, 0, 0, kguess, 0, 0, 0, 0]</pre>and we calculate the intermediate value as<pre>int = (intermediate_1(pt[tnum], k) >> 0) & 0xff</pre>This means that we're only going to be modifying one byte of our guess - the other 7 bytes will remain unchanged - and we're only looking at the first byte of attack point 1. Once we're done attacking this byte, we can move our guess to a different byte and examine a different part of the intermediate value to continue the attack. Run the script. You should see an output that looks like<pre>Key = 00: 0.491256496954Key = 01: 0.491256496954Key = 02: 0.491256496954Key = 03: 0.491256496954Key = 04: 0.491256496954Key = 05: 0.491256496954Key = 06: 0.491256496954Key = 07: 0.491256496954Key = 08: 0.491256496954Key = 09: 0.491256496954Key = 0a: 0.491256496954Key = 0b: 0.491256496954Key = 0c: 0.491256496954Key = 0d: 0.491256496954Key = 0e: 0.491256496954Key = 0f: 0.491256496954Key = 10: 0.25438721963Key = 11: 0.25438721963Key = 12: 0.25438721963Key = 13: 0.25438721963Key = 14: 0.25438721963Key = 15: 0.25438721963Key = 16: 0.25438721963Key = 17: 0.25438721963Key = 18: 0.25438721963Key = 19: 0.25438721963Key = 1a: 0.25438721963Key = 1b: 0.25438721963Key = 1c: 0.25438721963Key = 1d: 0.25438721963Key = 1e: 0.25438721963Key = 1f: 0.25438721963...<removed>Key = f0: 0.208801829135Key = f1: 0.208801829135Key = f2: 0.208801829135Key = f3: 0.208801829135Key = f4: 0.208801829135Key = f5: 0.208801829135Key = f6: 0.208801829135Key = f7: 0.208801829135Key = f8: 0.208801829135Key = f9: 0.208801829135Key = fa: 0.208801829135Key = fb: 0.208801829135Key = fc: 0.208801829135Key = fd: 0.208801829135Key = fe: 0.208801829135Key = ff: 0.208801829135Best Key Guess: 00['0x0', '0xb', '0x4', '0x5', '0x6', '0x7', '0x8', '0xa', '0x9', '0x3', '0xc', '0xd', ...</pre>This tells us a few things. First of all, like we expected, we can't attack the bottom four bits of <code>k[0]</code> because the correlation coefficient isn't affected by these bits. Second, the most likely value of the top four bits is <code>0x0</code>. Change the attack script to<pre>k = [0, 0, kguess, 0x00, 0, 0, 0, 0]...int = (intermediate_1(pt[tnum], k) >> 8) & 0xff</pre>and run it again. The correlation coefficients should be much different. My output shows <code>Best Key Guess: 02</code>, which is correct.  Continue this process:* Repeat the same attack for the first two bytes of the key. <code>intermediate_1</code> shifted by 16 and 24 bits should have no trouble with this.* To get the other half of the key, change the attack to<pre>k = [0x00, 0x01, 0x02, 0x00, 0, 0, 0, kguess]...int = (intermediate_2(pt[tnum], k) >> 0) & 0xff</pre>: and attack all four bytes like before. Note that you will not recover the top 5 bits of <code>k[1]</code> this way.* To clean up the two incomplete bytes, switch to <code>intermediate_3</code> and retry these two guesses. If all goes well, you should be able to recover the entire key this way!