diff options
| -rw-r--r-- | docs/references.rst | 5 | ||||
| -rw-r--r-- | pyecsca/ec/configuration.py | 4 | ||||
| -rw-r--r-- | pyecsca/ec/curve.py | 17 | ||||
| -rw-r--r-- | pyecsca/sca/re/rpa.py | 6 | ||||
| -rw-r--r-- | pyecsca/sca/re/zvp.py | 190 | ||||
| -rw-r--r-- | test/ec/test_mult.py | 1 | ||||
| -rw-r--r-- | test/sca/test_zvp.py | 80 |
7 files changed, 282 insertions, 21 deletions
diff --git a/docs/references.rst b/docs/references.rst index 63aaf41..d215948 100644 --- a/docs/references.rst +++ b/docs/references.rst @@ -8,3 +8,8 @@ References .. [HEHCC] Handbook of Elliptic and Hyper-Elliptic Curve Cryptography, https://www.hyperelliptic.org/HEHCC/ .. [HAC] Handbook of Applied Cryptography, https://cacr.uwaterloo.ca/hac/ .. [BBG+17] Sliding right into disaster: Left-to-right sliding windows leak, https://eprint.iacr.org/2017/627.pdf +.. [RPA] A Refined Power-Analysis Attack on Elliptic Curve Cryptosystems, http://www.goubin.fr/papers/ecc-dpa.pdf +.. [ZVP] Zero-value point attacks on elliptic curve cryptosystem, https://doi.org/10.1007/10958513_17 +.. [EPA] Exceptional procedure attack on elliptic curve cryptosystems, https://doi.org/10.1007/3-540-36288-6_17 +.. [FFD] A formula for disaster: a unified approach to elliptic curve special-point-based attacks, https://eprint.iacr.org/2021/1595.pdf +.. [MT1991] Mazur, B., & Tate, J. (1991). The `p`-adic sigma function. Duke Mathematical Journal, 62 (3), 663-688. diff --git a/pyecsca/ec/configuration.py b/pyecsca/ec/configuration.py index 03dc86b..6ed2190 100644 --- a/pyecsca/ec/configuration.py +++ b/pyecsca/ec/configuration.py @@ -1,5 +1,6 @@ """Provides a way to work with and enumerate implementation configurations.""" import warnings +from abc import ABC from dataclasses import dataclass from enum import Enum from itertools import product @@ -146,7 +147,7 @@ def all_configurations(**kwargs) -> Generator[Configuration, Configuration, None for subclass in subs: if subclass.__subclasses__(): result.update(leaf_subclasses(subclass)) - else: + elif not issubclass(subclass, ABC): result.add(subclass) return result @@ -240,6 +241,7 @@ def all_configurations(**kwargs) -> Generator[Configuration, Configuration, None continue coords_formulas = coords.formulas.values() mult_classes = leaf_subclasses(ScalarMultiplier) + if "scalarmult" in kwargs: if isinstance(kwargs["scalarmult"], ScalarMultiplier): mults = [kwargs["scalarmult"]] diff --git a/pyecsca/ec/curve.py b/pyecsca/ec/curve.py index fb567e8..8cc7dba 100644 --- a/pyecsca/ec/curve.py +++ b/pyecsca/ec/curve.py @@ -2,7 +2,7 @@ from ast import Module from astunparse import unparse from copy import copy -from typing import MutableMapping, Union, List, Optional, Dict +from typing import MutableMapping, Union, List, Optional, Dict, Set from public import public from sympy import FF, sympify @@ -303,6 +303,21 @@ class EllipticCurve: f"Wrong encoding type: {hex(encoded[0])}, should be one of 0x04, 0x06, 0x02, 0x03 or 0x00" ) + def affine_lift_x(self, x: Mod) -> Set[Point]: + """ + Lift an x-coordinate to the curve. + + :param x: The x-coordinate. + :return: Lifted (affine) points, if any. + """ + loc = {**self.parameters, "x": x} + ysquared = eval(compile(self.model.ysquared, "", mode="eval"), loc) + if not ysquared.is_residue(): + return set() + y = ysquared.sqrt() + return {Point(AffineCoordinateModel(self.model), x=x, y=y), + Point(AffineCoordinateModel(self.model), x=x, y=-y)} + def affine_random(self) -> Point: """Generate a random affine point on the curve.""" while True: diff --git a/pyecsca/sca/re/rpa.py b/pyecsca/sca/re/rpa.py index 212e147..721498c 100644 --- a/pyecsca/sca/re/rpa.py +++ b/pyecsca/sca/re/rpa.py @@ -89,7 +89,7 @@ class MultipleContext(Context): def rpa_point_0y(params: DomainParameters) -> Optional[Point]: - """Construct an (affine) RPA point (0, y) for given domain parameters.""" + """Construct an (affine) [RPA]_ point (0, y) for given domain parameters.""" if isinstance(params.curve.model, ShortWeierstrassModel): if not params.curve.parameters["b"].is_residue(): return None @@ -104,7 +104,7 @@ def rpa_point_0y(params: DomainParameters) -> Optional[Point]: def rpa_point_x0(params: DomainParameters) -> Optional[Point]: - """Construct an (affine) RPA point (x, 0) for given domain parameters.""" + """Construct an (affine) [RPA]_ point (x, 0) for given domain parameters.""" if isinstance(params.curve.model, ShortWeierstrassModel): if (params.order * params.cofactor) % 2 != 0: return None @@ -129,7 +129,7 @@ def rpa_point_x0(params: DomainParameters) -> Optional[Point]: def rpa_distinguish(params: DomainParameters, mults: List[ScalarMultiplier], oracle: Callable[[int, Point], bool]) -> List[ScalarMultiplier]: """ Distinguish the scalar multiplier used (from the possible :paramref:`~.rpa_distinguish.mults`) using - an RPA :paramref:`~.rpa_distinguish.oracle`. + an [RPA]_ :paramref:`~.rpa_distinguish.oracle`. :param params: The domain parameters to use. :param mults: The list of possible multipliers. diff --git a/pyecsca/sca/re/zvp.py b/pyecsca/sca/re/zvp.py index 413e75a..9d1a6d1 100644 --- a/pyecsca/sca/re/zvp.py +++ b/pyecsca/sca/re/zvp.py @@ -4,18 +4,23 @@ Provides functionality inspired by the Zero-value point attack. Zero-Value Point Attacks on Elliptic Curve Cryptosystem, Toru Akishita & Tsuyoshi Takagi , ISC '03 `<https://doi.org/10.1007/10958513_17>`_ """ -from typing import List +from typing import List, Set +from public import public +import contextlib -from sympy import symbols +from sympy import symbols, FF, Poly, Monomial, Symbol, Expr from ...ec.context import DefaultContext, local +from ...ec.curve import EllipticCurve +from ...ec.divpoly import mult_by_n from ...ec.formula import Formula -from ...ec.mod import SymbolicMod +from ...ec.mod import SymbolicMod, Mod from ...ec.point import Point from ...misc.cfg import TemporaryConfig -def unroll_formula(formula: Formula, prime: int) -> List[SymbolicMod]: +@public +def unroll_formula(formula: Formula, prime: int) -> List[Poly]: """ Unroll a given formula symbolically to obtain symbolic expressions for its intermediate values. @@ -23,6 +28,7 @@ def unroll_formula(formula: Formula, prime: int) -> List[SymbolicMod]: :param prime: Field to unroll over, necessary for technical reasons. :return: List of symbolic intermediate values. """ + field = FF(prime) inputs = [Point(formula.coordinate_model, **{var: SymbolicMod(symbols(var + str(i)), prime) for var in formula.coordinate_model.variables}) for i in @@ -31,4 +37,178 @@ def unroll_formula(formula: Formula, prime: int) -> List[SymbolicMod]: with local(DefaultContext()) as ctx, TemporaryConfig() as cfg: cfg.ec.mod_implementation = "symbolic" formula(prime, *inputs, **params) - return [op_result.value for op_result in ctx.actions.get_by_index([0])[0].op_results] + return [Poly(op_result.value.x, *op_result.value.x.free_symbols, domain=field) for op_result in + ctx.actions.get_by_index([0])[0].op_results] + + +def curve_equation(x: Symbol, curve: EllipticCurve, symbolic: bool = True) -> Expr: + """ + Get the "ysquared" curve polynomial in :paramref:`~.x` for the :paramref:`~.curve`, + either symbolically or with concrete parameter values. + + :param x: + :param curve: + :param symbolic: + :return: + """ + parameters = {name: symbols(name) if symbolic else curve.parameters[name] for name in curve.model.parameter_names} + return eval(compile(curve.model.ysquared, "", mode="eval"), {"x": x, **parameters}) + + +def subs_curve_equation(poly: Poly, curve: EllipticCurve) -> Poly: + """ + Substitute in the curve equation "ysquared" for Y repeatedly to + eliminate all but singular powers of Y. + + :param poly: + :param curve: + :return: + """ + terms = [] + for term in poly.terms(): + sub = 1 + new_term = [] + for power, gen in zip(term[0], poly.gens): + if str(gen).startswith("Y"): + X = symbols("X" + str(gen)[1:]) + ysquared = curve_equation(X, curve) + sub *= ysquared ** (power // 2) + power %= 2 + new_term.append(power) + expr = Monomial(new_term, poly.gens).as_expr() * sub * term[1] + terms.append(expr) + return Poly(sum(terms), domain=poly.domain) + + +def subs_curve_params(poly: Poly, curve: EllipticCurve) -> Poly: + """ + Substitute in the concrete curve parameters. + + :param poly: + :param curve: + :return: + """ + for name, value in curve.parameters.items(): + symbol = symbols(name) + if symbol in poly.gens: + poly = poly.subs(symbol, value) + return poly + + +def subs_dlog(poly: Poly, k: int, curve: EllipticCurve): + """ + Substitute in the multiplication-by-k-map(X1) in place of X2. + + :param poly: + :param k: + :param curve: + :return: + """ + X1, X2 = symbols("X1,X2") + if X2 not in poly.gens: + return poly + max_degree = poly.degree(X2) + X2i = poly.gens.index(X2) + new_gens = set(poly.gens) + new_gens.remove(X2) + + mx, my = mult_by_n(curve, k) + u, v = mx[0].subs("x", X1), mx[1].subs("x", X1) + + res = 0 + for term in poly.terms(): + powers = list(term[0]) + u_power = powers[X2i] + u_factor = u**u_power + v_power = max_degree - u_power + v_factor = v**v_power + powers[X2i] = 0 + monom = Monomial(powers, poly.gens).as_expr() * term[1] + res += Poly(monom, *new_gens, domain=poly.domain) * u_factor * v_factor + return Poly(res, domain=poly.domain) + + +def remove_z(poly: Poly) -> Poly: + """ + Substitute in 1 for all Zs (because we can do that ;). + + :param poly: + :return: + """ + for gen in poly.gens: + if str(gen).startswith("Z"): + poly = poly.subs(gen, 1) + return poly + + +def eliminate_y(poly: Poly, curve: EllipticCurve) -> Poly: + """ + Eliminate the remaining Ys (only power 1). + + See [FFD]_ page 11. + + :param poly: + :param curve: + :return: + """ + Y1, Y2 = symbols("Y1,Y2") + Y1i = None + with contextlib.suppress(ValueError): + Y1i = poly.gens.index(Y1) + Y2i = None + with contextlib.suppress(ValueError): + Y2i = poly.gens.index(Y2) + f0 = 0 + f1 = 0 + f2 = 0 + f12 = 0 + for term in poly.terms(): + monom = term[0] + monom_expr = Monomial(term[0], poly.gens).as_expr() * term[1] + y1_present = not (Y1i is None or monom[Y1i] == 0) + y2_present = not (Y2i is None or monom[Y2i] == 0) + if y1_present and y2_present: + f12 += monom_expr.subs(Y1, 1).subs(Y2, 1) + elif y1_present and not y2_present: + f1 += monom_expr.subs(Y1, 1) + elif not y1_present and y2_present: + f2 += monom_expr.subs(Y2, 1) + elif not y1_present and not y2_present: + f0 += monom_expr + fe_X1 = curve_equation(symbols("X1"), curve) + fe_X2 = curve_equation(symbols("X2"), curve) + + # [FFD] page 11 + f_prime = fe_X2 * (fe_X1 * 2 * f1 * f12 - 2 * f0 * f2) ** 2 - \ + (f0 ** 2 + f2 ** 2 * fe_X2 - fe_X1 * (f1 ** 2 + f12 ** 2 * fe_X2)) ** 2 + return Poly(f_prime, domain=poly.domain) + + +@public +def zvp_point(poly: Poly, curve: EllipticCurve, k: int) -> Set[Point]: + """ + Find a set of ZVP points for a given intermediate value and dlog relationship. + + :param poly: The polynomial to zero out, obtained as a result of :py:meth:`.unroll_formula`. + :param curve: The curve to compute over. + :param k: The discrete-log relationship between the two points, i.e. (X2, Y2) = [k](X1, Y1) + :return: The set of points (X1, Y1). + """ + # Start with removing all squares of Y1, Y2 + subbed = subs_curve_equation(poly, curve) + # Remove the Zs by setting them to 1 + removed = remove_z(subbed) + # Now remove the rest of the Ys by clever curve equation use + eliminated = eliminate_y(removed, curve) + # Substitute in the mult-by-k map + dlog = subs_dlog(eliminated, k, curve) + # Put in concrete curve parameters + final = subs_curve_params(dlog, curve) + # Find the roots (X1) + roots = final.ground_roots() + points = set() + # Finally lift the roots to find the points (if any) + for root, multiplicity in roots.items(): + pt = curve.affine_lift_x(Mod(int(root), curve.prime)) + points.update(pt) + return points diff --git a/test/ec/test_mult.py b/test/ec/test_mult.py index 2a17867..8e5a06e 100644 --- a/test/ec/test_mult.py +++ b/test/ec/test_mult.py @@ -18,7 +18,6 @@ from pyecsca.ec.mult import ( AccumulationOrder, ScalarMultiplier, SlidingWindowMultiplier ) from pyecsca.ec.point import InfinityPoint, Point -from .utils import cartesian def get_formulas(coords, *names): diff --git a/test/sca/test_zvp.py b/test/sca/test_zvp.py index 3b6b046..76fb7cb 100644 --- a/test/sca/test_zvp.py +++ b/test/sca/test_zvp.py @@ -1,13 +1,73 @@ -from pyecsca.sca.re.zvp import unroll_formula +import pytest +from pyecsca.sca.re.zvp import unroll_formula, subs_curve_equation, remove_z, eliminate_y, subs_dlog, subs_curve_params, \ + zvp_point +from sympy import symbols, Poly -def test_unroll(secp128r1): - add = secp128r1.curve.coordinate_model.formulas["add-2007-bl"] - dbl = secp128r1.curve.coordinate_model.formulas["dbl-2007-bl"] - neg = secp128r1.curve.coordinate_model.formulas["neg"] - results = unroll_formula(add, 11) - assert results is not None - results = unroll_formula(dbl, 11) - assert results is not None - results = unroll_formula(neg, 11) + +@pytest.fixture(params=["add-2007-bl", "dbl-2007-bl", "add-2016-rcb"]) +def formula(secp128r1, request): + return secp128r1.curve.coordinate_model.formulas[request.param] + + +def test_unroll(secp128r1, formula): + results = unroll_formula(formula, secp128r1.curve.prime) assert results is not None + for res in results: + assert isinstance(res, Poly) + + +def test_curve_elimination(secp128r1, formula): + unrolled = unroll_formula(formula, secp128r1.curve.prime) + subbed = subs_curve_equation(unrolled[-1], secp128r1.curve) + assert subbed is not None + Y1, Y2 = symbols("Y1,Y2") + + # The resulting polynomial should not have Y1 and Y2 in higher powers than 1. + for term in subbed.terms(): + powers = dict(zip(subbed.gens, term[0])) + assert powers.get(Y1, 0) in (0, 1) + assert powers.get(Y2, 0) in (0, 1) + + +def test_remove_z(secp128r1, formula): + unrolled = unroll_formula(formula, secp128r1.curve.prime) + removed = remove_z(unrolled[-1]) + for gen in removed.gens: + assert not str(gen).startswith("Z") + + +def test_eliminate_y(secp128r1, formula): + unrolled = unroll_formula(formula, secp128r1.curve.prime) + subbed = subs_curve_equation(unrolled[-1], secp128r1.curve) + eliminated = eliminate_y(subbed, secp128r1.curve) + assert eliminated is not None + assert isinstance(eliminated, Poly) + Y1, Y2 = symbols("Y1,Y2") + + assert Y1 not in eliminated.gens + assert Y2 not in eliminated.gens + + +def test_full(secp128r1, formula): + unrolled = unroll_formula(formula, secp128r1.curve.prime) + subbed = subs_curve_equation(unrolled[-1], secp128r1.curve) + removed = remove_z(subbed) + eliminated = eliminate_y(removed, secp128r1.curve) + dlog = subs_dlog(eliminated, 3, secp128r1.curve) + assert dlog is not None + assert isinstance(dlog, Poly) + X1, X2 = symbols("X1,X2") + assert X2 not in dlog.gens + + final = subs_curve_params(dlog, secp128r1.curve) + assert final is not None + assert isinstance(final, Poly) + assert final.gens == (X1,) + + +def test_zvp(secp128r1, formula): + unrolled = unroll_formula(formula, secp128r1.curve.prime) + poly = unrolled[-2] + points = zvp_point(poly, secp128r1.curve, 5) + assert isinstance(points, set) |