From 24f4be7acc3ec7ff613715a7a97597e587f6d6d8 Mon Sep 17 00:00:00 2001
From: Loup Vaillant <loup@loup-vaillant.fr>
Date: Wed, 15 Aug 2018 20:02:03 +0200
Subject: [PATCH] Properly prevent S malleability

S malleability was mostly prevented in a previous commit, for reasons
that had nothing to do with S malleability.  This mislead users into
thinking Monocypher was not S malleable.

To avoid confusion, I properly verify that S is strictly lower than L
(the order of the curve).  S malleability is no longer a thing.

We still have nonce malleability, but that one can't be helped.

Also added Wycheproof test vectors about malleability.
---
 src/monocypher.c             | 22 ++++++++++++++------
 tests/vectors/ed_25519_check | 40 ++++++++++++++++++++++++++++++++++++
 2 files changed, 56 insertions(+), 6 deletions(-)

diff --git a/src/monocypher.c b/src/monocypher.c
index 8a7b4e3..319a29e 100644
--- a/src/monocypher.c
+++ b/src/monocypher.c
@@ -1353,12 +1353,13 @@ void crypto_x25519_public_key(u8       public_key[32],
 /// Ed25519 ///
 ///////////////
 
+static const  u64 L[32] = { 0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58,
+                            0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
+                            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+                            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10};
+
 static void modL(u8 *r, i64 x[64])
 {
-    static const  u64 L[32] = { 0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58,
-                                0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
-                                0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-                                0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10};
     for (unsigned i = 63; i >= 32; i--) {
         i64 carry = 0;
         FOR (j, i-32, i-12) {
@@ -1410,6 +1411,15 @@ static void mul_add(u8 r[32], const u8 a[32], const u8 b[32], const u8 c[32])
     WIPE_BUFFER(s);
 }
 
+static int is_above_L(const u8 a[32])
+{
+    for (int i = 31; i >= 0; i--) {
+        if (a[i] > L[i]) { return 1; }
+        if (a[i] < L[i]) { return 0; }
+    }
+    return 1;
+}
+
 // Point in a twisted Edwards curve,
 // in extended projective coordinates.
 // x = X/Z, y = Y/Z, T = XY/Z
@@ -1925,8 +1935,8 @@ int crypto_check_final(crypto_check_ctx *ctx)
     u8 h_ram[64], R_check[32];
     u8 *s = ctx->sig + 32;                       // s
     u8 *R = ctx->sig;                            // R
-    if (ge_frombytes_neg_vartime(&A, ctx->pk) || // -A
-        (s[31] & 224) != 0) { // reduce malleability for the sliding windows
+    if (ge_frombytes_neg_vartime(&A, ctx->pk) ||
+        is_above_L(s)) { // prevent s malleability
         return -1;
     }
     HASH_FINAL(&ctx->hash, h_ram);
diff --git a/tests/vectors/ed_25519_check b/tests/vectors/ed_25519_check
index d5f9ffe..74cc216 100644
--- a/tests/vectors/ed_25519_check
+++ b/tests/vectors/ed_25519_check
@@ -258,6 +258,46 @@ ff:
 9a83eb6dbfd54a31fc1d3c580fc7b2fae4630ca8f0edf803873e433673d7e3d40e94254586cb6188c5386c3febed477cb9a6cb29e3979adc4cb27cf5278fb70a:
 ff:
 
+7d4d0e7f6153a69b6242b522abbee685fda4420f8834b108c3bdae369ef549fa:
+54657374:
+7c38e026f29e14aabd059a0f2db8b0cd783040609a8be684db12f82a27774ab067654bce3832c2d76f8f6f5dafc08d9339d4eef676573336a5c51eb6f946b31d:
+ff:
+
+7d4d0e7f6153a69b6242b522abbee685fda4420f8834b108c3bdae369ef549fa:
+54657374:
+7c38e026f29e14aabd059a0f2db8b0cd783040609a8be684db12f82a27774ab05439412b5395d42f462c67008eba6ca839d4eef676573336a5c51eb6f946b32d:
+ff:
+
+7d4d0e7f6153a69b6242b522abbee685fda4420f8834b108c3bdae369ef549fa:
+54657374:
+7c38e026f29e14aabd059a0f2db8b0cd783040609a8be684db12f82a27774ab02ee12ce5875bf9dff26556464bae2ad239d4eef676573336a5c51eb6f946b34d:
+ff:
+
+7d4d0e7f6153a69b6242b522abbee685fda4420f8834b108c3bdae369ef549fa:
+54657374:
+7c38e026f29e14aabd059a0f2db8b0cd783040609a8be684db12f82a27774ab0e2300459f1e742404cd934d2c595a6253ad4eef676573336a5c51eb6f946b38d:
+ff:
+
+7d4d0e7f6153a69b6242b522abbee685fda4420f8834b108c3bdae369ef549fa:
+54657374:
+7c38e026f29e14aabd059a0f2db8b0cd783040609a8be684db12f82a27774ab07a9155711ecfaf7f99f277bad0c6ae7e39d4eef676573336a5c51eb6f946b32d:
+ff:
+
+7d4d0e7f6153a69b6242b522abbee685fda4420f8834b108c3bdae369ef549fa:
+54657374:
+7c38e026f29e14aabd059a0f2db8b0cd783040609a8be684db12f82a27774ab07a9155711ecfaf7f99f277bad0c6ae7e39d4eef676573336a5c51eb6f946b34d:
+ff:
+
+7d4d0e7f6153a69b6242b522abbee685fda4420f8834b108c3bdae369ef549fa:
+54657374:
+7c38e026f29e14aabd059a0f2db8b0cd783040609a8be684db12f82a27774ab07a9155711ecfaf7f99f277bad0c6ae7e39d4eef676573336a5c51eb6f946b38d:
+ff:
+
+7d4d0e7f6153a69b6242b522abbee685fda4420f8834b108c3bdae369ef549fa:
+54657374:
+7c38e026f29e14aabd059a0f2db8b0cd783040609a8be684db12f82a27774ab0679155711ecfaf7f99f277bad0c6ae7e39d4eef676573336a5c51eb6f946b38d:
+ff:
+
 a12c2beb77265f2aac953b5009349d94155a03ada416aad451319480e983ca4c:
 :
 5056325d2ab440bf30bbf0f7173199aa8b4e6fbc091cf3eb6bc6cf87cd73d992ffc216c85e4ab5b8a0bbc7e9a6e9f8d33b7f6e5ac0ffdc22d9fcaf784af84302:
-- 
2.47.3