X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb/blobdiff_plain/d56fd9d102115283485493dbe56b0d320ac99097..3709f7955d5d52033464831d5c07fc31783479d0:/pub/ed25519.c

diff --git a/pub/ed25519.c b/pub/ed25519.c
index a5fe57b7..c6b805c4 100644
--- a/pub/ed25519.c
+++ b/pub/ed25519.c
@@ -86,35 +86,35 @@ const key_fetchdef ed25519_privfetch[] = {
 
 #if F25519_IMPL == 26
 # define P p26
-  static const int32 bx_pieces[] = {
+  static const f25519_piece bx_pieces[] = {
     -14297830,  -7645148,  16144683, -16471763,  27570974,
      -2696100, -26142465,   8378389,  20764389,   8758491
   }, by_pieces[] = {
-    -26843560,  -6710886,  13421773, -13421773,  26843546,
-      6710886, -13421773,  13421773, -26843546,  26843546
+    -26843541,  -6710886,  13421773, -13421773,  26843546,
+      6710886, -13421773,  13421773, -26843546,  -6710886
   }, d_pieces[] = {
-    -10913629,  13857413, -15372611,   6949391,    114729,
-     -8787816,  -6275908,  -3247719, -18696448,  21499316
+    -10913610,  13857413, -15372611,   6949391,    114729,
+     -8787816,  -6275908,  -3247719, -18696448, -12055116
   };
 #endif
 #if F25519_IMPL == 10
 # define P p10
-  static const int16 bx_pieces[] = {
+  static const f25519_piece bx_pieces[] = {
      282,  373,  242,  386, -467,   86, -423,  318, -437,
       75,  236, -308,  421,   92,  439,  -35,  400,  452,
       82,  -40,  160,  441,  -51,  437, -365,  134
   }, by_pieces[] = {
-    -424,  410, -410,  410, -410, -102,  205, -205,  205,
+    -405,  410, -410,  410, -410, -102,  205, -205,  205,
     -205,  205, -410,  410, -410,  410,  102, -205,  205,
-    -205,  205, -205,  410, -410,  410, -410,  410
+    -205,  205, -205,  410, -410,  410, -410, -102
   }, d_pieces[] = {
-     163, -418,  310, -216, -178, -133,  367, -315, -380,
+     182, -418,  310, -216, -178, -133,  367, -315, -380,
     -351, -182, -255,    2,  152, -390, -136,  -52, -383,
-    -412, -398,  -12,  448, -469, -196,   55,  328
+    -412, -398,  -12,  448, -469, -196,   55, -184
   };
 #endif
 
-static const scaf_piece bz_pieces[NPIECE] = { 1, 0, /* ... */ };
+static const f25519_piece bz_pieces[NPIECE] = { 1, 0, /* ... */ };
 #define BX ((const f25519 *)bx_pieces)
 #define BY ((const f25519 *)by_pieces)
 #define BZ ((const f25519 *)bz_pieces)
@@ -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);
 }
 
@@ -154,7 +172,7 @@ static void ptadd(f25519 *X, f25519 *Y, f25519 *Z,
 		  const f25519 *X0, const f25519 *Y0, const f25519 *Z0,
 		  const f25519 *X1, const f25519 *Y1, const f25519 *Z1)
 {
-  f25519 t0, t1, t2, t3, t4, t5;
+  f25519 t0, t1, t2, t3;
 
   /* Bernstein, Birkner, Joye, Lange, and Peters, `Twisted Edwards Curves',
    * 2008-03-13, https://cr.yp.to/newelliptic/twisted-20080313.pdf shows the
@@ -169,23 +187,23 @@ static void ptadd(f25519 *X, f25519 *Y, f25519 *Z,
    */
 
   f25519_mul(&t0, Z0, Z1);		/* t0 = A = Z0 Z1 */
-  f25519_sqr(&t1, &t0);			/* t1 = B = A^2 */
+  f25519_add(&t1, X0, Y0);		/* t1 = X0 + Y0 */
+  f25519_add(&t2, X1, Y1);		/* t2 = X1 + Y1 */
+  f25519_mul(&t1, &t1, &t2);		/* t1 = (X0 + Y0) (X1 + Y1) */
   f25519_mul(&t2, X0, X1);		/* t2 = C = X0 X1 */
   f25519_mul(&t3, Y0, Y1);		/* t3 = D = Y0 Y1 */
-  f25519_mul(&t4, &t2, &t3);		/* t4 = C D */
-  f25519_mul(&t4, &t4, D);		/* t4 = E = d C D */
-  f25519_sub(&t5, &t1, &t4);		/* t5 = F = B - E */
-  f25519_add(&t4, &t1, &t4);		/* t4 = G = B + E */
-  f25519_add(&t1, &t2, &t3);		/* t1 = C + D */
-  f25519_add(&t2, X0, Y0);		/* t2 = X0 + Y0 */
-  f25519_add(&t3, X1, Y1);		/* t3 = X1 + Y1 */
-  f25519_mul(X, &t0, &t5);		/* X = A F */
-  f25519_mul(Y, &t0, &t4);		/* Y = A G */
-  f25519_mul(Z, &t5, &t4);		/* Z = F G */
-  f25519_mul(Y, Y, &t1);		/* Y = A G (C + D) = A G (D - a C) */
-  f25519_mul(&t0, &t2, &t3);		/* t0 = (X0 + Y0) (X1 + Y1) */
-  f25519_sub(&t0, &t0, &t1);	       /* t0 = (X0 + Y0) (X1 + Y1) - C - D */
-  f25519_mul(X, X, &t0);	  /* X = A F ((X0 + Y0) (X1 + Y1) - C - D) */
+  f25519_add(Y, &t2, &t3);		/* Y = C + D = D - a C */
+  f25519_sub(X, &t1, Y);		/* X = (X0 + Y0) (X1 + Y1) - C - D */
+  f25519_mul(X, X, &t0);	    /* X = A ((X0 + Y0) (X1 + Y1) - C - D) */
+  f25519_mul(Y, Y, &t0);		/* Y = A (D - a C) */
+  f25519_sqr(&t0, &t0);			/* t0 = B = A^2 */
+  f25519_mul(&t1, &t2, &t3);		/* t1 = C D */
+  f25519_mul(&t1, &t1, D);		/* t1 = E = d C D */
+  f25519_sub(&t2, &t0, &t1);		/* t2 = F = B - E */
+  f25519_add(&t1, &t0, &t1);		/* t1 = G = B + E */
+  f25519_mul(X, X, &t2);	  /* X = A F ((X0 + Y0) (X1 + Y1) - C - D) */
+  f25519_mul(Y, Y, &t1);		/* Y = A G (D - a C) */
+  f25519_mul(Z, &t1, &t2);		/* Z = F G */
 }
 
 static void ptdbl(f25519 *X, f25519 *Y, f25519 *Z,
@@ -371,7 +389,7 @@ static void unpack_key(scaf_piece a[NPIECE], octet h1[32],
   sha512_init(&h); sha512_hash(&h, k, ksz); sha512_done(&h, b);
   b[0] &= 0xf8u; b[31] = (b[31]&0x3f) | 0x40;
   scaf_load(a, b, 32, NPIECE, PIECEWD);
-  memcpy(h1, b + 32, 32);
+  if (h1) memcpy(h1, b + 32, 32);
 }
 
 /*----- Main code ---------------------------------------------------------*/
@@ -391,9 +409,8 @@ void ed25519_pubkey(octet K[ED25519_PUBSZ], const void *k, size_t ksz)
 {
   scaf_piece a[NPIECE];
   f25519 AX, AY, AZ;
-  octet h1[32];
 
-  unpack_key(a, h1, k, ksz);
+  unpack_key(a, 0, k, ksz);
   ptmul(&AX, &AY, &AZ, a, BX, BY, BZ);
   ptencode(K, &AX, &AY, &AZ);
 }
@@ -480,13 +497,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);
@@ -512,11 +536,11 @@ static int vrf_pubkey(dstr dv[])
   dstr dpub = DSTR_INIT;
   int ok = 1;
 
-  if (dv[1].len != 32) die(1, "bad pub length");
+  if (dv[1].len != ED25519_PUBSZ) die(1, "bad pub length");
 
-  dstr_ensure(&dpub, 32); dpub.len = 32;
+  dstr_ensure(&dpub, ED25519_PUBSZ); dpub.len = ED25519_PUBSZ;
   ed25519_pubkey((octet *)dpub.buf, dv[0].buf, dv[0].len);
-  if (memcmp(dpub.buf, dv[1].buf, 64) != 0) {
+  if (memcmp(dpub.buf, dv[1].buf, ED25519_PUBSZ) != 0) {
     ok = 0;
     fprintf(stderr, "failed!");
     fprintf(stderr, "\n\tpriv = "); type_hex.dump(&dv[0], stderr);
@@ -535,13 +559,13 @@ static int vrf_sign(dstr dv[])
   dstr dsig = DSTR_INIT;
   int ok = 1;
 
-  if (dv[2].len != 64) die(1, "bad result length");
+  if (dv[2].len != ED25519_SIGSZ) die(1, "bad result length");
 
-  dstr_ensure(&dsig, 64); dsig.len = 64;
+  dstr_ensure(&dsig, ED25519_SIGSZ); dsig.len = ED25519_SIGSZ;
   ed25519_pubkey(K, dv[0].buf, dv[0].len);
   ed25519_sign((octet *)dsig.buf, dv[0].buf, dv[0].len, K,
 	       dv[1].buf, dv[1].len);
-  if (memcmp(dsig.buf, dv[2].buf, 64) != 0) {
+  if (memcmp(dsig.buf, dv[2].buf, ED25519_SIGSZ) != 0) {
     ok = 0;
     fprintf(stderr, "failed!");
     fprintf(stderr, "\n\tpriv = "); type_hex.dump(&dv[0], stderr);
@@ -560,8 +584,8 @@ static int vrf_verify(dstr dv[])
   int rc_want, rc_calc;
   int ok = 1;
 
-  if (dv[0].len != 32) die(1, "bad pub length");
-  if (dv[2].len != 64) die(1, "bad sig length");
+  if (dv[0].len != ED25519_PUBSZ) die(1, "bad pub length");
+  if (dv[2].len != ED25519_SIGSZ) die(1, "bad sig length");
   rc_want = *(int *)dv[3].buf;
 
   rc_calc = ed25519_verify((const octet *)dv[0].buf,