Repository: dalek-cryptography/ed25519-dalek (language: rust)

Issue:
feat: Add is_small_order_point, is_prime_subgroup_point
## What
In a nutshell, this offers an opt-in way of performing some public key checks relating to small order components, without having to pay an additional point decompression.

## In detail
Since https://github.com/dalek-cryptography/ed25519-dalek/commit/8dbaf9a8d249a24a5225a1247195d4135669f608, the `PublicKey` type is the performant way to carry public key material, with an eager check that the point is on curve.

However, some applications which may like eager point decompression also need to check whether the point is small order, or even torsion-free:
- interpreting a discrepancy in verification between batch verification and iterated verification (see #115 https://github.com/dalek-cryptography/ed25519-dalek/pull/151#discussion_r513084546),
- avoiding small subgroup confinement attacks in a DH,
- ...

`verify_strict` was introduced to offer an opt-in approach to some of this sort of scrutiny at the time the key is used for signing, but cannot be performed eagerly, e.g. as soon as deserializing a public key.

OTOH, rejecting small order keys (or worse non-torsion-free) keys by default on deserialization would have a significant performance impact.

However, it's still desirable to have the *option* to seek for small-order or torsion-free-ness, long before the key is ever used for any actual cryptographic purpose (e.g. signature verification). In order to perform this sort of check, some code bases have taken to [re-implementing it from the bytes representation of the key, which involves an additional decompression](https://github.com/diem/diem/blob/a290b0859a6152a5ffd6f85773a875f17334adac/crates/diem-crypto/src/ed25519.rs#L358-L386).

The added functions of this PR allow the checks to be performed without additional decompression.



Discussion / hints:
I'm running into the same performance issue due to the lack of this functionality. Will this be merged?
I'd suggest evaluating ideas like this for ed25519-zebra since `verify_strict` winds up being kinda the opposite of what is needed for many use cases. 

Fix patch:
diff --git a/src/verifying.rs b/src/verifying.rs
index e57f2e9..2f207fe 100644
--- a/src/verifying.rs
+++ b/src/verifying.rs
@@ -163,6 +163,15 @@ impl VerifyingKey {
         Context::new(self, context_value)
     }
 
+    /// Returns whether this is a _weak_ public key, i.e., if this public key has low order.
+    ///
+    /// A weak public key can be used to generate a siganture that's valid for almost every
+    /// message. [`Self::verify_strict`] denies weak keys, but if you want to check for this
+    /// property before verification, then use this method.
+    pub fn is_weak(&self) -> bool {
+        self.1.is_small_order()
+    }
+
     /// Internal utility function for clamping a scalar representation and multiplying by the
     /// basepont to produce a public key.
     fn clamp_and_mul_base(bits: [u8; 32]) -> VerifyingKey {


Test patch:
diff --git a/tests/ed25519.rs b/tests/ed25519.rs
index 4ed0f72..a3a7ebc 100644
--- a/tests/ed25519.rs
+++ b/tests/ed25519.rs
@@ -228,6 +228,9 @@ mod vectors {
         assert!(vk.verify(message1, &sig).is_ok());
         assert!(vk.verify(message2, &sig).is_ok());
 
+        // Check that this public key appears as weak
+        assert!(vk.is_weak());
+
         // Now check that the sigs fail under verify_strict. This is because verify_strict rejects
         // small order pubkeys.
         assert!(vk.verify_strict(message1, &sig).is_err());
@@ -306,6 +309,9 @@ mod integrations {
         good_sig = signing_key.sign(&good);
         bad_sig = signing_key.sign(&bad);
 
+        // Check that an honestly generated public key is not weak
+        assert!(!verifying_key.is_weak());
+
         assert!(
             signing_key.verify(&good, &good_sig).is_ok(),
             "Verification of a valid signature failed!"