[Feature] Add catena PBKDF function

6 files changed, 544 insertions, 1 deletions

diff --git a/src/libcryptobox/CMakeLists.txt b/src/libcryptobox/CMakeLists.txt
index 8318f3ed9..89b42b726 100644
--- a/src/libcryptobox/CMakeLists.txt
+++ b/src/libcryptobox/CMakeLists.txt
@@ -88,7 +88,8 @@ CONFIGURE_FILE(platform_config.h.in platform_config.h)
 INCLUDE_DIRECTORIES("${CMAKE_CURRENT_BINARY_DIR}")
 SET(LIBCRYPTOBOXSRC	${CMAKE_CURRENT_SOURCE_DIR}/cryptobox.c
 					${CMAKE_CURRENT_SOURCE_DIR}/keypair.c
-					${CMAKE_CURRENT_SOURCE_DIR}/keypairs_cache.c)
+					${CMAKE_CURRENT_SOURCE_DIR}/keypairs_cache.c
+					${CMAKE_CURRENT_SOURCE_DIR}/catena/catena.c)
 
 SET(RSPAMD_CRYPTOBOX ${LIBCRYPTOBOXSRC} ${CHACHASRC} ${POLYSRC} ${SIPHASHSRC}
 	${CURVESRC} ${BLAKE2SRC} ${EDSRC} PARENT_SCOPE)
diff --git a/src/libcryptobox/catena/LICENSE b/src/libcryptobox/catena/LICENSE
new file mode 100644
index 000000000..ff22dc8a0
--- /dev/null
+++ b/src/libcryptobox/catena/LICENSE
@@ -0,0 +1,20 @@
+The MIT License (MIT)
+
+Copyright (c) 2014 cforler
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of
+this software and associated documentation files (the "Software"), to deal in
+the Software without restriction, including without limitation the rights to
+use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
+the Software, and to permit persons to whom the Software is furnished to do so,
+subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
+FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
+COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
+IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
diff --git a/src/libcryptobox/catena/README.md b/src/libcryptobox/catena/README.md
new file mode 100644
index 000000000..4a0f948bd
--- /dev/null
+++ b/src/libcryptobox/catena/README.md
@@ -0,0 +1,18 @@
+Catena
+======
+Catena is a memory-consuming password scrambler that excellently
+thwarts massively parallel attacks on cheap memory-constrained
+hardware, such as recent graphical processing units (GPUs).
+Furthermore, Catena provides resistance against cache-timing attacks, since
+its memory-access pattern is password-independent.
+
+Academic paper:
+<a href="http://www.uni-weimar.de/fileadmin/user/fak/medien/professuren/Mediensicherheit/Research/Publications/catena-v3.1.pdf">catena-v3.1.pdf</a>
+
+Rspamd specific
+---------------
+
+Rspamd implements Catena-Butterfly using full blake2b hash implemented in the
+cryptobox.
+
+Original code: https://github.com/medsec/catena
\ No newline at end of file
diff --git a/src/libcryptobox/catena/catena.c b/src/libcryptobox/catena/catena.c
new file mode 100644
index 000000000..c7f21637f
--- /dev/null
+++ b/src/libcryptobox/catena/catena.c
@@ -0,0 +1,448 @@
+/*-
+ * Copyright 2016 Vsevolod Stakhov
+ * Copyright (c) 2014 cforler
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy of
+ * this software and associated documentation files (the "Software"), to deal in
+ * the Software without restriction, including without limitation the rights to
+ * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
+ * the Software, and to permit persons to whom the Software is furnished to do so,
+ * subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in all
+ * copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
+ * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
+ * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
+ * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+#include "config.h"
+#include "catena.h"
+#include "../blake2/blake2.h"
+
+#if __BYTE_ORDER == __LITTLE_ENDIAN
+#define TO_LITTLE_ENDIAN_64(n) (n)
+#define TO_LITTLE_ENDIAN_32(n) (n)
+#else
+#define TO_LITTLE_ENDIAN_64 GUINT64_SWAP_LE_BE
+#define TO_LITTLE_ENDIAN_32 GUINT32_SWAP_LE_BE
+#endif
+
+/* Recommended default values */
+#define H_LEN      CATENA_HLEN
+#define KEY_LEN    16
+
+const uint8_t VERSION_ID[] = "Butterfly-Full";
+const uint8_t LAMBDA = 4;
+const uint8_t GARLIC = 16;
+const uint8_t MIN_GARLIC = 16;
+
+/*
+ * Hash part
+ */
+
+static inline void
+__Hash1(const uint8_t *input, const uint32_t inputlen,
+		uint8_t hash[H_LEN])
+{
+	blake2b_state ctx;
+	blake2b_init (&ctx);
+	blake2b_update (&ctx, input, inputlen);
+	blake2b_final (&ctx, hash);
+}
+
+/***************************************************/
+
+static inline
+void __Hash2(const uint8_t *i1, const uint8_t i1len, const uint8_t *i2,
+		const uint8_t i2len, uint8_t hash[H_LEN])
+{
+	blake2b_state ctx;
+	blake2b_init (&ctx);
+	blake2b_update (&ctx, i1, i1len);
+	blake2b_update (&ctx, i2, i2len);
+	blake2b_final (&ctx, hash);
+}
+
+/***************************************************/
+
+static inline
+void __Hash3(const uint8_t *i1, const uint8_t i1len, const uint8_t *i2,
+		const uint8_t i2len, const uint8_t *i3, const uint8_t i3len,
+		uint8_t hash[H_LEN])
+{
+	blake2b_state ctx;
+	blake2b_init (&ctx);
+	blake2b_update (&ctx, i1, i1len);
+	blake2b_update (&ctx, i2, i2len);
+	blake2b_update (&ctx, i3, i3len);
+	blake2b_final (&ctx, hash);
+}
+
+/***************************************************/
+
+static inline
+void __Hash4(const uint8_t *i1, const uint8_t i1len, const uint8_t *i2,
+		const uint8_t i2len, const uint8_t *i3, const uint8_t i3len,
+		const uint8_t *i4, const uint8_t i4len, uint8_t hash[H_LEN])
+{
+	blake2b_state ctx;
+	blake2b_init (&ctx);
+	blake2b_update (&ctx, i1, i1len);
+	blake2b_update (&ctx, i2, i2len);
+	blake2b_update (&ctx, i3, i3len);
+	blake2b_update (&ctx, i4, i4len);
+	blake2b_final (&ctx, hash);
+}
+
+/***************************************************/
+
+static inline
+void __Hash5(const uint8_t *i1, const uint8_t i1len, const uint8_t *i2,
+		const uint8_t i2len, const uint8_t *i3, const uint8_t i3len,
+		const uint8_t *i4, const uint8_t i4len, const uint8_t *i5,
+		const uint8_t i5len, uint8_t hash[H_LEN])
+{
+	blake2b_state ctx;
+	blake2b_init (&ctx);
+	blake2b_update (&ctx, i1, i1len);
+	blake2b_update (&ctx, i2, i2len);
+	blake2b_update (&ctx, i3, i3len);
+	blake2b_update (&ctx, i4, i4len);
+	blake2b_update (&ctx, i5, i5len);
+	blake2b_final (&ctx, hash);
+}
+
+static inline void
+__HashFast(int vindex, const uint8_t* i1, const uint8_t* i2,
+		uint8_t hash[H_LEN])
+{
+	__Hash2 (i1, H_LEN, i2, H_LEN, hash);
+}
+
+static void __ResetState(void)
+{
+}
+
+/*
+ * Misc utils
+ */
+const uint8_t ZERO8[H_LEN] = {0};
+
+/* see: http://en.wikipedia.org/wiki/Xorshift#Variations */
+static int p;
+static uint64_t s[16];
+
+static void
+initXSState (const uint8_t* a, const uint8_t* b)
+{
+	p = 0;
+
+	for (int i = 0; i < 8; i++) {
+		s[i] = UINT64_C(0);
+		s[i + 8] = UINT64_C(0);
+
+		for (int j = 0; j < 8; j++) {
+			s[i] |= ((uint64_t) a[i * 8 + j]) << j * 8;
+			s[i + 8] |= ((uint64_t) b[i * 8 + j]) << j * 8;
+		}
+	}
+}
+
+static uint64_t
+xorshift1024star (void)
+{
+	uint64_t s0 = s[p];
+	uint64_t s1 = s[p = (p + 1) & 15];
+	s1 ^= s1 << 31;
+	s1 ^= s1 >> 11;
+	s0 ^= s0 >> 30;
+	return (s[p] = s0 ^ s1) * UINT64_C(1181783497276652981);
+}
+
+static void
+H_INIT (const uint8_t* x, const uint16_t xlen, uint8_t *vm1, uint8_t *vm2)
+{
+	const uint8_t l = 2;
+	uint8_t *tmp = (uint8_t*) g_malloc (l * H_LEN);
+
+	for (uint8_t i = 0; i != l; ++i) {
+		__Hash2 (&i, 1, x, xlen, tmp + i * H_LEN);
+	}
+
+	memcpy (vm1, tmp, H_LEN);
+	memcpy (vm2, tmp+(l/2*H_LEN), H_LEN);
+	g_free (tmp);
+}
+
+static void
+H_First (const uint8_t* i1, const uint8_t* i2, uint8_t* hash)
+{
+	uint8_t i = 0;
+	uint8_t *x = (uint8_t*) g_malloc (H_LEN);
+
+	__ResetState ();
+	__Hash2 (i1, H_LEN, i2, H_LEN, x);
+	__Hash2 (&i, 1, x, H_LEN, hash);
+	g_free (x);
+}
+
+static inline void
+initmem (const uint8_t x[H_LEN], const uint64_t c, uint8_t *r)
+{
+	uint8_t *vm2 = (uint8_t*) g_malloc (H_LEN);
+	uint8_t *vm1 = (uint8_t*) g_malloc (H_LEN);
+
+	H_INIT (x, H_LEN, vm1, vm2);
+	__ResetState ();
+	__HashFast (0, vm1, vm2, r);
+	__HashFast (1, r, vm1, r + H_LEN);
+
+	/* Top row */
+	for (uint64_t i = 2; i < c; i++) {
+		__HashFast (i, r + (i - 1) * H_LEN, r + (i - 2) * H_LEN, r + i * H_LEN);
+	}
+
+	g_free (vm2);
+	g_free (vm1);
+}
+
+static inline void
+gamma (const uint8_t garlic, const uint8_t *salt,
+		const uint8_t saltlen, uint8_t *r)
+{
+	const uint64_t q = UINT64_C(1) << ((3 * garlic + 3) / 4);
+
+	uint64_t i, j, j2;
+	uint8_t *tmp = g_malloc (H_LEN);
+	uint8_t *tmp2 = g_malloc (H_LEN);
+
+	__Hash1 (salt, saltlen, tmp);
+	__Hash1 (tmp, H_LEN, tmp2);
+	initXSState (tmp, tmp2);
+
+	__ResetState ();
+	for (i = 0; i < q; i++) {
+		j = xorshift1024star () >> (64 - garlic);
+		j2 = xorshift1024star () >> (64 - garlic);
+		__HashFast (i, r + j * H_LEN, r + j2 * H_LEN, r + j * H_LEN);
+	}
+
+	g_free (tmp);
+	g_free (tmp2);
+}
+
+static void
+XOR (const uint8_t *input1, const uint8_t *input2, uint8_t *output)
+{
+	uint32_t i;
+
+	for(i = 0; i < H_LEN; i++) {
+		output[i] = input1[i] ^ input2[i];
+	}
+}
+
+/*
+ * Butterfly part
+ */
+/*
+ * Sigma function that defines the diagonal connections of a DBG
+ * diagonal front: flip the (g-i)th bit (Inverse Buttferly Graph)
+ * diagonal back: flip the i-(g-1)th bit (Regular Butterfly Graph)
+ */
+static uint64_t
+sigma(const uint8_t g, const uint64_t i, const uint64_t j)
+{
+	if (i < g) {
+		return (j ^ (UINT64_C(1) << (g - 1 - i))); /* diagonal front */
+	}
+	else {
+		return (j ^ (UINT64_C(1) << (i - (g - 1)))); /* diagonal back */
+	}
+}
+
+/*calculate actual index from level and element index*/
+static uint64_t
+idx(uint64_t i, uint64_t j, uint8_t co, uint64_t c, uint64_t m)
+{
+	i += co;
+	if (i % 3 == 0) {
+		return j;
+	}
+	else if (i % 3 == 1) {
+		if (j < m) {
+			/* still fits in the array */
+			return j + c;
+		}
+		else {
+			/* start overwriting elements at the beginning */
+			return j - m;
+		}
+	}
+	/* i % 3 == 2 */
+	return j + m;
+}
+
+/*
+ * Computes the hash of x using a Double Butterfly Graph,
+ * that forms as (2^g,\lamba)-Superconcentrator
+ */
+static void
+Flap (const uint8_t x[H_LEN], const uint8_t lambda, const uint8_t garlic,
+		const uint8_t *salt, const uint8_t saltlen, uint8_t h[H_LEN])
+{
+	const uint64_t c = UINT64_C(1) << garlic;
+	const uint64_t m = UINT64_C(1) << (garlic - 1);    /* 0.5 * 2^g */
+	const uint32_t l = 2 * garlic;
+
+	uint8_t *r = g_malloc ((c + m) * H_LEN);
+	uint8_t *tmp = g_malloc (H_LEN);
+	uint64_t i, j;
+	uint8_t k;
+	uint8_t co = 0;    /* carry over from last iteration */
+
+	/* Top row */
+	initmem (x, c, r);
+
+	/*Gamma Function*/
+	gamma (garlic, salt, saltlen, r);
+
+	/* DBH */
+	for (k = 0; k < lambda; k++) {
+		for (i = 1; i < l; i++) {
+			XOR (r + idx (i - 1, c - 1, co, c, m) * H_LEN,
+					r + idx (i - 1, 0, co, c, m) * H_LEN, tmp);
+
+			/*
+			 * r0 := H(tmp || vsigma(g,i-1,0) )
+			 * __Hash2(tmp, H_LEN, r+idx(i-1,sigma(garlic,i-1,0),co,c,m) * H_LEN, H_LEN,
+			 * r+idx(i,0,co,c,m) *H_LEN);
+			 */
+			H_First (tmp,
+					r + idx (i - 1, sigma (garlic, i - 1, 0), co, c, m) * H_LEN,
+					r + idx (i, 0, co, c, m) * H_LEN);
+			__ResetState ();
+
+			/* vertices */
+			for (j = 1; j < c; j++) {
+				/* tmp:= rj-1 XOR vj */
+				XOR (r + idx (i, j - 1, co, c, m) * H_LEN,
+						r + idx (i - 1, j, co, c, m) * H_LEN, tmp);
+				/* rj := H(tmp || vsigma(g,i-1,j)) */
+				__HashFast (j, tmp,
+						r + idx (i - 1, sigma (garlic, i - 1, j), co, c, m) * H_LEN,
+						r + idx (i, j, co, c, m) * H_LEN);
+			}
+		}
+		co = (co + (i - 1)) % 3;
+	}
+
+	memcpy(h, r + idx(0,c-1,co,c,m) * H_LEN, H_LEN);
+	g_free (r);
+	g_free (tmp);
+}
+
+static int __Catena(const uint8_t *pwd, const uint32_t pwdlen,
+		const uint8_t *salt, const uint8_t saltlen, const uint8_t *data,
+		const uint32_t datalen, const uint8_t lambda, const uint8_t min_garlic,
+		const uint8_t garlic, const uint8_t hashlen, const uint8_t client,
+		const uint8_t tweak_id, uint8_t *hash)
+{
+	uint8_t x[H_LEN];
+	uint8_t hv[H_LEN];
+	uint8_t t[4];
+	uint8_t c;
+
+	if ((hashlen > H_LEN) || (garlic > 63) || (min_garlic > garlic)
+			|| (lambda == 0) || (min_garlic == 0)) {
+		return -1;
+	}
+
+	/*Compute H(V)*/
+	__Hash1 (VERSION_ID, strlen ((char*) VERSION_ID), hv);
+
+	/* Compute Tweak */
+	t[0] = tweak_id;
+	t[1] = lambda;
+	t[2] = hashlen;
+	t[3] = saltlen;
+
+	/* Compute H(AD) */
+	__Hash1 ((uint8_t *) data, datalen, x);
+
+	/* Compute the initial value to hash  */
+	__Hash5 (hv, H_LEN, t, 4, x, H_LEN, pwd, pwdlen, salt, saltlen, x);
+
+	/*Overwrite Password if enabled*/
+#ifdef OVERWRITE
+	erasepwd(pwd,pwdlen);
+#endif
+
+	Flap (x, lambda, (min_garlic + 1) / 2, salt, saltlen, x);
+
+	for (c = min_garlic; c <= garlic; c++) {
+		Flap (x, lambda, c, salt, saltlen, x);
+		if ((c == garlic) && (client == CLIENT)) {
+			memcpy (hash, x, H_LEN);
+			return 0;
+		}
+		__Hash2 (&c, 1, x, H_LEN, x);
+		memset (x + hashlen, 0, H_LEN - hashlen);
+	}
+
+	memcpy (hash, x, hashlen);
+
+	return 0;
+}
+
+/***************************************************/
+
+int
+catena (uint8_t *pwd, const uint32_t pwdlen, const uint8_t *salt,
+		const uint8_t saltlen, const uint8_t *data, const uint32_t datalen,
+		const uint8_t lambda, const uint8_t min_garlic, const uint8_t garlic,
+		const uint8_t hashlen, uint8_t *hash)
+{
+	return __Catena (pwd, pwdlen, salt, saltlen, data, datalen, lambda,
+			min_garlic, garlic, hashlen, REGULAR, PASSWORD_HASHING_MODE, hash);
+
+}
+
+int
+simple_catena (uint8_t *pwd,   const uint32_t pwdlen,
+		  const uint8_t *salt,  const uint8_t  saltlen,
+		  const uint8_t *data,  const uint32_t datalen,
+		  uint8_t hash[H_LEN])
+{
+  return __Catena(pwd, pwdlen, salt, saltlen, data, datalen,
+		  LAMBDA, MIN_GARLIC, GARLIC, H_LEN,
+		  REGULAR, PASSWORD_HASHING_MODE, hash);
+}
+
+int
+catena_test (void)
+{
+	/* From catena-v3.1 spec */
+	guint8 pw[] = {0x70, 0x61, 0x73, 0x73, 0x77, 0x6f, 0x72, 0x64};
+	guint8 salt[] = {0x73, 0x61, 0x6c, 0x74};
+	guint8 ad[] = {0x64, 0x61,0x74, 0x61};
+	guint8 expected[] = {
+		0x20, 0xc5, 0x91, 0x93, 0x8f, 0xc3, 0xaf, 0xcc, 0x3b, 0xba, 0x91, 0xd2, 0xfb,
+		0x84, 0xbf, 0x7b, 0x44, 0x04, 0xf9, 0x4c, 0x45, 0xed, 0x4d, 0x11, 0xa7, 0xe2,
+		0xb4, 0x12, 0x3e, 0xab, 0x0b, 0x77, 0x4a, 0x12, 0xb4, 0x22, 0xd0, 0xda, 0xb5,
+		0x25, 0x29, 0x02, 0xfc, 0x54, 0x47, 0xea, 0x82, 0x63, 0x8c, 0x1a, 0xfb, 0xa7,
+		0xa9, 0x94, 0x24, 0x13, 0x0e, 0x44, 0x36, 0x3b, 0x9d, 0x9f, 0xc9, 0x60
+	};
+	guint8 real[H_LEN];
+
+	if (catena (pw, sizeof (pw), salt, sizeof (salt), ad, sizeof (ad),
+			4, 10, 10, H_LEN, real) != 0) {
+		return -1;
+	}
+
+	return memcmp (real, expected, H_LEN);
+}
diff --git a/src/libcryptobox/catena/catena.h b/src/libcryptobox/catena/catena.h
new file mode 100644
index 000000000..6624a54ec
--- /dev/null
+++ b/src/libcryptobox/catena/catena.h
@@ -0,0 +1,55 @@
+/*-
+ * Copyright 2016 Vsevolod Stakhov
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#ifndef SRC_LIBCRYPTOBOX_CATENA_CATENA_H_
+#define SRC_LIBCRYPTOBOX_CATENA_CATENA_H_
+
+/* Modes  */
+#define PASSWORD_HASHING_MODE 0
+#define KEY_DERIVATION_MODE   1
+#define REGULAR 0
+#define CLIENT 1
+
+#define CATENA_HLEN 64
+
+int
+catena (uint8_t *pwd,   const uint32_t pwdlen,
+	   const uint8_t *salt,  const uint8_t  saltlen,
+	   const uint8_t *data,  const uint32_t datalen,
+	   const uint8_t lambda, const uint8_t  min_garlic,
+	   const uint8_t garlic, const uint8_t hashlen,  uint8_t *hash);
+
+/**
+ * Simple interface for catena PBKDF
+ * @param pwd password
+ * @param pwdlen length of password
+ * @param salt salt
+ * @param saltlen length of salt
+ * @param data additional data
+ * @param datalen length of additional data
+ * @param hash output hash
+ * @return 0 if hash is generated, -1 in case of error
+ */
+int simple_catena(uint8_t *pwd, const uint32_t pwdlen,
+		   const uint8_t *salt, const uint8_t  saltlen,
+		   const uint8_t *data, const uint32_t datalen,
+		   uint8_t hash[CATENA_HLEN]);
+
+/**
+ * Run a quick test on catena implementation
+ */
+int catena_test (void);
+
+#endif /* SRC_LIBCRYPTOBOX_CATENA_CATENA_H_ */
diff --git a/src/libcryptobox/cryptobox.c b/src/libcryptobox/cryptobox.c
index 88da5b35f..22860695a 100644
--- a/src/libcryptobox/cryptobox.c
+++ b/src/libcryptobox/cryptobox.c
@@ -28,6 +28,7 @@
 #include "ed25519/ed25519.h"
 #include "blake2/blake2.h"
 #include "siphash/siphash.h"
+#include "catena/catena.h"
 #include "ottery.h"
 #include "printf.h"