pub/ed25519.c: Range-check coordinates and scalars when verifying.

This is a requirement of RFC8032, though Bernstein et al don't see the
point.

It's easy enough to test that verification rejects an out-of-range
scalar part in the signature, but there's hardly any space in the
curve-point part, so I've had to cheat.

diff --git a/pub/Makefile.am b/pub/Makefile.am
index 7047066..98c0a15 100644 (file)
--- a/pub/Makefile.am
+++ b/pub/Makefile.am
@@ -108,15 +108,17 @@ EXTRA_DIST                += t/x25519
 pkginclude_HEADERS     += ed25519.h
 libpub_la_SOURCES      += ed25519.c
 TESTS                  += ed25519.t$(EXEEXT)
 pkginclude_HEADERS     += ed25519.h
 libpub_la_SOURCES      += ed25519.c
 TESTS                  += ed25519.t$(EXEEXT)

-EXTRA_DIST             += t/ed25519 t/ed25519.djb ed25519-tvconv
+EXTRA_DIST             += t/ed25519 t/ed25519.local
+EXTRA_DIST             += t/ed25519.djb ed25519-tvconv

 MAINTAINERCLEANFILES   += t/ed25519
 ed25519.log: t/ed25519
 MAINTAINERCLEANFILES   += t/ed25519
 ed25519.log: t/ed25519

-t/ed25519: ed25519-tvconv t/ed25519.djb
+t/ed25519: ed25519-tvconv t/ed25519.djb t/ed25519.local

        $(AM_V_GEN)cd $(srcdir) && \
                { echo "### GENERATED by ed25519-tvconv" && \
                  ./ed25519-tvconv k <t/ed25519.djb && \
                  ./ed25519-tvconv s <t/ed25519.djb && \
                  ./ed25519-tvconv v <t/ed25519.djb; \
        $(AM_V_GEN)cd $(srcdir) && \
                { echo "### GENERATED by ed25519-tvconv" && \
                  ./ed25519-tvconv k <t/ed25519.djb && \
                  ./ed25519-tvconv s <t/ed25519.djb && \
                  ./ed25519-tvconv v <t/ed25519.djb; \

+                 cat t/ed25519.local; \

                } >t/ed25519.new && \
                mv t/ed25519.new t/ed25519
 
                } >t/ed25519.new && \
                mv t/ed25519.new t/ed25519
 

diff --git a/pub/ed25519.c b/pub/ed25519.c
index 655b1e6..830e5de 100644 (file)
--- a/pub/ed25519.c
+++ b/pub/ed25519.c
@@ -135,16 +135,34 @@ static void ptencode(octet q[32],
 static int ptdecode(f25519 *X, f25519 *Y, f25519 *Z, const octet q[32])
 {
   octet b[32];
 static int ptdecode(f25519 *X, f25519 *Y, f25519 *Z, const octet q[32])
 {
   octet b[32];

+  unsigned i, a;

   f25519 t, u;
   uint32 m;
   f25519 t, u;
   uint32 m;

-  int rc;
+  int rc = 0;

 
 

+  /* Load the y-coordinate. */

   memcpy(b, q, 32); b[31] &= 0x7fu; f25519_load(Y, b);
   memcpy(b, q, 32); b[31] &= 0x7fu; f25519_load(Y, b);

+
+  /* Check that the coordinate was in range.  If we store it, we'll get a
+   * canonical version which we can compare against Q; be careful not to
+   * check the top bit.
+   */
+  f25519_store(b, Y);
+  for (i = a = 0; i < 31; i++) a |= b[i] ^ q[i];
+  a |= (b[31] ^ q[31])&0x7fu;
+  a = ((a - 1) >> 8)&0x01u;            /* 0 |-> 1, non-0 |-> 0 */
+  rc |= (int)a - 1;
+
+  /* Decompress the x-coordinate. */

   f25519_sqr(&t, Y); f25519_mul(&u, &t, D); t.P[0] -= 1; u.P[0] += 1;
   f25519_sqr(&t, Y); f25519_mul(&u, &t, D); t.P[0] -= 1; u.P[0] += 1;

-  rc = f25519_quosqrt(X, &t, &u);
-  f25519_store(b, X); m = -(((q[31] >> 7) ^ b[0])&0x1u);
+  rc |= f25519_quosqrt(X, &t, &u);
+  f25519_store(b, X); m = -(uint32)(((q[31] >> 7) ^ b[0])&0x1u);

   f25519_condneg(X, X, m);
   f25519_condneg(X, X, m);

+
+  /* Set Z. */

   f25519_set(Z, 1);
   f25519_set(Z, 1);

+
+  /* And we're done. */

   return (rc);
 }
 
   return (rc);
 }
 


@@ -480,13 +498,20 @@ int ed25519_verify(const octet K[ED25519_PUBSZ],
   if (ptdecode(&AX, &AY, &AZ, K)) return (-1);
   f25519_neg(&AX, &AX);
 
   if (ptdecode(&AX, &AY, &AZ, K)) return (-1);
   f25519_neg(&AX, &AX);
 

+  /* Load the scalar and check that it's in range.  The easy way is to store
+   * it again and see if the two match.
+   */
+  scaf_loaddbl(tt, sig + 32, 32, 2*NPIECE, PIECEWD);
+  scaf_reduce(s, tt, l, mu, NPIECE, PIECEWD, scratch);
+  scaf_store(b, 32, s, NPIECE, PIECEWD);
+  if (memcmp(b, sig + 32, 32) != 0) return (-1);
+

   /* Check the signature. */
   sha512_init(&h);
   sha512_hash(&h, sig, 32);
   sha512_hash(&h, K, 32);
   sha512_hash(&h, m, msz);
   sha512_done(&h, b);
   /* Check the signature. */
   sha512_init(&h);
   sha512_hash(&h, sig, 32);
   sha512_hash(&h, K, 32);
   sha512_hash(&h, m, msz);
   sha512_done(&h, b);

-  scaf_load(s, sig + 32, 32, NPIECE, PIECEWD);

   scaf_loaddbl(tt, b, 64, 2*NPIECE, PIECEWD);
   scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch);
   ptsimmul(&RX, &RY, &RZ, s, BX, BY, BZ, t, &AX, &AY, &AZ);
   scaf_loaddbl(tt, b, 64, 2*NPIECE, PIECEWD);
   scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch);
   ptsimmul(&RX, &RY, &RZ, s, BX, BY, BZ, t, &AX, &AY, &AZ);

diff --git a/pub/t/ed25519.local b/pub/t/ed25519.local
new file mode 100644 (file)
index 0000000..699d4c9
--- /dev/null
+++ b/pub/t/ed25519.local
@@ -0,0 +1,43 @@
+### Local tests for Ed25519
+
+verify {
+  ## Check that noncanonical scalars are rejected.  The base test is repeated
+  ## from the main suite; let s be the scalar part of the signature, and ℓ be
+  ## the curve order.  The negative test has s' = s + ℓ < 2^254, so the value
+  ## fits.
+  74d29127f199d86a8676aec33b4ce3f225ccb191f52c191ccd1e8cca65213a6b
+    bd8e05033f3a8bcdcbf4beceb70901c82e31
+    fbe929d743a03c17910575492f3092ee2a2bf14a60a3fcacec74a58c7334510fc262db582791322d6c8c41f1700adb80027ecabc14270b703444ae3ee7623e0a
+    0;
+  74d29127f199d86a8676aec33b4ce3f225ccb191f52c191ccd1e8cca65213a6b
+    bd8e05033f3a8bcdcbf4beceb70901c82e31
+    fbe929d743a03c17910575492f3092ee2a2bf14a60a3fcacec74a58c7334510faf36d1b541f44485422939944f04ba95027ecabc14270b703444ae3ee7623e1a
+    -1;
+
+  ## OK, so this is a massive cheat, but otherwise testing that out-of-range
+  ## coordinates are rejected is really hard.  Pick A = (0, 1), which is the
+  ## identity in E.  Then n A = A for all n; in particular, H(R, A, M) A = A
+  ## for any choice of R and M.  Furthermore, R = R + H(R, A, M) A for any R.
+  ## Let's pick R = A = (0, 1), because that seems to be working out for us.
+  ## Then s P = R + H(R, A, M) A exactly when s = 0 (mod ℓ).
+  ##
+  ## This is obviously a really daft choice of public key for security,
+  ## because the following is a completely general-purpose signature for all
+  ## messages.
+  ##
+  ## Why bother, you ask?  Well, because (0, 1) is one of the few points
+  ## which has a reduntant representation.  So we can use this to check that
+  ## we're correctly rejecting signatures which aren't in normal form.
+  0100000000000000000000000000000000000000000000000000000000000000
+    416c6c2d707572706f7365207369676e6174757265210a
+    01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
+    0;
+  eeffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f
+    416c6c2d707572706f7365207369676e6174757265210a
+    01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
+    -1;
+  0100000000000000000000000000000000000000000000000000000000000000
+    416c6c2d707572706f7365207369676e6174757265210a
+    eeffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f0000000000000000000000000000000000000000000000000000000000000000
+    -1;
+}