Rating:
So, we have a json file with a bunch of plaintexts and a bunch of traces: https://github.com/b01lers/b01lers-library/blob/master/2019ritsec/crypto/500-evil-accountant/traces.json
The challenge text references "CPA" and "Pearson", which will probably lead googlers to this page:https://wiki.newae.com/Correlation_Power_Analysis
As this suggests, we want to carry out a Hamming distance-based Correlative Power analysis attack that should allow us to drastically reduce our key search space.
Instead of suffering through my explanation of what that means, I suggest reading the above. I got some code from here: https://wiki.newae.com/Correlation_Power_Analysis
And modified it slightly to accept our input. I ended up with this:
```
import json
import math
import numpy as np
HW = [bin(n).count("1") for n in range(0,256)]
s=(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 s[pt ^ keyguess]
f = open("traces.json")
data = json.load(f)
traces = np.array(data["traces"])
pt = np.array(data["plaintexts"])
numtraces = np.shape(traces)[0] - 1
numpoint = np.shape(traces)[1]
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 {:02d}, hyp = 0x{:02x}".format(bnum, kguess))
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)]
meanh = np.mean(hyp, dtype=np.float64)
meant = np.mean(traces, axis=0, dtype=np.float64)
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]
for b in bestguess:
print("{:02x}, ".format(b), end="")
```
This gives us the key:
45, 7e, 15, d7, 58, ae, d2, a6, ab, f7, 15, 88, 09, cf, 4f, 3c
However decrypting using that key yields some garbage. We need to listen to the second part of the description that tells us "something is up with the oscilloscope, might have to brute force a few bytes of the key". At this point, I tried brute forcing one, then two bytes of the key to no avail. I was going to bed, so I set a script to brute force three bytes of the key and went to sleep hoping I'd have some results in the morning. I added on to my script:
```
import json
import math
import numpy as np
from Crypto.Cipher import AES
import base64
import itertools
HW = [bin(n).count("1") for n in range(0,256)]
s=(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 s[pt ^ keyguess]
f = open("traces.json")
data = json.load(f)
traces = np.array(data["traces"])
pt = np.array(data["plaintexts"])
numtraces = np.shape(traces)[0] - 1
numpoint = np.shape(traces)[1]
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 {:02d}, hyp = 0x{:02x}".format(bnum, kguess))
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)]
meanh = np.mean(hyp, dtype=np.float64)
meant = np.mean(traces, axis=0, dtype=np.float64)
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]
for b in bestguess:
print("{:02x}, ".format(b), end="")
ciphertext_cpa_account = base64.b64decode("5z+joNqYQhpXz/2Njz+/ePD8m8+A2S3ZZ5tWIvRw1ueq4cO9EYgvQjGKeJzFtIZF9hg9/2NGIFQqgDfwxNHUiQ==")
ciphertext = ciphertext_cpa_account
key = bestguess #[0x45, 0x7e, 0x15, 0xd7, 0x58, 0xae, 0xd2, 0xa6, 0xab, 0xf7, 0x15, 0x88, 0x09, 0xcf, 0x4f, 0x3c]
indices = [i for i in range(16)]
values = [i for i in range(256)]
# keystring = bytes.fromhex("".join("{:02x}".format(k) for k in key))
# keys.append(keystring)
for pair in itertools.permutations(indices, 3):
for vals in itertools.permutations(values, 3):
k2 = key.copy()
k2[pair[0]] = vals[0]
k2[pair[1]] = vals[1]
k2[pair[2]] = vals[2]
ks = bytes.fromhex("".join("{:02x}".format(k) for k in k2))
cipher = AES.new(ks, AES.MODE_ECB)
plaintext = cipher.decrypt(ciphertext)
if b"RITSEC" in plaintext:
print(plaintext)
print(plaintext, k2)
del k2
```
Note that for two byte or less brute force, precomputing all the possible keys and then trying them is faster than this, but I don't have enough RAM for a three byte brute force's keyspace, so this is what I ended up with. In the morning, I woke up to:
b'RITSEC{K0rr3LA710n_CAN_50M371m35_1MpLY_cau5A710N_24544110ad75a4}'
Solved!
