Herein you find my test implementation of EME[2] for CryptoAPI. EME is a
"wide block" cipher mode intended to facilitate a secret storage method
of data at rest. EME-32-AES[1] is currently considered as standard for
SISWG, http://siswg.org/ 

Please notice, that this patch can be improved in a _lot_ of ways. I
choose to go for quick results, because I never intended to get this
patch merged. The reason: EME is patent encumbered by a patent of the
Univ. of California. Fortunately, I'm living in the jurisdiction of the
good old Europe and I wallow in my ignorance for this issue.

AFAIK, this patch is the first implementation of a usable hard disk
encryption solution according to the drafts of SISWG. Please feel free
to test it's performance. To use, set cipher mode to "aes-eme-plain".
The patch for dm-crypt.c is diffed against latest 2.6.9-um1. Feedback
appreciated (as ever).

 crypto/api.c           |    5 +
 crypto/cipher.c        |  211 ++++++++++++++++++++++++++++++++++++++++-
 drivers/md/dm-crypt.c  |    2
 include/linux/crypto.h |    2
 4 files changed, 217 insertions(+), 3 deletions(-)

[1] http://siswg.org/docs/EME-AES-03-22-2004.pdf
[2] S. Halevi and P. Rogaway, "A parallelizable enciphering mode." The
RSA Cryptographer's track, RSA-CT '04. LNCS vol. 2964, pages 292-304.
Springer-Verlag 2004. 
(For students of European German technical universities: You might be
able to access LNCS issues by http://rzblx1.uni-regensburg.de/ . Your
university must have a site subscription of LNCS, as well your IP range
must fit)

-- 
Fruhwirth Clemens <clemens@...>  http://clemens.endorphin.org

--- linux-2.6.9-therp3/crypto/cipher.c	2004-08-14 07:36:58.000000000 +0200
+++ linux-2.6.9-therp3-eme/crypto/cipher.c	2004-10-29 16:25:55.617674464 +0200
@@ -129,13 +129,27 @@
 static int setkey(struct crypto_tfm *tfm, const u8 *key, unsigned int keylen)
 {
 	struct cipher_alg *cia = &tfm->__crt_alg->cra_cipher;
+	int r;
 	
 	if (keylen < cia->cia_min_keysize || keylen > cia->cia_max_keysize) {
 		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_KEY_LEN;
 		return -EINVAL;
-	} else
-		return cia->cia_setkey(crypto_tfm_ctx(tfm), key, keylen,
+	} else {
+		r = cia->cia_setkey(crypto_tfm_ctx(tfm), key, keylen,
 		                       &tfm->crt_flags);
+		if (r < 0)
+			return r;
+			
+		if (tfm->crt_cipher.cit_mode & CRYPTO_TFM_MODE_EME) {
+			const unsigned int bsize = crypto_tfm_alg_blocksize(tfm);
+			u8 zero[bsize];
+			memset(zero,0,bsize);
+			cia->cia_encrypt(crypto_tfm_ctx(tfm),
+					 tfm->crt_u.cipher.L,
+					 (const u8 *)zero);
+		}
+		return 0;
+	}
 }
 
 static int ecb_encrypt(struct crypto_tfm *tfm,
@@ -197,6 +211,190 @@
 	             cbc_process, 0, iv);
 }
 
+/*
+ * Multiplication with x (0x02 element of GF(2^128)) under the reduction
+ * polynomial x^128 + x^7 + x^2 + x + 1 (0x00..0087 element of GF(2^128))
+ * optimized
+ */
+
+static void xtimeGF128(unsigned char *_src, unsigned char *_dst)
+{
+	u32 buf[4];
+	u32 *src = (u32 *)_src;
+	u32 *dst;
+
+	if(_src == _dst) 
+		dst=buf;
+	else
+		dst=(u32 *)_dst;
+	
+	dst[3] = (src[3] << 1) | (src[2] & 0x80000000 >> 31);
+	dst[2] = (src[2] << 1) | (src[1] & 0x80000000 >> 31);
+	dst[1] = (src[1] << 1) | (src[0] & 0x80000000 >> 31);
+	if(src[3] & 0x80000000) 
+		dst[0] = (src[0] << 1) ^ 0x87;
+	else
+		dst[0] = (src[0] << 1);
+	if(_src == _dst) memcpy(_dst,dst,16);
+}
+
+/*************************************************
+ * WARNING                                       *
+ * EME IS PATENT ENCUMBERED.                     *
+ * NEVER EVER MERGE THIS INTO ANY OFFICIAL TREE  *
+ *************************************************/
+
+/* EME Stage1: dst = E(src ^ L); L = xtime(L) */
+
+static void eme_process_enc1(struct crypto_tfm *tfm, u8 *dst, u8 *src,
+			cryptfn_t fn, int enc, void *L, int in_place)
+{
+	const unsigned int bsize = crypto_tfm_alg_blocksize(tfm);
+	char scratch[bsize];
+	
+	if(in_place) {
+		tfm->crt_u.cipher.cit_xor_block(src,L);
+		fn(crypto_tfm_ctx(tfm),dst,src);
+	} else {
+		memcpy(scratch,src,bsize);
+		tfm->crt_u.cipher.cit_xor_block(scratch,L);
+		fn(crypto_tfm_ctx(tfm),dst,scratch);	
+	}
+	xtimeGF128(L,L);
+}
+
+/* EME Stage2: dst = L^E(src); L = xtime(L)  */
+
+static void eme_process_enc2(struct crypto_tfm *tfm, u8 *dst, u8 *src,
+			cryptfn_t fn, int enc, void *L, int in_place)
+{
+	const unsigned int bsize = crypto_tfm_alg_blocksize(tfm);
+	char scratch[bsize];
+	
+	if(in_place) {
+		/* In fact, it must be in place */
+		fn(crypto_tfm_ctx(tfm),dst,src);
+		tfm->crt_u.cipher.cit_xor_block(dst,L);
+	} else {
+		memcpy(scratch,src,bsize);
+		fn(crypto_tfm_ctx(tfm),dst,scratch);	
+		tfm->crt_u.cipher.cit_xor_block(dst,L);
+	}
+	xtimeGF128(L,L);
+}
+
+/* EME - XORsum all PPP */
+static void eme_process_XORsum(struct crypto_tfm *tfm, u8 *dst, u8 *src,
+			cryptfn_t fn, int enc, void *info, int in_place)
+{
+	tfm->crt_u.cipher.cit_xor_block(info,src);
+}
+
+/* EME - Apply M to all PPP: dst=src ^ M; M=xtime(M);  */
+static void eme_process_apply_mask(struct crypto_tfm *tfm, u8 *dst, u8 *src,
+			cryptfn_t fn, int enc, void *M, int in_place)
+{
+	const unsigned int bsize = crypto_tfm_alg_blocksize(tfm);
+	if(!in_place) 
+		memcpy(dst,src,bsize);
+	tfm->crt_u.cipher.cit_xor_block(dst,M);
+	xtimeGF128(M,M);
+}
+
+/* Helper function: Replace first bytes of scatterlist dst with buf */
+static inline void replace_first_with(struct scatterlist *dst, void *buf, int size)
+{
+	struct scatter_walk walk;
+	u8 scratch[size];
+	u8 *dst_p;
+	
+	scatterwalk_start(&walk,dst);
+	scatterwalk_map(&walk,1);
+	dst_p = scatterwalk_whichbuf(&walk,size,scratch);
+	memcpy(dst_p,buf,size);
+	scatterwalk_copychunks(dst_p,&walk,size,1);
+	scatterwalk_done(&walk,1,0);
+}
+
+/* 
+ * EME - Symmetric processing structure with variable function crfn 
+ * variables and comments are labeled as if it would be encryption
+ */
+ 
+static int eme_generic_tweak(struct crypto_tfm *tfm,
+                          struct scatterlist *dst,
+                          struct scatterlist *src,
+                          unsigned int nbytes, u8 *T,
+                          cryptfn_t crfn)
+{
+	const unsigned int bsize = crypto_tfm_alg_blocksize(tfm);
+	u8 L[bsize];
+	u8 MP[bsize];
+	u8 MC[bsize];
+	u8 M[bsize];
+	u8 CCC1[bsize];
+	
+	if (nbytes/bsize != 32 || nbytes % bsize != 0) {
+		printk(KERN_WARNING "internal code error: incorrect EME call\n");
+		return -EINVAL;
+	}
+
+	memcpy(L,tfm->crt_u.cipher.L, bsize);
+	/* Stage1 converts P to PPP */
+	crypt(tfm, dst, src, nbytes,
+		  crfn, eme_process_enc1, 0, L);
+
+	/* After this, everything is "in place" */
+
+	/* Compute MP as T ^ PPP_1 ^ ... ^ PPP_n */ 
+	memcpy(MP,T,bsize);
+	crypt(tfm,dst,dst,nbytes,NULL,
+			eme_process_XORsum, 0, MP);
+	/* MC = E(MP) */
+	crfn(crypto_tfm_ctx(tfm),MC,MP);
+	
+	/* M =  MP ^ MC */
+	memcpy(M,MC,bsize);
+	tfm->crt_u.cipher.cit_xor_block(M,MP);
+
+	/* Apply M */
+	crypt(tfm,dst,dst,nbytes,NULL,
+			eme_process_apply_mask, 0, M);
+	replace_first_with(dst,MC,bsize);
+
+	/* Compute CCC1 as T ^ MC ^ CCC2 ^ .. ^ CCCn */
+	memcpy(CCC1,T,bsize);
+	crypt(tfm,dst,dst,nbytes,NULL,
+			eme_process_XORsum, 0, CCC1);
+	replace_first_with(dst,CCC1,bsize);
+	
+	/* Apply final encryption step and XOR with L */
+	memcpy(L,tfm->crt_u.cipher.L, bsize);
+	crypt(tfm, dst, dst, nbytes,
+	             crfn,
+	             eme_process_enc2, 0, L);
+	return 0;
+}
+
+static int eme_encrypt_tweak(struct crypto_tfm *tfm,
+                          struct scatterlist *dst,
+                          struct scatterlist *src,
+                          unsigned int nbytes, u8 *T)
+{
+	return eme_generic_tweak(tfm,dst,src,nbytes,T,
+	             tfm->__crt_alg->cra_cipher.cia_encrypt);
+
+}
+
+static int eme_decrypt_tweak(struct crypto_tfm *tfm,
+                          struct scatterlist *dst,
+                          struct scatterlist *src,
+                          unsigned int nbytes, u8 *T)
+{
+	return eme_generic_tweak(tfm, dst, src, nbytes, T,
+	             tfm->__crt_alg->cra_cipher.cia_decrypt);
+}
+
 static int nocrypt(struct crypto_tfm *tfm,
                    struct scatterlist *dst,
                    struct scatterlist *src,
@@ -258,11 +456,18 @@
 		ops->cit_decrypt_iv = nocrypt_iv;
 		break;
 
+	case CRYPTO_TFM_MODE_EME:
+		ops->cit_encrypt = nocrypt;
+		ops->cit_decrypt = nocrypt;
+		ops->cit_encrypt_iv = eme_encrypt_tweak;
+		ops->cit_decrypt_iv = eme_decrypt_tweak;
+		break;
+
 	default:
 		BUG();
 	}
 	
-	if (ops->cit_mode == CRYPTO_TFM_MODE_CBC) {
+	if (ops->cit_mode == CRYPTO_TFM_MODE_CBC || ops->cit_mode == CRYPTO_TFM_MODE_EME) {
 	    	
 	    	switch (crypto_tfm_alg_blocksize(tfm)) {
 	    	case 8:
--- linux-2.6.9-therp3/crypto/api.c	2004-10-19 08:33:14.000000000 +0200
+++ linux-2.6.9-therp3-eme/crypto/api.c	2004-10-29 16:32:54.179043464 +0200
@@ -126,6 +126,11 @@
 	if (alg == NULL)
 		goto out;
 	
+	if (flags & CRYPTO_TFM_MODE_EME && alg->cra_blocksize != 16) {
+		printk(KERN_WARNING "EME can only operate with 128 bit"
+				   " ciphers (implementation limitation)\n");
+		goto out_put;
+	}
 	tfm = kmalloc(sizeof(*tfm) + alg->cra_ctxsize, GFP_KERNEL);
 	if (tfm == NULL)
 		goto out_put;
--- linux-2.6.9-therp3/include/linux/crypto.h	2004-08-14 07:36:33.000000000 +0200
+++ linux-2.6.9-therp3-eme/include/linux/crypto.h	2004-10-29 16:27:39.042951432 +0200
@@ -42,6 +42,7 @@
 #define CRYPTO_TFM_MODE_CBC		0x00000002
 #define CRYPTO_TFM_MODE_CFB		0x00000004
 #define CRYPTO_TFM_MODE_CTR		0x00000008
+#define CRYPTO_TFM_MODE_EME		0x00000010
 
 #define CRYPTO_TFM_REQ_WEAK_KEY		0x00000100
 #define CRYPTO_TFM_RES_WEAK_KEY		0x00100000
@@ -150,6 +151,7 @@
 			   struct scatterlist *src,
 			   unsigned int nbytes, u8 *iv);
 	void (*cit_xor_block)(u8 *dst, const u8 *src);
+	u8 L[16];
 };
 
 struct digest_tfm {
--- linux-2.6.9-therp3/drivers/md/dm-crypt.c	2004-10-29 16:43:57.014277192 +0200
+++ linux-2.6.9-therp3-eme/drivers/md/dm-crypt.c	2004-10-28 20:20:18.000000000 +0200
@@ -586,6 +586,8 @@
 		crypto_flags = CRYPTO_TFM_MODE_CBC;
 	else if (strcmp(chainmode, "ecb") == 0)
 		crypto_flags = CRYPTO_TFM_MODE_ECB;
+	else if (strcmp(chainmode, "eme") == 0)
+		crypto_flags = CRYPTO_TFM_MODE_EME;
 	else {
 		ti->error = PFX "Unknown chaining mode";
 		goto bad1;