From: Mark Wooding Date: Mon, 27 May 2013 21:23:35 +0000 (+0100) Subject: ct.c, ct.h: New constant-time operations. X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/commitdiff_plain/d4bb7fded5f9a4b0db99f82e88f22effe94f2ff7 ct.c, ct.h: New constant-time operations. --- diff --git a/Makefile.m4 b/Makefile.m4 index d05e6ee..636d9b6 100644 --- a/Makefile.m4 +++ b/Makefile.m4 @@ -167,7 +167,7 @@ libcatacomb_la_LDFLAGS = -version-info $(LIBTOOL_VERSION_INFO) ## difference between the first and last numbers is major version. pkginclude_HEADERS = \ - arena.h paranoia.h buf.h qdparse.h keysz.h \ + arena.h paranoia.h buf.h ct.h qdparse.h keysz.h \ blkc.h hash.h gcipher.h ghash.h gmac.h grand.h ghash-def.h \ lcrand.h fibrand.h rc4.h seal.h rand.h noise.h fipstest.h maurer.h \ key.h key-error.h key-data.h passphrase.h pixie.h lmem.h \ @@ -237,7 +237,7 @@ define(`PGEN_SOURCES', primetab.c wheel.c share.c') libcatacomb_la_SOURCES = \ - grand.c keysz.c keysz-conv.c \ + grand.c ct.c keysz.c keysz-conv.c \ lcrand.c fibrand.c rc4.c seal.c rand.c noise.c fipstest.c maurer.c \ arena.c \ passphrase.c pixie-common.c lmem.c \ diff --git a/ct.c b/ct.c new file mode 100644 index 0000000..ef2adeb --- /dev/null +++ b/ct.c @@ -0,0 +1,144 @@ +/* -*-c-*- + * + * Constant-time operations + * + * (c) 2013 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 + +#include "ct.h" + +/*----- Main code ---------------------------------------------------------*/ + +#define MASK(a) (U32(~((a) - 1))) + +/* --- @ct_inteq@ --- * + * + * Arguments: @uint32 x, y@ = two 32-bit unsigned integers + * + * Returns: One if @x@ and @y@ are equal, zero if they differ. + * + * Use: Answers whether two integers are equal, in constant time. + */ + +int ct_inteq(uint32 x, uint32 y) +{ + uint32 a = U32(~(x ^ y)); + + a &= a >> 16; + a &= a >> 8; + a &= a >> 4; + a &= a >> 2; + a &= a >> 1; + return (a & 1); +} + +/* --- @ct_intle@ --- * + * + * Arguments: @uint32 x, y@ = two 32-bit unsigned integers + * + * Returns: One if %$x \le y$% are equal, zero if @x@ is greater. + * + * Use: Answers whether two integers are ordered, in constant time. + */ + +int ct_intle(uint32 x, uint32 y) +{ + /* --- This bit's a little fiddly --- * + * + * If the top bits of @x@ and @y@ are the same then %$x \le y$% if and only + * if %$y - x$% has its top bit clear; otherwise, %$x \le y$% if and only + * if the top bit of @x@ is clear and the top bit of @y@ is set. + * + * This assumes we can do subtraction in constant time, which seems like a + * safe enough bet. + */ + + uint32 xx = x >> 31, yy = y >> 31, zz = (y - x) >> 31; + return ((~xx&yy) | (~(xx^yy)&~zz)) & 1; +} + +/* --- @ct_pick@ --- * + * + * Arguments: @uint32 a@ = a switch, either zero or one + * @uint32 x0, x1@ = two 32-bit unsigned integers + * + * Returns: @x0@ if @a@ is zero; @x1@ if @a@ is one. Other values of @a@ + * will give you unhelpful results. + * + * Use: Picks one of two results according to a switch variable, in + * constant time. + */ + +int ct_pick(uint32 a, uint32 x0, uint32 x1) + { uint32 m = MASK(a); return (x0&~m) | (x1&m); } + +/* --- @ct_condcopy@ --- * + * + * Arguments: @uint32 a@ = a switch, either zero or one + * @void *d@ = destination pointer + * @const void *s@ = source pointer + * @size_t n@ amount to copy + * + * Returns: --- + * + * Use: If @a@ is one then copy the @n@ bytes starting at @s@ to + * @d@; if @a@ is zero then leave @d@ unchanged (but it will + * still be written). All of this is done in constant time. + */ + +void ct_condcopy(uint32 a, void *d, const void *s, size_t n) +{ + octet *dd = d; + const octet *ss = s; + uint32 m = MASK(a); + + while (n--) { + *dd = (*ss++&m) | (*dd&~m); + dd++; + } +} + +/* --- @ct_memeq@ --- + * + * Arguments: @const void *p, *q@ = two pointers to buffers + * @size_t n@ = the (common) size of the buffers + * + * Returns: One if the two buffers are equal, zero if they aren't. + * + * Use: Compares two chunks of memory, in constant time. + */ + +int ct_memeq(const void *p, const void *q, size_t n) +{ + const octet *pp = p, *qq = q; + octet a = 0; + + while (n--) a |= *pp++ ^ *qq++; + return (ct_inteq(a, 0)); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/ct.h b/ct.h new file mode 100644 index 0000000..00cecc0 --- /dev/null +++ b/ct.h @@ -0,0 +1,112 @@ +/* -*-c-*- + * + * Constant-time operations + * + * (c) 2013 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. + */ + +#ifndef CATACOMB_CT_H +#define CATACOMB_CT_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#include + +/*----- Functions provided ------------------------------------------------*/ + +/* --- @ct_inteq@ --- * + * + * Arguments: @uint32 x, y@ = two 32-bit unsigned integers + * + * Returns: One if @x@ and @y@ are equal, zero if they differ. + * + * Use: Answers whether two integers are equal, in constant time. + */ + +extern int ct_inteq(uint32 /*x*/, uint32 /*y*/); + +/* --- @ct_intle@ --- * + * + * Arguments: @uint32 x, y@ = two 32-bit unsigned integers + * + * Returns: One if %$x \le y$% are equal, zero if @x@ is greater. + * + * Use: Answers whether two integers are ordered, in constant time. + */ + +extern int ct_intle(uint32 /*x*/, uint32 /*y*/); + +/* --- @ct_pick@ --- * + * + * Arguments: @uint32 a@ = a switch, either zero or one + * @uint32 x0, x1@ = two 32-bit unsigned integers + * + * Returns: @x0@ if @a@ is zero; @x1@ if @a@ is one. Other values of @a@ + * will give you unhelpful results. + * + * Use: Picks one of two results according to a switch variable, in + * constant time. + */ + +extern int ct_pick(uint32 /*a*/, uint32 /*x0*/, uint32 /*x1*/); + +/* --- @ct_condcopy@ --- * + * + * Arguments: @uint32 a@ = a switch, either zero or one + * @void *d@ = destination pointer + * @const void *s@ = source pointer + * @size_t n@ amount to copy + * + * Returns: --- + * + * Use: If @a@ is one then copy the @n@ bytes starting at @s@ to + * @d@; if @a@ is zero then leave @d@ unchanged (but it will + * still be written). All of this is done in constant time. + */ + +extern void ct_condcopy(uint32 /*a*/, + void */*d*/, const void */*s*/, size_t /*n*/); + +/* --- @ct_memeq@ --- + * + * Arguments: @const void *p, *q@ = two pointers to buffers + * @size_t n@ = the (common) size of the buffers + * + * Returns: One if the two buffers are equal, zero if they aren't. + * + * Use: Compares two chunks of memory, in constant time. + */ + +extern int ct_memeq(const void */*p*/, const void */*q*/, size_t /*n*/); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif