From: Mark Wooding Date: Sun, 1 Oct 2017 02:01:02 +0000 (+0100) Subject: Start verifying that code which should be constant-time really is. X-Git-Tag: 2.4.2~21 X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb/commitdiff_plain/1aaccf40b93719fd3df7cc89e023b9bb48b358b6 Start verifying that code which should be constant-time really is. Introduce utilities `ct_poison' and `ct_remedy' to control Valgrind's uninitialized-data checking, based on Adam Langley's `ctgrind' idea described in https://www.imperialviolet.org/2010/04/01/ctgrind.html. Use these in the tests for fancy-bignum algorithms, such as Poly1305 and X25519. There's currently no automated machinery for running these tests. This is a little tricky: * Some of the tests will need to be skipped because they just take too long if they run under Valgrind. * The test programs are actually libtool wrappers, which are bash(1) scripts. Firstly, this means we get lots of spurious errors about bash; and secondly, the actual test program doesn't end up being checked by Valgrind at all. So it's just manual for now. --- diff --git a/base/Makefile.am b/base/Makefile.am index 0ac43f2e..c9560ca2 100644 --- a/base/Makefile.am +++ b/base/Makefile.am @@ -38,7 +38,7 @@ libbase_la_SOURCES += arena.c ## Constant-type operations. pkginclude_HEADERS += ct.h -libbase_la_SOURCES += ct.c +libbase_la_SOURCES += ct.c ct-test.c ## CPU-specific dispatch. pkginclude_HEADERS += dispatch.h diff --git a/base/ct-test.c b/base/ct-test.c new file mode 100644 index 00000000..b4cddc62 --- /dev/null +++ b/base/ct-test.c @@ -0,0 +1,79 @@ +/* -*-c-*- + * + * Utilities for verifying constant-time programming + * + * (c) 2017 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software: you can redistribute it and/or modify it + * under the terms of the GNU Library General Public License as published + * by the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * Catacomb is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, + * USA. + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "config.h" + +#include "ct.h" + +#ifdef HAVE_VALGRIND_H +# include +# include +#endif + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @ct_poison@ --- * + * + * Arguments: @const void *p@ = pointer to a secret + * @size_t sz@ = size of the secret + * + * Returns: --- + * + * Use: Ordinarily, does nothing. If the process is running under + * the control of Valgrind's `memcheck' utility, then mark the + * secret as `uninitialized', so that Valgrind warns about + * conditional execution or memory addressing based on the value + * of the secret. + * + * Credit for this idea goes to Adam Langley, who described it + * in https://www.imperialviolet.org/2010/04/01/ctgrind.html, + * though this implementation doesn't require patching Valgrind. + */ + +void ct_poison(const void *p, size_t sz) + { VALGRIND_MAKE_MEM_UNDEFINED(p, sz); } + +/* --- @ct_remedy@ --- * + * + * Arguments: @const void *p@ = pointer to a secret + * @size_t sz@ = size of the secret + * + * Returns: --- + * + * Use: Ordinarily, does nothing. If the process is running under + * the control of Valgrind's `memcheck' utility, then mark the + * secret as `initialized'. This is intended to reverse the + * effect of @ct_poison@ so that a test program can verify + * function outputs wihtout Valgrind warning. + */ + +void ct_remedy(const void *p, size_t sz) + { VALGRIND_MAKE_MEM_DEFINED(p, sz); } + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/base/ct.h b/base/ct.h index 3066e4f2..445d889d 100644 --- a/base/ct.h +++ b/base/ct.h @@ -36,7 +36,7 @@ #include -/*----- Functions provided ------------------------------------------------*/ +/*----- Miscellaneous constant-time utilities -----------------------------*/ /* --- @ct_inteq@ --- * * @@ -103,6 +103,44 @@ extern void ct_condcopy(uint32 /*a*/, extern int ct_memeq(const void */*p*/, const void */*q*/, size_t /*n*/); +/*----- Utilities for testing ---------------------------------------------*/ + +/* --- @ct_poison@ --- * + * + * Arguments: @const void *p@ = pointer to a secret + * @size_t sz@ = size of the secret + * + * Returns: --- + * + * Use: Ordinarily, does nothing. If the process is running under + * the control of Valgrind's `memcheck' utility, then mark the + * secret as `uninitialized', so that Valgrind warns about + * conditional execution or memory addressing based on the value + * of the secret. + * + * Credit for this idea goes to Adam Langley, who described it + * in https://www.imperialviolet.org/2010/04/01/ctgrind.html, + * though this implementation doesn't require patching Valgrind. + */ + +extern void ct_poison(const void */*p*/, size_t /*sz*/); + +/* --- @ct_remedy@ --- * + * + * Arguments: @const void *p@ = pointer to a secret + * @size_t sz@ = size of the secret + * + * Returns: --- + * + * Use: Ordinarily, does nothing. If the process is running under + * the control of Valgrind's `memcheck' utility, then mark the + * secret as `initialized'. This is intended to reverse the + * effect of @ct_poison@ so that a test program can verify + * function outputs wihtout Valgrind warning. + */ + +extern void ct_remedy(const void */*p*/, size_t /*sz*/); + /*----- That's all, folks -------------------------------------------------*/ #ifdef __cplusplus diff --git a/configure.ac b/configure.ac index bdc94be7..40353daa 100644 --- a/configure.ac +++ b/configure.ac @@ -368,6 +368,12 @@ LIBS=$mdw_ORIG_LIBS dnl Memory locking support. AC_CHECK_FUNCS([mlock]) +dnl See if we can find Valgrind's header files. +AC_CHECK_HEADER([valgrind/memcheck.h], + AC_DEFINE([HAVE_VALGRIND_H], [1], + [Define if the Valgrind header files are available.]) + []) + dnl Set the master libraries we need. AC_SUBST([CATACOMB_LIBS]) diff --git a/pub/ed25519.c b/pub/ed25519.c index f23c272a..7fddf987 100644 --- a/pub/ed25519.c +++ b/pub/ed25519.c @@ -441,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; @@ -448,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!"); @@ -473,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; @@ -487,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!"); diff --git a/pub/ed448.c b/pub/ed448.c index 714987f4..ae565566 100644 --- a/pub/ed448.c +++ b/pub/ed448.c @@ -424,6 +424,8 @@ int ed448_verify(const octet K[ED448_PUBSZ], #include #include +#include "ct.h" + static int vrf_pubkey(dstr dv[]) { dstr dpub = DSTR_INIT; @@ -431,8 +433,10 @@ static int vrf_pubkey(dstr dv[]) if (dv[1].len != ED448_PUBSZ) die(1, "bad pub length"); + ct_poison(dv[0].buf, dv[0].len); dstr_ensure(&dpub, ED448_PUBSZ); dpub.len = ED448_PUBSZ; ed448_pubkey((octet *)dpub.buf, dv[0].buf, dv[0].len); + ct_remedy(dpub.buf, dpub.len); if (memcmp(dpub.buf, dv[1].buf, ED448_PUBSZ) != 0) { ok = 0; fprintf(stderr, "failed!"); @@ -456,6 +460,7 @@ static int vrf_sign(dstr *priv, int phflag, dstr *perso, if (want->len != ED448_SIGSZ) die(1, "bad result length"); + ct_poison(priv->buf, priv->len); dstr_ensure(&dsig, ED448_SIGSZ); dsig.len = ED448_SIGSZ; if (phflag <= 0) m = msg; @@ -470,6 +475,7 @@ static int vrf_sign(dstr *priv, int phflag, dstr *perso, ed448_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, ED448_SIGSZ) != 0) { ok = 0; fprintf(stderr, "failed!"); diff --git a/pub/x25519.c b/pub/x25519.c index aeff290e..f8971298 100644 --- a/pub/x25519.c +++ b/pub/x25519.c @@ -114,6 +114,8 @@ void x25519(octet zz[X25519_OUTSZ], #include #include +#include "ct.h" + static int vrf_x25519(dstr dv[]) { dstr dz = DSTR_INIT; @@ -123,10 +125,12 @@ static int vrf_x25519(dstr dv[]) if (dv[1].len != X25519_PUBSZ) die(1, "bad public length"); if (dv[2].len != X25519_OUTSZ) die(1, "bad result length"); + ct_poison(dv[0].buf, dv[0].len); dstr_ensure(&dz, X25519_OUTSZ); dz.len = X25519_OUTSZ; x25519((octet *)dz.buf, (const octet *)dv[0].buf, (const octet *)dv[1].buf); + ct_remedy(dz.buf, dz.len); if (memcmp(dz.buf, dv[2].buf, X25519_OUTSZ) != 0) { ok = 0; fprintf(stderr, "failed!"); diff --git a/pub/x448.c b/pub/x448.c index 73ca6bf7..6bef9dd3 100644 --- a/pub/x448.c +++ b/pub/x448.c @@ -101,6 +101,8 @@ void x448(octet zz[X448_OUTSZ], #include #include +#include "ct.h" + static int vrf_x448(dstr dv[]) { dstr dz = DSTR_INIT; @@ -110,10 +112,12 @@ static int vrf_x448(dstr dv[]) if (dv[1].len != X448_PUBSZ) die(1, "bad public length"); if (dv[2].len != X448_OUTSZ) die(1, "bad result length"); + ct_poison(dv[0].buf, dv[0].len); dstr_ensure(&dz, X448_OUTSZ); dz.len = X448_OUTSZ; x448((octet *)dz.buf, (const octet *)dv[0].buf, (const octet *)dv[1].buf); + ct_remedy(dz.buf, dz.len); if (memcmp(dz.buf, dv[2].buf, X448_OUTSZ) != 0) { ok = 0; fprintf(stderr, "failed!"); diff --git a/symm/poly1305.c b/symm/poly1305.c index 3a838a83..942aa384 100644 --- a/symm/poly1305.c +++ b/symm/poly1305.c @@ -875,6 +875,7 @@ void poly1305_done(poly1305_ctx *ctx, void *h) #include +#include "ct.h" #include "rijndael-ecb.h" static int vrf_hash(dstr v[]) @@ -889,6 +890,7 @@ static int vrf_hash(dstr v[]) if (v[3].len != 16) { fprintf(stderr, "bad tag length\n"); exit(2); } dstr_ensure(&t, 16); t.len = 16; + ct_poison(v[0].buf, v[0].len); poly1305_keyinit(&k, v[0].buf, v[0].len); for (i = 0; i < v[2].len; i++) { for (j = i; j < v[2].len; j++) { @@ -897,6 +899,7 @@ static int vrf_hash(dstr v[]) poly1305_hash(&ctx, v[2].buf + i, j - i); poly1305_hash(&ctx, v[2].buf + j, v[2].len - j); poly1305_done(&ctx, t.buf); + ct_remedy(t.buf, t.len); if (memcmp(t.buf, v[3].buf, 16) != 0) { fprintf(stderr, "failed..."); fprintf(stderr, "\n\tkey = "); type_hex.dump(&v[0], stderr);