From 3b09bd841c6f31e968717e46b5e995fff0481924 Mon Sep 17 00:00:00 2001
From: Mark Wooding <mdw@distorted.org.uk>
Date: Tue, 8 Jun 2021 00:30:20 +0100
Subject: [PATCH] symm/des.c: Introduce a function to fix or check key parity.

I found myself wanting this (though Python) today, and realised that not
only was it missing from the Python bindings, it wasn't in the library
at all.  So here it is.  The Python bindings will come later.
---
 progs/key.c | 10 ++--------
 symm/des.c  | 43 +++++++++++++++++++++++++++++++++++++++++++
 symm/des.h  | 17 +++++++++++++++++
 3 files changed, 62 insertions(+), 8 deletions(-)

diff --git a/progs/key.c b/progs/key.c
index c59eac0f..d5bfedb8 100644
--- a/progs/key.c
+++ b/progs/key.c
@@ -53,6 +53,7 @@
 
 #include "bintab.h"
 #include "bbs.h"
+#include "des.h"
 #include "dh.h"
 #include "dsa.h"
 #include "dsarand.h"
@@ -411,7 +412,6 @@ static void alg_des(keyopts *k)
   unsigned sz;
   octet *p;
   key_data *kd;
-  int i;
 
   if (!k->bits)
     k->bits = 168;
@@ -422,13 +422,7 @@ static void alg_des(keyopts *k)
   sz = k->bits / 7;
   p = sub_alloc(sz);
   k->r->ops->fill(k->r, p, sz);
-  for (i = 0; i < sz; i++) {
-    octet x = p[i] | 0x01;
-    x = x ^ (x >> 4);
-    x = x ^ (x >> 2);
-    x = x ^ (x >> 1);
-    p[i] = (p[i] & 0xfe) | (x & 0x01);
-  }
+  des_fixparity(p, p, sz);
   kd = key_newbinary(KCAT_SYMM | KF_BURN, p, sz);
   memset(p, 0, sz);
   dolock(k, &kd, 0);
diff --git a/symm/des.c b/symm/des.c
index 06400a15..19407bc8 100644
--- a/symm/des.c
+++ b/symm/des.c
@@ -100,6 +100,49 @@ static void permute(const char *p, uint32 a, uint32 b, uint32 *d)
   d[1] = y;
 }
 
+/* --- @des_fixparity@ --- *
+ *
+ * Arguments:	@octet *z@ = output buffer pointer, or null
+ *		@const octet *p@ = input buffer pointer
+ *		@size_t sz@ = size of the buffers
+ *
+ * Returns:	Zero if the input already had correct parity, @-1@ if changes
+ *		were necessary (in constant time).
+ *
+ * Use:		Check the @sz@ bytes at @p@ for odd parity (as used in DES
+ *		keys); if @z@ is not null, then copy a parity-fixed version
+ *		of @p@ to @z@.  The two buffers at @p@ and @z@ may coincide,
+ *		or be disjoint, but not otherwise overlap.
+ */
+
+int des_fixparity(octet *z, const octet *p, size_t sz)
+{
+  int a = 0, t, u;
+
+  while (sz--) {
+
+    /* Collect the byte. */
+    t = *p++;
+
+    /* Compute the parity.  Specifically, this will determine the overall
+     * parity of the byte: 0 for odd, and 1 for even (since we complement
+     * the result).  This is therefore the change which needs to be applied
+     * to the incoming byte to ensure that it has odd parity.
+     */
+    u = t; u ^= u >> 4; u ^= u >> 2; u ^= u >> 1; u ^= 1; u &= 1;
+
+    /* Accumulate the difference.  If any bytes had even parity, then this
+     * will equal 1. */
+    a |= u;
+
+    /* Maybe write out the fixed value. */
+    if (z) *z++ = t ^ u;
+  }
+
+  /* Done. */
+  return (-a);
+}
+
 /* --- @des_expand@ --- *
  *
  * Arguments:	@const octet *k@ = pointer to key material
diff --git a/symm/des.h b/symm/des.h
index 682be6b0..6f5ebbe8 100644
--- a/symm/des.h
+++ b/symm/des.h
@@ -66,6 +66,23 @@ typedef struct des_ctx {
 
 /*----- Functions provided ------------------------------------------------*/
 
+/* --- @des_fixparity@ --- *
+ *
+ * Arguments:	@octet *z@ = output buffer pointer, or null
+ *		@const octet *p@ = input buffer pointer
+ *		@size_t sz@ = size of the buffers
+ *
+ * Returns:	Zero if the input already had correct parity, @-1@ if changes
+ *		were necessary (in constant time).
+ *
+ * Use:		Check the @sz@ bytes at @p@ for odd parity (as used in DES
+ *		keys); if @z@ is not null, then copy a parity-fixed version
+ *		of @p@ to @z@.  The two buffers at @p@ and @z@ may coincide,
+ *		or be disjoint, but not otherwise overlap.
+ */
+
+extern int des_fixparity(octet */*z*/, const octet */*p*/, size_t /*sz*/);
+
 /* --- @des_expand@ --- *
  *
  * Arguments:	@const octet *k@ = pointer to key material
-- 
2.11.0