X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb/blobdiff_plain/a7aa36f2e3359a9d5cc164cc418352b629451e7c..6a024d24d97cb5d42c0091571735475b849f59f4:/pub/ed25519.c diff --git a/pub/ed25519.c b/pub/ed25519.c index 82099f2c..676fe8ca 100644 --- a/pub/ed25519.c +++ b/pub/ed25519.c @@ -32,6 +32,7 @@ #include "f25519.h" #include "ed25519.h" #include "scaf.h" +#include "scmul.h" #include "sha512.h" /*----- Key fetching ------------------------------------------------------*/ @@ -231,7 +232,7 @@ static void ptdbl(f25519 *X, f25519 *Y, f25519 *Z, /* (E = a C = -C) */ f25519_sub(&t0, &t2, &t1); /* t0 = F = D - C = E + D */ f25519_sqr(&t1, Z0); /* t1 = H = Z0^2 */ - f25519_mulconst(&t1, &t1, 2); /* t1 = 2 H */ + f25519_add(&t1, &t1, &t1); /* t1 = 2 H */ f25519_sub(&t1, &t0, &t1); /* t1 = J = F - 2 H */ f25519_mul(X, X, &t1); /* X = (B - C - D) J */ f25519_mul(Y, Y, &t0); /* Y = -F (E - D) */ @@ -239,144 +240,8 @@ static void ptdbl(f25519 *X, f25519 *Y, f25519 *Z, f25519_mul(Z, &t0, &t1); /* Z = F J */ } -static void ptmul(f25519 *X, f25519 *Y, f25519 *Z, - const scaf_piece n[NPIECE], - const f25519 *X0, const f25519 *Y0, const f25519 *Z0) -{ - /* We assume that the window width divides the scalar piece width. */ -#define WINWD 4 -#define WINLIM (1 << WINWD) -#define WINMASK (WINLIM - 1) -#define TABSZ (WINLIM/2 + 1) - - f25519 VX[TABSZ], VY[TABSZ], VZ[TABSZ]; - f25519 TX, TY, TZ, UX, UY, UZ; - unsigned i, j, k, w; - uint32 m_neg; - scaf_piece ni; - - /* Build a table of small multiples. */ - f25519_set(&VX[0], 0); f25519_set(&VY[0], 1); f25519_set(&VZ[0], 1); - VX[1] = *X0; VY[1] = *Y0; VZ[1] = *Z0; - ptdbl(&VX[2], &VY[2], &VZ[2], &VX[1], &VY[1], &VZ[1]); - for (i = 3; i < TABSZ; i += 2) { - ptadd(&VX[i], &VY[i], &VZ[i], - &VX[i - 1], &VY[i - 1], &VZ[i - 1], X0, Y0, Z0); - ptdbl(&VX[i + 1], &VY[i + 1], &VZ[i + 1], - &VX[(i + 1)/2], &VY[(i + 1)/2], &VZ[(i + 1)/2]); - } - - /* Now do the multiplication. We lag a window behind the cursor position - * because of the scalar recoding we do. - */ - f25519_set(&TX, 0); f25519_set(&TY, 1); f25519_set(&TZ, 1); - for (i = NPIECE, w = 0, m_neg = 0; i--; ) { - ni = n[i]; - - /* Work through each window in the scalar piece. */ - for (j = 0; j < PIECEWD; j += WINWD) { - - /* Shift along by a window. */ - for (k = 0; k < WINWD; k++) ptdbl(&TX, &TY, &TZ, &TX, &TY, &TZ); - - /* Peek at the next window of four bits. If the top bit is set we lend - * a bit leftwards, into w. It's too late for this to affect the sign - * now, but if we negated earlier then the addition would be wrong. - */ - w += (ni >> (PIECEWD - 1))&0x1u; - w = ((WINLIM - w)&m_neg) | (w&~m_neg); - - /* Collect the entry from the table, and add or subtract. */ - f25519_pickn(&UX, VX, TABSZ, w); - f25519_pickn(&UY, VY, TABSZ, w); - f25519_pickn(&UZ, VZ, TABSZ, w); - f25519_condneg(&UX, &UX, m_neg); - ptadd(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ); - - /* Move the next window into the delay slot. If its top bit is set, - * then negate it and set m_neg. - */ - w = (ni >> (PIECEWD - WINWD))&WINMASK; - m_neg = -(uint32)((w >> (WINWD - 1))&0x1u); - ni <<= WINWD; - } - } - - /* Do the final window. Just fix the sign and go. */ - for (k = 0; k < WINWD; k++) ptdbl(&TX, &TY, &TZ, &TX, &TY, &TZ); - w = ((WINLIM - w)&m_neg) | (w&~m_neg); - f25519_pickn(&UX, VX, TABSZ, w); - f25519_pickn(&UY, VY, TABSZ, w); - f25519_pickn(&UZ, VZ, TABSZ, w); - f25519_condneg(&UX, &UX, m_neg); - ptadd(X, Y, Z, &TX, &TY, &TZ, &UX, &UY, &UZ); - -#undef WINWD -#undef WINLIM -#undef WINMASK -#undef TABSZ -} - -static void ptsimmul(f25519 *X, f25519 *Y, f25519 *Z, - const scaf_piece n0[NPIECE], - const f25519 *X0, const f25519 *Y0, const f25519 *Z0, - const scaf_piece n1[NPIECE], - const f25519 *X1, const f25519 *Y1, const f25519 *Z1) -{ - /* We assume that the window width divides the scalar piece width. */ -#define WINWD 2 -#define WINLIM (1 << WINWD) -#define WINMASK (WINLIM - 1) -#define TABSZ (1 << 2*WINWD) - - f25519 VX[TABSZ], VY[TABSZ], VZ[TABSZ]; - f25519 TX, TY, TZ, UX, UY, UZ; - unsigned i, j, k, w, ni0, ni1; - - /* Build a table of small linear combinations. */ - f25519_set(&VX[0], 0); f25519_set(&VY[0], 1); f25519_set(&VZ[0], 1); - VX[1] = *X0; VX[WINLIM] = *X1; - VY[1] = *Y0; VY[WINLIM] = *Y1; - VZ[1] = *Z0; VZ[WINLIM] = *Z1; - for (i = 2; i < WINLIM; i <<= 1) { - ptdbl(&VX[i], &VY[i], &VZ[i], - &VX[i/2], &VY[i/2], &VZ[i/2]); - ptdbl(&VX[i*WINLIM], &VY[i*WINLIM], &VZ[i*WINLIM], - &VX[i*WINLIM/2], &VY[i*WINLIM/2], &VZ[i*WINLIM/2]); - } - for (i = 2; i < TABSZ; i <<= 1) { - for (j = 1; j < i; j++) - ptadd(&VX[i + j], &VY[i + j], &VZ[i + j], - &VX[i], &VY[i], &VZ[i], &VX[j], &VY[j], &VZ[j]); - } - - /* Do the multiplication. */ - f25519_set(&TX, 0); f25519_set(&TY, 1); f25519_set(&TZ, 1); - for (i = NPIECE; i--; ) { - ni0 = n0[i]; ni1 = n1[i]; - - /* Work through each window in the scalar pieces. */ - for (j = 0; j < PIECEWD; j += WINWD) { - - /* Shift along by a window. */ - for (k = 0; k < WINWD; k++) ptdbl(&TX, &TY, &TZ, &TX, &TY, &TZ); - - /* Collect the next window from the scalars. */ - w = ((ni0 >> (PIECEWD - WINWD))&WINMASK) | - ((ni1 >> (PIECEWD - 2*WINWD))&(WINMASK << WINWD)); - ni0 <<= WINWD; ni1 <<= WINWD; - - /* Collect the entry from the table, and add. */ - f25519_pickn(&UX, VX, TABSZ, w); - f25519_pickn(&UY, VY, TABSZ, w); - f25519_pickn(&UZ, VZ, TABSZ, w); - ptadd(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ); - } - } - - /* Done. */ - *X = TX; *Y = TY; *Z = TZ; -} +static DEFINE_SCMUL(ptmul, f25519, 4, PIECEWD, NPIECE, ptadd, ptdbl) +static DEFINE_SCSIMMUL(ptsimmul, f25519, 2, PIECEWD, NPIECE, ptadd, ptdbl) /*----- Key derivation utilities ------------------------------------------*/ @@ -454,7 +319,7 @@ void ed25519ctx_sign(octet sig[ED25519_SIGSZ], const void *m, size_t msz) { sha512_ctx h; - scaf_piece a[NPIECE], r[NPIECE], t[NPIECE], scratch[3*NPIECE + 1]; + scaf_piece a[NPIECE], r[NPIECE], t[NPIECE], scratch[3*NPIECE]; scaf_dblpiece tt[2*NPIECE]; f25519 RX, RY, RZ; octet h1[32], pb[PREFIX_BUFSZ], rb[SHA512_HASHSZ]; @@ -523,7 +388,7 @@ int ed25519ctx_verify(const octet K[ED25519_PUBSZ], const octet sig[ED25519_SIGSZ]) { sha512_ctx h; - scaf_piece s[NPIECE], t[NPIECE], scratch[3*NPIECE + 1]; + scaf_piece s[NPIECE], t[NPIECE], scratch[3*NPIECE]; scaf_dblpiece tt[2*NPIECE]; f25519 AX, AY, AZ, RX, RY, RZ; octet b[PREFIX_BUFSZ]; @@ -576,6 +441,8 @@ int ed25519_verify(const octet K[ED25519_PUBSZ], #include #include +#include "ct.h" + static int vrf_pubkey(dstr dv[]) { dstr dpub = DSTR_INIT; @@ -583,8 +450,10 @@ static int vrf_pubkey(dstr dv[]) if (dv[1].len != ED25519_PUBSZ) die(1, "bad pub length"); + ct_poison(dv[0].buf, dv[0].len); dstr_ensure(&dpub, ED25519_PUBSZ); dpub.len = ED25519_PUBSZ; ed25519_pubkey((octet *)dpub.buf, dv[0].buf, dv[0].len); + ct_remedy(dpub.buf, dpub.len); if (memcmp(dpub.buf, dv[1].buf, ED25519_PUBSZ) != 0) { ok = 0; fprintf(stderr, "failed!"); @@ -608,6 +477,7 @@ static int vrf_sign(dstr *priv, int phflag, dstr *perso, if (want->len != ED25519_SIGSZ) die(1, "bad result length"); + ct_poison(priv->buf, priv->len); dstr_ensure(&dsig, ED25519_SIGSZ); dsig.len = ED25519_SIGSZ; if (phflag <= 0) m = msg; @@ -622,6 +492,7 @@ static int vrf_sign(dstr *priv, int phflag, dstr *perso, ed25519ctx_sign((octet *)dsig.buf, priv->buf, priv->len, K, phflag, perso ? perso->buf : 0, perso ? perso->len : 0, m->buf, m->len); + ct_remedy(dsig.buf, dsig.len); if (memcmp(dsig.buf, want->buf, ED25519_SIGSZ) != 0) { ok = 0; fprintf(stderr, "failed!");