From 674c45bfe5766fb621bdbfa578d403f3f15dd5da Mon Sep 17 00:00:00 2001 From: J08nY Date: Sun, 26 Oct 2025 16:44:32 +0100 Subject: Add MultPointBlinding countermeasure and test it. --- pyecsca/ec/countermeasures.py | 91 +++++++++++++++++++++++++++++++++++++---- pyecsca/ec/mult/fake.py | 13 ++++++ pyecsca/sca/re/rpa.py | 21 +++++++++- test/ec/test_countermeasures.py | 41 ++++++++++++++++--- 4 files changed, 151 insertions(+), 15 deletions(-) diff --git a/pyecsca/ec/countermeasures.py b/pyecsca/ec/countermeasures.py index da45150..e155663 100644 --- a/pyecsca/ec/countermeasures.py +++ b/pyecsca/ec/countermeasures.py @@ -118,7 +118,7 @@ class GroupScalarRandomization(ScalarMultiplierCountermeasure): :class: frame &r \xleftarrow{\$} \{0, 1, \ldots, 2^{\text{rand_bits}}\} \\ - &\textbf{return}\ [k + r n]G + &\textbf{return}\ [k + r n]P """ @@ -167,7 +167,7 @@ class AdditiveSplitting(ScalarMultiplierCountermeasure): :class: frame &r \xleftarrow{\$} \{0, 1, \ldots, n\} \\ - &\textbf{return}\ [k - r]G + [r]G + &\textbf{return}\ [k - r]P + [r]P """ @@ -221,7 +221,7 @@ class MultiplicativeSplitting(ScalarMultiplierCountermeasure): :class: frame &r \xleftarrow{\$} \{0, 1, \ldots, 2^{\text{rand_bits}}\} \\ - &S = [r]G \\ + &S = [r]P \\ &\textbf{return}\ [k r^{-1} \mod n]S """ @@ -273,10 +273,10 @@ class EuclideanSplitting(ScalarMultiplierCountermeasure): :class: frame &r \xleftarrow{\$} \{0, 1, \ldots, 2^{\log_2{(n)}/2}\} \\ - &S = [r]G \\ + &S = [r]P \\ &k_1 = k \mod r \\ &k_2 = \lfloor \frac{k}{r} \rfloor \\ - &\textbf{return}\ [k_1]G + [k_2]S + &\textbf{return}\ [k_1]P + [k_2]S """ @@ -354,7 +354,7 @@ class BrumleyTuveri(ScalarMultiplierCountermeasure): k + 2n \quad \text{if } \lceil \log_2(k+n) \rceil = \lceil \log_2 n \rceil\\ k + n \quad \text{otherwise}. \end{cases}\\ - &\textbf{return}\ [\hat{k}]G + &\textbf{return}\ [\hat{k}]P """ @@ -390,7 +390,19 @@ class BrumleyTuveri(ScalarMultiplierCountermeasure): @public class PointBlinding(ScalarMultiplierCountermeasure): - """Point blinding countermeasure.""" + r""" + Point blinding countermeasure. + + .. math:: + :class: frame + + &R \xleftarrow{\$} E_{\mathbb{F}_p} \\ + &S = [k]R \\ + &T = P + S \\ + &Q = [k]T \\ + &\textbf{return}\ Q - S + + """ nmults = 2 requires = {AdditionFormula, NegationFormula} @@ -432,3 +444,68 @@ class PointBlinding(ScalarMultiplierCountermeasure): Q = self.mults[1].multiply(int(scalar)) return action.exit(self._add(Q, self._neg(S))) + + +@public +class MultPointBlinding(ScalarMultiplierCountermeasure): + r""" + Point blinding countermeasure. + + .. math:: + :class: frame + + &r \xleftarrow{\$} \{0, 1, \ldots, 2^{\text{rand_bits}}\} \\ + $R = [r]G$ \\ + &S = [k]R \\ + &T = P + S \\ + &Q = [k]T \\ + &\textbf{return}\ Q - S + + """ + + nmults = 3 + requires = {AdditionFormula, NegationFormula} + rand_bits: int + add: Optional[AdditionFormula] + neg: Optional[NegationFormula] + + def __init__( + self, + mult1: "ScalarMultiplier | ScalarMultiplierCountermeasure", + mult2: "ScalarMultiplier | ScalarMultiplierCountermeasure", + mult3: "ScalarMultiplier | ScalarMultiplierCountermeasure", + rng: Callable[[int], Mod] = Mod.random, + rand_bits: int = 32, + add: Optional[AdditionFormula] = None, + neg: Optional[NegationFormula] = None, + ): + """ + + :param mult1: The multiplier to use. + :param mult2: The multiplier to use. + :param mult3: The multiplier to use. + :param rng: The random number generator to use. + :param add: Addition formula to use, if None, the formula from the multiplier is used. + :param neg: Negation formula to use, if None, the formula from the multiplier is used. + """ + super().__init__(mult1, mult2, mult3, rng=rng) + self.rand_bits = rand_bits + self.add = add + self.neg = neg + + def multiply(self, scalar: int) -> Point: + if self.params is None or self.point is None or self.bits is None: + raise ValueError("Not initialized.") + with ScalarMultiplicationAction(self.point, self.params, scalar) as action: + r = self.rng(1 << self.rand_bits) + self.mults[0].init(self.params, self.params.generator, self.rand_bits) + R = self.mults[0].multiply(int(r)) + + self.mults[1].init(self.params, R, self.bits) + S = self.mults[1].multiply(int(scalar)) + + T = self._add(self.point, R) + self.mults[2].init(self.params, T, self.bits) + Q = self.mults[2].multiply(int(scalar)) + + return action.exit(self._add(Q, self._neg(S))) diff --git a/pyecsca/ec/mult/fake.py b/pyecsca/ec/mult/fake.py index f18d695..95bebb5 100644 --- a/pyecsca/ec/mult/fake.py +++ b/pyecsca/ec/mult/fake.py @@ -17,6 +17,7 @@ from pyecsca.ec.formula.fake import ( FakeLadderFormula, FakeNegationFormula, FakeScalingFormula, + FakePoint, ) from pyecsca.ec.mult import ScalarMultiplier from pyecsca.ec.params import DomainParameters @@ -51,6 +52,18 @@ def fake_mult( return mult +def fake_params(params: DomainParameters) -> DomainParameters: + """ + Turn the domain parameters into fake domain parameters. + + :param params: The domain parameters to turn into fake domain parameters. + :return: The fake domain parameters. + """ + copy = deepcopy(params) + copy.generator = FakePoint(params.curve.coordinate_model) + return copy + + def turn_fake(mult: ScalarMultiplier) -> ScalarMultiplier: """ Turn a multiplier into a fake multiplier. diff --git a/pyecsca/sca/re/rpa.py b/pyecsca/sca/re/rpa.py index e7e033b..e899f20 100644 --- a/pyecsca/sca/re/rpa.py +++ b/pyecsca/sca/re/rpa.py @@ -38,7 +38,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 cached_fake_mult +from pyecsca.ec.mult.fake import cached_fake_mult, fake_params from pyecsca.misc.utils import log, warn @@ -420,6 +420,7 @@ def multiple_graph( params: DomainParameters, mult_class: Type[ScalarMultiplier], mult_factory: Callable, + dlog: Optional[int] = None, ) -> Tuple[MultipleContext, MultipleContext, Point]: """ Compute the multiples computed for a given scalar and multiplier (quickly). @@ -428,12 +429,28 @@ def multiple_graph( :param params: The domain parameters to use. :param mult_class: The class of the scalar multiplier to use. :param mult_factory: A callable that takes the formulas and instantiates the multiplier. + :param dlog: Make an assumption that the symbolic input point is the `dlog` multiple of the base point. + This is necessary if the multiplier does computation with the base point. :return: The context with the computed multiples and the resulting point. """ + params = fake_params(params) mult = cached_fake_mult(mult_class, mult_factory, params) ctx = MultipleContext(keep_base=True) with local(ctx, copy=False) as precomp_ctx: - mult.init(params, FakePoint(params.curve.coordinate_model)) + point = FakePoint(params.curve.coordinate_model) + if dlog: + ctx.base = params.generator + ctx.neutral = params.curve.neutral + ctx.points[ctx.base] = 1 + ctx.points[point] = dlog + ctx.points[ctx.neutral] = 0 + ctx.formulas[ctx.base] = "" + ctx.formulas[point] = "" + ctx.formulas[ctx.neutral] = "" + ctx.parents[ctx.base] = [] + ctx.parents[point] = [] + ctx.parents[ctx.neutral] = [] + mult.init(params, point) with local(ctx, copy=True) as full_ctx: out = mult.multiply(scalar) diff --git a/test/ec/test_countermeasures.py b/test/ec/test_countermeasures.py index cb1e4aa..28d3f33 100644 --- a/test/ec/test_countermeasures.py +++ b/test/ec/test_countermeasures.py @@ -10,6 +10,7 @@ from pyecsca.ec.countermeasures import ( EuclideanSplitting, BrumleyTuveri, PointBlinding, + MultPointBlinding, ) from pyecsca.ec.mod import mod from pyecsca.ec.mult import * @@ -269,6 +270,27 @@ def test_point_blinding(mults, secp128r1, num): assert raw.equals(masked) +@pytest.mark.parametrize( + "num", + [ + 3253857902090173296443513219124437746, + 1234567893141592653589793238464338327, + ], +) +def test_mult_point_blinding(mults, secp128r1, num): + mult = copy(mults[0]) + mult.init(secp128r1, secp128r1.generator) + raw = mult.multiply(num) + + neg = secp128r1.curve.coordinate_model.formulas["neg"] + + for mult in mults: + pb = MultPointBlinding(mult, mult, mult, neg=neg) + pb.init(secp128r1, secp128r1.generator) + masked = pb.multiply(num) + assert raw.equals(masked) + + @pytest.mark.parametrize( "scalar", [ @@ -288,6 +310,7 @@ def test_point_blinding(mults, secp128r1, num): EuclideanSplitting, BrumleyTuveri, PointBlinding, + MultPointBlinding ), repeat=2, ), @@ -308,14 +331,14 @@ def test_combination(scalar, one, two, secp128r1): if one in (AdditiveSplitting, EuclideanSplitting): layer_one = one.from_single(mult, add=add) - elif one == PointBlinding: + elif one in (PointBlinding, MultPointBlinding): layer_one = one.from_single(mult, neg=neg) else: layer_one = one.from_single(mult) if two in (AdditiveSplitting, EuclideanSplitting): kws = {"add": add} - elif two == PointBlinding: + elif two in (PointBlinding, MultPointBlinding): kws = {"neg": neg} else: kws = {} @@ -348,6 +371,7 @@ def test_combination(scalar, one, two, secp128r1): EuclideanSplitting, BrumleyTuveri, PointBlinding, + MultPointBlinding ), repeat=2, ), @@ -369,14 +393,14 @@ def test_combination_multiples(scalar, one, two, secp128r1): if one in (AdditiveSplitting, EuclideanSplitting): layer_one = one.from_single(mult, add=add) - elif one == PointBlinding: + elif one in (PointBlinding, MultPointBlinding): layer_one = one.from_single(mult, neg=neg) else: layer_one = one.from_single(mult) if two in (AdditiveSplitting, EuclideanSplitting): kws = {"add": add} - elif two == PointBlinding: + elif two in (PointBlinding, MultPointBlinding): kws = {"neg": neg} else: kws = {} @@ -385,8 +409,13 @@ def test_combination_multiples(scalar, one, two, secp128r1): combo = two(*args, **kws) return combo - res = multiple_graph(scalar, secp128r1, LTRMultiplier, partial) - assert res is not None + if one == MultPointBlinding or two == MultPointBlinding: + dlog = 1 + else: + dlog = None + precomp_ctx, full_ctx, out = multiple_graph(scalar, secp128r1, LTRMultiplier, partial, dlog=dlog) + assert out is not None + assert mod(full_ctx.points[out], secp128r1.order) == mod(scalar, secp128r1.order) @pytest.mark.parametrize( -- cgit v1.2.3-70-g09d2