Add NSS.

5 files changed, 129 insertions, 8 deletions

diff --git a/docs/libraries.rst b/docs/libraries.rst
index e5264ee..a7aa1e2 100644
--- a/docs/libraries.rst
+++ b/docs/libraries.rst
@@ -793,6 +793,97 @@ Verify:
 NSS
 ===
 
+| Version: ``3.94``
+| Repository: https://hg.mozilla.org/projects/nss
+| Docs:
+
+
+Primitives
+----------
+
+ECDH, ECDSA, also x25519.
+
+Two ECMethods:
+ - Curve25519
+    - 32-bit -> own impl
+    - 64-bit -> HACL*
+ - P-256 from HACL*
+
+Several ECGroups:
+ - generic ``ECGroup_consGFp``
+ - Montgomery arithmetic ``ECGroup_consGFp_mont``
+ - P-256
+ - P-384 from ECCkiila
+ - P-521 from ECCkiila
+
+The ECMethods override the scalarmult of the ECGroups in:
+ - ``ec_NewKey`` via ``ec_get_method_from_name`` and then calling the ``method.mul``.
+ - ``EC_ValidatePublicKey`` via ``ec_get_method_from_name`` and then calling the ``method.validate``.
+ - ``ECDH_Derive`` via ``ec_get_method_from_name`` and then calling the ``method.mul``.
+ - ``ECDSA_SignDigest`` and ``ECDSA_SignDigestWithSeed`` via ``ec_SignDigestWithSeed``, then ``ec_get_method_from_name`` and then calling the ``method.mul``.
+
+
+P-256 from HACL*
+^^^^^^^^^^^^^^^^
+
+KeyGen:
+ - Short-Weierstrass
+ - Fixed Window (width = 4)? points to https://eprint.iacr.org/2013/816.pdf? via ``ec_secp256r1_pt_mul -> (Hacl*) Hacl_P256_dh_initiator -> point_mul_g``
+ - projective-3 coords.
+ - `add-2015-rcb`, `dbl-2015-rcb-3`
+
+Derive:
+ - Same as KeyGen.
+
+Sign:
+ - Same as Keygen.
+
+Verify:
+ - Short-Weierstrass
+ - Multi-scalar simultaneous Fixed Window
+ - Same coords and formulas as KeyGen.
+
+P-384
+^^^^^
+
+KeyGen:
+ - Short-Weierstrass
+ - Comb from ecckiila: ``EC_NewKeyFromSeed -> ec_NewKey -> ec_points_mul -> ECPoints_mul -> ecgroup.points_mul -> point_mul_two_secp384r1_wrap -> point_mul_g_secp384r1_wrap -> point_mul_g_secp384r1 -> fixed_smul_cmb``.
+ - projective-3 coords.
+ - `dbl-2015-rcb-3`, `madd-2015-rcb-3` also `add-2015-rcb` in point_add_proj.
+
+Derive:
+ - Short-Weierstrass
+ - Regular Window NAF (width = 5) from ecckiila: ``ECDH_Derive -> ec_points_mul -> ECPoints_mul -> ecgroup.points_mul -> point_mul_secp384r1_wrap -> point_mul_secp384r1 -> var_smul_rwnaf``.
+ - projective-3 coords.
+ - `dbl-2015-rcb-3`, `add-2015-rcb`.
+
+Sign:
+ - Same as KeyGen.
+
+Verify:
+ - Short-Weierstrass
+ - Interleaved multi-scalar window NAF (width = 5) with Shamir's trick from ecckiila: ``ECDSA_SignDigest -> ECDSA_SignDigestWithSeed -> ec_SignDigestWithSeed -> ec_points_mul -> ECPoints_mul -> ecgroup.points_mul -> point_mul_two_secp384r1_wrap -> point_mul_two_secp384r1 -> var_smul_wnaf_two``
+ - projective-3 coords.
+ - `dbl-2015-rcb-3`, `madd-2015-rcb-3` also `add-2015-rcb` in point_add_proj.
+
+P-521
+^^^^^
+
+Same as P-384.
+
+x25519
+^^^^^^
+
+KeyGen:
+ - Montgomery
+ - Montgomery ladder via ``-> ec_Curve25519_pt_mul -> ec_Curve25519_mul``.
+ - xz coords
+ - Unknown ladder formula
+
+Derive:
+ - Same as KeyGen.
+
 libsecp256k1
 ============
 
@@ -810,7 +901,7 @@ ECDH
 
 KeyGen:
  - Short-Weierstrass
- - `Fixed findow with full precomputation <https://github.com/bitcoin-core/secp256k1/blob/v0.4.0/src/ecmult_gen_impl.h#L45>`__ via ``secp256k1_ec_pubkey_create -> secp256k1_ec_pubkey_create_helper -> secp256k1_ecmult_gen``. Window of size 4.
+ - `Fixed window with full precomputation <https://github.com/bitcoin-core/secp256k1/blob/v0.4.0/src/ecmult_gen_impl.h#L45>`__ via ``secp256k1_ec_pubkey_create -> secp256k1_ec_pubkey_create_helper -> secp256k1_ecmult_gen``. Window of size 4.
  - Uses scalar blinding.
  - `Jacobian version of add-2002-bj <https://github.com/bitcoin-core/secp256k1/blob/v0.4.0/src/group_impl.h#L670>`__  (via ``secp256k1_gej_add_ge``).
  - No doubling.
diff --git a/pyecsca/sca/re/structural.py b/pyecsca/sca/re/structural.py
index 092cf46..3581b0d 100644
--- a/pyecsca/sca/re/structural.py
+++ b/pyecsca/sca/re/structural.py
@@ -49,7 +49,7 @@ def formula_similarity_fuzz(
         P = Paff.to_model(one.coordinate_model, curve)
         Q = Qaff.to_model(one.coordinate_model, curve)
         R = Raff.to_model(one.coordinate_model, curve)
-        inputs = (P, Q, R)[:one.num_inputs]
+        inputs = (P, Q, R)[: one.num_inputs]
         with local(DefaultContext()) as ctx:
             res_one = one(curve.prime, *inputs, **curve.parameters)
         action_one = ctx.actions.get_by_index([0])
@@ -62,11 +62,12 @@ def formula_similarity_fuzz(
         ivs_other = set(
             map(attrgetter("value"), sum(action_other[0].intermediates.values(), []))
         )
-        iv_matches += len(ivs_one.intersection(ivs_other)) / max(len(ivs_one), len(ivs_other))
+        iv_matches += len(ivs_one.intersection(ivs_other)) / max(
+            len(ivs_one), len(ivs_other)
+        )
         one_coords = set(res_one)
         other_coords = set(res_other)
-        output_matches += len(one_coords.intersection(other_coords)) / max(len(one_coords), len(other_coords))
-    return {
-        "output": output_matches / samples,
-        "ivs": iv_matches / samples
-    }
+        output_matches += len(one_coords.intersection(other_coords)) / max(
+            len(one_coords), len(other_coords)
+        )
+    return {"output": output_matches / samples, "ivs": iv_matches / samples}
diff --git a/test/data/formulas/ladd-hacl-x25519 b/test/data/formulas/ladd-hacl-x25519
new file mode 100644
index 0000000..1dbe8cc
--- /dev/null
+++ b/test/data/formulas/ladd-hacl-x25519
@@ -0,0 +1,4 @@
+source HACL* https://github.com/hacl-star/hacl-star/blob/v0.3.0/specs/Spec.Curve25519.fst#L56
+parameter am24
+assume am24 = (a-2)/4
+coords xz
diff --git a/test/data/formulas/ladd-hacl-x25519.op3 b/test/data/formulas/ladd-hacl-x25519.op3
new file mode 100644
index 0000000..7893eb9
--- /dev/null
+++ b/test/data/formulas/ladd-hacl-x25519.op3
@@ -0,0 +1,18 @@
+a = X2 + Z2
+b = X2 - Z2
+c = X3 + Z3
+d = X3 - Z3
+da = d * a
+cb = c * b
+X3 = da + cb
+Z3 = da - cb
+aa = a^2
+bb = b^2
+X5 = X3^2
+Z3 = Z3^2
+e = aa - bb
+e121665 = e * am24
+aa_e121665 = aa + e121665
+X4 = aa * bb
+Z4 = e * aa_e121665
+Z5 = Z3 * X1
diff --git a/test/sca/test_structural.py b/test/sca/test_structural.py
index 0645972..099e348 100644
--- a/test/sca/test_structural.py
+++ b/test/sca/test_structural.py
@@ -185,6 +185,13 @@ def test_efd_formula_match():
             ("other", "Curve25519"),
             LadderEFDFormula,
         ],
+        [
+            "ladd-hacl-x25519",
+            MontgomeryModel,
+            "xz",
+            ("other", "Curve25519"),
+            LadderEFDFormula,
+        ],
     ],
 )
 def test_formula_correctness(name, model, coords, param_spec, formula_type):