Add UHASH implementation

8 files changed, 378 insertions, 25 deletions

diff --git a/src/crypto/mac/CMakeLists.txt b/src/crypto/mac/CMakeLists.txt
index 971c04b..08fd194 100644
--- a/src/crypto/mac/CMakeLists.txt
+++ b/src/crypto/mac/CMakeLists.txt
@@ -60,6 +60,7 @@ endmacro(fastd_mac_impl_compile_flags)
 
 
 add_subdirectory(ghash)
+add_subdirectory(uhash)
 
 
 set(MAC_DEFINITIONS "")
diff --git a/src/crypto/mac/uhash/CMakeLists.txt b/src/crypto/mac/uhash/CMakeLists.txt
new file mode 100644
index 0000000..04884d3
--- /dev/null
+++ b/src/crypto/mac/uhash/CMakeLists.txt
@@ -0,0 +1,2 @@
+fastd_mac(uhash uhash.c)
+add_subdirectory(builtin)
diff --git a/src/crypto/mac/uhash/builtin/CMakeLists.txt b/src/crypto/mac/uhash/builtin/CMakeLists.txt
new file mode 100644
index 0000000..0bdc2ba
--- /dev/null
+++ b/src/crypto/mac/uhash/builtin/CMakeLists.txt
@@ -0,0 +1,3 @@
+fastd_mac_impl(uhash builtin
+  uhash_builtin.c
+)
diff --git a/src/crypto/mac/uhash/builtin/uhash_builtin.c b/src/crypto/mac/uhash/builtin/uhash_builtin.c
new file mode 100644
index 0000000..07ee749
--- /dev/null
+++ b/src/crypto/mac/uhash/builtin/uhash_builtin.c
@@ -0,0 +1,305 @@
+/*
+  Copyright (c) 2012-2014, Matthias Schiffer <mschiffer@universe-factory.net>
+  All rights reserved.
+
+  Redistribution and use in source and binary forms, with or without
+  modification, are permitted provided that the following conditions are met:
+
+    1. Redistributions of source code must retain the above copyright notice,
+       this list of conditions and the following disclaimer.
+    2. Redistributions in binary form must reproduce the above copyright notice,
+       this list of conditions and the following disclaimer in the documentation
+       and/or other materials provided with the distribution.
+
+  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+  FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+  OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+/**
+   \file
+
+   Builtin UHASH implementation
+*/
+
+
+#include "../../../../crypto.h"
+#include "../../../../alloc.h"
+#include "../../../../util.h"
+#include "../../../../log.h"
+
+#include <endian.h>
+
+
+/** MAC state used by this UHASH implmentation */
+struct fastd_mac_state {
+	uint32_t L1Key[256+3*4];	/**< The keys used by the L1-HASH */
+	uint64_t L2Key[12];		/**< The keys used by the L2-HASH */
+	uint64_t L3Key1[32];		/**< The first keys used by the L3-HASH */
+	uint32_t L3Key2[4];		/**< The second keys used by the L3-HASH */
+};
+
+
+/** An unsigned 64bit integer, split into two 32bit parts */
+typedef struct uint32_2 {
+	uint32_t h;			/**< The high half */
+	uint32_t l;			/**< The low half */
+} uint32_2_t;
+
+/** An unsigned 128bit integer, split into two 64bit parts */
+typedef struct uint64_2 {
+	uint64_t h;			/**< The high half */
+	uint64_t l;			/**< The low half */
+} uint64_2_t;
+
+/** Four unsigned 64bit integers */
+typedef struct uint64_4 {
+	uint64_t v[4];			/**< The values */
+} uint64_4_t;
+
+
+/** Splits a 64bit interger into its 32bit halves */
+static inline uint32_2_t split64(uint64_t x) {
+	return (uint32_2_t){.h = x >> 32, .l = x};
+}
+
+/** Joins two 32bit halves into a 64bit integer */
+static inline uint64_t join64(uint32_t h, uint32_t l) {
+	return ((uint64_t)h << 32) | l;
+}
+
+/** Multiplies two 32bit integers to a 64bit value */
+static inline uint64_t mul64(uint32_t a, uint32_t b) {
+	return (uint64_t)a * b;
+}
+
+/** Returns \a a if s is 0 and \a b if s is 1 in a manner safe against timing side channels */
+static inline uint64_t sel(uint64_t a, uint64_t b, unsigned int s) {
+	uint64_t s1 = (uint64_t)s - 1;
+
+	return b ^ (s1 & (a ^ b));
+}
+
+/** Reduces a 64bit integer by a modulus of \f$ p_{36} = 2^{36}-5 \f$ */
+static inline uint64_t mod_p36(uint64_t a) {
+	const uint64_t mask = 0x0000000fffffffffull;
+
+	uint64_t a1 = (a & mask) + 5 * (a >> 36);
+	uint64_t a2 = a1 + 5;
+
+	return sel(a1, a2 & mask, a2 >> 36);
+}
+
+
+/** Initializes the MAC state with the unpacked key data */
+static fastd_mac_state_t * uhash_init(const uint8_t *key) {
+	fastd_mac_state_t *state = fastd_new(fastd_mac_state_t);
+
+	const uint32_t *key32 = (const uint32_t *)key;
+	size_t i;
+
+	for (i = 0; i < array_size(state->L1Key); i++)
+		state->L1Key[i] = be32toh(*(key32++));
+
+	for (i = 0; i < array_size(state->L2Key); i++) {
+		uint32_t h = be32toh(*(key32++)) & 0x01ffffff;
+		uint32_t l = be32toh(*(key32++)) & 0x01ffffff;
+		state->L2Key[i] = join64(h, l);
+	}
+
+	for (i = 0; i < array_size(state->L3Key1); i++) {
+		uint32_t h = be32toh(*(key32++));
+		uint32_t l = be32toh(*(key32++));
+		state->L3Key1[i] = mod_p36(join64(h, l));
+	}
+
+	for (i = 0; i < array_size(state->L3Key2); i++)
+		state->L3Key2[i] = be32toh(*(key32++));
+
+	return state;
+}
+
+
+/**
+   The UHASH NH function
+
+   The four iterations are interleaved to improve cache locality.
+*/
+static uint64_4_t nh(const uint32_t *K, const uint32_t *M, size_t length) {
+	uint64_4_t Y = {{8 * length, 8 * length, 8 * length, 8 * length}};
+
+	size_t i, j;
+	for (i = 0; i < max_size_t(block_count(length, 4), 1); i += 8) {
+		uint32_t b[8];
+
+		for (j = 0; j < 8; j++)
+			b[j] = le32toh(M[i+j]);
+
+		for (j = 0; j < 4; j++) {
+			Y.v[j] += mul64(b[0] + K[i+4*j+0], b[4] + K[i+4*j+4]);
+			Y.v[j] += mul64(b[1] + K[i+4*j+1], b[5] + K[i+4*j+5]);
+			Y.v[j] += mul64(b[2] + K[i+4*j+2], b[6] + K[i+4*j+6]);
+			Y.v[j] += mul64(b[3] + K[i+4*j+3], b[7] + K[i+4*j+7]);
+		}
+	}
+
+	return Y;
+}
+
+/**
+   The L1-HASH function (with all four iterations interleaved)
+
+   The message must be padded with zeros to a positive multiple of 32 bytes.
+*/
+static void l1hash(uint64_4_t *Y, const uint32_t *K, const fastd_block128_t *message, size_t length) {
+	size_t blocks = max_size_t(block_count(length, 1024), 1), i;
+
+	for (i = 0; i < blocks; i++) {
+		size_t blocklen = min_size_t(length, 1024);
+		Y[i] = nh(K, (message+64*i)->dw, blocklen);
+		length -= 1024;
+	}
+}
+
+/**
+   Multiplies two 64bit integers to a 128bit value
+
+   This optimized implementation will only work correctly if none of the 64bit
+   intermediate values overflow. This is given by the limited space of the L2 keys.
+*/
+static inline uint64_2_t mul128(uint32_2_t a, uint32_2_t b) {
+	uint32_2_t lo = split64(mul64(a.l, b.l));
+	uint32_2_t mid = split64(mul64(a.l, b.h) + mul64(a.h, b.l) + lo.h);
+	uint64_t hi = mul64(a.h, b.h) + mid.h;
+
+	return (uint64_2_t) {
+		.h = hi,
+		.l = join64(mid.l, lo.l),
+	};
+}
+
+/**
+   Adds two 64bit intergers modulo \f$ p_{64} = 2^{64}-59 \f$
+
+   \a a must be smaller than \f$ p_{64} \f$.
+*/
+static inline uint64_t add_p64(uint64_t a, uint64_t b) {
+	uint64_t c1 = a + b;
+	a += 59;
+	uint64_t c2 = a + b;
+
+	unsigned int s = ((a & b) | ((a | b) & ~c2)) >> 63;
+
+	return sel(c1, c2, s);
+}
+
+/**
+   Multiplies two 64bit intergers modulo \f$ p_{64} = 2^{64}-59 \f$
+
+   This function is optimized for the limited L2 key space, it won't work
+   correctly with greater numbers.
+*/
+static inline uint64_t mul_p64(uint64_t a, uint64_t b) {
+	uint64_2_t m = mul128(split64(a), split64(b));
+
+	return add_p64(m.h * 59, m.l);
+}
+
+/** One L2-HASH multiply-add step */
+static inline uint64_t l2add(uint64_t Y, uint64_t K, uint64_t m) {
+	const uint64_t marker = 0xffffffffffffffc4ull;
+
+	uint64_t Y1, Y2;
+
+	Y = mul_p64(Y, K);
+
+	Y1 = add_p64(Y, marker);
+	Y1 = mul_p64(Y1, K);
+	Y1 = add_p64(Y1, m - 59);
+
+	Y2 = add_p64(Y, m);
+
+	unsigned int s = ((m >> 32) + 1) >> 32;
+	return sel(Y2, Y1, s);
+}
+
+/**
+   The L2-HASH function (with all four iterations interleaved)
+
+   Handling for block counts greater than \f$ 2^{14} \f$, i.e. messages with more
+   than \f$ 2^{24} \f$ bytes, is not implemented.
+*/
+static uint64_4_t l2hash(const uint64_t *K, const uint64_4_t *M, size_t count) {
+	if (count > 0x4000)
+		exit_bug("uhash (builtin): l2hash: message too long");
+
+	uint64_4_t y = {{1, 1, 1, 1}};
+
+	size_t i, j;
+	for (i = 0; i < count; i++) {
+		for (j = 0; j < 4; j++)
+			y.v[j] = l2add(y.v[j], K[3*j], M[i].v[j]);
+	}
+
+	return y;
+}
+
+/** The L3-HASH function */
+static uint32_t l3hash(const uint64_t *K1, uint32_t K2, uint64_t M) {
+	uint64_t y = 0;
+
+	size_t i;
+	for (i = 4; i < 8; i++) {
+		uint16_t m = M >> (16 * (3 - i%4));
+		y += m * K1[i];
+	}
+
+	return mod_p36(y) ^ K2;
+}
+
+/** Calculates the UHASH of the supplied blocks */
+static bool uhash_digest(const fastd_mac_state_t *state, fastd_block128_t *out, const fastd_block128_t *in, size_t length) {
+	size_t blocks = max_size_t(block_count(length, 1024), 1);
+	size_t i;
+
+	uint64_4_t A[blocks];
+	l1hash(A, state->L1Key, in, length);
+
+	uint64_4_t B;
+	if (blocks <= 1)
+		B = A[0];
+	else
+		B = l2hash(state->L2Key, A, blocks);
+
+	for (i = 0; i < 4; i++) {
+		const uint64_t *L3Key1 = state->L3Key1 + 8*i;
+		uint32_t L3Key2 = state->L3Key2[i];
+
+		uint32_t c = l3hash(L3Key1, L3Key2, B.v[i]);
+		out->dw[i] = htobe32(c);
+	}
+
+	return true;
+}
+
+/** Frees the MAC state */
+static void uhash_free(fastd_mac_state_t *state) {
+	if (state) {
+		secure_memzero(state, sizeof(*state));
+		free(state);
+	}
+}
+
+/** The builtin UHASH implementation */
+const fastd_mac_t fastd_mac_uhash_builtin = {
+	.init = uhash_init,
+	.digest = uhash_digest,
+	.free = uhash_free,
+};
diff --git a/src/crypto/mac/uhash/uhash.c b/src/crypto/mac/uhash/uhash.c
new file mode 100644
index 0000000..2cc89e0
--- /dev/null
+++ b/src/crypto/mac/uhash/uhash.c
@@ -0,0 +1,41 @@
+/*
+  Copyright (c) 2012-2014, Matthias Schiffer <mschiffer@universe-factory.net>
+  All rights reserved.
+
+  Redistribution and use in source and binary forms, with or without
+  modification, are permitted provided that the following conditions are met:
+
+    1. Redistributions of source code must retain the above copyright notice,
+       this list of conditions and the following disclaimer.
+    2. Redistributions in binary form must reproduce the above copyright notice,
+       this list of conditions and the following disclaimer in the documentation
+       and/or other materials provided with the distribution.
+
+  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+  FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+  OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+/**
+   \file
+
+   General information about the UHASH algorithm
+
+   \sa http://en.wikipedia.org/wiki/UMAC
+   \sa https://tools.ietf.org/html/rfc4418
+*/
+
+#include "../../../crypto.h"
+
+
+/** MAC info about the UHASH algorithm */
+const fastd_mac_info_t fastd_mac_info_uhash = {
+	.key_length = 1024+3*16 + 4*24 + 4*64 + 4*4, /* we use 4 iterations */
+};
diff --git a/src/fastd.h b/src/fastd.h
index f1825ea..acdc572 100644
--- a/src/fastd.h
+++ b/src/fastd.h
@@ -430,28 +430,3 @@ static inline bool fastd_allow_verify(void) {
 	return false;
 #endif
 }
-
-/**
-   Checks if two strings are equal
-
-   @param str1 The first string (may be NULL)
-   @param str2 The second string (may be NULL)
-
-   @return True if both strings are NULL or both strings are not NULL and equal
-*/
-static inline bool strequal(const char *str1, const char *str2) {
-	if (str1 && str2)
-		return (!strcmp(str1, str2));
-	else
-		return (str1 == str2);
-}
-
-/** Returns the maximum of two size_t values */
-static inline size_t max_size_t(size_t a, size_t b) {
-	return (a > b) ? a : b;
-}
-
-/** Returns the minimum of two size_t values */
-static inline size_t min_size_t(size_t a, size_t b) {
-	return (a < b) ? a : b;
-}
diff --git a/src/types.h b/src/types.h
index 352e7be..d0a0221 100644
--- a/src/types.h
+++ b/src/types.h
@@ -119,6 +119,7 @@ typedef struct fastd_shell_env fastd_shell_env_t;
 /** A 128-bit aligned block of data, primarily used by the cryptographic functions */
 typedef union fastd_block128 {
 	uint8_t b[16];		/**< Byte-wise access to the data */
+	uint32_t dw[4];		/**< Doubleword-wise access to the data */
 	uint64_t qw[2];		/**< Quadword-wise access to the data */
 } __attribute__((aligned(16))) fastd_block128_t;
 
diff --git a/src/util.h b/src/util.h
index e36f028..fe6720b 100644
--- a/src/util.h
+++ b/src/util.h
@@ -66,3 +66,28 @@ static inline size_t block_count(size_t l, size_t a) {
 static inline size_t alignto(size_t l, size_t a) {
 	return block_count(l, a)*a;
 }
+
+/**
+   Checks if two strings are equal
+
+   @param str1 The first string (may be NULL)
+   @param str2 The second string (may be NULL)
+
+   @return True if both strings are NULL or both strings are not NULL and equal
+*/
+static inline bool strequal(const char *str1, const char *str2) {
+	if (str1 && str2)
+		return (!strcmp(str1, str2));
+	else
+		return (str1 == str2);
+}
+
+/** Returns the maximum of two size_t values */
+static inline size_t max_size_t(size_t a, size_t b) {
+	return (a > b) ? a : b;
+}
+
+/** Returns the minimum of two size_t values */
+static inline size_t min_size_t(size_t a, size_t b) {
+	return (a < b) ? a : b;
+}