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!

Original writeup (https://github.com/b01lers/b01lers-library/tree/master/2019ritsec/crypto/500-evil-accountant).