add flags for strongly binding EdDSA signatures, per https://eprint.iacr.org/2020/1244.pdfstrongly-binding

4 files changed, 223 insertions, 25 deletions

diff --git a/src/per_curve/eddsa.tmpl.c b/src/per_curve/eddsa.tmpl.c
index b1dea71..6a9916a 100644
--- a/src/per_curve/eddsa.tmpl.c
+++ b/src/per_curve/eddsa.tmpl.c
@@ -321,21 +321,26 @@ void decaf_ed$(gf_shortname)_keypair_sign_prehash (
     decaf_bzero(hash_output,sizeof(hash_output));
 }
 
-decaf_error_t decaf_ed$(gf_shortname)_verify (
+decaf_error_t decaf_ed$(gf_shortname)_verify_with_flags (
     const uint8_t signature[DECAF_EDDSA_$(gf_shortname)_SIGNATURE_BYTES],
     const uint8_t pubkey[DECAF_EDDSA_$(gf_shortname)_PUBLIC_BYTES],
     const uint8_t *message,
     size_t message_len,
     uint8_t prehashed,
     const uint8_t *context,
-    uint8_t context_len
+    uint8_t context_len,
+    uint32_t flags
 ) { 
     API_NS(point_t) pk_point, r_point;
     decaf_error_t error = API_NS(point_decode_like_eddsa_and_mul_by_ratio)(pk_point,pubkey);
     if (DECAF_SUCCESS != error) { return error; }
+    if ((flags & DECAF_EDDSA_STRONGLY_BINDING)
+        && API_NS(point_eq(pk_point,$(c_ns)_point_identity))) {
+        return DECAF_FAILURE;
+    }
     
     error = API_NS(point_decode_like_eddsa_and_mul_by_ratio)(r_point,signature);
-    if (DECAF_SUCCESS != error) { return error; }
+    if (DECAF_SUCCESS != error) { return error; } 
     
     API_NS(scalar_t) challenge_scalar;
     {
@@ -374,7 +379,6 @@ decaf_error_t decaf_ed$(gf_shortname)_verify (
         API_NS(scalar_add)(response_scalar,response_scalar,response_scalar);
     }
     
-    
     /* pk_point = -c(x(P)) + (cx + k)G = kG */
     API_NS(base_double_scalarmul_non_secret)(
         pk_point,
@@ -385,16 +389,40 @@ decaf_error_t decaf_ed$(gf_shortname)_verify (
     return decaf_succeed_if(API_NS(point_eq(pk_point,r_point)));
 }
 
+decaf_error_t decaf_ed$(gf_shortname)_verify (
+    const uint8_t signature[DECAF_EDDSA_$(gf_shortname)_SIGNATURE_BYTES],
+    const uint8_t pubkey[DECAF_EDDSA_$(gf_shortname)_PUBLIC_BYTES],
+    const uint8_t *message,
+    size_t message_len,
+    uint8_t prehashed,
+    const uint8_t *context,
+    uint8_t context_len
+) {
+    return decaf_ed$(gf_shortname)_verify_with_flags(signature,pubkey,
+        message,message_len,prehashed,context,context_len,0);
+}
 
-decaf_error_t decaf_ed$(gf_shortname)_verify_prehash (
+decaf_error_t decaf_ed$(gf_shortname)_verify_strong (
     const uint8_t signature[DECAF_EDDSA_$(gf_shortname)_SIGNATURE_BYTES],
     const uint8_t pubkey[DECAF_EDDSA_$(gf_shortname)_PUBLIC_BYTES],
-    const decaf_ed$(gf_shortname)_prehash_ctx_t hash,
+    const uint8_t *message,
+    size_t message_len,
+    uint8_t prehashed,
     const uint8_t *context,
     uint8_t context_len
 ) {
-    decaf_error_t ret;
-    
+    return decaf_ed$(gf_shortname)_verify_with_flags(signature,pubkey,
+        message,message_len,prehashed,context,context_len,DECAF_EDDSA_STRONGLY_BINDING);
+}
+
+decaf_error_t decaf_ed$(gf_shortname)_verify_prehash_with_flags (
+    const uint8_t signature[DECAF_EDDSA_$(gf_shortname)_SIGNATURE_BYTES],
+    const uint8_t pubkey[DECAF_EDDSA_$(gf_shortname)_PUBLIC_BYTES],
+    const decaf_ed$(gf_shortname)_prehash_ctx_t hash,
+    const uint8_t *context,
+    uint8_t context_len,
+    uint32_t flags
+) {
     uint8_t hash_output[EDDSA_PREHASH_BYTES];
     {
         decaf_ed$(gf_shortname)_prehash_ctx_t hash_too;
@@ -402,8 +430,29 @@ decaf_error_t decaf_ed$(gf_shortname)_verify_prehash (
         hash_final(hash_too,hash_output,sizeof(hash_output));
         hash_destroy(hash_too);
     }
-    
-    ret = decaf_ed$(gf_shortname)_verify(signature,pubkey,hash_output,sizeof(hash_output),1,context,context_len);
-    
-    return ret;
+
+    return decaf_ed$(gf_shortname)_verify_with_flags(signature,pubkey,
+        hash_output,sizeof(hash_output),1,context,context_len,flags);
+}
+
+decaf_error_t decaf_ed$(gf_shortname)_verify_prehash (
+    const uint8_t signature[DECAF_EDDSA_$(gf_shortname)_SIGNATURE_BYTES],
+    const uint8_t pubkey[DECAF_EDDSA_$(gf_shortname)_PUBLIC_BYTES],
+    const decaf_ed$(gf_shortname)_prehash_ctx_t hash,
+    const uint8_t *context,
+    uint8_t context_len
+) {
+    return decaf_ed$(gf_shortname)_verify_prehash_with_flags(signature,pubkey,
+        hash,context,context_len,0);
+}
+
+decaf_error_t decaf_ed$(gf_shortname)_verify_prehash_strong (
+    const uint8_t signature[DECAF_EDDSA_$(gf_shortname)_SIGNATURE_BYTES],
+    const uint8_t pubkey[DECAF_EDDSA_$(gf_shortname)_PUBLIC_BYTES],
+    const decaf_ed$(gf_shortname)_prehash_ctx_t hash,
+    const uint8_t *context,
+    uint8_t context_len
+) {
+    return decaf_ed$(gf_shortname)_verify_prehash_with_flags(signature,pubkey,
+        hash,context,context_len,DECAF_EDDSA_STRONGLY_BINDING);
 }
diff --git a/src/per_curve/eddsa.tmpl.h b/src/per_curve/eddsa.tmpl.h
index e25a6b4..8ba023b 100644
--- a/src/per_curve/eddsa.tmpl.h
+++ b/src/per_curve/eddsa.tmpl.h
@@ -49,6 +49,12 @@ $("DECAF_API_VIS extern const uint8_t * const DECAF_ED" + gf_shortname + "_NO_CO
 #define DECAF_EDDSA_NON_KEYPAIR_API_IS_DEPRECATED 1
 #endif
 
+#ifndef DECAF_EDDSA_STRONGLY_BINDING
+/** Flag to decaf_ed$(gf_shortname)_verify_with_flags: if set, use the
+ * strongly-binding verification conditions */
+#define DECAF_EDDSA_STRONGLY_BINDING (1<<0)
+#endif
+
 /** @cond internal */
 /** @brief Scheduled EdDSA keypair */
 typedef struct decaf_eddsa_$(gf_shortname)_keypair_s {
@@ -224,7 +230,7 @@ void DECAF_API_VIS decaf_ed$(gf_shortname)_prehash_init (
 /**
  * @brief EdDSA signature verification.
  *
- * Uses the standard (i.e. less-strict) verification formula.
+ * Uses the standard (i.e. less-strict) verification formula.  RFC 8032 compliant.
  *
  * @param [in] signature The signature.
  * @param [in] pubkey The public key.
@@ -250,7 +256,72 @@ decaf_error_t DECAF_API_VIS decaf_ed$(gf_shortname)_verify (
 ) __attribute__((nonnull(1,2))) DECAF_NOINLINE;
 
 /**
- * @brief EdDSA signature verification.
+ * @brief EdDSA signature verification, with flags.
+ *
+ * Uses the less-strict verification formula.
+ * 
+ * If flags & DECAF_EDDSA_STRONGLY_BINDING, then forbid small-order keys.  This makes the verification
+ * operation strongly binding, but not RFC 8032 compliant.  See https://eprint.iacr.org/2020/1244.pdf.
+ *
+ * @param [in] signature The signature.
+ * @param [in] pubkey The public key.
+ * @param [in] message The message to verify.
+ * @param [in] message_len The length of the message.
+ * @param [in] prehashed Nonzero if the message is actually the hash of something you want to verify.
+ * @param [in] context A "context" for this signature of up to 255 bytes.
+ * @param [in] context_len Length of the context.
+ * @param [in] flags Flags for the operation
+ *
+ * @warning For Ed25519, it is unsafe to use the same key for both prehashed and non-prehashed
+ * messages, at least without some very careful protocol-level disambiguation.  For Ed448 it is
+ * safe.  The C++ wrapper is designed to make it harder to screw this up, but this C code gives
+ * you no seat belt.
+ */
+decaf_error_t DECAF_API_VIS decaf_ed$(gf_shortname)_verify_with_flags (
+    const uint8_t signature[DECAF_EDDSA_$(gf_shortname)_SIGNATURE_BYTES],
+    const uint8_t pubkey[DECAF_EDDSA_$(gf_shortname)_PUBLIC_BYTES],
+    const uint8_t *message,
+    size_t message_len,
+    uint8_t prehashed,
+    const uint8_t *context,
+    uint8_t context_len,
+    uint32_t flags
+) __attribute__((nonnull(1,2))) DECAF_NOINLINE;
+
+/**
+ * @brief EdDSA signature verification; strongly binding version.
+ *
+ * Uses the less-strict verification formula.
+ * 
+ * Forbid small-order keys.  This makes the verification operation strongly binding, but not
+ * RFC 8032 compliant.  See https://eprint.iacr.org/2020/1244.pdf.
+ *
+ * @param [in] signature The signature.
+ * @param [in] pubkey The public key.
+ * @param [in] message The message to verify.
+ * @param [in] message_len The length of the message.
+ * @param [in] prehashed Nonzero if the message is actually the hash of something you want to verify.
+ * @param [in] context A "context" for this signature of up to 255 bytes.
+ * @param [in] context_len Length of the context.
+ * @param [in] flags Flags for the operation.
+ *
+ * @warning For Ed25519, it is unsafe to use the same key for both prehashed and non-prehashed
+ * messages, at least without some very careful protocol-level disambiguation.  For Ed448 it is
+ * safe.  The C++ wrapper is designed to make it harder to screw this up, but this C code gives
+ * you no seat belt.
+ */
+decaf_error_t DECAF_API_VIS decaf_ed$(gf_shortname)_verify_strong (
+    const uint8_t signature[DECAF_EDDSA_$(gf_shortname)_SIGNATURE_BYTES],
+    const uint8_t pubkey[DECAF_EDDSA_$(gf_shortname)_PUBLIC_BYTES],
+    const uint8_t *message,
+    size_t message_len,
+    uint8_t prehashed,
+    const uint8_t *context,
+    uint8_t context_len
+) __attribute__((nonnull(1,2))) DECAF_NOINLINE;
+
+/**
+ * @brief EdDSA signature verification, prehashed version.
  *
  * Uses the standard (i.e. less-strict) verification formula.
  *
@@ -274,6 +345,62 @@ decaf_error_t DECAF_API_VIS decaf_ed$(gf_shortname)_verify_prehash (
 ) __attribute__((nonnull(1,2))) DECAF_NOINLINE;
 
 /**
+ * @brief EdDSA signature verification, strongly binding, prehashed version.
+ *
+ * Uses the standard (i.e. less-strict) verification formula.
+ * 
+ * Forbid small-order keys.  This makes the verification operation strongly binding, but not
+ * RFC 8032 compliant.  See https://eprint.iacr.org/2020/1244.pdf.
+ *
+ * @param [in] signature The signature.
+ * @param [in] pubkey The public key.
+ * @param [in] hash The hash of the message.  This object will not be modified by the call.
+ * @param [in] context A "context" for this signature of up to 255 bytes.  Must be the same as what was used for the prehash.
+ * @param [in] context_len Length of the context.
+ *
+ * @warning For Ed25519, it is unsafe to use the same key for both prehashed and non-prehashed
+ * messages, at least without some very careful protocol-level disambiguation.  For Ed448 it is
+ * safe.  The C++ wrapper is designed to make it harder to screw this up, but this C code gives
+ * you no seat belt.
+ */
+decaf_error_t DECAF_API_VIS decaf_ed$(gf_shortname)_verify_prehash_strong (
+    const uint8_t signature[DECAF_EDDSA_$(gf_shortname)_SIGNATURE_BYTES],
+    const uint8_t pubkey[DECAF_EDDSA_$(gf_shortname)_PUBLIC_BYTES],
+    const decaf_ed$(gf_shortname)_prehash_ctx_t hash,
+    const uint8_t *context,
+    uint8_t context_len
+) __attribute__((nonnull(1,2))) DECAF_NOINLINE;
+
+/**
+ * @brief EdDSA signature verification with flags, prehashed version.
+ *
+ * Uses the less-strict verification formula.
+ * 
+ * If flags & DECAF_EDDSA_STRONGLY_BINDING, then forbid small-order keys.  This makes the verification
+ * operation strongly binding, but not RFC 8032 compliant.  See https://eprint.iacr.org/2020/1244.pdf.
+ *
+ * @param [in] signature The signature.
+ * @param [in] pubkey The public key.
+ * @param [in] hash The hash of the message.  This object will not be modified by the call.
+ * @param [in] context A "context" for this signature of up to 255 bytes.  Must be the same as what was used for the prehash.
+ * @param [in] context_len Length of the context.
+ * @param [in] flags Flags for the operation.
+ *
+ * @warning For Ed25519, it is unsafe to use the same key for both prehashed and non-prehashed
+ * messages, at least without some very careful protocol-level disambiguation.  For Ed448 it is
+ * safe.  The C++ wrapper is designed to make it harder to screw this up, but this C code gives
+ * you no seat belt.
+ */
+decaf_error_t DECAF_API_VIS decaf_ed$(gf_shortname)_verify_prehash_with_flags (
+    const uint8_t signature[DECAF_EDDSA_$(gf_shortname)_SIGNATURE_BYTES],
+    const uint8_t pubkey[DECAF_EDDSA_$(gf_shortname)_PUBLIC_BYTES],
+    const decaf_ed$(gf_shortname)_prehash_ctx_t hash,
+    const uint8_t *context,
+    uint8_t context_len,
+    uint32_t flags
+) __attribute__((nonnull(1,2))) DECAF_NOINLINE;
+
+/**
  * @brief EdDSA point encoding.  Used internally, exposed externally.
  * Multiplies by $(C_NS)_EDDSA_ENCODE_RATIO first.
  *
diff --git a/src/per_curve/eddsa.tmpl.hxx b/src/per_curve/eddsa.tmpl.hxx
index 7adde57..3cf99fa 100644
--- a/src/per_curve/eddsa.tmpl.hxx
+++ b/src/per_curve/eddsa.tmpl.hxx
@@ -253,20 +253,22 @@ public:
     inline decaf_error_t DECAF_WARN_UNUSED verify_noexcept (
         const FixedBlock<DECAF_EDDSA_$(gf_shortname)_SIGNATURE_BYTES> &sig,
         const Block &message,
-        const Block &context = NO_CONTEXT()
+        const Block &context = NO_CONTEXT(),
+        bool strong = false
     ) const /*DECAF_NOEXCEPT*/ {
         if (context.size() > 255) {
             return DECAF_FAILURE;
         }
         
-        return decaf_ed$(gf_shortname)_verify (
+        return decaf_ed$(gf_shortname)_verify_with_flags (
             sig.data(),
             ((const CRTP*)this)->pub_.data(),
             message.data(),
             message.size(),
             0,
             context.data(),
-            static_cast<uint8_t>(context.size())
+            static_cast<uint8_t>(context.size()),
+            strong ? DECAF_EDDSA_STRONGLY_BINDING : 0
         );
     }
     
@@ -280,13 +282,14 @@ public:
     inline void verify (
         const FixedBlock<DECAF_EDDSA_$(gf_shortname)_SIGNATURE_BYTES> &sig,
         const Block &message,
-        const Block &context = NO_CONTEXT()
+        const Block &context = NO_CONTEXT(),
+        bool strong = false
     ) const /*throw(LengthException,CryptoException)*/ {
         if (context.size() > 255) {
             throw LengthException();
         }
         
-        if (DECAF_SUCCESS != verify_noexcept( sig, message, context )) {
+        if (DECAF_SUCCESS != verify_noexcept( sig, message, context, strong )) {
             throw CryptoException();
         }
     }
@@ -298,28 +301,32 @@ public:
     /** Verify that a signature is valid for a given prehashed message, given the context. */
     inline decaf_error_t DECAF_WARN_UNUSED verify_prehashed_noexcept (
         const FixedBlock<DECAF_EDDSA_$(gf_shortname)_SIGNATURE_BYTES> &sig,
-        const Prehash &ph
+        const Prehash &ph,
+        bool strong = false
     ) const /*DECAF_NOEXCEPT*/ {
-        return decaf_ed$(gf_shortname)_verify_prehash (
+        return decaf_ed$(gf_shortname)_verify_prehash_with_flags (
             sig.data(),
             ((const CRTP*)this)->pub_.data(),
             (const decaf_ed$(gf_shortname)_prehash_ctx_s*)ph.wrapped,
             ph.context_.data(),
-            ph.context_.size()
+            ph.context_.size(),
+            strong ? DECAF_EDDSA_STRONGLY_BINDING : 0
         );
     }
 
     /** Verify that a signature is valid for a given prehashed message, given the context. */
     inline void verify_prehashed (
         const FixedBlock<DECAF_EDDSA_$(gf_shortname)_SIGNATURE_BYTES> &sig,
-        const Prehash &ph
+        const Prehash &ph,
+        bool strong = false
     ) const /*throw(CryptoException)*/ {
-        if (DECAF_SUCCESS != decaf_ed$(gf_shortname)_verify_prehash (
+        if (DECAF_SUCCESS != decaf_ed$(gf_shortname)_verify_prehash_with_flags (
             sig.data(),
             ((const CRTP*)this)->pub_.data(),
             (const decaf_ed$(gf_shortname)_prehash_ctx_s*)ph.wrapped,
             ph.context_.data(),
-            static_cast<uint8_t>(ph.context_.size())
+            static_cast<uint8_t>(ph.context_.size()),
+            strong ? DECAF_EDDSA_STRONGLY_BINDING : 0
         )) {
             throw CryptoException();
         }
diff --git a/test/test_decaf.cxx b/test/test_decaf.cxx
index 841a40e..5aafe06 100644
--- a/test/test_decaf.cxx
+++ b/test/test_decaf.cxx
@@ -587,6 +587,9 @@ static void test_eddsa() {
     }
     typename Group::Scalar more_than_size = 1;
     for (int i=0; i<lg_scalar; i++) more_than_size *= 2;
+    FixedArrayBuffer<EdDSA<Group>::PublicKey::SER_BYTES> zero_pubkey;
+    FixedArrayBuffer<EdDSA<Group>::PublicKey::SIG_BYTES> zero_sig;
+    typename EdDSA<Group>::PublicKey pub0(zero_pubkey);
     
     for (int i=0; i<NTESTS && test.passing_now; i++) {
         typename EdDSA<Group>::PrivateKey priv(rng);
@@ -599,6 +602,18 @@ static void test_eddsa() {
         rng.read(context);
         
         SecureBuffer sig = priv.sign(message,context); 
+
+
+        bool accept_weak   = pub0.verify_noexcept(zero_sig,message,EdDSA<Group>::NO_CONTEXT(), false);
+        bool accept_strong = pub0.verify_noexcept(zero_sig,message,EdDSA<Group>::NO_CONTEXT(), true);
+        if (accept_strong) {
+            test.fail();
+            printf("    Strong-accepted sig with zero pubkey on try %d\n", i);
+        }
+        if (!accept_weak) {
+            test.fail();
+            printf("    Didn't weak-accept sig with zero pubkey on try %d\n", i);
+        }
         
         try {
             pub.verify(sig,message,context);