From 839cb94bb7ec2469b3287cfb9943ef03590724a9 Mon Sep 17 00:00:00 2001 From: J08nY Date: Mon, 28 Jul 2025 17:52:11 +0200 Subject: Add epa tracking functionality. --- pyecsca/ec/mult/fake.py | 21 +++++++++++-- pyecsca/sca/re/epa.py | 78 +++++++++++++++++++++++++++++++++++++++++++++++++ pyecsca/sca/re/rpa.py | 18 +++--------- pyecsca/sca/re/zvp.py | 16 ++-------- test/sca/test_epa.py | 70 ++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 173 insertions(+), 30 deletions(-) create mode 100644 pyecsca/sca/re/epa.py create mode 100644 test/sca/test_epa.py diff --git a/pyecsca/ec/mult/fake.py b/pyecsca/ec/mult/fake.py index e0c8610..f18d695 100644 --- a/pyecsca/ec/mult/fake.py +++ b/pyecsca/ec/mult/fake.py @@ -1,3 +1,4 @@ +from functools import lru_cache from typing import Type, Callable from copy import deepcopy @@ -9,8 +10,14 @@ from pyecsca.ec.formula import ( NegationFormula, ScalingFormula, ) -from pyecsca.ec.formula.fake import FakeAdditionFormula, FakeDifferentialAdditionFormula, \ - FakeDoublingFormula, FakeLadderFormula, FakeNegationFormula, FakeScalingFormula +from pyecsca.ec.formula.fake import ( + FakeAdditionFormula, + FakeDifferentialAdditionFormula, + FakeDoublingFormula, + FakeLadderFormula, + FakeNegationFormula, + FakeScalingFormula, +) from pyecsca.ec.mult import ScalarMultiplier from pyecsca.ec.params import DomainParameters @@ -60,3 +67,13 @@ def turn_fake(mult: ScalarMultiplier) -> ScalarMultiplier: formulas[key] = fake(formula.coordinate_model) copy.formulas = formulas return copy + + +@lru_cache(maxsize=256, typed=True) +def cached_fake_mult( + mult_class: Type[ScalarMultiplier], mult_factory: Callable, params: DomainParameters +) -> ScalarMultiplier: + fm = fake_mult(mult_class, mult_factory, params) + if getattr(fm, "short_circuit", False): + raise ValueError("The multiplier must not short-circuit.") + return fm diff --git a/pyecsca/sca/re/epa.py b/pyecsca/sca/re/epa.py new file mode 100644 index 0000000..14c7206 --- /dev/null +++ b/pyecsca/sca/re/epa.py @@ -0,0 +1,78 @@ +""" +Provides functionality inspired by the Exceptional Procedure Attack [EPA]_. +""" + +from typing import Type, Callable, Literal + +from public import public + +from pyecsca.ec.context import local +from pyecsca.ec.formula.fake import FakePoint +from pyecsca.ec.mult import ScalarMultiplier +from pyecsca.ec.mult.fake import cached_fake_mult +from pyecsca.ec.params import DomainParameters +from pyecsca.sca.re.rpa import MultipleContext + + +@public +def errors_out( + scalar: int, + params: DomainParameters, + mult_class: Type[ScalarMultiplier], + mult_factory: Callable, + check_funcs: dict[str, Callable], + check_condition: Literal["all"] | Literal["necessary"], + precomp_to_affine: bool, +) -> bool: + """ + + :param scalar: + :param params: + :param mult_class: + :param mult_factory: + :param check_funcs: + :param check_condition: + :param precomp_to_affine: + :return: + + .. note:: + The scalar multiplier must not short-circuit. + """ + mult = cached_fake_mult(mult_class, mult_factory, params) + ctx = MultipleContext(keep_base=True) + with local(ctx, copy=False): + mult.init(params, FakePoint(params.curve.coordinate_model)) + + with local(ctx, copy=False): + out = mult.multiply(scalar) + + affine_points = {out, *ctx.precomp.values()} if precomp_to_affine else {out} + if check_condition == "all": + points = set(ctx.points.keys()) + elif check_condition == "necessary": + points = set(affine_points) + queue = set(affine_points) + while queue: + point = queue.pop() + for parent in ctx.parents[point]: + points.add(parent) + queue.add(parent) + else: + raise ValueError("check_condition must be 'all' or 'necessary'") + + # Special case the "to affine" transform and checks + # This actually passes the multiple itself to the check, not the inputs(parents) + for point in affine_points: + if "affine" in check_funcs: + func = check_funcs["affine"] + if func(ctx.points[point]): + return True + # Now handle the regular checks + for point in points: + formula = ctx.formulas[point] + if formula in check_funcs: + func = check_funcs[formula] + inputs = list(map(lambda pt: ctx.points[pt], ctx.parents[point])) + if func(*inputs): + return True + return False diff --git a/pyecsca/sca/re/rpa.py b/pyecsca/sca/re/rpa.py index 6e6da08..f9ccd1b 100644 --- a/pyecsca/sca/re/rpa.py +++ b/pyecsca/sca/re/rpa.py @@ -3,7 +3,6 @@ Provides functionality inspired by the Refined-Power Analysis attack by Goubin [ """ from copy import copy, deepcopy -from functools import lru_cache from public import public from typing import ( @@ -32,7 +31,8 @@ from pyecsca.ec.formula import ( TriplingFormula, NegationFormula, DifferentialAdditionFormula, - LadderFormula, ScalingFormula, + LadderFormula, + ScalingFormula, ) from pyecsca.ec.mod import Mod, mod from pyecsca.ec.mult import ( @@ -44,7 +44,7 @@ from pyecsca.ec.params import DomainParameters from pyecsca.ec.model import ShortWeierstrassModel, MontgomeryModel from pyecsca.ec.point import Point from pyecsca.ec.context import Context, Action, local -from pyecsca.ec.mult.fake import fake_mult +from pyecsca.ec.mult.fake import cached_fake_mult from pyecsca.misc.utils import log, warn @@ -420,16 +420,6 @@ class RPA(RE): return mults -@lru_cache(maxsize=256, typed=True) -def _cached_fake_mult( - mult_class: Type[ScalarMultiplier], mult_factory: Callable, params: DomainParameters -) -> ScalarMultiplier: - fm = fake_mult(mult_class, mult_factory, params) - if getattr(fm, "short_circuit", False): - raise ValueError("The multiplier must not short-circuit.") - return fm - - @public def multiples_computed( scalar: int, @@ -465,7 +455,7 @@ def multiples_computed( if kind != "all" and not use_init: raise ValueError("Cannot use kind other than 'all' with use_init=False.") - mult = _cached_fake_mult(mult_class, mult_factory, params) + mult = cached_fake_mult(mult_class, mult_factory, params) ctx = MultipleContext(keep_base=True) if use_init: with local(ctx, copy=False): diff --git a/pyecsca/sca/re/zvp.py b/pyecsca/sca/re/zvp.py index efa4ede..7e6c7ce 100644 --- a/pyecsca/sca/re/zvp.py +++ b/pyecsca/sca/re/zvp.py @@ -4,7 +4,6 @@ Provides functionality inspired by the Zero-value point attack [ZVP]_. Implements ZVP point construction from [FFD]_. """ -from functools import lru_cache from typing import List, Set, Tuple, Dict, Type, Callable from public import public import warnings @@ -12,6 +11,7 @@ from astunparse import unparse from sympy import FF, Poly, Monomial, Symbol, Expr, sympify, symbols, div +from pyecsca.ec.mult.fake import cached_fake_mult from pyecsca.sca.re.rpa import MultipleContext from pyecsca.ec.context import local from pyecsca.ec.curve import EllipticCurve @@ -25,8 +25,6 @@ from pyecsca.ec.mult import ScalarMultiplier from pyecsca.ec.params import DomainParameters from pyecsca.ec.point import Point -from pyecsca.ec.mult.fake import fake_mult - has_pari = False try: import cypari2 @@ -584,16 +582,6 @@ def solve_hard_dcp_cypari( return res -@lru_cache(maxsize=256, typed=True) -def _cached_fake_mult( - mult_class: Type[ScalarMultiplier], mult_factory: Callable, params: DomainParameters -) -> ScalarMultiplier: - fm = fake_mult(mult_class, mult_factory, params) - if getattr(fm, "short_circuit", False): - raise ValueError("The multiplier must not short-circuit.") - return fm - - @public def addition_chain( scalar: int, @@ -618,7 +606,7 @@ def addition_chain( .. note:: The scalar multiplier must not short-circuit. """ - mult = _cached_fake_mult(mult_class, mult_factory, params) + mult = cached_fake_mult(mult_class, mult_factory, params) ctx = MultipleContext(keep_base=True) if use_init: with local(ctx, copy=False): diff --git a/test/sca/test_epa.py b/test/sca/test_epa.py new file mode 100644 index 0000000..0362e4e --- /dev/null +++ b/test/sca/test_epa.py @@ -0,0 +1,70 @@ +from functools import partial + +from pyecsca.ec.mult import LTRMultiplier, CombMultiplier +from pyecsca.sca.re.epa import errors_out + + +def test_errors_out(secp128r1): + res_empty_checks = errors_out( + scalar=15, + params=secp128r1, + mult_class=LTRMultiplier, + mult_factory=LTRMultiplier, + check_funcs={}, + check_condition="all", + precomp_to_affine=True, + ) + assert not res_empty_checks + + def add_check(k, l): # noqa + return k == 6 + + res_check_k_add = errors_out( + scalar=15, + params=secp128r1, + mult_class=LTRMultiplier, + mult_factory=LTRMultiplier, + check_funcs={"add": add_check}, + check_condition="all", + precomp_to_affine=True, + ) + assert res_check_k_add + + def affine_check(k): + return k == 15 + + res_check_k_affine = errors_out( + scalar=15, + params=secp128r1, + mult_class=LTRMultiplier, + mult_factory=LTRMultiplier, + check_funcs={"affine": affine_check}, + check_condition="all", + precomp_to_affine=True, + ) + assert res_check_k_affine + + def affine_check_comb(k): + return k == 2**64 + + res_check_k_affine_precomp = errors_out( + scalar=15, + params=secp128r1, + mult_class=CombMultiplier, + mult_factory=partial(CombMultiplier, width=2), + check_funcs={"affine": affine_check_comb}, + check_condition="all", + precomp_to_affine=True, + ) + assert res_check_k_affine_precomp + + res_check_k_no_affine_precomp = errors_out( + scalar=15, + params=secp128r1, + mult_class=CombMultiplier, + mult_factory=partial(CombMultiplier, width=2), + check_funcs={"affine": affine_check_comb}, + check_condition="all", + precomp_to_affine=False, + ) + assert not res_check_k_no_affine_precomp -- cgit v1.2.3-70-g09d2