Require that Ed25519 |s| values be < order.

https://tools.ietf.org/html/rfc8032#section-5.1.7 adds this requirement
to prevent signature malleability.

Change-Id: Iac9a3649d97fc69e6efb4aea1ab1e002768fadc9
Reviewed-on: https://boringssl-review.googlesource.com/25564
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: David Benjamin <davidben@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
diff --git a/crypto/curve25519/ed25519_test.cc b/crypto/curve25519/ed25519_test.cc
index 31216f1..4f34675 100644
--- a/crypto/curve25519/ed25519_test.cc
+++ b/crypto/curve25519/ed25519_test.cc
@@ -44,6 +44,28 @@
   });
 }
 
+TEST(Ed25519Test, Malleability) {
+  // https://tools.ietf.org/html/rfc8032#section-5.1.7 adds an additional test
+  // that s be in [0, order). This prevents someone from adding a multiple of
+  // order to s and obtaining a second valid signature for the same message.
+  static const uint8_t kMsg[] = {0x54, 0x65, 0x73, 0x74};
+  static const uint8_t kSig[] = {
+      0x7c, 0x38, 0xe0, 0x26, 0xf2, 0x9e, 0x14, 0xaa, 0xbd, 0x05, 0x9a,
+      0x0f, 0x2d, 0xb8, 0xb0, 0xcd, 0x78, 0x30, 0x40, 0x60, 0x9a, 0x8b,
+      0xe6, 0x84, 0xdb, 0x12, 0xf8, 0x2a, 0x27, 0x77, 0x4a, 0xb0, 0x67,
+      0x65, 0x4b, 0xce, 0x38, 0x32, 0xc2, 0xd7, 0x6f, 0x8f, 0x6f, 0x5d,
+      0xaf, 0xc0, 0x8d, 0x93, 0x39, 0xd4, 0xee, 0xf6, 0x76, 0x57, 0x33,
+      0x36, 0xa5, 0xc5, 0x1e, 0xb6, 0xf9, 0x46, 0xb3, 0x1d,
+  };
+  static const uint8_t kPub[] = {
+      0x7d, 0x4d, 0x0e, 0x7f, 0x61, 0x53, 0xa6, 0x9b, 0x62, 0x42, 0xb5,
+      0x22, 0xab, 0xbe, 0xe6, 0x85, 0xfd, 0xa4, 0x42, 0x0f, 0x88, 0x34,
+      0xb1, 0x08, 0xc3, 0xbd, 0xae, 0x36, 0x9e, 0xf5, 0x49, 0xfa,
+  };
+
+  EXPECT_FALSE(ED25519_verify(kMsg, sizeof(kMsg), kSig, kPub));
+}
+
 TEST(Ed25519Test, KeypairFromSeed) {
   uint8_t public_key1[32], private_key1[64];
   ED25519_keypair(public_key1, private_key1);
diff --git a/third_party/fiat/curve25519.c b/third_party/fiat/curve25519.c
index d5928af..ecf00e5 100644
--- a/third_party/fiat/curve25519.c
+++ b/third_party/fiat/curve25519.c
@@ -3014,8 +3014,31 @@
   OPENSSL_memcpy(pkcopy, public_key, 32);
   uint8_t rcopy[32];
   OPENSSL_memcpy(rcopy, signature, 32);
-  uint8_t scopy[32];
-  OPENSSL_memcpy(scopy, signature + 32, 32);
+  union {
+    uint64_t u64[4];
+    uint8_t u8[32];
+  } scopy;
+  OPENSSL_memcpy(&scopy.u8[0], signature + 32, 32);
+
+  // https://tools.ietf.org/html/rfc8032#section-5.1.7 requires that s be in
+  // the range [0, order) in order to prevent signature malleability.
+
+  // kOrder is the order of Curve25519 in little-endian form.
+  static const uint64_t kOrder[4] = {
+    UINT64_C(0x5812631a5cf5d3ed),
+    UINT64_C(0x14def9dea2f79cd6),
+    0,
+    UINT64_C(0x1000000000000000),
+  };
+  for (size_t i = 3;; i--) {
+    if (scopy.u64[i] > kOrder[i]) {
+      return 0;
+    } else if (scopy.u64[i] < kOrder[i]) {
+      break;
+    } else if (i == 0) {
+      return 0;
+    }
+  }
 
   SHA512_CTX hash_ctx;
   SHA512_Init(&hash_ctx);
@@ -3028,7 +3051,7 @@
   x25519_sc_reduce(h);
 
   ge_p2 R;
-  ge_double_scalarmult_vartime(&R, h, &A, scopy);
+  ge_double_scalarmult_vartime(&R, h, &A, scopy.u8);
 
   uint8_t rcheck[32];
   x25519_ge_tobytes(rcheck, &R);