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

[catacomb] / pub / ed25519.c

diff --git a/pub/ed25519.c b/pub/ed25519.c
index 655b1e6078213b7670dbbb5cb0dab35168195007..830e5de4bec438825da6770bead7717325838ad6 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];
+  unsigned i, a;
   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);
+
+  /* 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;
-  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);
+
+  /* Set Z. */
   f25519_set(Z, 1);
+
+  /* And we're done. */
   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);
 
+  /* 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);
-  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);