Add fully simulated RPA-RE demo.

1 files changed, 150 insertions, 9 deletions

diff --git a/re/rpa.ipynb b/re/rpa.ipynb
index 316a68b..8f3ef48 100644
--- a/re/rpa.ipynb
+++ b/re/rpa.ipynb
@@ -16,6 +16,9 @@
    "outputs": [],
    "source": [
     "from collections import Counter\n",
+    "import numpy as np\n",
+    "import holoviews as hv\n",
+    "from scipy.signal import find_peaks\n",
     "\n",
     "from pyecsca.ec.key_generation import KeyGeneration\n",
     "from pyecsca.ec.key_agreement import ECDH_SHA1\n",
@@ -23,11 +26,29 @@
     "from pyecsca.ec.coordinates import AffineCoordinateModel\n",
     "from pyecsca.ec.curve import EllipticCurve\n",
     "from pyecsca.ec.params import DomainParameters\n",
+    "from pyecsca.ec.formula import FormulaAction\n",
     "from pyecsca.ec.point import Point\n",
     "from pyecsca.ec.mod import Mod\n",
     "from pyecsca.ec.mult import *\n",
+    "from pyecsca.sca.trace.sampling import downsample_average, downsample_max\n",
+    "from pyecsca.sca.trace.process import normalize, rolling_mean\n",
+    "from pyecsca.sca.trace.combine import average, subtract\n",
+    "from pyecsca.sca.trace.test import welch_ttest\n",
+    "from pyecsca.sca.attack.leakage_model import HammingWeight, NormalNoice\n",
     "from pyecsca.ec.context import DefaultContext, local\n",
-    "from pyecsca.sca.re.rpa import MultipleContext, rpa_distinguish"
+    "from pyecsca.sca.re.rpa import MultipleContext, rpa_distinguish\n",
+    "from pyecsca.sca.trace import Trace\n",
+    "from pyecsca.sca.trace.plot import plot_trace, plot_traces"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "3ff1d591-f922-4c94-9e47-ab053fc21cf1",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "hv.extension(\"bokeh\")"
    ]
   },
   {
@@ -68,6 +89,7 @@
    "id": "29fb8683-bcad-4a3e-869b-95f0e4b7bde3",
    "metadata": {},
    "source": [
+    "## Exploration\n",
     "First select a bunch of multipliers. We will be trying to distinguish among these."
    ]
   },
@@ -125,15 +147,23 @@
    ]
   },
   {
+   "cell_type": "markdown",
+   "id": "ba284641-c29b-4e42-95ec-aa630e305b10",
+   "metadata": {},
+   "source": [
+    "Pick a multiple `k` that is computed by some multiplier for the scalar,\n",
+    "invert it mod n, and do `[k^-1]P0` to obtain a point `P0_target`,\n",
+    "such that, `[k]P0_target = P0` and `P0` has a zero coordinate."
+   ]
+  },
+  {
    "cell_type": "code",
    "execution_count": null,
    "id": "a7fb8a3f-7938-493b-88dc-582ba4d8959d",
    "metadata": {},
    "outputs": [],
    "source": [
-    "# Pick a multiple \"k\", invert it mod n, and do [k^-1]P0 to obtain a point P0_target,\n",
-    "# such that, [k]P0_target = P0 and P0 has a zero coordinate.\n",
-    "k = 23547513796\n",
+    "k = 7186132\n",
     "kinv = Mod(k, n).inverse()\n",
     "P0_target = curve.affine_multiply(P0_aff, int(kinv)).to_model(coords, curve)\n",
     "\n",
@@ -143,16 +173,22 @@
    ]
   },
   {
+   "cell_type": "markdown",
+   "id": "914a67a5-b6a2-4d02-811f-a423099853c3",
+   "metadata": {},
+   "source": [
+    "Now go over the multipliers with P0_target and the original scalar as input.\n",
+    "Then look whether a zero coordinate point was computed.\n",
+    "Also look at whether the multiple \"k\" was computed. These two should be the same."
+   ]
+  },
+  {
    "cell_type": "code",
    "execution_count": null,
    "id": "8113cb3f-dc06-4cb7-955c-11cedb4fbdd7",
    "metadata": {},
    "outputs": [],
    "source": [
-    "# Now go over the multipliers with P0_target and the original scalar as input.\n",
-    "# Then look whether a zero coordinate point was computed.\n",
-    "# Also look at whether the multiple \"k\" was computed. These two should be the same.\n",
-    "\n",
     "for mult in multipliers:\n",
     "    print(mult.__class__.__name__)\n",
     "    with local(MultipleContext()) as ctx:\n",
@@ -164,18 +200,35 @@
    ]
   },
   {
+   "cell_type": "markdown",
+   "id": "0d2b9fe8-5064-4887-b782-dcfe9f42d217",
+   "metadata": {},
+   "source": [
+    "Now lets look at the relation of multiples to multipliers."
+   ]
+  },
+  {
    "cell_type": "code",
    "execution_count": null,
    "id": "67d7705c-6a41-47d9-ad1e-23ea549aaf00",
    "metadata": {},
    "outputs": [],
    "source": [
-    "# Now lets look at the relation of multiples to multipliers\n",
     "for multiple, mults in multiples.items():\n",
     "    print(multiple, [mult.__class__.__name__ for mult in mults])"
    ]
   },
   {
+   "cell_type": "markdown",
+   "id": "e9015f3c-fba6-4614-b722-848b8522d072",
+   "metadata": {},
+   "source": [
+    "## Reverse-engineering\n",
+    "The `simulated_oracle` function simulates an RPA oracle that detect a zero coordinate point in the scalar multiplication.\n",
+    "This can be used by the `rpa_distinguish` function to distinguish the true scalar multiplier."
+   ]
+  },
+  {
    "cell_type": "code",
    "execution_count": null,
    "id": "9bb61ac5-d837-4287-a5de-a9a63c346acf",
@@ -202,9 +255,97 @@
    ]
   },
   {
+   "cell_type": "markdown",
+   "id": "62b0b8f2-8149-4abd-9aa7-a056b237ac6e",
+   "metadata": {},
+   "source": [
+    "The `simulate_trace` function simulates a Hamming weight leakage trace of a given multiplier computing a scalar multiple.\n",
+    "This is used by the `simulated_rpa_trace` function that does the RPA attack on simulated traces and returns the differential\n",
+    "trace. This is in turn used to build the `simulated_rpa_oracle` which can be used by the `rpa_distinguish` function to perform\n",
+    "RPA-RE and distinguish the true scalar multiplier."
+   ]
+  },
+  {
    "cell_type": "code",
    "execution_count": null,
    "id": "96bec03e-5397-440b-9e8c-81ba5253921b",
+   "metadata": {
+    "scrolled": true
+   },
+   "outputs": [],
+   "source": [
+    "def simulate_trace(mult, scalar, point):\n",
+    "    with local(DefaultContext()) as ctx:\n",
+    "        mult.init(params, point)\n",
+    "        mult.multiply(scalar)\n",
+    "\n",
+    "    lm = HammingWeight()\n",
+    "    trace = []\n",
+    "\n",
+    "    def callback(action):\n",
+    "        if isinstance(action, FormulaAction):\n",
+    "            for intermediate in action.op_results:\n",
+    "                leak = lm(intermediate.value)\n",
+    "                trace.append(leak)\n",
+    "\n",
+    "    ctx.actions.walk(callback)\n",
+    "    return Trace(np.array(trace))\n",
+    "\n",
+    "def simulated_rpa_trace(mult, scalar, affine_point, noise):\n",
+    "    target_point = affine_point.to_model(params.curve.coordinate_model, params.curve)\n",
+    "    random_point = params.curve.affine_random().to_model(params.curve.coordinate_model, params.curve)\n",
+    "\n",
+    "    random_traces = [noise(simulate_trace(mult, scalar, random_point)) for _ in range(10)]\n",
+    "    target_traces = [noise(simulate_trace(mult, scalar, target_point)) for _ in range(500)]\n",
+    "\n",
+    "    random_avg = average(*random_traces)\n",
+    "    target_avg = average(*target_traces)\n",
+    "\n",
+    "    diff_trace = downsample_max(subtract(random_avg, target_avg), 25)\n",
+    "    return diff_trace\n",
+    "\n",
+    "def simulated_rpa_oracle(scalar, affine_point):\n",
+    "    real_mult = BinaryNAFMultiplier(add, dbl, neg, None, True)\n",
+    "    noise = NormalNoice(0, 1)\n",
+    "    diff_trace = normalize(simulated_rpa_trace(real_mult, scalar, affine_point, noise))\n",
+    "    peaks, props = find_peaks(diff_trace.samples, height=4)\n",
+    "    return len(peaks) != 0"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "d74a944f-e0a6-434d-8a12-138dfb9d516e",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "rpa_distinguish(params, multipliers, simulated_rpa_oracle)"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "id": "e694b3b3-290d-4528-a611-16a183662944",
+   "metadata": {},
+   "source": [
+    "Note that the oracle function above has several parameters, like noise amplitude, amount of traces simulated and peak finding height threshold. The cell below compares the differential RPA trace when the multiple is computed in the simulation vs when it is not."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "e47a70d7-7993-4560-9257-dbbc1cf658cf",
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "diff_real = normalize(simulated_rpa_trace(BinaryNAFMultiplier(add, dbl, neg, None, True), scalar, P0_target.to_affine(), NormalNoice(0, 1)))\n",
+    "diff_nothing = normalize(simulated_rpa_trace(LTRMultiplier(add, dbl, None, False, True, True), scalar, P0_target.to_affine(), NormalNoice(0, 1)))\n",
+    "plot_traces(diff_real, diff_nothing).opts(width=950, height=600)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "51a78d40-0cc1-49e2-9753-ddf49a496ed9",
    "metadata": {},
    "outputs": [],
    "source": []