diff options
| -rw-r--r-- | .github/workflows/lint.yml | 10 | ||||
| -rw-r--r-- | .github/workflows/perf.yml | 14 | ||||
| -rw-r--r-- | .github/workflows/test.yml | 14 | ||||
| -rw-r--r-- | README.md | 1 | ||||
| -rw-r--r-- | docs/index.rst | 2 | ||||
| -rw-r--r-- | pyecsca/sca/re/tree.py | 15 | ||||
| -rw-r--r-- | pyecsca/sca/re/zvp.py | 133 | ||||
| -rw-r--r-- | pyproject.toml | 8 |
8 files changed, 132 insertions, 65 deletions
diff --git a/.github/workflows/lint.yml b/.github/workflows/lint.yml index 0f64bd9..88553e6 100644 --- a/.github/workflows/lint.yml +++ b/.github/workflows/lint.yml @@ -6,25 +6,25 @@ env: LLVM_CONFIG: /usr/bin/llvm-config-10 PS_PACKAGES: libps4000 libps5000 libps6000 GMP_PACKAGES: libgmp-dev libmpfr-dev libmpc-dev - OTHER_PACKAGES: swig gcc libpcsclite-dev llvm-10 libllvm10 llvm-10-dev + OTHER_PACKAGES: swig gcc libpcsclite-dev llvm-10 libllvm10 llvm-10-dev libpari-dev pari-gp pari-seadata jobs: lint: runs-on: ubuntu-20.04 steps: - - uses: actions/checkout@v3 + - uses: actions/checkout@v4 with: submodules: true - - uses: actions/cache@v3 + - uses: actions/cache@v4 with: path: ~/.cache/pip key: pip-${{ runner.os }}-3.9-${{ hashFiles('pyproject.toml') }} restore-keys: | pip-${{ runner.os }}- - name: Setup Python 3.9 - uses: actions/setup-python@v3 + uses: actions/setup-python@v5 with: - python-version: "3.9" + python-version: "3.10" - name: Add picoscope repository run: | curl "https://labs.picotech.com/debian/dists/picoscope/Release.gpg.key" | sudo apt-key add diff --git a/.github/workflows/perf.yml b/.github/workflows/perf.yml index 3a6bf7a..6f1da7e 100644 --- a/.github/workflows/perf.yml +++ b/.github/workflows/perf.yml @@ -6,23 +6,23 @@ env: LLVM_CONFIG: /usr/bin/llvm-config-10 PS_PACKAGES: libps4000 libps5000 libps6000 GMP_PACKAGES: libgmp-dev libmpfr-dev libmpc-dev - OTHER_PACKAGES: swig gcc libpcsclite-dev llvm-10 libllvm10 llvm-10-dev + OTHER_PACKAGES: swig gcc libpcsclite-dev llvm-10 libllvm10 llvm-10-dev libpari-dev pari-gp pari-seadata jobs: perf: runs-on: ubuntu-20.04 strategy: matrix: - python-version: ["3.8", "3.9"] + python-version: ["3.9", "3.10"] gmp: [0, 1] env: PYTHON: ${{ matrix.python-version }} USE_GMP: ${{ matrix.gmp }} steps: - - uses: actions/checkout@v3 + - uses: actions/checkout@v4 with: submodules: true - - uses: actions/cache@v3 + - uses: actions/cache@v4 with: path: ~/.cache/pip key: pip-${{ runner.os }}-${{ matrix.gmp }}-${{ matrix.python-version }}-${{ hashFiles('pyproject.toml') }} @@ -31,7 +31,7 @@ jobs: pip-${{ runner.os }}-${{ matrix.gmp }}- pip-${{ runner.os }}- - name: Setup Python ${{ matrix.python-version }} - uses: actions/setup-python@v3 + uses: actions/setup-python@v5 with: python-version: ${{ matrix.python-version }} - name: Add picoscope repository @@ -53,8 +53,8 @@ jobs: - name: Install dependencies run: | python -m pip install -U pip setuptools wheel - if [ $USE_GMP == 1 ]; then pip install -e ".[picoscope_sdk, picoscope_alt, chipwhisperer, smartcard, gmp, test, dev]"; fi - if [ $USE_GMP == 0 ]; then pip install -e ".[picoscope_sdk, picoscope_alt, chipwhisperer, smartcard, test, dev]"; fi + if [ $USE_GMP == 1 ]; then pip install -e ".[picoscope_sdk, picoscope_alt, chipwhisperer, smartcard, pari, gmp, test, dev]"; fi + if [ $USE_GMP == 0 ]; then pip install -e ".[picoscope_sdk, picoscope_alt, chipwhisperer, smartcard, pari, test, dev]"; fi - name: Perf run: | make perf diff --git a/.github/workflows/test.yml b/.github/workflows/test.yml index 09736e4..77aae77 100644 --- a/.github/workflows/test.yml +++ b/.github/workflows/test.yml @@ -6,23 +6,23 @@ env: LLVM_CONFIG: /usr/bin/llvm-config-10 PS_PACKAGES: libps4000 libps5000 libps6000 GMP_PACKAGES: libgmp-dev libmpfr-dev libmpc-dev - OTHER_PACKAGES: swig gcc libpcsclite-dev llvm-10 libllvm10 llvm-10-dev + OTHER_PACKAGES: swig gcc libpcsclite-dev llvm-10 libllvm10 llvm-10-dev libpari-dev pari-gp pari-seadata jobs: test: runs-on: ubuntu-20.04 strategy: matrix: - python-version: ["3.8", "3.9", "3.10"] + python-version: ["3.9", "3.10"] gmp: [0, 1] env: PYTHON: ${{ matrix.python-version }} USE_GMP: ${{ matrix.gmp }} steps: - - uses: actions/checkout@v3 + - uses: actions/checkout@v4 with: submodules: true - - uses: actions/cache@v3 + - uses: actions/cache@v4 with: path: ~/.cache/pip key: pip-${{ runner.os }}-${{ matrix.gmp }}-${{ matrix.python-version }}-${{ hashFiles('pyproject.toml') }} @@ -31,7 +31,7 @@ jobs: pip-${{ runner.os }}-${{ matrix.gmp }}- pip-${{ runner.os }}- - name: Setup Python ${{ matrix.python-version }} - uses: actions/setup-python@v3 + uses: actions/setup-python@v5 with: python-version: ${{ matrix.python-version }} - name: Add picoscope repository @@ -53,8 +53,8 @@ jobs: - name: Install dependencies run: | python -m pip install -U pip setuptools wheel - if [ $USE_GMP == 1 ]; then pip install -e ".[picoscope_sdk, picoscope_alt, chipwhisperer, smartcard, gmp, test, dev]"; fi - if [ $USE_GMP == 0 ]; then pip install -e ".[picoscope_sdk, picoscope_alt, chipwhisperer, smartcard, test, dev]"; fi + if [ $USE_GMP == 1 ]; then pip install -e ".[picoscope_sdk, picoscope_alt, chipwhisperer, smartcard, pari, gmp, test, dev]"; fi + if [ $USE_GMP == 0 ]; then pip install -e ".[picoscope_sdk, picoscope_alt, chipwhisperer, smartcard, pari, test, dev]"; fi - name: Test run: | make test @@ -34,6 +34,7 @@ It is currently in an alpha stage of development and thus only provides: - [Numpy](https://www.numpy.org/) - [Scipy](https://www.scipy.org/) - [sympy](https://sympy.org/) + - [pandas](https://pandas.pydata.org/) - [atpublic](https://public.readthedocs.io/) - [fastdtw](https://github.com/slaypni/fastdtw) - [asn1crypto](https://github.com/wbond/asn1crypto) diff --git a/docs/index.rst b/docs/index.rst index 88b9292..a6943ae 100644 --- a/docs/index.rst +++ b/docs/index.rst @@ -126,6 +126,7 @@ Requirements - Numpy_ - Scipy_ - sympy_ + - pandas_ - atpublic_ - fastdtw_ - asn1crypto_ @@ -220,6 +221,7 @@ Development was supported by the Masaryk University grant `MUNI/C/1707/2018 <htt .. _Numpy: https://www.numpy.org .. _Scipy: https://www.scipy.org .. _sympy: https://sympy.org/ +.. _pandas: https://pandas.pydata.org/ .. _matplotlib: https://matplotlib.org/ .. _atpublic: https://public.readthedocs.io/ .. _fastdtw: https://github.com/slaypni/fastdtw diff --git a/pyecsca/sca/re/tree.py b/pyecsca/sca/re/tree.py index 305d1b1..0f6bcf1 100644 --- a/pyecsca/sca/re/tree.py +++ b/pyecsca/sca/re/tree.py @@ -189,9 +189,9 @@ def _build_tree(cfgs: Set[Any], *maps: Map, response: Optional[Any] = None) -> N # 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). n_cfgs = len(cfgs) - ncfgs = set(cfgs) + cfgset = set(cfgs) if n_cfgs == 1: - return Node(ncfgs, response=response) + return Node(cfgset, response=response) # Go over the maps and figure out which one splits the best. best_distinguishing_column = None @@ -214,18 +214,23 @@ def _build_tree(cfgs: Set[Any], *maps: Map, response: Optional[Any] = None) -> N # Early abort if optimal score is hit. The +1 is for "None" values which are not in the codomain. if score == ceil(n_cfgs / (len(dmap.codomain) + 1)): break + # We found nothing distinguishing the configs, so return them all (base case 2). + if best_distinguishing_column is None or best_distinguishing_dmap is None: + return Node(cfgset, response=response) - best_distinguishing_element = best_distinguishing_dmap.domain[best_distinguishing_column] + best_distinguishing_element = best_distinguishing_dmap.domain[ + best_distinguishing_column + ] # Now we have a dmap as well as an element in it that splits the best. # Go over the groups of configs that share the response groups = best_restricted.groupby(best_distinguishing_column, dropna=False) # type: ignore # We found nothing distinguishing the configs, so return them all (base case 2). if groups.ngroups == 1: - return Node(ncfgs, response=response) + return Node(cfgset, response=response) # Create our node dmap_index = maps.index(best_distinguishing_dmap) - result = Node(ncfgs, dmap_index, best_distinguishing_element, response=response) + result = Node(cfgset, dmap_index, best_distinguishing_element, response=response) for output, group in groups: child = _build_tree(set(group.index), *maps, response=output) diff --git a/pyecsca/sca/re/zvp.py b/pyecsca/sca/re/zvp.py index 9608745..4a783a2 100644 --- a/pyecsca/sca/re/zvp.py +++ b/pyecsca/sca/re/zvp.py @@ -8,8 +8,6 @@ from public import public from astunparse import unparse from sympy import FF, Poly, Monomial, Symbol, Expr, sympify, symbols, div -from tqdm.auto import tqdm - from .rpa import MultipleContext from ...ec.context import local from ...ec.curve import EllipticCurve @@ -29,6 +27,15 @@ from ...ec.params import DomainParameters from ...ec.point import Point +has_pari = False +try: + import cypari2 + + has_pari = True +except ImportError: + cypari2 = None + + @public def unroll_formula_expr(formula: Formula) -> List[Tuple[str, Expr]]: """ @@ -464,55 +471,105 @@ def zvp_points(poly: Poly, curve: EllipticCurve, k: int, n: int) -> Set[Point]: # Now decide on the special case: if only_1: # if only_1, dlog sub is not necessary, also computing the other point is not necessary - final = subs_curve_params(eliminated, curve) - roots = final.ground_roots() - for root, multiplicity in roots.items(): - pt = curve.affine_lift_x(Mod(int(root), curve.prime)) - for point in pt: - inputs = {"x1": point.x, "y1": point.y, **curve.parameters} - res = poly.eval([inputs[str(gen)] for gen in poly.gens]) # type: ignore[attr-defined] - if res == 0: - points.add(point) + for point in solve_easy_dcp(eliminated, curve): + inputs = {"x1": point.x, "y1": point.y, **curve.parameters} + res = poly.eval([inputs[str(gen)] for gen in poly.gens]) # type: ignore[attr-defined] + if res == 0: + points.add(point) elif only_2: # if only_2, dlog sub is not necessary, then multiply with k_inverse to obtain target point - final = subs_curve_params(eliminated, curve) - roots = final.ground_roots() k_inv = Mod(k, n).inverse() - for root, multiplicity in roots.items(): - pt = curve.affine_lift_x(Mod(int(root), curve.prime)) - for point in pt: - inputs = {"x2": point.x, "y2": point.y, **curve.parameters} - res = poly.eval([inputs[str(gen)] for gen in poly.gens]) # type: ignore[attr-defined] - if res == 0: - one = curve.affine_multiply(point, int(k_inv)) - points.add(one) + for point in solve_easy_dcp(eliminated, curve): + inputs = {"x2": point.x, "y2": point.y, **curve.parameters} + res = poly.eval([inputs[str(gen)] for gen in poly.gens]) # type: ignore[attr-defined] + if res == 0: + one = curve.affine_multiply(point, int(k_inv)) + points.add(one) else: # otherwise we need to sub in the dlog and solve the general case + for point in solve_hard_dcp(eliminated, curve, k): + # Check that the points zero out the original polynomial to filter out erroneous candidates + other = curve.affine_multiply(point, k) + inputs = { + "x1": point.x, + "y1": point.y, + "x2": other.x, + "y2": other.y, + **curve.parameters, + } + res = poly.eval([inputs[str(gen)] for gen in poly.gens]) # type: ignore[attr-defined] + if res == 0: + points.add(point) + return points + + +def solve_easy_dcp(xonly_polynomial: Poly, curve: EllipticCurve) -> Set[Point]: + points = set() + final = subs_curve_params(xonly_polynomial, curve) + if has_pari: + pari = cypari2.Pari() + polynomial = pari(str(final.expr).replace("**", "^")) + roots = list(map(int, pari.polrootsmod(polynomial, curve.prime))) + else: + roots = final.ground_roots().keys() + for root in roots: + points.update(curve.affine_lift_x(Mod(int(root), curve.prime))) + return points + + +def solve_hard_dcp(xonly_polynomial: Poly, curve: EllipticCurve, k: int) -> Set[Point]: + points = set() + if has_pari: + roots = solve_hard_dcp_cypari(xonly_polynomial, curve, k) + else: # Substitute in the mult-by-k map - dlog = subs_dlog(eliminated, k, curve) + dlog = subs_dlog(xonly_polynomial, k, curve) # Put in concrete curve parameters final = subs_curve_params(dlog, curve) # Find the roots (X1) - roots = final.ground_roots() + roots = final.ground_roots().keys() # 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)) - # Check that the points zero out the original polynomial to filter out erroneous candidates - for point in pt: - other = curve.affine_multiply(point, k) - inputs = { - "x1": point.x, - "y1": point.y, - "x2": other.x, - "y2": other.y, - **curve.parameters, - } - res = poly.eval([inputs[str(gen)] for gen in poly.gens]) # type: ignore[attr-defined] - if res == 0: - points.add(point) + for root in roots: + points.update(curve.affine_lift_x(Mod(int(root), curve.prime))) return points +def solve_hard_dcp_cypari(xonly_polynomial: Poly, curve: EllipticCurve, k: int) -> Set[int]: + a, b = int(curve.parameters["a"]), int(curve.parameters["b"]) + xonly_polynomial = subs_curve_params(xonly_polynomial, curve) + + pari = cypari2.Pari() + e = pari.ellinit([a, b], curve.prime) + while True: + try: + mul = pari.ellxn(e, k) + break + except cypari2.PariError as e: + if e.errnum() == 17: # out of stack memory + pari.allocatemem(0) + else: + raise e + x1, x2 = pari("x1"), pari("x2") + polynomial = pari(str(xonly_polynomial.expr).replace("**", "^")) + + polydeg = pari.poldegree(polynomial, x2) + subspoly = 0 + x = pari("x") + num, den = pari.subst(mul[0], x, x1), pari.subst(mul[1], x, x1) + for deg in range(polydeg+1): + monomial = pari.polcoef(polynomial, deg, x2) + monomial *= polypower(pari, num, deg) + monomial *= polypower(pari, den, polydeg-deg) + subspoly += monomial + return set(map(int, pari.polrootsmod(subspoly, curve.prime))) + + +def polypower(pari, polynomial, power): + g = pari("g") + gpower = pari(f"g^{power}") + return pari.subst(gpower, g, polynomial) + + def addition_chain( scalar: int, params: DomainParameters, diff --git a/pyproject.toml b/pyproject.toml index 089c6c2..c0968fa 100644 --- a/pyproject.toml +++ b/pyproject.toml @@ -19,18 +19,19 @@ "License :: OSI Approved :: MIT License", "Topic :: Security", "Topic :: Security :: Cryptography", - "Programming Language :: Python :: 3.8", "Programming Language :: Python :: 3.9", "Programming Language :: Python :: 3.10", "Programming Language :: Python :: 3.11", + "Programming Language :: Python :: 3.12", "Intended Audience :: Developers", "Intended Audience :: Science/Research" ] - requires-python = ">=3.8" + requires-python = ">=3.9" dependencies = [ "numpy==1.24.4", "scipy", "sympy>=1.7.1", + "pandas", "atpublic", "cython", "fastdtw", @@ -81,7 +82,8 @@ markers = [ "slow: marks tests as slow (deselect with '-m \"not slow\"')", ] filterwarnings = [ - "ignore:Deprecated call to `pkg_resources.declare_namespace" + "ignore:Deprecated call to `pkg_resources.declare_namespace", + "ignore:(?s).*Pyarrow will become a required dependency of pandas:DeprecationWarning", # pandas pyarrow (pandas<3.0), ] [tool.mypy] |