From accdbbc96b8ee45ba633af3980046b9db5cd8e7e Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Wed, 10 May 2017 21:13:54 +0100 Subject: [PATCH] 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. --- pub/Makefile.am | 6 ++++-- pub/ed25519.c | 33 +++++++++++++++++++++++++++++---- pub/t/ed25519.local | 43 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 76 insertions(+), 6 deletions(-) create mode 100644 pub/t/ed25519.local diff --git a/pub/Makefile.am b/pub/Makefile.am index 70470665..98c0a15f 100644 --- 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) -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 -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.new && \ mv t/ed25519.new t/ed25519 diff --git a/pub/ed25519.c b/pub/ed25519.c index 655b1e60..830e5de4 100644 --- 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); diff --git a/pub/t/ed25519.local b/pub/t/ed25519.local new file mode 100644 index 00000000..699d4c90 --- /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; +} -- 2.11.0