diff options
| -rw-r--r-- | pyecsca/ec/formula/efd.py | 3 | ||||
| -rw-r--r-- | pyecsca/sca/re/rpa.py | 55 | ||||
| -rw-r--r-- | pyecsca/sca/re/tree.py | 63 |
3 files changed, 68 insertions, 53 deletions
diff --git a/pyecsca/ec/formula/efd.py b/pyecsca/ec/formula/efd.py index 4e3a82d..485e6f5 100644 --- a/pyecsca/ec/formula/efd.py +++ b/pyecsca/ec/formula/efd.py @@ -1,7 +1,4 @@ """""" -from functools import cached_property -from itertools import product - from public import public from importlib_resources.abc import Traversable diff --git a/pyecsca/sca/re/rpa.py b/pyecsca/sca/re/rpa.py index b1661e6..6d2218b 100644 --- a/pyecsca/sca/re/rpa.py +++ b/pyecsca/sca/re/rpa.py @@ -3,13 +3,13 @@ Provides functionality inspired by the Refined-Power Analysis attack by Goubin [ """ from copy import copy, deepcopy -from anytree import Node, RenderTree +from anytree import RenderTree from public import public -from typing import MutableMapping, Optional, Callable, List, Set -from collections import Counter +from typing import MutableMapping, Optional, Callable, List from sympy import FF, sympify, Poly, symbols +from .tree import build_distinguishing_tree from ...ec.coordinates import AffineCoordinateModel from ...ec.formula import ( FormulaAction, @@ -149,51 +149,6 @@ def rpa_input_point(k: Mod, rpa_point: Point, params: DomainParameters) -> Point return params.curve.affine_multiply(rpa_point, int(kinv)) -def build_distinguishing_tree(mults_to_multiples: MutableMapping[ScalarMultiplier, Set[Mod]], - **kwargs) -> Optional[Node]: - """ - Build an RPA distinguishing tree for a given mults-to-multiples mapping (induced by some fixed scalar). - - :param mults_to_multiples: - :param kwargs: - :return: - """ - n_mults = len(mults_to_multiples) - # If there is only one remaining multiple, put a single - if n_mults == 1: - return Node(None, mults=list(mults_to_multiples.keys()), **kwargs) - - counts: Counter = Counter() - for multiples in mults_to_multiples.values(): - counts.update(multiples) - - nhalf = n_mults / 2 - best_distinguishing_multiple = None - best_count = None - best_nhalf_distance = None - for multiple, count in counts.items(): - if best_distinguishing_multiple is None or abs(count - nhalf) < best_nhalf_distance: - best_distinguishing_multiple = multiple - best_count = count - best_nhalf_distance = abs(count - nhalf) - - if best_count in (0, n_mults, None): - return Node(None, mults=list(mults_to_multiples.keys()), **kwargs) - - result = Node(best_distinguishing_multiple, mults=list(mults_to_multiples.keys()), **kwargs) - true_mults = {mult: multiples for mult, multiples in mults_to_multiples.items() if - best_distinguishing_multiple in multiples} - true_child = build_distinguishing_tree(true_mults, oracle_response=True) - if true_child: - true_child.parent = result - false_mults = {mult: multiples for mult, multiples in mults_to_multiples.items() if - best_distinguishing_multiple not in multiples} - false_child = build_distinguishing_tree(false_mults, oracle_response=False) - if false_child: - false_child.parent = result - return result - - @public def rpa_distinguish(params: DomainParameters, mults: List[ScalarMultiplier], oracle: Callable[[int, Point], bool], bound: Optional[int] = None, majority: int = 1, use_init: bool = True, use_multiply: bool = True) -> List[ScalarMultiplier]: @@ -263,7 +218,7 @@ def rpa_distinguish(params: DomainParameters, mults: List[ScalarMultiplier], ora tree = build_distinguishing_tree(mults_to_multiples) log("Built distinguishing tree.") - log(RenderTree(tree).by_attr(lambda n: n.name if n.name else [mult.__class__.__name__ for mult in n.mults])) + log(RenderTree(tree).by_attr(lambda n: n.name if n.name else [mult.__class__.__name__ for mult in n.cfgs])) if tree is None or not tree.children: tries += 1 continue @@ -285,7 +240,7 @@ def rpa_distinguish(params: DomainParameters, mults: List[ScalarMultiplier], ora log(mult.__class__.__name__, best_distinguishing_multiple in mults_to_multiples[mult]) response_map = {child.oracle_response: child for child in current_node.children} current_node = response_map[response] - mults = current_node.mults + mults = current_node.cfgs log([mult.__class__.__name__ for mult in mults]) log() diff --git a/pyecsca/sca/re/tree.py b/pyecsca/sca/re/tree.py new file mode 100644 index 0000000..d3433cc --- /dev/null +++ b/pyecsca/sca/re/tree.py @@ -0,0 +1,63 @@ +from typing import Mapping, Any, Set +from collections import Counter +from public import public +from anytree import Node + + +@public +def build_distinguishing_tree( + cfg2resp: Mapping[Any, Set[Any]], **kwargs +) -> Node: + """ + Build a distinguishing tree for a given mapping of configs to True oracle responses. + + :param cfg2resp: + :param kwargs: + :return: + """ + n_cfgs = len(cfg2resp) + # If there is only one remaining cfg, we do not need to continue and just return (base case 1). + # Note that n_cfgs will never be 0 here, as the base case 2 returns if the cfgs cannot be split into two sets (one would be empty). + if n_cfgs == 1: + return Node(None, cfgs=list(cfg2resp.keys()), **kwargs) + + counts: Counter = Counter() + for elements in cfg2resp.values(): # Elements of the set need to be hashable + counts.update(elements) + + nhalf = n_cfgs / 2 + best_distinguishing_element = None + best_count = None + best_nhalf_distance = None + for multiple, count in counts.items(): + if ( + best_distinguishing_element is None + or abs(count - nhalf) < best_nhalf_distance + ): + best_distinguishing_element = multiple + best_count = count + best_nhalf_distance = abs(count - nhalf) + + # We found nothing distinguishing the configs, so return them all (base case 2). + if best_count in (0, n_cfgs, None): + return Node(None, cfgs=list(cfg2resp.keys()), **kwargs) + + result = Node( + best_distinguishing_element, cfgs=list(cfg2resp.keys()), **kwargs + ) + # Now go deeper and split based on the best-distinguishing element. + true_cfgs = { + mult: elements + for mult, elements in cfg2resp.items() + if best_distinguishing_element in elements + } + true_child = build_distinguishing_tree(true_cfgs, oracle_response=True) + true_child.parent = result + false_cfgs = { + mult: elements + for mult, elements in cfg2resp.items() + if best_distinguishing_element not in elements + } + false_child = build_distinguishing_tree(false_cfgs, oracle_response=False) + false_child.parent = result + return result |