[PATCH resend][CRYPTO]: RSA algorithm patch

[PATCH resend][CRYPTO]: RSA algorithm patch

[Tasos Parisinos]

From: Tasos Parisinos <t.parisinos@sciensis.com>

This patch adds module rsa.ko in the kernel (built-in or as a kernel module) 
and offers an API to do fast modular exponentiation, using the Montgomery 
algorithm, thus the exponentiation is not generic but can be used only when
the modulus is odd, such as RSA public/private key pairs. This module is the
computational core (using multiple precision integer arithmetics) and does not
provide any means to do key management, implement padding schemas e.t.c. so the
calling code should implement all those as needed. 

Signed-off-by: Tasos Parisinos <t.parisinos@sciensis.com>

---
This module exports some symbols, through its header file include/crypto/rsa.h 
and does not use the glue code of include/crypto.h. This decision was taken 
because this glue code is not really suitable for asymmetric cryptography in my
opinion. First of all RSA is not a block cipher but a stream cipher. It does not
only have a key but also an exponent that are two different entities. And the most
important is that the key size can be of any length. So it is not practical -yet- 
to register the algorithm with the crypto api using a struct such as crypto_alg. 
So another module can include the file include/crypto/rsa.h and call its interface 
functions to create the operands for the modular exponentiation, execute the 
exponentiation and use the results. All these functions and structures are 
well documented kernel-doc style. Also in this way the calling in-kernel code can
implement key management, padding schemas, hashing e.t.c as needed. 

diff -uprN -X linux/Documentation/dontdiff \
linux.orig/crypto/Kconfig linux/crypto/Kconfig
--- linux.orig/crypto/Kconfig 2007-03-26 01:56:23.000000000 +0300
+++ linux/crypto/Kconfig 2007-04-02 11:17:24.000000000 +0300
@@ -440,6 +440,31 @@ config CRYPTO_CAMELLIA
 	  See also:
 	  <https://info.isl.ntt.co.jp/crypt/eng/camellia/index_s.html>

+config CRYPTO_RSA
+	tristate "RSA asymmetric cipher algorithm"
+	help
+	  RSA asymmetric cipher algorithm.
+
+	  This module uses the montgomery algorithm to compute fast modular
+	  exponentiation. All operands of the modular exponentiation can be
+	  of any bit length, thus you can use any public and/or private key
+	  lengths.
+
+	  If it is selected it will add approximately 8K to the kernel size.
+	  Select M to build this as a module. The module will be called rsa.
+
+config RSA_AUX_OPERAND_SIZE
+	int "Size of the preallocated auxilliary operands"
+	default "128"
+	depends on CRYPTO_RSA
+	help
+	  The rsa module needs some preallocated space to avoid computation-time
+	  allocations. The 'rsa_op' is the struct used by the rsa module to hold
+	  a multi-precision integer operand. This struct maps such an integer on
+	  multiple 32bit limbs. Here you select the size (in 32bit limbs) of the
+	  preallocated auxilliary operands. This size should be close to the key
+	  sizes that are usually used.
+
 config CRYPTO_TEST
 	tristate "Testing module"
 	depends on m
diff -uprN -X linux/Documentation/dontdiff \
linux.orig/crypto/Makefile linux/crypto/Makefile
--- linux.orig/crypto/Makefile 2007-03-26 01:56:23.000000000 +0300
+++ linux/crypto/Makefile 2007-04-02 11:17:24.000000000 +0300
@@ -46,5 +46,6 @@ obj-$(CONFIG_CRYPTO_ANUBIS) += anubis.o
 obj-$(CONFIG_CRYPTO_DEFLATE) += deflate.o
 obj-$(CONFIG_CRYPTO_MICHAEL_MIC) += michael_mic.o
 obj-$(CONFIG_CRYPTO_CRC32C) += crc32c.o
+obj-$(CONFIG_CRYPTO_RSA) += rsa.o

 obj-$(CONFIG_CRYPTO_TEST) += tcrypt.o
diff -uprN -X linux/Documentation/dontdiff \
linux.orig/crypto/rsa.c linux/crypto/rsa.c
--- linux.orig/crypto/rsa.c 1970-01-01 02:00:00.000000000 +0200
+++ linux/crypto/rsa.c 2007-04-02 11:52:28.000000000 +0300
@@ -0,0 +1,770 @@
+/*
+ * Cryptographic API
+ *
+ * RSA cipher algorithm implementation
+ *
+ * Copyright (c) 2007 Tasos Parisinos <t.parisinos@sciensis.com>
+ * Copyright (c) 2007 Sciensis Advanced Technology Systems
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version
+ *
+ */
+
+#include <linux/module.h>
+#include <linux/errno.h>
+#include <crypto/rsa.h>
+
+#define AUX_OPERAND_COUNT	4
+#define U32_MAX		0xFFFFFFFF
+#define U32_MSB_SET		0x80000000
+#define LEFTOP			aux[0]
+#define RIGHTOP		aux[1]
+
+static int rsa_op_resize(struct rsa_op **n, int size)
+{
+	int retval = 0;
+	struct rsa_op *handle = *n;
+
+	/* If there is no allocated rsa_op passed in, allocate one */
+	if (!handle)
+		return rsa_op_alloc(n, size);
+
+	/* If the rsa_op passed in has the available limbs */
+	if (handle->limbs >= size) {
+		/* Zero the xtra limbs */
+		if (size < handle->size)
+			memset(handle->data + size, 0,
+			       (handle->size - size) * sizeof(u32));
+		handle->size = size;
+	}
+	else {
+		struct rsa_op *tmp = NULL;
+
+		retval = rsa_op_alloc(&tmp, size);
+		if (retval < 0)
+			return retval;
+
+		/* Copy the original data */
+		memcpy(tmp->data, handle->data, handle->size * sizeof(u32));
+		tmp->sign = handle->sign;
+		rsa_op_free(*n);
+		*n = tmp;
+	}
+
+	return retval;
+}
+
+/* Count the leading zeroes of an operand */
+static u32 rsa_op_clz(struct rsa_op *n)
+{
+	int i;
+	u32 limb, retval = 0;
+
+	for (i = n->size - 1; i >= 0; i--) {
+		limb = n->data[i];
+
+		if (!limb) {
+			retval += 32;
+			continue;
+		}
+
+		while (!(limb & U32_MSB_SET)) {
+			retval++;
+			limb = limb << 1;
+		}
+		break;
+	}
+
+	return retval;
+}
+
+static char rsa_op_compare(struct rsa_op *l, struct rsa_op *r)
+{
+	int i;
+	u32 *lbuf, *rbuf;
+
+	/* Compare the two operands based on sign */
+	if (l->sign != r->sign)
+		return (l->sign)? -1 : 1;
+
+	/* Compare the two operands based on their size */
+	if (l->size > r->size && rsa_op_clz(l) < (l->size - r->size) * 32)
+		return 1;
+	else if (r->size > l->size && rsa_op_clz(r) < (r->size - l->size) * 32)
+		return -1;
+
+	/* Compare the two operands based on their hex values */
+	lbuf = l->data;
+	rbuf = r->data;
+	for (i = min(l->size, r->size) - 1; i >= 0; i--)
+		if (lbuf[i] > rbuf[i])
+			return 1;
+		else if (lbuf[i] < rbuf[i])
+			return -1;
+	return 0;
+}
+
+static void rsa_op_complement(struct rsa_op *n)
+{
+	int i, s;
+	u32 *buf;
+
+	s = n->size;
+	buf = n->data;
+	for (i = 0; i < s; i++)
+		buf[i] = ~buf[i];
+
+	/* Add 1 using the addition carry */
+	for (i = 0; i < s; i++) {
+		buf[i] += 1;
+		if (buf[i])
+			break;
+	}
+}
+
+static void rsa_op_canonicalize(struct rsa_op *n)
+{
+	int i;
+	u32 *buf = n->data;
+
+	for (i = n->size - 1; i >= 0; i--)
+		if (!buf[i] && n->size > 1)
+			n->size--;
+		else
+			break;
+}
+
+static int rsa_op_shift(struct rsa_op **n, int bits)
+{
+	int i, distance, size, lz, retval;
+	u32 *buf;
+	struct rsa_op *handle;
+
+	if (!bits)
+		return 0;
+	handle = *n;
+
+	/* Shifting to the right, no resize needed */
+	if (bits > 0) {
+		/* Drop off one limb for each 32 bit shift */
+		distance = bits / 32;
+		size = handle->size;
+		buf = handle->data;
+		for (i = 0; i < size; i++)
+			buf[i] = (i + distance >= size)? 0 : buf[i + distance];
+
+		/* Shift the remaining 'bits' mod 32 */
+		bits = bits % 32;
+		if (bits) {
+			size -= distance;
+			distance = 32 - bits;
+			for (i = 0; i < size; i++) {
+				buf[i] = buf[i] >> bits;
+				if (i < size - 1)
+					buf[i] |=  buf[i + 1] << distance;
+			}
+		}
+
+		rsa_op_canonicalize(handle);
+		return 0;
+	}
+
+	bits = -bits;
+	lz = rsa_op_clz(handle) + (handle->limbs - handle->size) * 32;
+
+	/*
+	 * Shifting to the left.
+	 * Reallocation is needed when the leading zeroes are less than
+	 * the shift distance
+	 */
+	if (lz < bits) {
+		/* Compute the size of the reallocation */
+		size = (bits - lz + 31) / 32;
+		retval = rsa_op_resize(n, handle->limbs + size);
+		if (retval < 0)
+			return retval;
+		handle = *n;
+	}
+	else
+		handle->size += ((bits - rsa_op_clz(handle) + 31) / 32);
+
+	buf = handle->data;
+	distance = bits / 32;
+	/* Shift data 1 byte to the left for each 32 bit shift */
+	if (distance) {
+		/* Shift bytes */
+		for (i = handle->size - distance - 1; i >= 0; i--)
+			buf[i + distance] = buf[i];
+
+		/* Zero the shifted in bytes */
+		memset(handle->data, 0, distance * sizeof(u32));
+	}
+
+	/* Shift the remaining 'bits' mod 32 */
+	bits = bits % 32;
+	distance = 32 - bits;
+	if (bits)
+		for (i = handle->size - 1; i >= 0; i--) {
+			buf[i] = buf[i] << bits;
+			if (i > 0)
+				buf[i] |= (buf[i - 1] >> distance);
+		}
+
+	return 0;
+}
+
+/*
+ * Compute the modular inverse of an operand using only its 32 least
+ * significant bits (single presicion modular inverse)
+ */
+static u32 rsa_op_modinv32(struct rsa_op *n)
+{
+	u32 i, x, y, tmp, pow1;
+
+	pow1 = y = 1;
+	x = n->data[0];
+
+	for (i = 2; i <= 32; i++) {
+		pow1 = pow1 << 1;
+
+		/*
+		 * This is the computation of x * y mod r, only r is a power
+		 * of 2, specifically 2^i so the modulo is computed by
+		 * keeping the least i bits of x * y.
+		 */
+		tmp = ((u64)x * y) & (U32_MAX >> (32 - i));
+		if (pow1 < tmp)
+			y += pow1;
+	}
+
+	y = ~y + 1;
+	return y;
+}
+
+static int rsa_product(struct rsa_op **res, struct rsa_op *l, struct rsa_op *r,
+		       struct rsa_op **aux)
+{
+	int i, j, ls, rs, retval;
+	u32 *buf, *lbuf, *rbuf;
+	u64 tmp;
+	struct rsa_op *handle;
+
+	retval = rsa_op_copy(&LEFTOP, l);
+	if (retval < 0)
+		return retval;
+
+	retval = rsa_op_copy(&RIGHTOP, r);
+	if (retval < 0)
+		return retval;
+
+	ls = l->size;
+	rs = r->size;
+	retval = rsa_op_resize(res, ls + rs);
+	if (retval < 0)
+		return retval;
+
+	handle = *res;
+	memset(handle->data, 0, handle->size * sizeof(u32));
+	handle->sign = LEFTOP->sign ^ RIGHTOP->sign;
+
+	buf = handle->data;
+	lbuf = LEFTOP->data;
+	rbuf = RIGHTOP->data;
+
+	/* Make the multiplication, using the standard algorithm */
+	for (i = 0; i < rs; i++) {
+		tmp = 0;
+		for (j = 0; j < ls; j++) {
+			tmp = buf[i + j] + (lbuf[j] * (u64)rbuf[i]) +
+			      (tmp >> 32);
+			buf[i + j] = (u32)tmp;
+		}
+
+		buf[i + ls] = tmp >> 32;
+	}
+
+	rsa_op_canonicalize(handle);
+	return 0;
+}
+
+static int rsa_difference(struct rsa_op **res, struct rsa_op *l,
+			  struct rsa_op *r, struct rsa_op **aux)
+{
+	int i, size, retval;
+	u32 *buf, *lbuf, *rbuf;
+	struct rsa_op *handle;
+
+	retval = rsa_op_copy(&LEFTOP, l);
+	if (retval < 0)
+		return retval;
+
+	retval = rsa_op_copy(&RIGHTOP, r);
+	if (retval < 0)
+		return retval;
+
+	size = max(l->size, r->size) + (l->sign != r->sign);
+	retval = rsa_op_resize(res, size);
+	if (retval < 0)
+		return retval;
+
+	retval = rsa_op_resize(&LEFTOP, size);
+	if (retval < 0)
+		return retval;
+
+	retval = rsa_op_resize(&RIGHTOP, size);
+	if (retval < 0)
+		return retval;
+
+	handle = *res;
+	buf = handle->data;
+	lbuf = LEFTOP->data;
+	rbuf = RIGHTOP->data;
+
+	/* If the operands are both negative or positive perform subtraction */
+	if (LEFTOP->sign == RIGHTOP->sign) {
+		bool borrow = false;
+		u32 limb;
+
+		for (i = 0; i < size; i++) {
+			limb = borrow + rbuf[i];
+			buf[i] = lbuf[i] - limb;
+			borrow = (lbuf[i] < limb);
+		}
+
+		if (borrow) {
+			rsa_op_complement(handle);
+			handle->sign = !RIGHTOP->sign;
+		}
+		else
+			handle->sign = RIGHTOP->sign;
+	}
+	/* If the operands are not signed in the same way perform addition */
+	else {
+		bool carry = false;
+		u64 sum;
+
+		for (i = 0; i < size; i++) {
+			sum = lbuf[i] + rbuf[i] + carry;
+			carry = (sum > U32_MAX);
+			buf[i] = (u32)sum;
+		}
+
+		handle->sign = LEFTOP->sign;
+	}
+
+	rsa_op_canonicalize(handle);
+	return 0;
+}
+
+static int rsa_remainder(struct rsa_op **res, struct rsa_op *l,
+			 struct rsa_op *r, struct rsa_op **aux)
+{
+	int i, k, retval;
+
+	retval = rsa_op_copy(&LEFTOP, l);
+	if (retval < 0)
+		return retval;
+
+	retval = rsa_op_copy(&RIGHTOP, r);
+	if (retval < 0)
+		return retval;
+
+	k = (LEFTOP->size - RIGHTOP->size) * 32;
+	k -= (rsa_op_clz(LEFTOP) - rsa_op_clz(RIGHTOP));
+
+	/* Align the divisor to the dividend */
+	retval = rsa_op_shift(&RIGHTOP, -k);
+	if (retval < 0)
+		return retval;
+
+	for (i = 0; i <= k; i++) {
+		retval = rsa_difference(res, LEFTOP, RIGHTOP, aux + 2);
+		if (retval < 0)
+			return retval;
+
+		if (!(*res)->sign) {
+			retval = rsa_op_copy(&LEFTOP, *res);
+			if (retval < 0)
+				return retval;
+		}
+
+		retval = rsa_op_shift(&RIGHTOP, 1);
+		if (retval < 0)
+			return retval;
+	}
+
+	rsa_op_canonicalize(LEFTOP);
+	return rsa_op_copy(res, LEFTOP);
+}
+
+/* Compute the montgomery product of two numbers */
+static int rsa_mproduct(struct rsa_op **res, struct rsa_op *l, struct rsa_op *r,
+			struct rsa_op *n, u32 modinv, struct rsa_op **aux)
+{
+	int nsize, i, j, k, retval;
+	u32 *buf, *nbuf, *tmp, m;
+	u64 product = 0;
+
+	nsize = n->size;
+	k = nsize << 1;
+	retval = rsa_product(res, l, r, aux);
+	if (retval < 0)
+		return retval;
+
+	retval = rsa_op_resize(res, max((*res)->size, k));
+	if (retval < 0)
+		return retval;
+
+	tmp = buf = (*res)->data;
+	nbuf = n->data;
+
+	for (i = 0; i < nsize; i++, tmp++) {
+		m = buf[i] * modinv;
+		product = 0;
+
+		for (j = 0; j < nsize; j++) {
+			product = tmp[j] + (m * (u64)nbuf[j]) + (product >> 32);
+			tmp[j] = (u32)product;
+		}
+
+		for (j = nsize + i; j < k; j++) {
+			product = buf[j] + (product >> 32);
+			buf[j] = (u32)product;
+		}
+	}
+
+	retval = rsa_op_resize(res, (*res)->size + 1);
+	if (retval < 0)
+		return retval;
+
+	(*res)->data[(*res)->size - 1] = product >> 32;
+	retval = rsa_op_shift(res, nsize * 32);
+	if (retval < 0)
+		return retval;
+
+	if (rsa_op_compare(*res, n) >= 0) {
+		retval = rsa_difference(res, *res, n, aux);
+		if (retval < 0)
+			return retval;
+	}
+	return 0;
+}
+
+/**
+ * rsa_op_alloc - allocate an rsa_op
+ * @n: pointer pointer to the allocated rsa_op
+ * @limbs: number of allocated limbs (32 bit digits)
+ *
+ * The allocated rsa_op will be zeroed and not canonicalized
+ */
+int rsa_op_alloc(struct rsa_op **n, int limbs)
+{
+	struct rsa_op *handle;
+
+	*n = NULL;
+	if (!limbs)
+		return -EINVAL;
+
+	/* Allocate space for the rsa_op */
+	handle = kmalloc(sizeof(struct rsa_op), GFP_KERNEL);
+	if (!handle)
+		return -ENOMEM;
+
+	/* Allocate space for its data */
+	handle->data = kzalloc(limbs * sizeof(u32), GFP_KERNEL);
+	if (!handle->data) {
+		kfree(handle);
+		return -ENOMEM;
+	}
+
+	handle->sign = 0;
+	handle->size = handle->limbs = limbs;
+	*n = handle;
+	return 0;
+}
+
+/**
+ * rsa_op_free - free the resources held by an rsa_op
+ * @n: pointer to the rsa_op to be freed
+ */
+void rsa_op_free(struct rsa_op *n)
+{
+	if (!n)
+		return;
+	kfree(n->data);
+	kfree(n);
+}
+
+/**
+ * rsa_op_init - initialize an rsa_op given its absolute value
+ * @n: pointer pointer to the allocated rsa_op
+ * @data: the value as a byte array
+ * @size: sizeof(data)
+ * @xtra: how many extra limbs to preallocate to avoid reallocations
+ *
+ * The optional leading zeroes will be taken into account, so that the
+ * rsa_op created will not be canonicalized
+ */
+int rsa_op_init(struct rsa_op **n, u8 *data, u32 size, u32 xtra)
+{
+	int i, j, s, retval;
+	u32 *buf;
+
+	*n = NULL;
+	if (!size && !xtra)
+		return -EINVAL;
+
+	/* Allocate space for the rsa_op and its data */
+	s = (size + 3) / 4;
+	retval = rsa_op_alloc(n, s + xtra);
+	if (retval < 0)
+		return retval;
+
+	(*n)->size = s;
+	buf = (*n)->data;
+
+	/* Copy the data */
+	for (i = size - 1, j = 0; i >= 0; i--, j++)
+		buf[j / 4] |= ((u32)data[i] << ((j % 4) * 8));
+	return 0;
+}
+
+/**
+ * rsa_op_set - set the value of an rsa_op given its absolute value
+ * @n: pointer pointer to the allocated rsa_op
+ * @data: the value as a byte array
+ * @size: sizeof(data)
+ *
+ * The optional leading zeroes will be taken into account, so that the rsa_op
+ * created will not be canonicalized. The rsa_op passed in will be reallocated
+ * (and relocated) if needed
+ */
+int rsa_op_set(struct rsa_op **n, u8 *data, u32 size)
+{
+	int s, i, j, retval;
+	u32 *buf;
+
+	if (!size)
+		return -EINVAL;
+
+	/* Size of the new rsa_op value (in limbs) */
+	s = (size + 3) / 4;
+	retval = rsa_op_resize(n, s);
+	if (retval < 0)
+		return retval;
+	memset((*n)->data, 0, (*n)->size * sizeof(u32));
+
+	/* Copy the data */
+	buf = (*n)->data;
+	for (i = size - 1, j = 0; i >= 0; i--, j++)
+		buf[j / 4] |= ((u32)data[i] << ((j % 4) * 8));
+	return 0;
+}
+
+/**
+ * rsa_op_copy - rsa_op to rsa_op copy
+ * @dest: destination rsa_op
+ * @src: source rsa_op
+ */
+int rsa_op_copy(struct rsa_op **dest, struct rsa_op *src)
+{
+	int retval;
+
+	retval = rsa_op_resize(dest, src->size);
+	if (retval < 0)
+		return retval;
+	memcpy((*dest)->data, src->data, src->size * sizeof(u32));
+	return 0;
+}
+
+/**
+ * rsa_op_print - print the value of an rsa_op
+ * @n: pointer to the rsa_op to be printed
+ * @how: true to print canonicalized
+ */
+void rsa_op_print(struct rsa_op *n, bool how)
+{
+	int i, j;
+	u32 limb;
+	u8 byte;
+	bool started = false;
+
+	printk("Operand @ 0x%x, %d limbs in size, %d limbs allocated, value = ",
+	       (u32)n, n->size, n->limbs);
+
+	/* Print the sign */
+	printk("%s", (n->sign)? "-" : " ");
+
+	/* Print the hex value */
+	for (i = n->size - 1; i >= 0; i--) {
+		limb = n->data[i];
+
+		/* Ignore leading zero limbs if canonicalization is selected */
+		if (!limb && !started && how)
+			continue;
+
+		/*
+		 * Print each limb as though each of its nibbles was a character
+		 * from the set '0' to '9' and 'a' to 'f'
+		 */
+		for (j = 28; j >= 0; j -= 4) {
+			byte = (u8)((limb >> j) & 0x0F);
+
+			/*
+			 * Ignore leading zero bytes if canonicalization
+			 * is selected
+			 */
+			if (!byte && !started && how)
+				continue;
+
+			started = true;
+			byte += (byte <= 0x09)? '0' : 'a' - 0x0A;
+			printk("%c", byte);
+		}
+	}
+
+	if (!started)
+		printk("0");
+	printk("\n");
+}
+
+/**
+ * rsa_cipher - compute montgomery modular exponentiation, m^e mod n
+ * @res: pointer pointer to the allocated result
+ * @m: data to be ciphered, also base of the exponentiation
+ * @e: exponent
+ * @n: modulus
+ *
+ * The montgomery modular exponentiation is not generic. It can be used only
+ * in cases where the modulus is odd as it is with RSA public and private key
+ * pairs, and this is because the algorithm depends in such number properties
+ * to speed things up. The calculation results will be invalid if the modulus
+ * is even. Furthermore the base must be in the residue class of the modulus
+ * (m < n). The calculation result if m > n will be mathematically valid but
+ * will be useless for the RSA cryptosystem, because it will be the result of
+ * (m mod n)^e mod n and not m^e mod n. Also the bit width of the base must
+ * be equal to the modulus bit width.
+ */
+int rsa_cipher(struct rsa_op **res, struct rsa_op *m, struct rsa_op *e,
+	       struct rsa_op *n)
+{
+	int i, j, retval;
+	u32 limb, modinv;
+	bool started = false;
+	struct rsa_op *aux[AUX_OPERAND_COUNT], *M, *x, *tmp;
+
+	/*
+	 * Check for bit width equality
+	 * Check if the base is in the residue class of the modulus
+	 * Check if the modulus is odd
+	 */
+	if (m->size != n->size || rsa_op_compare(m, n) > 0 || !(n->data[0] & 1))
+		return -EINVAL;
+
+	modinv = rsa_op_modinv32(n);
+	memset(&aux, 0, sizeof(aux));
+	M = x = NULL;
+
+	for (i = 0; i < AUX_OPERAND_COUNT; i++) {
+		retval = rsa_op_alloc(&aux[i],
+				      CONFIG_RSA_AUX_OPERAND_SIZE);
+		if (retval < 0)
+			goto rollback;
+	}
+
+	/* Compute M = m*r mod n where r is 2^k and k is the bit length of n */
+	retval = rsa_op_copy(&M, m);
+	if (retval < 0)
+		goto rollback;
+
+	retval = rsa_op_shift(&M, -(n->size * 32));
+	if (retval < 0)
+		goto rollback;
+
+	retval = rsa_remainder(&M, M, n, aux);
+	if (retval < 0)
+		goto rollback;
+
+	/* Compute x = r mod n where r is 2^k and k is the bit length of n */
+	retval = rsa_op_init(&x, "\x01", 1, 32);
+	if (retval < 0)
+		goto rollback;
+
+	retval = rsa_op_shift(&x, -(n->size * 32));
+	if (retval < 0)
+		goto rollback;
+
+	retval = rsa_remainder(&x, x, n, aux);
+	if (retval < 0)
+		goto rollback;
+
+	/*
+	 * Canonicalize the exponent and compute the modular exponentiation.
+	 * For each limb of the exponent perform left to right binary
+	 * exponentiation
+	 */
+	rsa_op_canonicalize(e);
+	for (i = e->size - 1; i >= 0; i--) {
+		/* Take a limb of the exponent */
+		limb = e->data[i];
+
+		/* For each of its bits */
+		for (j = 0; j < 32; j++) {
+			/*
+			 * While the exponent has non significant zeroes shift
+			 * it to the left
+			 */
+			if (!(limb & U32_MSB_SET) && !started) {
+				limb = limb << 1;
+				continue;
+			}
+			started = true;
+
+			/* Compute x = x*x mod n */
+			retval = rsa_mproduct(&x, x, x, n, modinv, aux);
+			if (retval < 0)
+				goto rollback;
+
+			if (limb & U32_MSB_SET) {
+				/* Compute x = M*x mod n */
+				retval = rsa_mproduct(&x, x, M, n, modinv, aux);
+				if (retval < 0)
+					goto rollback;
+			}
+
+			limb = limb << 1;
+		}
+	}
+
+	/* Compute res = x mod n */
+	retval = rsa_op_init(&tmp, "\x01", 1, 32);
+	if (retval < 0)
+		goto rollback;
+	retval = rsa_mproduct(res, x, tmp, n, modinv, aux);
+
+/* Free all allocated resources */
+rollback:
+	for (i = 0; i < AUX_OPERAND_COUNT; i++)
+		rsa_op_free(aux[i]);
+	rsa_op_free(M);
+	rsa_op_free(x);
+	rsa_op_free(tmp);
+	return retval;
+}
+
+EXPORT_SYMBOL(rsa_op_alloc);
+EXPORT_SYMBOL(rsa_op_free);
+EXPORT_SYMBOL(rsa_op_init);
+EXPORT_SYMBOL(rsa_op_set);
+EXPORT_SYMBOL(rsa_op_copy);
+EXPORT_SYMBOL(rsa_op_print);
+EXPORT_SYMBOL(rsa_cipher);
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Tasos Parisinos @ Sciensis Advanced Technology Systems");
+MODULE_DESCRIPTION("RSA cipher algorithm implementation");
+MODULE_ALIAS("rsa");
+
diff -uprN -X linux/Documentation/dontdiff \
linux.orig/include/crypto/rsa.h linux/include/crypto/rsa.h
--- linux.orig/include/crypto/rsa.h 1970-01-01 02:00:00.000000000 +0200
+++ linux/include/crypto/rsa.h 2007-04-02 11:49:03.000000000 +0300
@@ -0,0 +1,33 @@
+#ifndef _CRYPTO_RSA_H
+#define _CRYPTO_RSA_H
+
+/*
+ * struct rsa_op: multi-precision integer operand
+ * @data: array that holds the number absolute value
+ * @sign: 1 for negative, 0 for positive
+ * @size: significant number limbs
+ * @limbs: allocated limbs (sizeof data)
+ */
+struct rsa_op {
+	u32 *data;
+	int sign;
+	int size;
+	int limbs;
+};
+
+int	rsa_op_alloc(struct rsa_op **, int);
+
+void	rsa_op_free(struct rsa_op *);
+
+int 	rsa_op_init(struct rsa_op **, u8 *, u32, u32);
+
+int 	rsa_op_set(struct rsa_op **, u8 *, u32);
+
+int	rsa_op_copy(struct rsa_op **, struct rsa_op *);
+
+void	rsa_op_print(struct rsa_op *, bool);
+
+int 	rsa_cipher(struct rsa_op **, struct rsa_op *, struct rsa_op *,
+		   struct rsa_op *);
+
+#endif

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Tasos Parisinos]

Andi Kleen wrote:
> Tasos Parisinos <parisino@ceid.upatras.gr> writes:
>
>   
>> From: Tasos Parisinos <t.parisinos@sciensis.com>
>>
>> This patch adds module rsa.ko in the kernel (built-in or as a kernel
>> module) and offers an API to do fast modular exponentiation, using the
>> Montgomery algorithm, thus the exponentiation is not generic but can
>> be used only when
>> the modulus is odd, such as RSA public/private key pairs. This module is the
>> computational core (using multiple precision integer arithmetics) and does not
>> provide any means to do key management, implement padding schemas e.t.c. so the
>> calling code should implement all those as needed. Signed-off-by:
>> Tasos Parisinos <t.parisinos@sciensis.com>
>>     
>
> You forgot to answer the most important question.
>
> What would want to use RSA in the kernel and why?  
>
> -Andi
>
>   

The main purpose behind the creation of this module was to create the
cryptographic infrastructure to develop an in-kernel system of signed
modules.

The best environment to deploy such functionality is in updating by remote,
executable code (programs, libs and modules) on embedded devices running
Linux, that have some form of kernel physical security, so one can't 
tamper the
kernel, but can read it. In this case only a public key would be 
revealed. The
vendor of the devices can sign and distribute/update executable code to 
the devices,
and the kernel will not load/run any of them if they don't match with 
their signatures.
The signature can be embedded in the elf, so this system is portable and 
centralized.
Although this functionality can be achieved using userland helper 
programs this may
create the need to physically secure entire filesystems which adds to 
the cost of
developing such devices. In such cases one needs to use asymmetric 
cryptography
because in the case of symmetric it would be very easy to give away the 
key and
end with having all your devices being attacked.

There are already some systems that implement and utilize such 
functionality that
use windows platforms, and other Linux distros that use userland 
programs to do
so, assuming physical security of the host computer.

Moreover a same system that would use hashes is easier to brake and more 
difficult
to update each time new code must be loaded to the host devices.

See also this thread

http://lkml.org/lkml/2007/3/19/447

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Andi Kleen]

Tasos Parisinos <parisino@ceid.upatras.gr> writes:

> From: Tasos Parisinos <t.parisinos@sciensis.com>
> 
> This patch adds module rsa.ko in the kernel (built-in or as a kernel
> module) and offers an API to do fast modular exponentiation, using the
> Montgomery algorithm, thus the exponentiation is not generic but can
> be used only when
> the modulus is odd, such as RSA public/private key pairs. This module is the
> computational core (using multiple precision integer arithmetics) and does not
> provide any means to do key management, implement padding schemas e.t.c. so the
> calling code should implement all those as needed. Signed-off-by:
> Tasos Parisinos <t.parisinos@sciensis.com>

You forgot to answer the most important question.

What would want to use RSA in the kernel and why?  

-Andi

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Andi Kleen]

> The main purpose behind the creation of this module was to create the
> cryptographic infrastructure to develop an in-kernel system of signed
> modules.

So how do you plan to close the various interfaces that allow access to kernel
memory? 

I would suggest to discuss the high level design first before submitting
code. 

> 
> The best environment to deploy such functionality is in updating by remote,
> executable code (programs, libs and modules) on embedded devices running
> Linux, that have some form of kernel physical security, so one can't 

How would that physical security look like? Would it include DMA
protection?

For example to do any useful form of graphics you need
user controllable DMA, which can normally touch everything.
There are various other similar "backdoors" for root.

I'm somewhat sceptical because all kernels will need access
to the direct mapping to operate and there are also various
interfaces that can be as root (ab)used to change it.

And when you can do that they can change function pointers
and jump to arbitary code or change the kernel page tables
and map arbitary code.

Disallowing all this would probably end up with a quite
useless kernel. 

> There are already some systems that implement and utilize such 
> functionality that
> use windows platforms, and other Linux distros that use userland 

Yes, at least the Vista variant was just broken. And its designers spent
a lot of effort on it, but it didn't help.

-Andi

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Tasos Parisinos]

Andi Kleen wrote:
>> The main purpose behind the creation of this module was to create the
>> cryptographic infrastructure to develop an in-kernel system of signed
>> modules.
>>     
>
> So how do you plan to close the various interfaces that allow access to kernel
> memory? 
>
> I would suggest to discuss the high level design first before submitting
> code. 
>
>   
>> The best environment to deploy such functionality is in updating by remote,
>> executable code (programs, libs and modules) on embedded devices running
>> Linux, that have some form of kernel physical security, so one can't 
>>     
>
> How would that physical security look like? Would it include DMA
> protection?
>
> For example to do any useful form of graphics you need
> user controllable DMA, which can normally touch everything.
> There are various other similar "backdoors" for root.
>
> I'm somewhat sceptical because all kernels will need access
> to the direct mapping to operate and there are also various
> interfaces that can be as root (ab)used to change it.
>
> And when you can do that they can change function pointers
> and jump to arbitary code or change the kernel page tables
> and map arbitary code.
>
> Disallowing all this would probably end up with a quite
> useless kernel. 
>
>   
>> There are already some systems that implement and utilize such 
>> functionality that
>> use windows platforms, and other Linux distros that use userland 
>>     
>
> Yes, at least the Vista variant was just broken. And its designers spent
> a lot of effort on it, but it didn't help.
>
> -Andi
>
>
>   
Please read the thread i gave you for some details for things you ask

Have in thought that we mostly talk here about embedded devices
that run Linux in a very restricted environment where only specific
applications are allowed to exist and run, there are no user logons
and these applications need to be updated by remote once in a while
over public networks. These applications need not be tampered with
and must not be executed if they are, by someone that has hijacked
the connection by any means. Such devices can have some tamper
responsive hardware where the kernel (only) is protected in case
someone tries to tamper one of these devices by hand (not over the
network). You also need to have a centralized way of updating but
a de-centralized way of key usage so that if a person tampers with
one of these devices does not gain information that can be used
to attack the other devices over the network (like what would happened
if you used symmetric cryptography).

This is not a PC-security feature at all. Though it can be used in 
favour off
other tricks like trip-wire and digsig and others). Of course such 
functionality
could be easily by-passed in that case by someone root privileged with a 
good
understanding of the system internals.

As for Vista, no comments.... :)

Best regards
Tasos Parisinos
-

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Andi Kleen]

> Please read the thread i gave you for some details for things you ask

I don't see much useful information in the thread. It's the
same high level handwaving from you there as in this.

> Have in thought that we mostly talk here about embedded devices
> that run Linux in a very restricted environment where only specific

Ok so they don't X servers? But did you audit all the ioctls of
all their drivers that they don't allow memory access? And plugged
the other interfaces like io port access etc.? 

And besides where is this code for review? There's a pretty firm policy
to not integrate any code without users because that guarantees
bitrot.

-Andi

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Pavel Machek]

Hi!

> >>The best environment to deploy such functionality is 
> >>in updating by remote,
> >>executable code (programs, libs and modules) on 
> >>embedded devices running
> >>Linux, that have some form of kernel physical 
> >>security, so one can't 
> >
> >How would that physical security look like? Would it 
> >include DMA
> >protection?
> >
> >For example to do any useful form of graphics you need
> >user controllable DMA, which can normally touch 
> >everything.
> >There are various other similar "backdoors" for root.
> >
> >I'm somewhat sceptical because all kernels will need 
> >access
> >to the direct mapping to operate and there are also 
> >various
> >interfaces that can be as root (ab)used to change it.
> >
> >And when you can do that they can change function 
> >pointers
> >and jump to arbitary code or change the kernel page 
> >tables
> >and map arbitary code.
> >
> >Disallowing all this would probably end up with a quite
> >useless kernel. 
> >
> >  
> >>There are already some systems that implement and 
> >>utilize such functionality that
> >>use windows platforms, and other Linux distros that 
> >>use userland 
> >
> >Yes, at least the Vista variant was just broken. And 
> >its designers spent
> >a lot of effort on it, but it didn't help.
> >  
> Please read the thread i gave you for some details for 
> things you ask
> 
> Have in thought that we mostly talk here about embedded 
> devices
> that run Linux in a very restricted environment where 
> only specific
> applications are allowed to exist and run, there are no 
> user logons
> and these applications need to be updated by remote once 
> in a while
> over public networks. These applications need not be 
> tampered with

What kind of applications are we talking about here? I'd like to hack
hardware I own.

							Pavel
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Tasos Parisinos]

> What kind of applications are we talking about here? I'd like to hack
> hardware I own.

payment systems, EMV terminals, mobile phone applications

Tasos Parisinos
-

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Pavel Machek]

Hi!

> >What kind of applications are we talking about here? I'd like to hack
> >hardware I own.
> 
> payment systems, EMV terminals, mobile phone applications

I'd like to hack my cell phone, thank you. (Plus, cellphones do not
contain physical security).
									Pavel
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Bill Davidsen]

Tasos Parisinos wrote:
> Andi Kleen wrote:
>> Tasos Parisinos <parisino@ceid.upatras.gr> writes:
>>
>>  
>>> From: Tasos Parisinos <t.parisinos@sciensis.com>
>>>
>>> This patch adds module rsa.ko in the kernel (built-in or as a kernel
>>> module) and offers an API to do fast modular exponentiation, using the
>>> Montgomery algorithm, thus the exponentiation is not generic but can
>>> be used only when
>>> the modulus is odd, such as RSA public/private key pairs. This module 
>>> is the
>>> computational core (using multiple precision integer arithmetics) and 
>>> does not
>>> provide any means to do key management, implement padding schemas 
>>> e.t.c. so the
>>> calling code should implement all those as needed. Signed-off-by:
>>> Tasos Parisinos <t.parisinos@sciensis.com>
>>>     
>>
>> You forgot to answer the most important question.
>>
>> What would want to use RSA in the kernel and why? 
>> -Andi
>>
>>   
> 
> The main purpose behind the creation of this module was to create the
> cryptographic infrastructure to develop an in-kernel system of signed
> modules.
> 
I don't really see why this has to be in the kernel, even after reading 
your text below. This would be code which a tiny number of users would 
find useful, someone in the future might find exploitable, to perform a 
function which can be done in user space.

> The best environment to deploy such functionality is in updating by
> remote, executable code (programs, libs and modules) on embedded
> devices running Linux, that have some form of kernel physical
> security, so one can't tamper the kernel, but can read it. In this
> case only a public key would be revealed. The vendor of the devices
> can sign and distribute/update executable code to the devices, and
> the kernel will not load/run any of them if they don't match with
> their signatures. The signature can be embedded in the elf, so this
> system is portable and centralized. 

> Although this functionality can be achieved using userland helper
> programs this may create the need to physically secure entire
> filesystems which adds to the cost of developing such devices.

So to save cost on your end you want to make this feature part of the 
mainline kernel. Am I misreading your intent here?

> In such cases one needs to use asymmetric cryptography because in the
> case of symmetric it would be very easy to give away the key and end
> with having all your devices being attacked.
> 
Which make a good argument for doing asymmetric anyway, it would seem. 
That way any updates can be checked off the target machine and validated 
as authentic.

> There are already some systems that implement and utilize such 
> functionality that use windows platforms, and other Linux distros
> that use userland programs to do so, assuming physical security of
> the host computer.
> 
Exactly.

> Moreover a same system that would use hashes is easier to brake and
> more difficult to update each time new code must be loaded to the
> host devices.
> 
> See also this thread
> 
> http://lkml.org/lkml/2007/3/19/447
> 
Having said all this, we have a boatload of other crypto in the kernel, 
if it's just the crypto module, like aes, anubis or micheal_mic, and is 
GPL compatible, some people may agree. But if this is an embedded 
system, and you have the patch, why not just apply it to your kernel and 
forget mainline?

-- 
Bill Davidsen <davidsen@tmr.com>
   "We have more to fear from the bungling of the incompetent than from
the machinations of the wicked."  - from Slashdot

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Indan Zupancic]

On Fri, April 6, 2007 23:30, Bill Davidsen wrote:
> Tasos Parisinos wrote:
>> The main purpose behind the creation of this module was to create the
>> cryptographic infrastructure to develop an in-kernel system of signed
>> modules.
>>

>> Although this functionality can be achieved using userland helper
>> programs this may create the need to physically secure entire
>> filesystems which adds to the cost of developing such devices.
>
> So to save cost on your end you want to make this feature part of the
> mainline kernel. Am I misreading your intent here?

(Tasos was talking about the cost of securing whole file systems versus only
the kernel binary.)

But if that "entire filesystem" is initramfs, I don't
see any problem. If it fits into the kernel, it also has enough room for an
initramfs with a user space program with the RSA signing. I said this before,
so please look up how initramfs works and tell us why that isn't sufficient
for this case.

I suspect your answer will be because it isn't the only part and a lot other
infrastructure is need in the kernel to do all the binary signing. But that
code you didn't post, only a MPI module, however nice, which is only a partial
solution to what you want to achieve. Combine that with the kernel policy to
not merge unused code, and you're in the current situation.

> Having said all this, we have a boatload of other crypto in the kernel,
> if it's just the crypto module, like aes, anubis or micheal_mic, and is
> GPL compatible, some people may agree. But if this is an embedded
> system, and you have the patch, why not just apply it to your kernel and
> forget mainline?

Currently it's less than a cryptoapi module, as it only provide some functions
to do multi-precision integer calculations, which happen to be the tricky part
of implementing RSA.

That said, this implementation seems quite good, from a code size and complexity
point of view. So for that alone I think it wouldn't be bad to merge this or a
modified version of this, even if it's unused by the rest of the kernel, it might
be useful for other users. The burden to carry it along for the kernel is quite
small, while the code is worth something and might get improved by their users,
in the end having a central place to collect them. So I think from an open source
ecological point of view, it wouldn't be bad to merge it.

I see three possible way forwards (alternative is the status quo):

1) Move it to user space (into the initramfs embedded into the kernel).
But you'd still need to add binary (modules, libs and programs) load hooks.

2) Flesh it out into a ready to use, full blown RSA cryptoAPI module. Whatever
you said earlier, whether you want or not, it's just a block cipher, with the
modulo as block size (I suspect there's some room for code simplification when
assuming fixed block sizes too, by allocating blocksize * 2 space instead of
resizing when needed).

3) Go all the way, and post all the other kernel modifications too, to get the
whole binary signing you want to achieve.
Advantage will be that in the end you'll end up with something scrutinized to
death. Disadvantage is that it will be scrutinized to death, as that can take
a lot of time. Maybe you'll end up with a new LSM module, who knows?

The list is in increasing order of difficulty and quality of your end code.

It would help if you could find others who also wants something similar and
work together to get it into the kernel. But even if the last step fails,
you still have had people reviewing your code. And failing even that, you at
least shared your code with the rest of the world, which is already something
good (and required by the GPL. But doing it in the open is much more laudable
than hiding it on a website).

Greetings,

Indan

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Bill Davidsen]

Indan Zupancic wrote:
> On Fri, April 6, 2007 23:30, Bill Davidsen wrote:
>   
>> Tasos Parisinos wrote:
>>     
>>> The main purpose behind the creation of this module was to create the
>>> cryptographic infrastructure to develop an in-kernel system of signed
>>> modules.
>>>
>>>       
>
>   
>>> Although this functionality can be achieved using userland helper
>>> programs this may create the need to physically secure entire
>>> filesystems which adds to the cost of developing such devices.
>>>       
>> So to save cost on your end you want to make this feature part of the
>> mainline kernel. Am I misreading your intent here?
>>     
>
> (Tasos was talking about the cost of securing whole file systems versus only
> the kernel binary.)
>
> But if that "entire filesystem" is initramfs, I don't
> see any problem. If it fits into the kernel, it also has enough room for an
> initramfs with a user space program with the RSA signing. I said this before,
> so please look up how initramfs works and tell us why that isn't sufficient
> for this case.
>
> I suspect your answer will be because it isn't the only part and a lot other
> infrastructure is need in the kernel to do all the binary signing. But that
> code you didn't post, only a MPI module, however nice, which is only a partial
> solution to what you want to achieve. Combine that with the kernel policy to
> not merge unused code, and you're in the current situation.
>
>   
>> Having said all this, we have a boatload of other crypto in the kernel,
>> if it's just the crypto module, like aes, anubis or micheal_mic, and is
>> GPL compatible, some people may agree. But if this is an embedded
>> system, and you have the patch, why not just apply it to your kernel and
>> forget mainline?
>>     
>
> Currently it's less than a cryptoapi module, as it only provide some functions
> to do multi-precision integer calculations, which happen to be the tricky part
> of implementing RSA.
>
> That said, this implementation seems quite good, from a code size and complexity
> point of view. So for that alone I think it wouldn't be bad to merge this or a
> modified version of this, even if it's unused by the rest of the kernel, it might
> be useful for other users. The burden to carry it along for the kernel is quite
> small, while the code is worth something and might get improved by their users,
> in the end having a central place to collect them. So I think from an open source
> ecological point of view, it wouldn't be bad to merge it.
>
> I see three possible way forwards (alternative is the status quo):
>
> 1) Move it to user space (into the initramfs embedded into the kernel).
> But you'd still need to add binary (modules, libs and programs) load hooks.
>
> 2) Flesh it out into a ready to use, full blown RSA cryptoAPI module. Whatever
> you said earlier, whether you want or not, it's just a block cipher, with the
> modulo as block size (I suspect there's some room for code simplification when
> assuming fixed block sizes too, by allocating blocksize * 2 space instead of
> resizing when needed).
>
>   
This would probably be the best solution, to provide most of the hooks 
while presenting the cryptoAPI for others to use if they wish. Good 
suggestion.
> 3) Go all the way, and post all the other kernel modifications too, to get the
> whole binary signing you want to achieve.
> Advantage will be that in the end you'll end up with something scrutinized to
> death. Disadvantage is that it will be scrutinized to death, as that can take
> a lot of time. Maybe you'll end up with a new LSM module, who knows?
>
> The list is in increasing order of difficulty and quality of your end code.
>
> It would help if you could find others who also wants something similar and
> work together to get it into the kernel. But even if the last step fails,
> you still have had people reviewing your code. And failing even that, you at
> least shared your code with the rest of the world, which is already something
> good (and required by the GPL. But doing it in the open is much more laudable
> than hiding it on a website).
>
> Greetings,
>
> Indan
>
>
>   
I think you have covered the possibilities, my read is that your item 
number two is most likely to be accepted.

-- 
Bill Davidsen <davidsen@tmr.com>
  "We have more to fear from the bungling of the incompetent than from
the machinations of the wicked."  - from Slashdot

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Tasos Parisinos]

Hello to everybody

-----

Firstly i want to thank everybody for reviewing this code and posting all your
usefull comments

-----

Secondly i would like to give a generic (as possible) example of use of this
module. More and more nowadays Linux has started to be ported and running in a
wide variety of devices that are mostly described by the word embedded, from
mobile phones and smart phones to gadgets and multimedia players and from
routers to payment, identification, access and security systems. There is also
the big arena of industrial digital equipment as plc, motion controllers e.t.c.
These devices were running till now some other on-chip and in many cases
proprietary operating systems. The processors and the resources used where a lot
less than a full fledged OS needs to run on. Exception to all these devices
where some pda's. But now the processors used in embedded devices have evolved a
lot and while hardware is getting faster and cheaper the cost of creating and
maintaining the os has grown to a point where more and more designers need to
use either Linux or some OS of the windows family (CE, XP embedded, mobile).
The time is close where you are going to have the resources on-chip to download
and run a kernel from within a chip. As anyone can understand these devices are
not like servers, for example, hidden away in some well protected computer room,
with dedicated administrators and they can't be compared at all with
workstations and personal computers where noone usually spents time to intrude,
unless to practice his hobby. Most if not all of the designers and vendors of
such digital devices will very soon need to have a way of centrally and
transparently updating the software and personalization data in such devices in
a secure way over public networks.

If you are a vendor of a smart phone, a router, or worst, a point of sale
terminal you care about three things. The first is that the end user can't open
the device to probe it or alter it in a way that would create fraud. For example
a salesman could alter a credit card reader to see all cards as genuine and do
offline transactions. The second is that you dont want any eavesdropper
hijacking connectionsto such devices and replacing your updates with his in a
way that could create fraud. In that case the problem could be severe because
you don't have a user's device altered but possibly hundrends of them. And the
third thing is to do the first two as cheap as you can because in the embedded
world, as one can understand competition is tough.

The first need is solved generally by embedding hot data in security access
modules and hot software on chips or cryptomemories bla bla. Security can range
from tamper resistance to tamper rensonsiveness in means of such casings that
could detect any kind of intrusion attempt and erase all critical stuff,
rendering a device useless. For an example think of a processor that has all
its critical software and data inside it, on volatile memories. When this chip
is not powered it uses an internal (or external) battery to keep these data
alive. This chip can have sensors of heat, humidity, oscillator frequency
imbalancies, short circuits, currents going in and out of its pins, even light,
and be configured and programmed in a way to erase all critical data and
software when some of the above variables goes out of envelope.

The second need is solved by authentication and encryption. The system of
authentication must be asymmetric because if it is symmetric and the first need
is not well implemented then you may get really exposed. Of course you have to
secure first the software that does this authentication on the device.

We at Sciensis are designing embedded systems and we had the need to create such
a system for authentication. We have built it into the Linux kernel because this
is neat, simple and costs less to implement. As Indan said, in generic, its more
difficult to secure entire filesystems and this gets even more difficult when
you have your filesystem on removable media such as mmc or sd-cards. So we
thought, hell why not give it to others as well so we GPL'd it. It was first 
developed on an AVR32 so it is put for review on www.avr32linux.org (to be honest
it was published there rather late) and also given to you to review as well
because all flavours of embedded Linux whether they are run on ARM or AVR or PPC
BLACKFIN etc are all derived from the mainline, so having it as portable code in the
mainline you make it accessible to all these fellows wanting to use it in the
embedded world. Well it will be quite useless for your PC so dont select it when
you compile your kernel. Yes this thing does not have other in-kernel users yet
but i always wondered who uses khazad cipher algorithm, lol. (ok i suppose all
these symmetric cryptographic and digest options are all for IPSec, but khazad
(?!), come on guys). I understand codebloat, firm policies, bitrot e.t.c but how
can a thing be published and used if it is not brought out to the light?

-----
Thirdly some technical stuff that Indan brought up

1. Indan you have commented on an earlier patch that the multiplication
algorithm can be optimized a lot. Please post anything you have in mind because
that code is executed a lot.

2. Making it a full blown Crypto API is possible, because RSA can be seen as a
block cipher and you can hard code and compile the fixed size of the modulus and
thus simplify code as well, but this will make it less generic and cumbersome in
runtime (except if we add some kernel boot parameters). But there is a problem
with exponents... how would you pass them around using the current Crypto API
structs? Would it be wiser to take this module out of Cryptocraphic Options menu 
and put it in the Library routines menu?

3. We decided not to GPL other parts of the binary signing mechanism because
this are covered by some NDAs. So i must leave that to others to develop, or
come back with a very-very different version of these parts and this will take
time.

I think it is worth to try to make a version which will use the crypto api glue
code and re-post...

Best regards
Tasos Parisinos
-

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Indan Zupancic]

Hi,

On Wed, April 11, 2007 12:14, Tasos Parisinos wrote:
> If you are a vendor of a smart phone, a router, or worst, a point of sale
> terminal you care about three things. The first is that the end user can't open
> the device to probe it or alter it in a way that would create fraud. For example
> a salesman could alter a credit card reader to see all cards as genuine and do
> offline transactions.

I'd hope that for a smart phone and a router the owner can install whatever he wants
(that is, he has the private key). As for the card reader, I'd hope that using a
modified card reader isn't enough for fraud to succeed, or else the whole thing is
designed stupid. That said, the credit card system seems insecure anyway, with readers
being able to steal useful information.


> The second is that you dont want any eavesdropper
> hijacking connectionsto such devices and replacing your updates with his in a
> way that could create fraud. In that case the problem could be severe because
> you don't have a user's device altered but possibly hundrends of them. And the
> third thing is to do the first two as cheap as you can because in the embedded
> world, as one can understand competition is tough.

These are real problems.


> The first need is solved generally by embedding hot data in security access
> modules and hot software on chips or cryptomemories bla bla. Security can range
> from tamper resistance to tamper rensonsiveness in means of such casings that
> could detect any kind of intrusion attempt and erase all critical stuff,
> rendering a device useless. For an example think of a processor that has all
> its critical software and data inside it, on volatile memories. When this chip
> is not powered it uses an internal (or external) battery to keep these data
> alive. This chip can have sensors of heat, humidity, oscillator frequency
> imbalancies, short circuits, currents going in and out of its pins, even light,
> and be configured and programmed in a way to erase all critical data and
> software when some of the above variables goes out of envelope.

Read: http://www.cl.cam.ac.uk/TechReports/UCAM-CL-TR-630.pdf

There are other similar papers. The conclusion is that if someone really wants it,
he will get it from your device. Not sure if it was this paper or another one, but
volatile memory can be read out after the power went off. It's even possible to
retrieve overwritten data if it wasn't done very carefully, both RAM and flash.

If the tampering is done for a very short time, the detectors will probably miss it.
Or the tampering is done with the one thing the device wasn't protected against.
Or they think up some new way to bypass the protections.

Anyway, the question is what you're trying to protect. In general it's to keep the
code hidden, because there are plenty of obscure companies that steal that expensive
code and use it for their products. But it can also be a private key or something.


> The second need is solved by authentication and encryption. The system of
> authentication must be asymmetric because if it is symmetric and the first need
> is not well implemented then you may get really exposed. Of course you have to
> secure first the software that does this authentication on the device.

True. (Though asymmetric doesn't mean it has to be RSA. ;-)


> We at Sciensis are designing embedded systems and we had the need to create such
> a system for authentication. We have built it into the Linux kernel because this
> is neat, simple and costs less to implement.

Yes. But with that comes the obligation to publish your code under the GPL to your
customers, keep that in mind.


> As Indan said, in generic, its more
> difficult to secure entire filesystems and this gets even more difficult when
> you have your filesystem on removable media such as mmc or sd-cards.

Only true if that filesystem isn't initramfs embedded in the kernel library! Then it
gets the same protection as the kernel for free.


> So we thought, hell why not give it to others as well so we GPL'd it.

You did? We only saw a MPI implementation, nothing more. All the above mentioned
arguments and reasoning only applies to a complete implementation, not to an
incomplete partial solution, which on its own is useless. Don't mix up the binary
signing thing with a nice stand alone RSA crypto module.

That said, it was nice to share the RSA code, no matter what.


> Yes this thing does not have other in-kernel users yet
> but i always wondered who uses khazad cipher algorithm, lol. (ok i suppose all
> these symmetric cryptographic and digest options are all for IPSec, but khazad
> (?!), come on guys). I understand codebloat, firm policies, bitrot e.t.c but how
> can a thing be published and used if it is not brought out to the light?

I fully agree with this, but only for a RSA crypto API module.


> 1. Indan you have commented on an earlier patch that the multiplication
> algorithm can be optimized a lot. Please post anything you have in mind because
> that code is executed a lot.

I've no time right now, but I'll look it up when you've posted the crypto API version.


> 2. Making it a full blown Crypto API is possible, because RSA can be seen as a
> block cipher and you can hard code and compile the fixed size of the modulus and
> thus simplify code as well, but this will make it less generic and cumbersome in
> runtime (except if we add some kernel boot parameters).

As far as the memory management, I didn't mean to hardcode the size of the modulus,
but to have a hard coded limit (e.g. 4096 bits). The modulus can vary, as long as
it's less than the limit. As for the block size, it depends on what scheme you use.
In general the block size isn't exactly equal to the modulus, but smaller, and the
message is padded in some way. It depends on how you sign the binary hash. So maybe
it's best to move that decision to the user of the RSA module, and indeed use the
modulus as block size, in which case it would be variable and depend on the key used.
No idea how well the current crypto API copes with that, it might be a problem.


> But there is a problem
> with exponents... how would you pass them around using the current Crypto API
> structs? Would it be wiser to take this module out of Cryptocraphic Options menu
> and put it in the Library routines menu?

I don't know, I didn't look into the details yet. But I assume that at worst you
use a struct as key, and pass that transparently through the crypto API part.
But maybe there are better ways. Can try it out and use what seems best I suppose.


> 3. We decided not to GPL other parts of the binary signing mechanism because
> this are covered by some NDAs. So i must leave that to others to develop, or
> come back with a very-very different version of these parts and this will take
> time.

Well, you don't have much choice in the matter when using GPL software, I'm afraid.
You don't have to release it to everyone, only to your customers, but they're free
it give to anyone else they want. If that's not possible because of some NDA, then
you may not distribute the GPL code. The whole point of using GPL is that if someone
modifies the code, he's required to give back the modifications.

And squeezing out of this isn't possible in your situation as you don't have a
separate binary module, but have modified kernel code and are distributing the whole.

But I don't see why you're so mysterious about the rest anyway, because it looks rather
trivial to implement such binary signature checking thing. If it isn't trivial, then
small chance it's secure...

At least I won't ever buy "secure" hardware from any vendor who's mysterious about the
implemented protections. Because time after time it was proven that no matter how obscure
the protection is done, it's always bypassed if it couldn't stand on its own.
(Example: The GSM encryption used. Both reverse engineered and broken.)


> I think it is worth to try to make a version which will use the crypto api glue
> code and re-post...

Yes, certainly, independently from the rest of the implementation, which you might need
to move to userspace if you're really coy about it. (Though if it's only because of the
stupid NDA, then I'd consider replacing the NDA part with something of your own. NDA's
imply money drain.)

Greetings,

Indan

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Tasos Parisinos]

> On Wed, April 11, 2007 12:14, Tasos Parisinos wrote:
>> If you are a vendor of a smart phone, a router, or worst, a point of sale
>> terminal you care about three things. The first is that the end user can't open
>> the device to probe it or alter it in a way that would create fraud. For example
>> a salesman could alter a credit card reader to see all cards as genuine and do
>> offline transactions.
> 
> I'd hope that for a smart phone and a router the owner can install whatever he wants
> (that is, he has the private key). As for the card reader, I'd hope that using a
> modified card reader isn't enough for fraud to succeed, or else the whole thing is
> designed stupid. That said, the credit card system seems insecure anyway, with readers
> being able to steal useful information.

Well with old credit cards (magnetic) it was possible (as a matter of fact it was trivial)
With new chip cards its a lot harder but still possible, only the risk is smaller in means that
the fraud will be very limited.

> Read: http://www.cl.cam.ac.uk/TechReports/UCAM-CL-TR-630.pdf
> 
> There are other similar papers. The conclusion is that if someone really wants it,
> he will get it from your device. Not sure if it was this paper or another one, but
> volatile memory can be read out after the power went off. It's even possible to
> retrieve overwritten data if it wasn't done very carefully, both RAM and flash.
> 
> If the tampering is done for a very short time, the detectors will probably miss it.
> Or the tampering is done with the one thing the device wasn't protected against.
> Or they think up some new way to bypass the protections.
> 
> Anyway, the question is what you're trying to protect. In general it's to keep the
> code hidden, because there are plenty of obscure companies that steal that expensive
> code and use it for their products. But it can also be a private key or something.
> 
> 

I didn't have time to read the pdf but i will. As for erasing ram it usually means to also 
scramble it and there are chips that advertise that can do this in 1 cycle. Well reaching the bus or ram 
to probe it is another thing. Most die in such chip are also hidden under protective meshes so it 
takes some time. What you said is true, systems are created and broken, the question is what 
you have to hide and whether the person that wants to break it has the money the will the knowledge and the equipment 
to do it. Because if he is to spend a million euro only to create fraud of half a million euro then he wont do it.
That has to do with risk management.

>> The second need is solved by authentication and encryption. The system of
>> authentication must be asymmetric because if it is symmetric and the first need
>> is not well implemented then you may get really exposed. Of course you have to
>> secure first the software that does this authentication on the device.
> 
> True. (Though asymmetric doesn't mean it has to be RSA. ;-)
> 
> 

Sure, but its just more standardized and widely used

>> So we thought, hell why not give it to others as well so we GPL'd it.
> 
> You did? We only saw a MPI implementation, nothing more. All the above mentioned
> arguments and reasoning only applies to a complete implementation, not to an
> incomplete partial solution, which on its own is useless. Don't mix up the binary
> signing thing with a nice stand alone RSA crypto module.
> 
> That said, it was nice to share the RSA code, no matter what.
> 
> 

I understand and i agree, thing is that i dont decide about which parts are given GPL.
While the RSA module is given standalone, it can be still used by others to develop
their own signing and authenticating mechanisms. For example some will decide to do 
hashing of code with md5 while others with sha1 and some will do padding compliant
with pkcs1 other will implement other schemas e.t.c. I want to say although this is not
really ready to be used for binary signing, it has the advantage to provide basic functionality
and freedom to other developers to implement their own schemas.

> But I don't see why you're so mysterious about the rest anyway, because it looks rather
> trivial to implement such binary signature checking thing. If it isn't trivial, then
> small chance it's secure...
> 
> At least I won't ever buy "secure" hardware from any vendor who's mysterious about the
> implemented protections. Because time after time it was proven that no matter how obscure
> the protection is done, it's always bypassed if it couldn't stand on its own.
> (Example: The GSM encryption used. Both reverse engineered and broken.)
> 

people think that by hiding implementations (which can be reverse engineered of course)
will make it more difficult to break. Well i agree with you but... its not in my hands.
So i will come back with these parts replaced with some of my own

And a question
Can someone provide me with a full list of kernel functions where code is loaded?

Best regards 
Tasos Parisinos

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Satyam Sharma]

Hello,

> I understand and i agree, thing is that i dont decide about which parts are given GPL.
> While the RSA module is given standalone, it can be still used by others to develop
> their own signing and authenticating mechanisms. For example some will decide to do
> hashing of code with md5 while others with sha1 and some will do padding compliant
> with pkcs1 other will implement other schemas e.t.c. I want to say although this is not
> really ready to be used for binary signing, it has the advantage to provide basic functionality
> and freedom to other developers to implement their own schemas.

Firstly, I'd like to steer clear of all the RSA-in-kernel-or-userspace
/ MPI-in-kernel-or-userspace arguments. True, MPI / RSA / (PKI? that
even requires some knowledge of ASN.1 etc to parse certificates) do
add a lot of bloat to the kernel. That said, I don't see any other
reason to _not_ do asymmetric crypto in the kernel either. In some
situations, that in fact simplifies the overall system by avoiding the
use of additional userspace components / daemons to do the key
management stuff.

I do have some comments on the submitted patch, though:

1. First, sorry, I don't think an RSA implementation not conforming to
PKCS #1 qualifies to be called RSA at all. That is definitely a *must*
-- why break strong crypto algorithms such as RSA by implementing them
in insecure ways? It shouldn't be too difficult for you to add, and
you _can_ still allow the user to choose the appropriate padding
scheme by taking it as an argument to the encrypt / decrypt API
functions (some possibilities I can think of are PKCS#1 v1.5 padding,
v2.0 i.e. OAEP padding, or null padding).

2. Of course, you can forget about what digest was used to compute the
plaintext input to RSA. We don't really care, as RSA should never be
used to operate on multiple blocks anyway and no real-world hybrid
cryptosystem uses it in such a way either. (RSA could be thought of as
a block cipher of block size == modulus size)

3. Please, try to re-use the MPI library from GnuPG that has already
been ported to the kernel -- not the mainline tree, but most
distributions such as Red Hat, Fedora, Debian, Suse(?) have maintained
an MPI library in crypto/ for the modsign stuff for years now -- that
would make your entire RSA module merely a set of wrappers
(implementing PKCS#1) to the core modular exponentiation functions in
that MPI library. It also contains implementations of optimized
algorithms for a lot of the mathematics involved, so you have only to
benefit from utilizing a library that has been used, maintained and
tested for years.

4. Anything in crypto/ belongs to the CryptoAPI. You definitely need
to integrate with it.

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Indan Zupancic]

On Thu, April 12, 2007 11:35, Satyam Sharma wrote:
> Firstly, I'd like to steer clear of all the RSA-in-kernel-or-userspace
> / MPI-in-kernel-or-userspace arguments. True, MPI / RSA / (PKI? that
> even requires some knowledge of ASN.1 etc to parse certificates) do
> add a lot of bloat to the kernel. That said, I don't see any other
> reason to _not_ do asymmetric crypto in the kernel either. In some
> situations, that in fact simplifies the overall system by avoiding the
> use of additional userspace components / daemons to do the key
> management stuff.

Because it can all be done in userspace? Can trap all binary loading from
user-space too, though that must be done carefully, without changing the
kernel.

> 1. First, sorry, I don't think an RSA implementation not conforming to
> PKCS #1 qualifies to be called RSA at all. That is definitely a *must*
> -- why break strong crypto algorithms such as RSA by implementing them
> in insecure ways?

It's still RSA, that it's not enough to get a complete and secure crypto
system doesn't mean it isn't RSA anymore. Maybe you're right and having
RSA without the rest makes no sense. But things like padding schemes change,
the core RSA algorithm does't, so I think when adding anything that's unused
by the rest of the kernel it has more chance if it's a low maintenance bare
RSA implementation.


> 3. Please, try to re-use the MPI library from GnuPG that has already
> been ported to the kernel -- not the mainline tree, but most
> distributions such as Red Hat, Fedora, Debian, Suse(?) have maintained
> an MPI library in crypto/ for the modsign stuff for years now -- that
> would make your entire RSA module merely a set of wrappers
> (implementing PKCS#1) to the core modular exponentiation functions in
> that MPI library. It also contains implementations of optimized
> algorithms for a lot of the mathematics involved, so you have only to
> benefit from utilizing a library that has been used, maintained and
> tested for years.

Right, and that MPI implementation isn't merged. Perhaps a smaller, simpler,
not complexified by optimisations version has more chance. RSA is damn slow
anyway, so better to concentrate on other things than speed, IMHO.

That said, perhaps the different groups could concentrate on one implementation
they all agree on? That's the main advantage of having it mainline, that there's
a common place to cencentrate all effort into.

But keep in mind that it's a precaurious balance, at least that's how I see it.
Right now it's about a rather static 800 lines of code which implements some
common algorithms. Not much bloat, low maintenance, over all not much reason
to not merge it, except that it isn't used by the rest of the kernel.

If you're going to add the full kitchen sink, it might not look that appealing
anymore, and merging it will become much harder, especially as no one provided
good arguments why it can't be done in user space.

Perhaps, with that in mind, it's better to not merge the bare RSA version either,
as it might give false hope for more, because it looks like most implementations
should be done in user space (either because that's better anyway, or because of
legal reasons).

Greetings,

Indan

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Andi Kleen]

> Perhaps, with that in mind, it's better to not merge the bare RSA version either,
> as it might give false hope for more, because it looks like most implementations
> should be done in user space (either because that's better anyway, or because of
> legal reasons).

Before merging anything there would need to be clear applications
(with patches, discussions etc.) 

In general code with no users is not merged because it will just bitrot.

-Andi

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Indan Zupancic]

On Thu, April 12, 2007 10:34, Tasos Parisinos wrote:
> I didn't have time to read the pdf but i will. As for erasing ram it usually means to also
> scramble it and there are chips that advertise that can do this in 1 cycle. Well reaching the bus
> or ram
> to probe it is another thing. Most die in such chip are also hidden under protective meshes so it
> takes some time.

Those can be peeled off. But the paper I linked to concentrates on other kinds of attacks.

Quote:

"One of the main contributions of this thesis is fault injection attacks done in a semi-invasive
manner which can be used to modify the contents of SRAM and change the state of any
individual transistor inside the chip. That gives almost unlimited capabilities to the attacker in
getting control over the chip operation and abusing the protection mechanism.
Compared to non-invasive attacks, semi-invasive attacks are harder to implement as they
require decapsulation of the chip. However, very much less expensive equipment is needed than
for invasive attacks. These attacks can be performed in a reasonably short period of time. Also
they are scalable to a certain extent, and the skills and knowledge required to perform them can
be easily and quickly acquired. Some of these attacks, such as an exhaustive search for a"

It gives a good overview of all kind of other attacks and defences too. Personally I find the
non-invasive attacks the most interesting. (The pdf is 12 MB, for the low bandwidthers.)


> What you said is true, systems are created and broken, the question is what
> you have to hide and whether the person that wants to break it has the money the will the
> knowledge and the equipment
> to do it. Because if he is to spend a million euro only to create fraud of half a million euro
> then he wont do it.
> That has to do with risk management.

Very true, and the right way to look at it. (Vendors should say "it costs about $X to
break this chip", instead of saying that it's secure, and then not giving guarantees.)


> I understand and i agree, thing is that i dont decide about which parts are given GPL.

No, the kernel licence and others do. But you can't edit the kernel and distribute it without
releasing those modifications under the GPL.


> people think that by hiding implementations (which can be reverse engineered of course)
> will make it more difficult to break. Well i agree with you but... its not in my hands.
> So i will come back with these parts replaced with some of my own

What else is there except the signing and binary loading hooks? Perhaps some caching, but
not much more, is there? I'm a bit baffled about what's kept hidden here, as there doesn't
seem much to hide, except perhaps other, independent "protections", but we weren't talking
about those.

I don't know anything about your company, but I bet the marketing people are more in
favour to keeping it hidden than the security people. I'd ask the legal people for the
kernel parts though.


> And a question
> Can someone provide me with a full list of kernel functions where code is loaded?

Counter questions:

- Why should we give that list if you're not going to release the code you're going to write?
Or in other words, why should we help you?
(But if you're going to open it up, try to find people interested in the same functionality so
you can work together on it. Not me, I'm just a passer-by.)

- That you ask for that list implies that you're not going to audit the whole kernel source
for such functions. That might imply, to some, that your security code isn't as secure as it
should be. People make mistakes, forget things, so on. Both you and people providing a list.
And such mistakes are easiest spotted when more people look at the code. But that's not
possible when the code is hidden. Then only the ones with malicious intents keep looking. So
perhaps it's harder to spot deficiencies in closed source protection code, but it will probably
have more of it too. Your choice, you take the risk.

Greetings,

Indan

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Satyam Sharma]

> > Firstly, I'd like to steer clear of all the RSA-in-kernel-or-userspace
> > / MPI-in-kernel-or-userspace arguments. True, MPI / RSA / (PKI? that
> > even requires some knowledge of ASN.1 etc to parse certificates) do
> > add a lot of bloat to the kernel. That said, I don't see any other
> > reason to _not_ do asymmetric crypto in the kernel either. In some
> > situations, that in fact simplifies the overall system by avoiding the
> > use of additional userspace components / daemons to do the key
> > management stuff.
>
> Because it can all be done in userspace? Can trap all binary loading from
> user-space too, though that must be done carefully, without changing the
> kernel.

Aarghh ... just the argument I wanted to steer clear of, isn't this?
Continuing, however, we _can_ do a lot of things in userspace, but
still might choose to do them in the kernel, for various reasons in
each case (performance, convenience, application transparency etc
etc). So many things come to mind -- filesystems, readahead, the
cryptoapi itself -- some less controversial, and some more so.

Of course, once an infrastructure is indeed merged into the kernel, it
better already have (or quickly develop) some users for itself. If it
doesn't, it does end up as rot. If it does, that pretty much solves
the maintenance problem there itself.

Getting specific to *this* particular case, I _can_ think of other
users in the kernel that could gladly use general asymmetric crypto
capabilities added to the cryptoapi -- encrypting file systems, module
signing (as of now they've just implemented DSA directly for
themselves, not through the cryptoapi) to name a few.

> > 1. First, sorry, I don't think an RSA implementation not conforming to
> > PKCS #1 qualifies to be called RSA at all. That is definitely a *must*
> > -- why break strong crypto algorithms such as RSA by implementing them
> > in insecure ways?
>
> It's still RSA, that it's not enough to get a complete and secure crypto
> system doesn't mean it isn't RSA anymore. Maybe you're right and having
> RSA without the rest makes no sense. But things like padding schemes change,
> the core RSA algorithm does't, so I think when adding anything that's unused
> by the rest of the kernel it has more chance if it's a low maintenance bare
> RSA implementation.

Well, then *all* the users of the RSA cryptoapi code would end up
duplicating the PKCS padding for themselves! (because if we don't care
about padding in a "low-maintenance-bare-RSA-implementation", then we
might as well not implement any RSA crypto at all :-) Also, padding
schemes are careful cryptographic constructions -- much like ciphers
themselves. Much thought has gone into PKCS#1 over the years (and it's
later revisions). We wouldn't want users to re-invent some kind of
insecure padding for themselves.

The way I think about this is: (1) RSA without PKCS#1 makes no sense,
and (2) PKCS#1 is *defined* only for RSA. Combine (1) and (2), and it
makes *all* sense to encapsulate the two in just one module.

Coming to padding standards, RSA has been around for ~20 years now,
and only 3 PKCS#1 padding schemes were ever defined (at least AFAICR).
That's not something that changes so frequently as to not implement it
in the core RSA code itself, especially when the penalties of not
doing so could be quite embarrassing indeed.

> > 3. Please, try to re-use the MPI library from GnuPG that has already
> > been ported to the kernel -- not the mainline tree, but most
> > distributions such as Red Hat, Fedora, Debian, Suse(?) have maintained
> > an MPI library in crypto/ for the modsign stuff for years now -- that
> > would make your entire RSA module merely a set of wrappers
> > (implementing PKCS#1) to the core modular exponentiation functions in
> > that MPI library. It also contains implementations of optimized
> > algorithms for a lot of the mathematics involved, so you have only to
> > benefit from utilizing a library that has been used, maintained and
> > tested for years.
>
> Right, and that MPI implementation isn't merged. Perhaps a smaller, simpler,
> not complexified by optimisations version has more chance. RSA is damn slow
> anyway, so better to concentrate on other things than speed, IMHO.

If RSA is slow, then optimizing it to make it fast (and thus have more
impact on relative performance) should make *more* sense, shouldn't
it? That MPI implementation is derived from GPG, which has been around
for a decade now. I'd much rather prefer well-known and
well-understood code that has been used, tested and maintained for a
decade than some recent/unused contraption, thank you.

> If you're going to add the full kitchen sink, it might not look that appealing
> anymore, and merging it will become much harder, especially as no one provided
> good arguments why it can't be done in user space.
>
> Perhaps, with that in mind, it's better to not merge the bare RSA version either,
> as it might give false hope for more, because it looks like most implementations
> should be done in user space (either because that's better anyway, or because of
> legal reasons).

Hmmm ... and again I'll excuse myself from the debate whether to
*actually* merge MPI and asymmetric crypto capabilities into the
mainline tree or not -- it's all about whether the potential users
named earlier really want to be able to do all that stuff in-kernel or
wouldn't mind writing userspace components for it.

Cheers,
S

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Indan Zupancic]

On Thu, April 12, 2007 16:20, Satyam Sharma wrote:
> Of course, once an infrastructure is indeed merged into the kernel, it
> better already have (or quickly develop) some users for itself. If it
> doesn't, it does end up as rot. If it does, that pretty much solves
> the maintenance problem there itself.

Yes, but currently those users are more or less hidden and working
independently.


> Getting specific to *this* particular case, I _can_ think of other
> users in the kernel that could gladly use general asymmetric crypto
> capabilities added to the cryptoapi -- encrypting file systems, module
> signing (as of now they've just implemented DSA directly for
> themselves, not through the cryptoapi) to name a few.

The potential for users is the bare minimum expected, next step is that
there are any and them agreeing on common implementations.


> Well, then *all* the users of the RSA cryptoapi code would end up
> duplicating the PKCS padding for themselves! (because if we don't care
> about padding in a "low-maintenance-bare-RSA-implementation", then we
> might as well not implement any RSA crypto at all :-) Also, padding
> schemes are careful cryptographic constructions -- much like ciphers
> themselves. Much thought has gone into PKCS#1 over the years (and it's
> later revisions). We wouldn't want users to re-invent some kind of
> insecure padding for themselves.
>
> The way I think about this is: (1) RSA without PKCS#1 makes no sense,
> and (2) PKCS#1 is *defined* only for RSA. Combine (1) and (2), and it
> makes *all* sense to encapsulate the two in just one module.
>
> Coming to padding standards, RSA has been around for ~20 years now,
> and only 3 PKCS#1 padding schemes were ever defined (at least AFAICR).
> That's not something that changes so frequently as to not implement it
> in the core RSA code itself, especially when the penalties of not
> doing so could be quite embarrassing indeed.

Very good points there, you're right.


> If RSA is slow, then optimizing it to make it fast (and thus have more
> impact on relative performance) should make *more* sense, shouldn't
> it? That MPI implementation is derived from GPG, which has been around
> for a decade now. I'd much rather prefer well-known and
> well-understood code that has been used, tested and maintained for a
> decade than some recent/unused contraption, thank you.

I prefer clear, simple code that is easily audited to be correct or at least
not cause problems, which is small enough to not add much bloat. I don't care
about "very slow" or merely "slow" code. RSA/DSA isn't used as a symmetric block
cipher, where it does make sense to optimize it to death.

>From the kernel's point of view it's all new and unused code, so it should be
judged by its quality, not by its heritage.

I know you didn't want to talk about the user versus kernel space question,
but I think it's a very important and interesting one. As you said, GPG is
there around for years and tested, why making a new implementation in the kernel?
Your argument holds for the whole as much as for parts of the infrastructure.


> Hmmm ... and again I'll excuse myself from the debate whether to
> *actually* merge MPI and asymmetric crypto capabilities into the
> mainline tree or not -- it's all about whether the potential users
> named earlier really want to be able to do all that stuff in-kernel or
> wouldn't mind writing userspace components for it.

And whether they can agree on a common implementation. If they all just want to do
their own thing, and not combine resources, then it doesn't make any sense to merge
anything at all, as it would be ignored anyway.

As for the userspace issue, I get the impression that they didn't consider it very
well, ignoring things like initramfs versus main filesystem and so on. It's also a
gradual thing, some things can be done best in the kernel, and others in user space.
Another alternative is to push it up into the boot loader. ;-)

Greetings,

Indan

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Satyam Sharma]

Hi Indan,

On 4/12/07, Indan Zupancic <indan@nul.nu> wrote:
> I prefer clear, simple code that is easily audited to be correct or at least
> not cause problems, which is small enough to not add much bloat. I don't care
> about "very slow" or merely "slow" code. RSA/DSA isn't used as a symmetric block
> cipher, where it does make sense to optimize it to death.
>
> From the kernel's point of view it's all new and unused code, so it should be
> judged by its quality, not by its heritage.

Agreed, the GPG MPI library *is* significantly larger -- I'm looking
at the Fedora 4 kernel source here and their crypto/mpi/ comes to
about 5000 lines (not including comments). But there are reasons for
this -- they export far too many MPI operations. I suspect they just
ported the *entire* GNU MP lib.

For example, there's crypto/mpi/longlong.h, worth 1500 lines of
ugliness in itself. I see arch-specific assembly there for processors
that Linux doesn't even support. Wow.

There are some other better reasons for the bloat in the GNU MP lib,
though. Tasos' code uses the rsa_cipher() as a dual-purpose primitive.
Feed it the plaintext (p), public exponent (e) and public modulus (n),
and you get the ciphertext (c = p^e mod n). Feed it the ciphertext,
private exponent (d) and public modulus, and you get the plaintext (p
= c^d mod n) back. All modern RSA implementations, however, prefer
preserving the prime numbers (p, q, and their other derivatives such
as d mod (p-1), d mod (q-1) and inverse of q modulo p) generated at
the time of key generation along with the private exponent as the
complete "private key" (this is what is recommended by PKCS#1 too)
which enables us to use the chinese remainder theorem to decrypt
faster than simply do an (expensive) modulo exponentiation again.

Also, DSA signature generation and verification (which is what the
modsign guys use) doesn't exactly utilize the same MPI operations as
RSA does. If we really don't care about speed and DSA, we could strip
that library down to the basic and RSA-only operations Tasos' code
provides, and I'm quite sure we'd end up somewhere close to 1000 lines
there too.

Of course, that would then *force* other users such as modsign to
re-implement their own library for their needs again, thus defeating
the exercise of merging this bare-bones MPI library into the kernel in
the first place, as you have mentioned.

> I know you didn't want to talk about the user versus kernel space question,
> but I think it's a very important and interesting one. As you said, GPG is
> there around for years and tested, why making a new implementation in the kernel?
> Your argument holds for the whole as much as for parts of the infrastructure.
[...]
> And whether they can agree on a common implementation. If they all just want to do
> their own thing, and not combine resources, then it doesn't make any sense to merge
> anything at all, as it would be ignored anyway.

Yes, that "common implementation" bit is definitely crucial, which is
why merging a solid, feature-rich and fast MPI library could become
all the more important, in my opinion.

> As for the userspace issue, I get the impression that they didn't consider it very
> well, ignoring things like initramfs versus main filesystem and so on. It's also a
> gradual thing, some things can be done best in the kernel, and others in user space.
> Another alternative is to push it up into the boot loader. ;-)

Very true, it does make sense to explore userspace possibilities first.

Cheers,
S

> Greetings,
>
> Indan

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Indan Zupancic]

Hello,

On Thu, April 12, 2007 20:38, Satyam Sharma wrote:
> There are some other better reasons for the bloat in the GNU MP lib,
> though. Tasos' code uses the rsa_cipher() as a dual-purpose primitive.
> Feed it the plaintext (p), public exponent (e) and public modulus (n),
> and you get the ciphertext (c = p^e mod n). Feed it the ciphertext,
> private exponent (d) and public modulus, and you get the plaintext (p
> = c^d mod n) back. All modern RSA implementations, however, prefer
> preserving the prime numbers (p, q, and their other derivatives such
> as d mod (p-1), d mod (q-1) and inverse of q modulo p) generated at
> the time of key generation along with the private exponent as the
> complete "private key" (this is what is recommended by PKCS#1 too)
> which enables us to use the chinese remainder theorem to decrypt
> faster than simply do an (expensive) modulo exponentiation again.

Which, according to the Wikipedia page on RSA, is susceptible to timing
attacks, which requires measures to counter that (that might be needed in
Tasos' implementation too though).

Doing MPI well is already tricky. Doing it in such way that most side-channel
attacks don't work is challenging, and brings already code bloat and complexity
with it.  Doing all the previous with compact and simple code is hard. Speed is
the last thing I'm worried about.

I'd rather start with good and simple code, and speed it up without adding too
much complexity gradually, case by case.
(Though I'm not the one with any interests here, so my opinion isn't worth much.)


> Also, DSA signature generation and verification (which is what the
> modsign guys use) doesn't exactly utilize the same MPI operations as
> RSA does. If we really don't care about speed and DSA, we could strip
> that library down to the basic and RSA-only operations Tasos' code
> provides, and I'm quite sure we'd end up somewhere close to 1000 lines
> there too.

That's nice. But then you lose more or less all advantages of using an existing
implementation, don't you? Anyway, how much different would that code be from
Tasos'?

> Of course, that would then *force* other users such as modsign to
> re-implement their own library for their needs again, thus defeating
> the exercise of merging this bare-bones MPI library into the kernel in
> the first place, as you have mentioned.

Not if they go the other way round and strip everything except DSA functionality.
The question is, is an MPI library wanted, or do people just want RSA or DSA?

> Yes, that "common implementation" bit is definitely crucial, which is
> why merging a solid, feature-rich and fast MPI library could become
> all the more important, in my opinion.

You want feature-rich and fast, I prefer dense, clean and spartan, what would
others prefer? Perhaps deciding on a common implementation is harder than it looks.

Greetings,

Indan

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Satyam Sharma]

> > There are some other better reasons for the bloat in the GNU MP lib,
> > though. Tasos' code uses the rsa_cipher() as a dual-purpose primitive.
> > Feed it the plaintext (p), public exponent (e) and public modulus (n),
> > and you get the ciphertext (c = p^e mod n). Feed it the ciphertext,
> > private exponent (d) and public modulus, and you get the plaintext (p
> > = c^d mod n) back. All modern RSA implementations, however, prefer
> > preserving the prime numbers (p, q, and their other derivatives such
> > as d mod (p-1), d mod (q-1) and inverse of q modulo p) generated at
> > the time of key generation along with the private exponent as the
> > complete "private key" (this is what is recommended by PKCS#1 too)
> > which enables us to use the chinese remainder theorem to decrypt
> > faster than simply do an (expensive) modulo exponentiation again.
>
> Which, according to the Wikipedia page on RSA, is susceptible to timing
> attacks, which requires measures to counter that (that might be needed in
> Tasos' implementation too though).

Of course, I'd rather code to the PKCS#1 RSA Cryptography Standard
than an entry-level Wikipedia page :-) Timing attacks are particularly
problematic on smart cards (too slow, and with predictable operation
times, if not using constant-time crypto implementations) and not
really worthwhile in practice on any other platform where there's
enough noise around to make accurate timing difficult (that
hyper-threading "vulnerability" discovered some time back comes to
mind). Even so, constant-time crypto implementations do take care of
them, though I agree the GPG code too lacks that.

> > Of course, that would then *force* other users such as modsign to
> > re-implement their own library for their needs again, thus defeating
> > the exercise of merging this bare-bones MPI library into the kernel in
> > the first place, as you have mentioned.
>
> Not if they go the other way round and strip everything except DSA functionality.
> The question is, is an MPI library wanted, or do people just want RSA or DSA?

I do agree that only those parts of an MPI lib that are really needed
by any users must be included. But then we don't want to end up in a
situation where we merge such a small MPI library that code and/or
functionality are being sadly duplicated across users who want
different asymmetric cryptosystems (note the 2 DLMs in mainline, for
example). When we want to support both RSA and DSA, which require a
diverse set of MPI operations and primitives, I don't see how we can
still continue to retain the simplistic and "spartan" RSA-only MPI lib
that this code provides.

Cheers,
S

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Indan Zupancic]

On Thu, April 12, 2007 21:57, Satyam Sharma wrote:
> Of course, I'd rather code to the PKCS#1 RSA Cryptography Standard
> than an entry-level Wikipedia page :-) Timing attacks are particularly
> problematic on smart cards (too slow, and with predictable operation
> times, if not using constant-time crypto implementations) and not
> really worthwhile in practice on any other platform where there's
> enough noise around to make accurate timing difficult

Noise can be filtered out, and combined attacks can give enough information.
(E.g. throw in power usage or other measurements.) There are ways to add
noise to the timing, but still using those optimisations. The point was
that they add extra code and complexity.

(Personally I think RSA-like asymmetric encryption has so many, often
subtle problems, with complex, hard to get secure implementations, that
it's something I'd avoid using as much as possible. Unfortunately there's
not much alternative.)


> constant-time crypto implementations do take care of
> them, though I agree the GPG code too lacks that.

That's because for side-channel attacks you need physical access to the
hardware, something for most machines means security is breached anyway.
But when this code is going to be used to sign things by embedded devices
(with a local, secret key), it can be important.

For checking signatures the key is known and all this doesn't matter, but
we're talking about a common implementation. It are things to keep in mind.


>> Not if they go the other way round and strip everything except DSA functionality.
>> The question is, is an MPI library wanted, or do people just want RSA or DSA?
>
> I do agree that only those parts of an MPI lib that are really needed
> by any users must be included. But then we don't want to end up in a
> situation where we merge such a small MPI library that code and/or
> functionality are being sadly duplicated across users who want
> different asymmetric cryptosystems (note the 2 DLMs in mainline, for
> example). When we want to support both RSA and DSA, which require a
> diverse set of MPI operations and primitives, I don't see how we can
> still continue to retain the simplistic and "spartan" RSA-only MPI lib
> that this code provides.

We won't know until those users show themselves. Until then, we can only
speculate. Right now there is only user, with another one lurking in the
background.

Greetings,

Indan

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Satyam Sharma]

On 4/13/07, Indan Zupancic <indan@nul.nu> wrote:
> On Thu, April 12, 2007 21:57, Satyam Sharma wrote:
> > Of course, I'd rather code to the PKCS#1 RSA Cryptography Standard
> > than an entry-level Wikipedia page :-) Timing attacks are particularly
> > problematic on smart cards (too slow, and with predictable operation
> > times, if not using constant-time crypto implementations) and not
> > really worthwhile in practice on any other platform where there's
> > enough noise around to make accurate timing difficult
>
> Noise can be filtered out, and combined attacks can give enough information.
> (E.g. throw in power usage or other measurements.) There are ways to add
> noise to the timing, but still using those optimisations. The point was
> that they add extra code and complexity.
>
> (Personally I think RSA-like asymmetric encryption has so many, often
> subtle problems, with complex, hard to get secure implementations, that
> it's something I'd avoid using as much as possible. Unfortunately there's
> not much alternative.)

But timing attacks are not exclusive to RSA / asymmetric
cryptosystems. Such (side channel / timing / power measurement / bus
access) attacks are possible against AES, etc too.

Of course, now we're really moving into a different realm -- I guess
in security there is always a threshold, and you really needn't care
beyond a particular threat perception level. I don't see how even the
existing cryptoapi (or *any* security measure in the kernel for that
matter) stands up to the kind of attacks we're talking about now.

> > constant-time crypto implementations do take care of
> > them, though I agree the GPG code too lacks that.
>
> That's because for side-channel attacks you need physical access to the
> hardware, something for most machines means security is breached anyway.
> But when this code is going to be used to sign things by embedded devices
> (with a local, secret key), it can be important.
>
> For checking signatures the key is known and all this doesn't matter, but
> we're talking about a common implementation. It are things to keep in mind.

I think the original idea was to generate signatures at a centralized
place (not on an embedded system) and only *verify* them using
*public* keys on the embedded systems? For most common
implementations, as I suggested, you only need bother yourself upto a
certain security threshold.

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[David Wagner]

Indan Zupancic wrote:
>On Thu, April 12, 2007 11:35, Satyam Sharma wrote:
>> 1. First, sorry, I don't think an RSA implementation not conforming to
>> PKCS #1 qualifies to be called RSA at all. That is definitely a *must*
>> -- why break strong crypto algorithms such as RSA by implementing them
>> in insecure ways?
>
>It's still RSA, that it's not enough to get a complete and secure crypto
>system doesn't mean it isn't RSA anymore. Maybe you're right and having
>RSA without the rest makes no sense.

Yes, Satyam Sharma is 100% correct.  Unpadded RSA makes no sense.  RSA is
not secure if you omit the padding.  If you have a good reason why RSA
needs to be in the kernel for security reasons, then the padding has to be
in the kernel, too.  Putting plain unpadded RSA in the kernel seems bogus.

I worry about the quality of this patch if it is using unpadded RSA.
This is pretty elementary stuff.  No one should be implementing their
own crypto code unless they have considerable competence and knowledge
of cryptography.  This elementary error leaves reason to be concerned
about whether the developer of this patch has the skills that are needed
to write this kind of code and get it right.

People often take it personally when I tell them that they do are not
competent to write their own crypto code, but this is not a personal
attack.  It takes very specialized knowledge and considerable study
before one can write your own crypto implementation from scratch and
have a good chance that the result will be secure.  People without
those skills shouldn't be writing their own crypto code, at least not
if security is important, because it's too easy to get something wrong.
(No, just reading Applied Cryptography is not good enough.)  My experience
is that code that contains elementary errors like this is also likely
to contain more subtle errors that are harder to spot.  In short, I'm
not getting warm fuzzies here.

And no, you can't just blithely push padding into user space and expect
that to make the security issues go away.  If you are putting the
RSA exponentiation in the kernel because you don't trust user space,
then you have to put the padding in the kernel, too, otherwise you're
vulnerable to attack from evil user space code.

It is also not true that padding schemes change all the time.  They're
fairly stable.  Pick a reasonable modern padding scheme and leave it.

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Indan Zupancic]

On Thu, April 12, 2007 23:13, Satyam Sharma wrote:
> But timing attacks are not exclusive to RSA / asymmetric
> cryptosystems. Such (side channel / timing / power measurement / bus
> access) attacks are possible against AES, etc too.

True, but those are often easier to protect, or are less vulnerable in
the first place. (E.g. it isn't very hard to make a constant time AES
implementation. The operations it does are independent of the key.)


> Of course, now we're really moving into a different realm -- I guess
> in security there is always a threshold, and you really needn't care
> beyond a particular threat perception level. I don't see how even the
> existing cryptoapi (or *any* security measure in the kernel for that
> matter) stands up to the kind of attacks we're talking about now.

True, and very specialized hardware is needed in such cases anyway, so
arguing that it's not the kernel's task to protect against such attacks
is valid. But it are interesting attacks, and people should be aware of
them, instead of blindly trusting any security measure (not implying
anyone here does, I mean in general).


>> > constant-time crypto implementations do take care of
>> > them, though I agree the GPG code too lacks that.
>>
>> That's because for side-channel attacks you need physical access to the
>> hardware, something for most machines means security is breached anyway.
>> But when this code is going to be used to sign things by embedded devices
>> (with a local, secret key), it can be important.
>>
>> For checking signatures the key is known and all this doesn't matter, but
>> we're talking about a common implementation. It are things to keep in mind.
>
> I think the original idea was to generate signatures at a centralized
> place (not on an embedded system) and only *verify* them using
> *public* keys on the embedded systems? For most common
> implementations, as I suggested, you only need bother yourself upto a
> certain security threshold.

Yes, but it depends on how the code is used. It is supposed to be generic code,
so whether someone wants to use it for signing or not is an open question. So
far it seems only signature checking is needed, and that simplifies a lot, but
if that isn't the case more questions pop up, like where the security threshold
should be.

The user with the tightest requirements more or less dictates the implementation.

All in all, to get anything merged at all in the kernel it seems at least the
following needs to happen:

- Future users speaking up and uniting.

- Figuring out their needs (so overlapping needs can make it into common
  code, and other decisions can be made, as where the kernel and user
  space border should be.)

- Deciding on a commonly agreed security threshold, and making that explicit.

- Coding it all up and keeping it in sync with mainline.

I don't see this happening soon. But a good start would be if someone who
cares about this sets up a mailing list or website to collect all users
and information.

Good night,

Indan

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Indan Zupancic]

Hello,

Next time, please do a reply-all so CC's aren't dropped.

It seems you jumped halfway in, missing some background info, I'll try to
clarify some things.

On Thu, April 12, 2007 23:28, David Wagner wrote:
> Yes, Satyam Sharma is 100% correct.  Unpadded RSA makes no sense.  RSA is
> not secure if you omit the padding.  If you have a good reason why RSA
> needs to be in the kernel for security reasons, then the padding has to be
> in the kernel, too.  Putting plain unpadded RSA in the kernel seems bogus.

He is correct, I only argued that's it can still be named RSA (which Satyam
disputed), no matter what critical features are missing for a complete
infrastructure.

I don't know if you read the patch, but right now it's only a multi-precision
integer implementation, useful to implement RSA. The rest, including the
binary checking, is missing. We're pondering a bit about what, in the end,
would be useful to have in or around the kernel.


> I worry about the quality of this patch if it is using unpadded RSA.
> This is pretty elementary stuff.  No one should be implementing their
> own crypto code unless they have considerable competence and knowledge
> of cryptography.  This elementary error leaves reason to be concerned
> about whether the developer of this patch has the skills that are needed
> to write this kind of code and get it right.

As said above, the patch is only an MPI implementation, not RSA, and neither
the rest to make it useful, like a crypto API interface and padding.

So we can't really judge the developer's skills or crypto knowledge.

It does point out that having a hidden implementation can never foster
much trust, as no one can read the code and judge if it's good or not.


> People often take it personally when I tell them that they do are not
> competent to write their own crypto code, but this is not a personal
> attack.  It takes very specialized knowledge and considerable study
> before one can write your own crypto implementation from scratch and
> have a good chance that the result will be secure.  People without
> those skills shouldn't be writing their own crypto code, at least not
> if security is important, because it's too easy to get something wrong.

To a certain degree you're right, but the nice thing about open source is
that people who know better can spot errors, and if those are fixed, it
can happen that an "incompetent" person created something excellent. Maybe
not at first, but in the end. (I suspect that a good coder with no crypto
knowledge, but with feedback from experts, can implement something better
than one expert with mediocre coding skills.)

The code should be judged, not the people writing it. Besides, it isn't
always that hard to get something secure, if things are kept simple and
straightforward. E.g. writing a secure AES implementation isn't magic.
RSA is much more complex though. (Rather ironic, as the theory behind RSA
is simple, but the implementation hairy. With AES it's exactly the opposite.
The coder doesn't need to understand the algebra behind it, knowing that it
can be done with a simple table lookup is enough).

In general the tricky part is around the crypto implementation itself, how
it's used, key management, etc. (Though the border is vague, so maybe you
included all that when saying "crypto implementation".)


> (No, just reading Applied Cryptography is not good enough.)  My experience
> is that code that contains elementary errors like this is also likely
> to contain more subtle errors that are harder to spot.  In short, I'm
> not getting warm fuzzies here.

The code posted has no such errors, see above. Maybe the part that wasn't has,
who knows.


> And no, you can't just blithely push padding into user space and expect
> that to make the security issues go away.  If you are putting the
> RSA exponentiation in the kernel because you don't trust user space,
> then you have to put the padding in the kernel, too, otherwise you're
> vulnerable to attack from evil user space code.

True, but the code wasn't put into the kernel for security reasons. Why it
was remains a bit of a mystery, but it looks like it was for convenience.

Greetings,

Indan

Re: [PATCH resend][CRYPTO]: RSA algorithm patch

[Tasos Parisinos]

Hello again

As i formerly stated there was some 'management' mixup (and don't want to believe that it had to do with
my code and crypto competence :), anyway no offence about that, really) about what to submit and what 
not. Now things are getting a lot clearer and i think that we will be able to submit all the patches in
order to have:

The rsa module patch as is now with the following additions

1. Padding as PKCS#1 specificates
2. Crypto API glue code

And another patch that will be the code authenticating mechanism.

These two will be a complete binary authenticating mechanism to be used in embedded Linux much the way
it was described on a previous post of mine.

The above will take some time as they will be reworked significantly based on the experience 
gathered through this discussion

If this code organization is done, should this go in crypto as rsa module + binary signing module
or should be made as one unique module for code authentication (hiding the rsa implementation inside it) 
and putting it somewhere else (not in crypto)?

-----

Sharma really made a point about excluding padding from this module and leaving it to userspace
or other in-kernel code. It should be added in the module, as it is the only to be used anyway be everyone.
Also Indan is right, this module was supposed to be a simple mpi implementation to do modexp
using the montgomery algorithm to be used for binary authentication, but if it is to turn it into real RSA
it should have padding and crypto API glue code.

-----

Indan has said:
I don't see this happening soon. But a good start would be if someone who
cares about this sets up a mailing list or website to collect all users
and information.

I think that this is a nice idea, so i will try setup such a spot to be able to discuss and share code.

-----

I created this code taking Indan's way of looking at things. Not porting something like the whole
gmp but just re-implementing only the needed mpi code. This as a result can be a clear and robust
and really easy to audit, basis for future implementations and addons. The drawback is that it does
not provide generic mpi functions to be used in other places as well. The question is:

If a full mpi kernel lib would be big and complex and randomly used then it is better to have 
distinct little modules, implementing their own needed mpi functionality, isn't that so?

When there will be lots of them modules depending heavily on mpi calculations then those could
be reworked to reach that point and in that case you would have less complexity and code size.

-------

There was also big discussion about implementing CRT to do modexp with the private key.
In my view although this could be implemented in the RSA module in order for it to be generic
it is susceptible to timing and other attacks and i would personally would not use it neither i would
keep such keys on a plain filesystem on an embedded device on the market. That is why there is
only the implementation of the montgomery exponentiation in my patch to be used with public keys
and exponents to authenticate code on embedded devices as described in detail in a previous message. 
Excluding the use of private keys and CRT also makes code a lot simpler. I tell you again this module
is not created for PC security. It is created to address a specific need on embedded devices. Whether
it will be used by a PC user to cipher/decipher data on his disk is ok with me but really in that case there
is no added security anyway.

The question there is:

Create a generic and complex RSA module to be used by anyone even on PCs (where it could be done 
easily (and much with the same safety) on userland) or create a cut-down and specific authenticating 
mechanism (using RSA) to authenticate code, that would be able to be used by all Linux embedded
users at first (and for naive and unsafe usage in PC world)?

Bye for now
Tasos Parisinos
-