3-Multibit.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# Multi-bit leakage modelling\n",
    "\n",
    "Fitting multi-bit models for the leakage of the AES S-box output. \n",
    "\n",
    "The first model is of the form\n",
    "$$\\beta_0x_0 + \\beta_1x_1 + \\ldots + \\beta_7x_7 + \\beta_{const}$$\n",
    "\n",
    "where $x_i$ is bit $i$ of byte $x$, and 9 coefficients $\\beta_i$ and $\\beta_{const}$ are to be estimated\n",
    "with linear regression using ordinary least squares. $\\beta_{const}$ is the intercept and will not be used later (correlation is invariant to it).\n",
    "\n",
    "Other models are:\n",
    "* 2-component model (a reduced 8-component model with only 2 LSB's considered)\n",
    "* Hamming weight model, i.e. with only one basis function $g_0 = \\text{HW}(x)$\n",
    "* 256-component model with all possible products of the 8 bits\n",
    "\n",
    "Observe how the resulting coefficients match the single-bit model from the previous example in the sense\n",
    "of the contribution of each bit to the model.\n",
    "\n",
    "Results in terms of the adjusted coefficient of determination $\\bar R^2$:\n",
    "* HW model: 0.328\n",
    "* 9-component model: 0.435\n",
    "* 2-component model: 0.324\n",
    "* 256-component model: 0.437\n",
    "\n",
    "Part of the leakage modeling tutorial, license is GPLv3, see https://www.gnu.org/licenses/gpl-3.0.en.html<br>\n",
    "Requires traces and data from [pysca toolbox](https://github.com/ikizhvatov/pysca)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/ilya/anaconda3/lib/python3.6/site-packages/statsmodels/compat/pandas.py:56: FutureWarning: The pandas.core.datetools module is deprecated and will be removed in a future version. Please use the pandas.tseries module instead.\n",
      "  from pandas.core import datetools\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "import statsmodels.api as sm\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The functions in the next cell do 2 things in the same place:\n",
    "1. define basis functions $g_i(x)$ of a leakage model for a byte $x$:\n",
    "    $$\\beta_0g_0(x) + \\beta_1g_1(x) + \\ldots + \\beta_ng_n(x)$$\n",
    "1. compute and return the values of $g_i(x)$ such that they can be used later to obtain rows of the matrix for linear regression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# A simple 9-component linear model (sum of bits with different\n",
    "#  coefficients): gi = xi, 0 <= i < 8.\n",
    "def leakageModel9(x):\n",
    "    g = []\n",
    "    for i in range(0, 8):\n",
    "        bit = (x >> i) & 1  # this is the definition: gi = [bit i of x]\n",
    "        g.append(bit)\n",
    "    return g\n",
    "# same but only two LSB's included (because teh above shows that they are the\n",
    "#  most contributing ones)\n",
    "def leakageModel2(x):\n",
    "    g = []\n",
    "    for i in range(0, 2):\n",
    "        bit = (x >> i) & 1\n",
    "        g.append(bit)\n",
    "    return g\n",
    "\n",
    "# A Hamming weight model: g0 = HW(x)\n",
    "def leakageModelHW(x):\n",
    "    g = []\n",
    "    hw = byteHammingWeight[x]  # this is the definition: gi = HW(x)\n",
    "    g.append(hw)\n",
    "    return g\n",
    "\n",
    "# An 'all 256 bit combinations' model:\n",
    "# a) helper from http://wiki.python.org/moin/BitManipulation\n",
    "def parityOf(int_type):\n",
    "    parity = 0\n",
    "    while (int_type):\n",
    "        parity = ~parity\n",
    "        int_type = int_type & (int_type - 1)\n",
    "    if (parity != 0): # to convert -1 to 1\n",
    "        parity = 1\n",
    "    return(parity)\n",
    "# b) the model itself\n",
    "def leakageModel256(x):\n",
    "    g = []\n",
    "    # note that we start from 1 to exclude case 0 which means the function\n",
    "    # does not depend on any bit of x, i.e. a constant - we will add the\n",
    "    # constant explicitly later as the last column.\n",
    "    for i in np.arange(1, 256, dtype='uint8'):\n",
    "        xmasked = x & i\n",
    "        gi = parityOf(xmasked)\n",
    "        g.append(gi)\n",
    "    return g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Load AES S-box and the table for getting the Hamming weight of a byte"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "sbox = np.load('../data/aessbox.npy')\n",
    "byteHammingWeight = np.load('../data/bytehammingweight.npy')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Load samples and data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "inputRange = range(0, 1000) # range for traces (not samples!)\n",
    "SboxNum = 0\n",
    "SampleNum = 1025\n",
    "\n",
    "npzfile = np.load('../traces/swaes_atmega_power.npz')\n",
    "data = npzfile['data'][inputRange,SboxNum]\n",
    "traces = npzfile['traces'][inputRange,SampleNum]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, knowing the key byte, we compute the intermediate variable values: S-box outputs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "key = b'\\x2b\\x7e\\x15\\x16\\x28\\xae\\xd2\\xa6\\xab\\xf7\\x15\\x88\\x09\\xcf\\x4f\\x3c'\n",
    "keyByte = np.uint8(key[SboxNum])\n",
    "sBoxOut = sbox[data ^ keyByte]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Build the system of equations and solve it using OLS. Notice now there are several coefficients and a constant in the results.\n",
    "\n",
    "leakageModel9 can be replace to any other basis function set, e.g. leakageModel256, for comparison."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                            OLS Regression Results                            \n",
      "==============================================================================\n",
      "Dep. Variable:                      y   R-squared:                       0.446\n",
      "Model:                            OLS   Adj. R-squared:                  0.442\n",
      "Method:                 Least Squares   F-statistic:                     99.89\n",
      "Date:                Thu, 28 Sep 2017   Prob (F-statistic):          1.03e-121\n",
      "Time:                        17:03:53   Log-Likelihood:                -3200.1\n",
      "No. Observations:                1000   AIC:                             6418.\n",
      "Df Residuals:                     991   BIC:                             6462.\n",
      "Df Model:                           8                                         \n",
      "Covariance Type:            nonrobust                                         \n",
      "==============================================================================\n",
      "                 coef    std err          t      P>|t|      [0.025      0.975]\n",
      "------------------------------------------------------------------------------\n",
      "x1             5.9166      0.378     15.652      0.000       5.175       6.658\n",
      "x2             6.6095      0.381     17.346      0.000       5.862       7.357\n",
      "x3             2.7860      0.378      7.365      0.000       2.044       3.528\n",
      "x4             3.0673      0.379      8.083      0.000       2.323       3.812\n",
      "x5             2.9167      0.379      7.689      0.000       2.172       3.661\n",
      "x6             2.1117      0.379      5.576      0.000       1.369       2.855\n",
      "x7             0.8056      0.378      2.129      0.033       0.063       1.548\n",
      "x8             1.3553      0.378      3.588      0.000       0.614       2.097\n",
      "const       -105.3910      0.555   -189.956      0.000    -106.480    -104.302\n",
      "==============================================================================\n",
      "Omnibus:                       84.222   Durbin-Watson:                   2.267\n",
      "Prob(Omnibus):                  0.000   Jarque-Bera (JB):               27.234\n",
      "Skew:                          -0.015   Prob(JB):                     1.22e-06\n",
      "Kurtosis:                       2.192   Cond. No.                         6.24\n",
      "==============================================================================\n",
      "\n",
      "Warnings:\n",
      "[1] Standard Errors assume that the covariance matrix of the errors is correctly specified.\n"
     ]
    }
   ],
   "source": [
    "X = map(leakageModel9, sBoxOut)             # left-hand part of the system\n",
    "A = sm.add_constant(list(X), prepend=False) # add constant coefficient (trailing column of ones)\n",
    "results = sm.OLS(traces, A).fit()           # the OLS itself\n",
    "print(results.summary())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Save the model (do not forget to rename the file later!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "np.save('results/lrmodel', results.params)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Plot the coefficients except for the intercept"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYQAAAEPCAYAAABCyrPIAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAADd5JREFUeJzt3W9snedZgPHrrpuC2SqMiIWIs5AKTZ5W0sTIqpiCJigM\nd4BoFIZoJRDwxV8o6qph1IgP48tIJUsoSEyTrLYrEisVK6mZSpk11Jppk4jq1FHTNjOUqlPjMNXV\ncLduVpukNx/8uPlTp7N9bD/nnPf6SZF9Tl7Xt/ohl573z3kiM5Ek6braA0iS2oNBkCQBBkGSVBgE\nSRJgECRJhUGQJAEGQZJUGARJEmAQJEnF9bUHWI+dO3fm3r17a48hSR3j5MmTr2dm/1qO7agg7N27\nl5mZmdpjSFLHiIhvr/VYTxlJkgCDIEkqDIIkCTAIkqTCIEiSgA67y0jvb3J2nvGpOc4tLrGrr5ex\nkUEODQ3UHktShzAIXWJydp4jx0+zdP4iAPOLSxw5fhrAKEhaE08ZdYnxqbl3Y7Bi6fxFxqfmKk0k\nqdMYhC5xbnFpXe9L0tUMQpfY1de7rvcl6WoGoUuMjQzSu6Pnivd6d/QwNjJYaSJJncYgdIlDQwMc\nPbyPnrfegEwG+no5enifF5QlrZl3GXWRQ0MDHLt3AoDp6em6w0jqOK4QJEmAQZAkFQZBkgQYBElS\nYRAkSYBBkCQVBkGSBBgESVJhECRJgEGQJBVVgxARfRHxWER8KyLORMTHas4jSU1W+7OM/hb4amZ+\nKiJuAH6i8jyS1FjVghARPwl8HPhjgMx8G3i71jyS1HQ1Vwg3AQvAFyNiP3ASuCczf3D5QRExCowC\n7NmzZ9uHvBY3tJfUbWpeQ7ge+EXgC5k5BPwAuO/qgzJzIjOHM3O4v79/u2dc1cqG9vOLSySXNrSf\nnJ2vPZokbVjNIJwFzmbmifL6MZYD0fbc0F5SN6oWhMz8DvBqRKzs8fhrwIu15lkPN7SX1I1q32X0\nZ8CXyh1GLwN/UnmeNdnV18v8Kv/4u6G9pE5W9TmEzDxVrg/ckpmHMvP/as6zVm5oL6kb+aTyBrih\nvaRuVPuUUcdyQ3tJ3cYVgiQJMAiSpMIgSJIAgyBJKgyCJAkwCJKkwiBIkgCDIEkqDIIkCTAIkqTC\nIEiSAIMgSSoMgiQJMAiSpMIgSJIAgyBJKgyCJAkwCJKkwiBIkoDKeypHxCvA94GLwIXMHK45jyQ1\nWdUgFL+ama/XHkKSms5TRpIkoH4QEvj3iDgZEaOrHRARoxExExEzCwsL2zyeJDVH7SD8cmYeAD4J\n/GlEfPzqAzJzIjOHM3O4v79/+yeUpIaoGoTMnC9fXwMeB26tOY8kNVm1IETEByLixpXvgd8Anq81\njyQ1Xc27jH4GeDwiVuZ4JDO/WnEeSWq0akHIzJeB/bV+vyTpSrUvKkuS2oRBkCQBBkGSVBgESRJg\nECRJhUGQJAEGQZJUGARJEmAQJEmFQZAkAQZBklQYBEkSYBAkSYVBkCQBBkGSVBgESRJgECRJhUGQ\nJAEGQZJUGARJEmAQJElF9SBERE9EzEbEE7VnkaQmqx4E4B7gTO0hJKnpqgYhInYDvwU8UHMOSVL9\nFcIx4C+Ad651QESMRsRMRMwsLCxs32SS1DDVghARvw28lpkn3++4zJzIzOHMHO7v79+m6SSpeWqu\nEA4CvxMRrwCPArdFxD9UnEeSGq1aEDLzSGbuzsy9wJ3AU5n5B7XmkaSmq30NQZLUJq6vPQBAZk4D\n05XHkKRGc4UgSQIMgiSpMAiSJMAgSJIKgyBJAgyCJKkwCJIkwCBIkgqDIEkCDIIkqTAIkiRgg0GI\niHvL15sjomdzR5Ik1bDRD7c7Vb7+NfCRiFgCXgBOA89n5hObMZwkafusKQgREZmZK68z8+ny9Y7y\n9x8Ebgb2Ab8OGARJ6jA/8pRRRPwe8N2IuBARJyPi9yPiuog4FhEnImIc+OnMPJGZD2Tmp7d+bEnS\nZlvLNYTPAX8H/BIwCXyR5RXAHwH/wfKq4GRE3LxVQ0qStt5aThkNAA9m5ivATNkD+WHg7sz8AkBE\nfI7lcBzamjElSVttLSuE/wEOXvb6y+XrM5e99zDLKwhJUodaywrhfuCBiPgF4ElgFhgG5i475kag\nd/PHkyRtlx8ZhMx8JCK+B3wG+HMgWF41PBsRzwJngL8EvrmVg0qbZXJ2nvGpOc4tLrGrr5exkUEO\nDQ3UHkuqbk23nZbnCp6IiF7gFuAAMAT8LssXlXuB70TEvwDPAc9l5pev9d+TapmcnefI8dMsnb8I\nwPziEkeOnwYwCmq8dT2YlplLwInyB4CIuA4YZDkQB1i+ljDKpWsNq4qIHwe+DvxYmeOxzPzseuaR\n1mt8au7dGKxYOn+R8ak5g6DG2+iTyu/KzHdYPm10BnhkHT/6FnBbZr4ZETuAb0TEv2Xmf7Y6k3Qt\n5xaX1vW+1CTVPtwul71ZXu4of/J9fkRq2a6+1e99uNb7UpNU/bTTiOiJiFPAa8DXMvPEKseMRsRM\nRMwsLCxs/5DqKmMjg/TuuPLzGHt39DA2MlhpoksmZ+c5eP9T3HTfv3Lw/qeYnJ2vPZIapmoQMvNi\nZh4AdgO3lltbrz5mIjOHM3O4v79/+4dUVzk0NMDRw/voeesNyGSgr5ejh/dVv36wcrF7fnGJ5NLF\nbqOg7dTyNYTNkJmLEfE0cDvwfO151N0ODQ1w7N4JAKanp+sOU3ixW+2g2gohIvojoq983wt8AvhW\nrXmkmrzYrXZQc4Xws8Dflw12rgP+yX0Uuo8Pga3Nrr5e5lf5x9+L3dpO1YKQmc+x/OyCupQPga3d\n2MjgFf+voH0udqs53FNZW+b9zovrSu16sVvN0hYXldWdPC++Pu14sVvN4gpBW8aHwKTOYhC0Zdr5\nITBJ72UQtGU8Ly51Fq8haEt5XlzqHK4QJEmAQZAkFQZBkgQYBElSYRAkSYBBkCQVBkGSBBgESVJh\nECRJgEGQJBUGQZIEGARJUuGH20m6JvfEbhaDIGlV7ondPNVOGUXEhyLi6Yh4MSJeiIh7as0i6b3c\nE7t5aq4QLgCfycxnI+JG4GREfC0zX6w4k6TCPbGbp9oKITP/NzOfLd9/HzgDuA6V2oR7YjdPW9xl\nFBF7gSHgRN1JJK1wT+zmqR6EiPgg8M/ApzPze6v8/WhEzETEzMLCwvYPKDWUe2I3T9W7jCJiB8sx\n+FJmHl/tmMycACYAhoeHcxvHkxrPPbGbpeZdRgE8CJzJzL+pNYckaVnNU0YHgT8EbouIU+XPb1ac\nR5Iardopo8z8BhC1fr8k6UrVLypLktqDQZAkAQZBklQYBEkSYBAkSYVBkCQBBkGSVBgESRJgECRJ\nhUGQJAEGQZJUVP34a0nqBpOz84xPzXFucYldfb2MjQx25L4RBkGSWjA5O8+R46dZOn8RgPnFJY4c\nPw3QcVHwlJEktWB8au7dGKxYOn+R8am5ShNtnEGQpBacW1xa1/vtzCBIUgt29fWu6/12ZhAkqQVj\nI4P07ui54r3eHT2MjQxWmmjjDIIkteDQ0ABHD++j5603IJOBvl6OHt7XcReUwbuMJKllh4YGOHbv\nBADT09N1h2mBKwRJEmAQJElFtSBExEMR8VpEPF9rBknSJTVXCA8Dt1f8/ZKky1QLQmZ+Hfhurd8v\nSbqS1xAkSUAHBCEiRiNiJiJmFhYWao8jSV2r7YOQmROZOZyZw/39/bXHkaSu1fZBkCRtj2pPKkfE\nPwK/AuyMiLPAZzPzwVrzSOoM3bIZTTuqFoTMvKvW75bUmbppM5p25CkjSR2jmzajaUcGQVLH6KbN\naNqRQZDUMbppM5p2ZBAkdYxu2oymHRkESR2jmzajaUdukCOpo3TLZjTtyBWCJAkwCJKkwiBIkgCD\nIEkqDIIkCTAIkqTCIEiSAIMgSSoMgiQJMAiSpMIgSJIAgyBJKgyCJAkwCJKkwiBIkoDKQYiI2yNi\nLiJeioj7as4iSU1XLQgR0QN8Hvgk8FHgroj4aK15JKnpaq4QbgVeysyXM/Nt4FHgjorzSFKj1QzC\nAPDqZa/PlvckSRW0/Z7KETEKjALs2bOn8jRXOnDgQO0R3sOZ1qYdZ4L2nMuZ1qYdZ1qvyMw6vzji\nY8BfZeZIeX0EIDOPXutnhoeHc2ZmZpsmlKTOFxEnM3N4LcfWPGX0DPDhiLgpIm4A7gS+UnEeSWq0\naqeMMvNCRNwNTAE9wEOZ+UKteSSp6apeQ8jMJ4Ena84gSVrmk8qSJMAgSJIKgyBJAgyCJKkwCJIk\noOKDaRsREQvAt2vPcZWdwOu1h5Cka/i5zOxfy4EdFYR2FBEza30KUJLamaeMJEmAQZAkFQahdRO1\nB5CkzeA1BEkS4ApBklQYhA2KiNsjYi4iXoqI+2rPI0mt8pTRBkRED/BfwCdY3vrzGeCuzHyx6mCS\n1AJXCBtzK/BSZr6cmW8DjwJ3VJ5JklpiEDZmAHj1stdny3uS1LEMgiQJMAgbNQ986LLXu8t7ktSx\nDMLGPAN8OCJuiogbgDuBr1SeSZJaUnVP5U6VmRci4m5gCugBHsrMFyqPJUkt8bZTSRLgKSNJUmEQ\nJEmAQZAkFQZBkgQYBElSYRAkSYBBkDZFRHw+Ih6vPYfUCp9DkDZBRPwUcD4z36w9i7RRBkGSBHjK\nSGpZROyOiIyIj9SeRWqFQZBatx/4Icu76EkdyyBIrTsAnM7Md2oPIrXCIEit2w+cqj2E1CqDILXu\nAAZBXcAgSC2IiA8AP49BUBcwCFJrbilfn6s6hbQJDILUmv3Af2fmD2sPIrXKB9MkSYArBElSYRAk\nSYBBkCQVBkGSBBgESVJhECRJgEGQJBUGQZIEGARJUvH/UvsCgoFCKdoAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x115e03908>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "for i in range(len(results.params) - 1):\n",
    "    line = np.array([0, results.params[i]])\n",
    "    plt.plot(np.array([i, i]), line, '-', color='black')\n",
    "plt.plot(results.params[0:-1], 'o')\n",
    "plt.xlabel(r'$i$', fontsize=14)\n",
    "plt.ylabel(r'$\\beta_i$', fontsize=14)\n",
    "plt.xlim(-1, A.shape[1]-1)\n",
    "plt.xticks(np.arange(0, len(results.params) - 1, 32))\n",
    "plt.show()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}