diff options
| -rw-r--r-- | pyecsca/sca/re/epa.py | 26 | ||||
| -rw-r--r-- | pyecsca/sca/re/rpa.py | 2 | ||||
| -rw-r--r-- | test/sca/test_epa.py | 208 |
3 files changed, 217 insertions, 19 deletions
diff --git a/pyecsca/sca/re/epa.py b/pyecsca/sca/re/epa.py index af07bef..913a1ab 100644 --- a/pyecsca/sca/re/epa.py +++ b/pyecsca/sca/re/epa.py @@ -19,7 +19,7 @@ def graph_to_check_inputs( precomp_to_affine: bool, use_init: bool = True, use_multiply: bool = True, -) -> dict[str, list[tuple[int, ...]]]: +) -> dict[str, set[tuple[int, ...]]]: """ Compute the inputs for the checks based on the context and output point. This function traverses the graph of points and collects the inputs for each formula type, in the form of tuples of input multiples. It also adds a special @@ -32,7 +32,7 @@ def graph_to_check_inputs( :param precomp_to_affine: Whether to include the precomputed points in the to-affine checks. :param use_init: Whether to consider the point multiples that happen in scalarmult initialization. :param use_multiply: Whether to consider the point multiples that happen in scalarmult multiply (after initialization). - :return: A dictionary mapping formula names to lists of tuples of input multiples. + :return: A dictionary mapping formula names to sets of tuples of input multiples. .. note:: The scalar multiplier must not short-circuit. @@ -78,8 +78,8 @@ def graph_to_check_inputs( else: raise ValueError("check_condition must be 'all' or 'necessary'") # Special case the "to affine" transform and checks - formula_checks: dict[str, list[tuple[int, ...]]] = { - "affine": [(full_ctx.points[point],) for point in affine_points] + formula_checks: dict[str, set[tuple[int, ...]]] = { + "affine": {(full_ctx.points[point],) for point in affine_points} } # This actually passes the multiple itself to the check, not the inputs(parents) # Now handle the regular checks @@ -89,24 +89,24 @@ def graph_to_check_inputs( # Skip input point or infty point (they magically appear and do not have an origin formula) continue inputs = tuple(map(lambda pt: full_ctx.points[pt], full_ctx.parents[point])) - check_list = formula_checks.setdefault(formula, []) - check_list.append(inputs) + check_list = formula_checks.setdefault(formula, set()) + check_list.add(inputs) return formula_checks @public def evaluate_checks( - check_funcs: dict[str, Callable], check_inputs: dict[str, list[tuple[int, ...]]] + check_funcs: dict[str, Callable[[int, int], bool]], check_inputs: dict[str, set[tuple[int, ...]]] ) -> bool: """ Evaluate the checks for each formula type based on the provided functions and inputs. :param check_funcs: The functions to apply for each formula type. There are two callable types: - - `check(k, l, q)`, that gets applied to binary formulas (like `add`), where `k` and `l` are the input multiples + - `check(k, l)`, that gets applied to binary formulas (like `add`), where `k` and `l` are the input multiples of the base point and `q` is the base point order. - - `check(k, q)`, that gets applied to unary formulas (like conversion to affine `affine`), where `k` is the input multiple + - `check(k)`, that gets applied to unary formulas (like conversion to affine `affine`), where `k` is the input multiple of the base point and `q` is the base point order. - :param check_inputs: A dictionary mapping formula names to lists of tuples of input multiples. The output of + :param check_inputs: A dictionary mapping formula names to sets of tuples of input multiples. The output of :func:`graph_to_check_inputs`. :return: Whether any of the checks returned True -> whether the computation errors out. @@ -127,7 +127,7 @@ def errors_out( precomp_ctx: MultipleContext, full_ctx: MultipleContext, out: Point, - check_funcs: dict[str, Callable], + check_funcs: dict[str, Callable[[int, int], bool]], check_condition: Union[Literal["all"], Literal["necessary"]], precomp_to_affine: bool, use_init: bool = True, @@ -139,9 +139,9 @@ def errors_out( :param ctx: The context containing the points and formulas. :param out: The output point of the computation. :param check_funcs: The functions to apply for each formula type. There are two callable types: - - `check(k, l, q)`, that gets applied to binary formulas (like `add`), where `k` and `l` are the input multiples + - `check(k, l)`, that gets applied to binary formulas (like `add`), where `k` and `l` are the input multiples of the base point and `q` is the base point order. - - `check(k, q)`, that gets applied to unary formulas (like conversion to affine `affine`), where `k` is the input multiple + - `check(k)`, that gets applied to unary formulas (like conversion to affine `affine`), where `k` is the input multiple of the base point and `q` is the base point order. :param check_condition: Whether to check all points or only those necessary for the output point. :param precomp_to_affine: Whether to include the precomputed points in the to-affine checks. diff --git a/pyecsca/sca/re/rpa.py b/pyecsca/sca/re/rpa.py index 3fd87ba..83abbf5 100644 --- a/pyecsca/sca/re/rpa.py +++ b/pyecsca/sca/re/rpa.py @@ -486,7 +486,7 @@ def multiples_from_graph( return res def _necessary(ctx, for_what): - res = {ctx.points[out]} + res = {ctx.points[pt] for pt in for_what} queue = {*for_what} while queue: point = queue.pop() diff --git a/test/sca/test_epa.py b/test/sca/test_epa.py index e564177..23828b4 100644 --- a/test/sca/test_epa.py +++ b/test/sca/test_epa.py @@ -1,11 +1,12 @@ +import random from functools import partial import pytest from pyecsca.ec.coordinates import EFDCoordinateModel -from pyecsca.ec.mult import LTRMultiplier, CombMultiplier, WindowNAFMultiplier -from pyecsca.sca.re.rpa import multiple_graph -from pyecsca.sca.re.epa import errors_out +from pyecsca.ec.mult import * +from pyecsca.sca.re.rpa import multiple_graph, multiples_from_graph +from pyecsca.sca.re.epa import errors_out, graph_to_check_inputs def test_errors_out(secp128r1): @@ -109,7 +110,9 @@ def test_errors_out_precomp(secp128r1): scalar=15, params=secp128r1, mult_class=WindowNAFMultiplier, - mult_factory=partial(WindowNAFMultiplier, width=3, complete=False, precompute_negation=True), + mult_factory=partial( + WindowNAFMultiplier, width=3, complete=False, precompute_negation=True + ), ) affine_multiples = [] @@ -153,7 +156,9 @@ def test_errors_out_precomp(secp128r1): use_multiply=True, ) # There should be all of the results of the precomp, plus the final multiply result. - assert set(affine_multiples) == set(precomp_ctx.precomp.keys()) | {full_ctx.points[out]} + assert set(affine_multiples) == set(precomp_ctx.precomp.keys()) | { + full_ctx.points[out] + } # The add multiples should be the same as before, plus any inputs to add that happened # during the final multiply, there is only one, rest are doubles. assert set(add_multiples) == {(1, 2), (3, 2), (16, -1)} @@ -208,3 +213,196 @@ def test_errors_out_precomp(secp128r1): use_init=False, use_multiply=False, ) + + +@pytest.fixture( + params=[ + ( + SlidingWindowMultiplier, + dict(width=2, recoding_direction=ProcessingDirection.LTR), + ), + ( + SlidingWindowMultiplier, + dict(width=3, recoding_direction=ProcessingDirection.LTR), + ), + ( + SlidingWindowMultiplier, + dict(width=4, recoding_direction=ProcessingDirection.LTR), + ), + ( + SlidingWindowMultiplier, + dict(width=5, recoding_direction=ProcessingDirection.LTR), + ), + ( + SlidingWindowMultiplier, + dict(width=6, recoding_direction=ProcessingDirection.LTR), + ), + ( + SlidingWindowMultiplier, + dict(width=2, recoding_direction=ProcessingDirection.RTL), + ), + ( + SlidingWindowMultiplier, + dict(width=3, recoding_direction=ProcessingDirection.RTL), + ), + ( + SlidingWindowMultiplier, + dict(width=4, recoding_direction=ProcessingDirection.RTL), + ), + ( + SlidingWindowMultiplier, + dict(width=5, recoding_direction=ProcessingDirection.RTL), + ), + ( + SlidingWindowMultiplier, + dict(width=6, recoding_direction=ProcessingDirection.RTL), + ), + (FixedWindowLTRMultiplier, dict(m=2**1)), + (FixedWindowLTRMultiplier, dict(m=2**2)), + (FixedWindowLTRMultiplier, dict(m=2**3)), + (FixedWindowLTRMultiplier, dict(m=2**4)), + (FixedWindowLTRMultiplier, dict(m=2**5)), + (FixedWindowLTRMultiplier, dict(m=2**6)), + (WindowBoothMultiplier, dict(width=2)), + (WindowBoothMultiplier, dict(width=3)), + (WindowBoothMultiplier, dict(width=4)), + (WindowBoothMultiplier, dict(width=5)), + (WindowBoothMultiplier, dict(width=6)), + (WindowNAFMultiplier, dict(width=2)), + (WindowNAFMultiplier, dict(width=3)), + (WindowNAFMultiplier, dict(width=4)), + (WindowNAFMultiplier, dict(width=5)), + (WindowNAFMultiplier, dict(width=6)), + (BinaryNAFMultiplier, dict(always=False, direction=ProcessingDirection.LTR)), + (BinaryNAFMultiplier, dict(always=False, direction=ProcessingDirection.RTL)), + (BinaryNAFMultiplier, dict(always=True, direction=ProcessingDirection.LTR)), + (BinaryNAFMultiplier, dict(always=True, direction=ProcessingDirection.RTL)), + (CombMultiplier, dict(width=2, always=True)), + (CombMultiplier, dict(width=3, always=True)), + (CombMultiplier, dict(width=4, always=True)), + (CombMultiplier, dict(width=5, always=True)), + (CombMultiplier, dict(width=6, always=True)), + (CombMultiplier, dict(width=2, always=False)), + (CombMultiplier, dict(width=3, always=False)), + (CombMultiplier, dict(width=4, always=False)), + (CombMultiplier, dict(width=5, always=False)), + (CombMultiplier, dict(width=6, always=False)), + (BGMWMultiplier, dict(width=2, direction=ProcessingDirection.LTR)), + (BGMWMultiplier, dict(width=3, direction=ProcessingDirection.LTR)), + (BGMWMultiplier, dict(width=4, direction=ProcessingDirection.LTR)), + (BGMWMultiplier, dict(width=5, direction=ProcessingDirection.LTR)), + (BGMWMultiplier, dict(width=6, direction=ProcessingDirection.LTR)), + (BGMWMultiplier, dict(width=2, direction=ProcessingDirection.RTL)), + (BGMWMultiplier, dict(width=3, direction=ProcessingDirection.RTL)), + (BGMWMultiplier, dict(width=4, direction=ProcessingDirection.RTL)), + (BGMWMultiplier, dict(width=5, direction=ProcessingDirection.RTL)), + (BGMWMultiplier, dict(width=6, direction=ProcessingDirection.RTL)), + (LTRMultiplier, dict(always=False, complete=True)), + (LTRMultiplier, dict(always=True, complete=True)), + (LTRMultiplier, dict(always=False, complete=False)), + (LTRMultiplier, dict(always=True, complete=False)), + (RTLMultiplier, dict(always=False, complete=True)), + (RTLMultiplier, dict(always=True, complete=True)), + (RTLMultiplier, dict(always=False, complete=False)), + (RTLMultiplier, dict(always=True, complete=False)), + (CoronMultiplier, dict()), + (FullPrecompMultiplier, dict(always=False, complete=True)), + (FullPrecompMultiplier, dict(always=True, complete=True)), + (FullPrecompMultiplier, dict(always=False, complete=False)), + (FullPrecompMultiplier, dict(always=True, complete=False)), + (SimpleLadderMultiplier, dict(complete=True)), + (SimpleLadderMultiplier, dict(complete=False)), + ], + ids=lambda p: f"{p[0].__name__}-{','.join(f'{k}={v}' for k, v in p[1].items())}", +) +def mult(secp128r1, request): + mult_class, mult_kwargs = request.param + return mult_class, partial(mult_class, **mult_kwargs) + + +def test_independent_check_inputs(secp128r1, mult): + """ + Check that the set of check inputs is constant if (use_init = True, use_multiply = False) for all scalars + so that it only depends on the multiplier, countermeasure and error model, not particular scalars. + """ + mult_class, mult_factory = mult + for check_condition in ("all", "necessary"): + for precomp_to_affine in (True, False): + last_check_inputs = None + for i in range(20): + scalar = random.getrandbits(secp128r1.order.bit_length()) + precomp_ctx, full_ctx, out = multiple_graph( + scalar=scalar, + params=secp128r1, + mult_class=mult_class, + mult_factory=mult_factory, + ) + check_inputs = graph_to_check_inputs( + precomp_ctx, + full_ctx, + out, + check_condition=check_condition, + precomp_to_affine=precomp_to_affine, + use_init=True, + use_multiply=False, + ) + if last_check_inputs is not None: + assert ( + check_inputs == last_check_inputs + ), f"Failed for {check_condition}, precomp_to_affine={precomp_to_affine}, scalar={scalar}, mult={mult_class.__name__}" + last_check_inputs = check_inputs + + +@pytest.mark.parametrize("check_condition,precomp_to_affine,multiples_kind", [ + ("all", True, "all"), + ("all", False, "all"), + ("necessary", True, "precomp+necessary"), + ("necessary", False, "necessary"), +]) +def test_consistency_multiples(secp128r1, mult, check_condition, precomp_to_affine, multiples_kind): + """ + Test consistency between the graph_to_check_inputs and multiples_computed functions for the same error model + """ + for _ in range(10): + mult_class, mult_factory = mult + scalar = random.getrandbits(secp128r1.order.bit_length()) + precomp_ctx, full_ctx, out = multiple_graph( + scalar=scalar, + params=secp128r1, + mult_class=mult_class, + mult_factory=mult_factory, + ) + check_inputs = graph_to_check_inputs( + precomp_ctx, + full_ctx, + out, + check_condition=check_condition, + precomp_to_affine=precomp_to_affine, + use_init=True, + use_multiply=True, + ) + # Now map the check inputs to the set of multiples they cover + multiples_from_check_inputs = set() + for k, in check_inputs.get("neg", []): + multiples_from_check_inputs.add(k) + multiples_from_check_inputs.add(-k) + for k, in check_inputs.get("affine", []): + multiples_from_check_inputs.add(k) + for k, l in check_inputs.get("add", []): + multiples_from_check_inputs.add(k) + multiples_from_check_inputs.add(l) + multiples_from_check_inputs.add(k + l) + for k, in check_inputs.get("dbl", []): + multiples_from_check_inputs.add(k) + multiples_from_check_inputs.add(2 * k) + # Multiples computed removes the zero + multiples_from_check_inputs.discard(0) + + # Now compute the multiples via the other function to compare. + multiples = multiples_from_graph( + precomp_ctx, + full_ctx, + out, + kind=multiples_kind + ) + assert multiples_from_check_inputs == multiples |