From bfb450ccb248489a622c7dcb51ed5e150eb8f3b6 Mon Sep 17 00:00:00 2001
Message-Id: <bfb450ccb248489a622c7dcb51ed5e150eb8f3b6.1716245125.git.mdw@distorted.org.uk>
From: Mark Wooding <mdw@chiark.greenend.org.uk>
Date: Thu, 26 May 2016 09:26:09 +0100
Subject: [PATCH] bytestring.c, catacomb/__init__.py: Compare for equality in
 constant time.
Organization: Straylight/Edgeware

From: Mark Wooding <mdw@distorted.org.uk>

There's an explicit `ctstreq' function which just does what you wanted.
Also, `ByteString' objects now have a rich-compare method which always
compares for equality in constant time.  Ordering comparisons are
variable time still.

There's a little chicanery to retain the hash function from `str'.

Also add a simple `check' method to `GHash' and `Poly1305Hash' which
compares a hsah or MAC tag in constant time and returns a boolean
result.
---
 bytestring.c         | 56 +++++++++++++++++++++++++++++++++++++++++++-
 catacomb-python.h    |  1 +
 catacomb/__init__.py | 11 +++++++++
 3 files changed, 67 insertions(+), 1 deletion(-)

diff --git a/bytestring.c b/bytestring.c
index 7dcc406..4abb260 100644
--- a/bytestring.c
+++ b/bytestring.c
@@ -61,6 +61,52 @@ static PyObject *bytestring_pynew(PyTypeObject *ty,
   return (dowrap(ty, p, n));
 }
 
+static PyObject *meth_ctstreq(PyObject *me, PyObject *args)
+{
+  char *p, *q;
+  Py_ssize_t psz, qsz;
+  if (!PyArg_ParseTuple(args, "s#s#:ctstreq", &p, &psz, &q, &qsz))
+    goto end;
+  if (psz == qsz && ct_memeq(p, q, psz)) RETURN_TRUE;
+  else RETURN_FALSE;
+end:
+  return (0);
+}
+
+static PyObject *bytestring_pyrichcompare(PyObject *me,
+					  PyObject *you, int op)
+{
+  int b;
+  void *mystr, *yourstr;
+  Py_ssize_t mylen, yourlen, minlen;
+
+  if (!PyString_Check(me) || !PyString_Check(you)) RETURN_NOTIMPL;
+  mystr = PyString_AS_STRING(me); mylen = PyString_GET_SIZE(me);
+  yourstr = PyString_AS_STRING(you); yourlen = PyString_GET_SIZE(you);
+
+  switch (op) {
+    case Py_EQ:
+      b = mylen == yourlen && ct_memeq(mystr, yourstr, mylen);
+      break;
+    case Py_NE:
+      b = mylen != yourlen || !ct_memeq(mystr, yourstr, mylen);
+      break;
+    default:
+      minlen = mylen < yourlen ? mylen : yourlen;
+      b = memcmp(mystr, yourstr, minlen);
+      if (!b) b = mylen < yourlen ? -1 : mylen > yourlen ? +1 : 0;
+      switch (op) {
+	case Py_LT: b = b <  0; break;
+	case Py_LE: b = b <= 0; break;
+	case Py_GE: b = b >= 0; break;
+	case Py_GT: b = b >  0; break;
+	default: abort();
+      }
+  }
+  if (b) RETURN_TRUE;
+  else RETURN_FALSE;
+}
+
 #define BINOP(name, op)							\
   static PyObject *bytestring_py##name(PyObject *x, PyObject *y) {	\
     const void *xv, *yv;						\
@@ -158,7 +204,7 @@ static PyTypeObject bytestring_pytype_skel = {
 
   0,					/* @tp_traverse@ */
   0,					/* @tp_clear@ */
-  0,					/* @tp_richcompare@ */
+  bytestring_pyrichcompare,		/* @tp_richcompare@ */
   0,					/* @tp_weaklistoffset@ */
   0,					/* @tp_iter@ */
   0,					/* @tp_iternext@ */
@@ -179,10 +225,18 @@ static PyTypeObject bytestring_pytype_skel = {
 
 /*----- Initialization ----------------------------------------------------*/
 
+static PyMethodDef methods[] = {
+#define METHNAME(func) meth_##func
+  METH  (ctstreq,		"ctstreq(S, T) -> BOOL")
+#undef METHNAME
+  { 0 }
+};
+
 #define string_pytype &PyString_Type
 void bytestring_pyinit(void)
 {
   INITTYPE(bytestring, string);
+  addmethods(methods);
 }
 
 void bytestring_pyinsert(PyObject *mod)
diff --git a/catacomb-python.h b/catacomb-python.h
index 77c7eae..f1e6365 100644
--- a/catacomb-python.h
+++ b/catacomb-python.h
@@ -46,6 +46,7 @@
 #include <mLib/unihash.h>
 
 #include <catacomb/buf.h>
+#include <catacomb/ct.h>
 
 #include <catacomb/grand.h>
 #include <catacomb/rand.h>
diff --git a/catacomb/__init__.py b/catacomb/__init__.py
index 120ef11..6745bce 100644
--- a/catacomb/__init__.py
+++ b/catacomb/__init__.py
@@ -94,8 +94,19 @@ class _tmp:
   def __repr__(me):
     return 'bytes(%r)' % hex(me)
 _augment(ByteString, _tmp)
+ByteString.__hash__ = str.__hash__
 bytes = ByteString.fromhex
 
+###--------------------------------------------------------------------------
+### Hashing.
+
+class _tmp:
+  def check(me, h):
+    hh = me.done()
+    return ctstreq(h, hh)
+_augment(GHash, _tmp)
+_augment(Poly1305Hash, _tmp)
+
 ###--------------------------------------------------------------------------
 ### Multiprecision integers and binary polynomials.
 
-- 
[mdw]