Skip to contentSkip to conversation

LRW implementation, please comment

PATCH Superseded Rik Snel 2 participants 23 messages Aug 31, 2006 – Nov 29, 2006

Subsystems (3)
lore
Share & tools
lore

Rik Snel

author
#0 lore raw

Hello Herbert (cc: list),

This is an attempt at implementing LRW for the new blockcipher API. Please review, test and comment.

I intend to implement ABL also (arbitrary block length), an unencumbered wide block cipher mode (it is based on GMC (Galois/Counter Mode) which is explicitly claimed to be patent free and has the same creators).

The mode has been dropped by its creators (I don't know why) and is not formally publised, see:

http://grouper.ieee.org/groups/1619/email/pdf00005.pdf
http://grouper.ieee.org/groups/1619/email/rtf00000.rtf

It fulfills the same function as the patent-encumbered EME, CMC and XCB.

Greetings,

Rik.

author
#1 lore raw

PATCH 1/6 crypto: trivial comment improvements

Just some minor comment nits.

- little-endian is better than low-endian
- and since it is called essiv everywere it should also be essiv in the comments (and not ess_iv)

---
 drivers/md/dm-crypt.c |    8 ++++----
 1 files changed, 4 insertions(+), 4 deletions(-)
drivers/md/dm-crypt.c +4 -4
index 91d4081..06961f7 100644
@@ -99,12 +99,12 @@ static kmem_cache_t *_crypt_io_pool;
 /*
  * Different IV generation algorithms:
  *
- * plain: the initial vector is the 32-bit low-endian version of the sector
+ * plain: the initial vector is the 32-bit little-endian version of the sector
  *        number, padded with zeros if neccessary.
  *
- * ess_iv: "encrypted sector|salt initial vector", the sector number is
- *         encrypted with the bulk cipher using a salt as key. The salt
- *         should be derived from the bulk cipher's key via hashing.
+ * essiv: "encrypted sector|salt initial vector", the sector number is
+ *        encrypted with the bulk cipher using a salt as key. The salt
+ *        should be derived from the bulk cipher's key via hashing.
  *
  * plumb: unimplemented, see:
  * http://article.gmane.org/gmane.linux.kernel.device-mapper.dm-crypt/454
Signature · 1 line
1.4.1.1
author
#2 lore raw

PATCH 2/6 crypto: benbi IV, big endian narrow block count for LRW-32-AES

In reply to Rik Snel

LRW-32-AES needs a certain IV. This IV should be provided dm-crypt. The block cipher mode could, in principle generate the correct IV from the plain IV, but I think that it is cleaner to supply the right IV directly.

The sector -> narrow block calculation uses a shift for performance reasons. This shift is computed in .ctr and stored in cc->iv_gen_private (as a void*).

---
 drivers/md/dm-crypt.c |   56 ++++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 55 insertions(+), 1 deletions(-)
drivers/md/dm-crypt.c +55 -1
index 06961f7..12c871c 100644
@@ -106,6 +106,9 @@ static kmem_cache_t *_crypt_io_pool;
  *        encrypted with the bulk cipher using a salt as key. The salt
  *        should be derived from the bulk cipher's key via hashing.
  *
+ * benbi: the 64-bit "big-endian 'narrow block'-count", starting at 1
+ * 	  (needed for LRW-32-AES and possible other narrow block modes)
+ *
  * plumb: unimplemented, see:
  * http://article.gmane.org/gmane.linux.kernel.device-mapper.dm-crypt/454
  */
@@ -200,6 +203,49 @@ static int crypt_iv_essiv_gen(struct cry
 	return 0;
 }
 
+static int crypt_iv_benbi_ctr(struct crypt_config *cc, struct dm_target *ti,
+			      const char *opts)
+{
+	unsigned int bs = crypto_blkcipher_blocksize(cc->tfm);
+	int log = long_log2(bs);
+
+	/* we need to calculate how far we must shift the sector count
+	 * to get the cipher block count, we use this shift in _gen */
+
+	if (1 << log != bs) {
+		ti->error = "cypher blocksize is not a power of 2";
+		return -EINVAL;
+	}
+
+	if (log > 9) {
+		ti->error = "cypher blocksize is > 512";
+		return -EINVAL;
+	}
+	
+	if (crypto_blkcipher_ivsize(cc->tfm) < sizeof(u64)) {
+		ti->error = "cypher ivsize is < 8";
+		return -EINVAL;
+	}
+
+	cc->iv_gen_private = (void*)(9 - log);
+
+	return 0;
+}
+
+static void crypt_iv_benbi_dtr(struct crypt_config *cc) 
+{
+	cc->iv_gen_private = NULL; 
+}
+
+static int crypt_iv_benbi_gen(struct crypt_config *cc, u8 *iv, sector_t sector)
+{
+	memset(iv, 0, cc->iv_size - sizeof(u64)); /* rest is cleared below */
+	*(u64 *)(iv + cc->iv_size - sizeof(u64)) = 
+		cpu_to_be64(((u64)sector << (u32)cc->iv_gen_private) + 1);
+
+	return 0;
+}
+
 static struct crypt_iv_operations crypt_iv_plain_ops = {
 	.generator = crypt_iv_plain_gen
 };
@@ -210,6 +256,11 @@ static struct crypt_iv_operations crypt_
 	.generator = crypt_iv_essiv_gen
 };
 
+static struct crypt_iv_operations crypt_iv_benbi_ops = {
+	.ctr	   = crypt_iv_benbi_ctr,
+	.dtr	   = crypt_iv_benbi_dtr,
+	.generator = crypt_iv_benbi_gen
+};
 
 static int
 crypt_convert_scatterlist(struct crypt_config *cc, struct scatterlist *out,
@@ -579,7 +630,8 @@ static int crypt_ctr(struct dm_target *t
 	cc->tfm = tfm;
 
 	/*
-	 * Choose ivmode. Valid modes: "plain", "essiv:<esshash>".
+	 * Choose ivmode. Valid modes: "plain", "essiv:<esshash>", "benbi".
+	 *
 	 * See comments at iv code
 	 */
 
@@ -589,6 +641,8 @@ static int crypt_ctr(struct dm_target *t
 		cc->iv_gen_ops = &crypt_iv_plain_ops;
 	else if (strcmp(ivmode, "essiv") == 0)
 		cc->iv_gen_ops = &crypt_iv_essiv_ops;
+	else if (strcmp(ivmode, "benbi") == 0)
+		cc->iv_gen_ops = &crypt_iv_benbi_ops;
 	else {
 		ti->error = "Invalid IV mode";
 		goto bad2;
Signature · 1 line
1.4.1.1
author
#3 lore raw

PATCH 3/6 crypto: some common 128-bit block operations, nicely centralized

In reply to Rik Snel

128bit is a common blocksize in linux kernel cryptography, so it helps to centralize some common operations. The data must be aligned at sizeof(int) for decent performance.

The code, while mostly trivial, is based on a header file mode_hdr.h in
http://fp.gladman.plus.com/AES/modes.vc8.19-06-06.zip

The original copyright (and GPL statement) of the original author, Dr Brian Gladman, is preserved.

---
 crypto/b128ops.h |   72 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 72 insertions(+), 0 deletions(-)
crypto/b128ops.h new file +72 -0
new file mode 100644
index 0000000..d32bfc2
@@ -0,0 +1,72 @@
+/* b128ops.h - common 128-bit block operations
+ * 
+ * Copyright (c) 2003, Dr Brian Gladman, Worcester, UK.
+ * Copyright (c) 2006, Rik Snel <[email protected]>
+ *
+ * Based on Dr Brain Gladman's (GPL'd) work published at
+ * http://fp.gladman.plus.com/cryptography_technology/index.htm
+ * See the original copyright notice below.
+ *
+ * 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.
+ */
+/*
+ ---------------------------------------------------------------------------
+ Copyright (c) 2003, Dr Brian Gladman, Worcester, UK.   All rights reserved.
+
+ LICENSE TERMS
+
+ The free distribution and use of this software in both source and binary
+ form is allowed (with or without changes) provided that:
+
+   1. distributions of this source code include the above copyright
+      notice, this list of conditions and the following disclaimer;
+
+   2. distributions in binary form include the above copyright
+      notice, this list of conditions and the following disclaimer
+      in the documentation and/or other associated materials;
+
+   3. the copyright holder's name is not used to endorse products
+      built using this software without specific written permission.
+
+ ALTERNATIVELY, provided that this notice is retained in full, this product
+ may be distributed under the terms of the GNU General Public License (GPL),
+ in which case the provisions of the GPL apply INSTEAD OF those given above.
+
+ DISCLAIMER
+
+ This software is provided 'as is' with no explicit or implied warranties
+ in respect of its properties, including, but not limited to, correctness
+ and/or fitness for purpose.
+ ---------------------------------------------------------------------------
+ Issue Date: 13/06/2006
+*/
+
+#ifndef _LINUX_B128OPS_H
+#define _LINUX_B128OPS_H
+
+#include <linux/byteorder/swab.h>
+
+/* watch out: for good performance p and q must be aligned to 32bit
+ * boundaries on a 32bit machine and to 64bit boundaries on a 64bit 
+ * machine. */
+inline void b128ops_mov(void *p, const void *q)
+{
+	((u64*)p)[0] = ((u64*)q)[0];
+	((u64*)p)[1] = ((u64*)q)[1];
+}
+
+inline void b128ops_xor(void *p, const void *q)
+{
+	((u64*)p)[0] ^= ((u64*)q)[0];
+	((u64*)p)[1] ^= ((u64*)q)[1];
+}
+
+inline void bswap64_block(void* d, const void* s, u32 n)
+{ 
+    while(n--) ((u64*)d)[n] = __swab64(((u64*)s)[n]);
+}
+
+#endif /* _LINUX_B128OPS_H */
Signature · 1 line
1.4.1.1
author
#4 lore raw

PATCH 4/6 crypto: table driven multiplications in GF(2^128), needed by LRW (and in the future ABL)

In reply to Rik Snel

WARNING: untested on bigendian, please test.

A lot of cypher modes need multiplications in GF(2^128). LRW, ABL, GCM... I use functions from this library in my LRW implementation and I will also use them in my ABL (Arbitrary Block Length, an unencumbered (correct me if I am wrong, wide block cipher mode).

Elements of GF(2^128) must be presented as u64* (specifically u64[2]), it encourages automatic and proper alignment.

The library contains support for two different representations of GF(2^128), see the comment in gf128mul.h. There different levels of optimization (memory/speed tradeoff).

The code is based on work by Dr Brian Gladman. Notable changes:
- deletion of two optimization modes
- change from u32 to u64 for faster handling on 64bit machines
- support for 'bbe' representation in addition to the, already implemented, 'lle' representation.
- move 'inline void' functions from header to 'static void' in the source file
- update to use the linux coding style conventions

The original can be found at:
http://fp.gladman.plus.com/AES/modes.vc8.19-06-06.zip

The copyright (and GPL statement) of the original author is preserved.

---
 crypto/Kconfig    |   11 +
 crypto/Makefile   |    1 
 crypto/gf128mul.c |  401 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 crypto/gf128mul.h |  196 ++++++++++++++++++++++++++
 4 files changed, 609 insertions(+), 0 deletions(-)
crypto/Kconfig +11 -0
index 1e2f39c..6b23c20 100644
@@ -128,6 +128,17 @@ config CRYPTO_TGR192
 	  See also:
 	  <http://www.cs.technion.ac.il/~biham/Reports/Tiger/>.
 
+config CRYPTO_GF128MUL
+	tristate "GF(2^128) multiplication functions (EXPERIMENTAL)"
+	depends on EXPERIMENTAL
+	default n
+	help
+	  Efficient table driven implementation of multiplications in the
+	  field GF(2^128). This is needed by some cypher modes. This
+	  option will be selected automatically if you select such a
+	  cipher mode. Only select this option by hand if you expect to load
+	  an external module that requires these functions.
+
 config CRYPTO_ECB
 	tristate "ECB support"
 	select CRYPTO_BLKCIPHER
crypto/Makefile +1 -0
index 7236620..bf0406b 100644
@@ -23,6 +23,7 @@ obj-$(CONFIG_CRYPTO_SHA256) += sha256.o
 obj-$(CONFIG_CRYPTO_SHA512) += sha512.o
 obj-$(CONFIG_CRYPTO_WP512) += wp512.o
 obj-$(CONFIG_CRYPTO_TGR192) += tgr192.o
+obj-$(CONFIG_CRYPTO_GF128MUL) += gf128mul.o
 obj-$(CONFIG_CRYPTO_ECB) += ecb.o
 obj-$(CONFIG_CRYPTO_CBC) += cbc.o
 obj-$(CONFIG_CRYPTO_DES) += des.o
crypto/gf128mul.c new file +401 -0

401 lines not on this page · raw message

crypto/gf128mul.h new file +196 -0

196 lines not on this page · raw message

Signature · 1 line
1.4.1.1
author
#5 lore raw

PATCH 5/6 crypto: LRW, Liskov Rivest Wagner, a tweakable narrow block cipher mode

In reply to Rik Snel

Main module, this implements the Liskov Rivest Wagner block cipher mode in the new blockcipher API. The implementation is based on ecb.c. The first iteration of the blockcipher_walk loop is unrolled to give the first narrow block special treatment.

The LRW-32-AES specification I used can be found at:

http://grouper.ieee.org/groups/1619/email/pdf00017.pdf

It implements the optimization specified as optional in the specification, and in addition it uses optimized multiplication routines from gf128mul.c.

Since gf128mul.[ch] is not tested on bigendian, this cipher mode may currently fail badly on bigendian machines.

---
 crypto/Kconfig  |   13 ++
 crypto/Makefile |    1 
 crypto/lrw.c    |  297 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 311 insertions(+), 0 deletions(-)
crypto/Kconfig +13 -0
index 6b23c20..dfdfe08 100644
@@ -156,6 +156,19 @@ config CRYPTO_CBC
 	  CBC: Cipher Block Chaining mode
 	  This block cipher algorithm is required for IPSec.
 
+config CRYPTO_LRW
+	tristate "LRW support (EXPERIMENTAL)"
+	depends on EXPERIMENTAL
+	select CRYPTO_BLKCIPHER
+	select CRYPTO_GF128MUL
+	default n
+	help
+	  LRW: Liskov Rivest Wagner, a tweakable, non malleable, non movable
+	  narrow block cipher mode. Use it with cipher specification string
+	  aes-lrw-benbi, the key must be 256, 320 or 384. The first 128, 192
+	  or 256 bits in the key are used for AES and the rest is used to tie
+	  each cipher block to its logical position.
+
 config CRYPTO_DES
 	tristate "DES and Triple DES EDE cipher algorithms"
 	select CRYPTO_ALGAPI
crypto/Makefile +1 -0
index bf0406b..e2e57be 100644
@@ -26,6 +26,7 @@ obj-$(CONFIG_CRYPTO_TGR192) += tgr192.o
 obj-$(CONFIG_CRYPTO_GF128MUL) += gf128mul.o
 obj-$(CONFIG_CRYPTO_ECB) += ecb.o
 obj-$(CONFIG_CRYPTO_CBC) += cbc.o
+obj-$(CONFIG_CRYPTO_LRW) += lrw.o
 obj-$(CONFIG_CRYPTO_DES) += des.o
 obj-$(CONFIG_CRYPTO_BLOWFISH) += blowfish.o
 obj-$(CONFIG_CRYPTO_TWOFISH) += twofish.o
crypto/lrw.c new file +297 -0

297 lines not on this page · raw message

Signature · 1 line
1.4.1.1
author
#6 lore raw

PATCH 6/6 crypto: a simple way of storing and checking test vectors, LRW vectors included

In reply to Rik Snel

Test vectors for LRW and a simple way of checking them. For your convenience and/or for real inclusion.

---
 Documentation/crypto/README.testvector |    7 ++
 Documentation/crypto/lrw-32-aes        |  113 ++++++++++++++++++++++++++++++++
 Documentation/crypto/testvector.fun    |   57 ++++++++++++++++
 3 files changed, 177 insertions(+), 0 deletions(-)
Documentation/crypto/README.testvector new file +7 -0
new file mode 100644
index 0000000..2d4a0f0
@@ -0,0 +1,7 @@
+How to check the testvectors included in ./lrw-32-aes?
+
+Simply execute them; lrw-32-aes is a bash script that calls some functions
+in testvector.fun. Tools like dm-setup and some hex utitities will be used 
+to check them through the usual kernel interface. You can add testvectors of
+other modes in an analogous manner.
+
Documentation/crypto/lrw-32-aes new file +113 -0

113 lines not on this page · raw message

Documentation/crypto/testvector.fun new file +57 -0

57 lines not on this page · raw message

Signature · 1 line
1.4.1.1
maintainer
#7 lore raw
In reply to Rik Snel

Hi Rik:

Quoted 3 lines · Rik Snel

This is an attempt at implementing LRW for the new blockcipher API. Please review, test and comment.

Thanks a lot for doing this. It looks good to me.

There are a few style (see Documentation/CodingStyle) issues. It would be good if you can fix them up before I apply the patches.

Could you also convert the test vectors to use tcrypt.h/tcrypt.c?

Cheers,

Signature · 4 lines
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
#8 lore raw

Hello,

Quoted 5 lines · Herbert Xu
Quoted 2 lines · Rik Snel

This is an attempt at implementing LRW for the new blockcipher API. Please review, test and comment.

Thanks a lot for doing this. It looks good to me.

That's good to hear.

Quoted 2 lines

There are a few style (see Documentation/CodingStyle) issues. It would be good if you can fix them up before I apply the patches.

Can you give some examples about what I missed from CodingStyle? (I just reread it and I think my patch adheres pretty well to those
rules: tabs=8, K&R bracing, don't pollute global namespace etc...)

Quoted 1 line

Could you also convert the test vectors to use tcrypt.h/tcrypt.c?

Yes, I just didn't know what tcrypt.[ch] was for, otherwise I would have put those vectors there in the first place. The last testvector, however, won't fit because it is an entire 512 byte sector. (which is not that bad, because alle narrow blocks (16 bytes) are encrypted independently, no realistic testvector of a wide block cipher mode would fit. (ABL uses blocks of any size, say 512 bytes, and if 1 bit changes in the plaintext block, the whole cypher block will be affected) I will propose something to fix that if ABL is finished.

Greetings,

Rik.

Signature · 1 line
Nothing is ever a total loss; it can always serve as a bad example.
maintainer
#9 lore raw
Quoted 4 lines · On Fri, Sep 01, 2006 at 10:55:14AM +0200, [email protected] wrote:

Can you give some examples about what I missed from CodingStyle? (I just reread it and I think my patch adheres pretty well to those
rules: tabs=8, K&R bracing, don't pollute global namespace etc...)

It's only a few spots:

* Space before * for pointers, e.g., (u64 *) instead of (u64*).
* There is one line near the end b128ops.h that starts with spaces.
* Some lines terminate with spaces.

The last two issues can be caught if you test your patch with

git apply --check --whitespace=error-all diff

Quoted 8 lines

Yes, I just didn't know what tcrypt.[ch] was for, otherwise I would have put those vectors there in the first place. The last testvector, however, won't fit because it is an entire 512 byte sector. (which is not that bad, because alle narrow blocks (16 bytes) are encrypted independently, no realistic testvector of a wide block cipher mode would fit. (ABL uses blocks of any size, say 512 bytes, and if 1 bit changes in the plaintext block, the whole cypher block will be affected) I will propose something to fix that if ABL is finished.

Feel free to extend the tcrypt cipher test buffer to 512 bytes.

Cheers,

Signature · 4 lines
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
#10 lore raw

Re: LRW... v2

Hello Herbert/list,

Here is the updated version of my LRW patch set.

Greetings,

Rik.

Signature · 1 line
VGER BF report: U 0.476584
maintainer
#11 lore raw

Re: LRW... v2

Quoted 2 lines · On Sat, Sep 02, 2006 at 03:00:21AM +0200, [email protected] wrote:

Here is the updated version of my LRW patch set.

All patches merged and pushed into cryptodev-2.6.

Thanks again!

Signature · 4 lines
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
#12 lore raw

PATCH v2 1/6 crypto: trivial comment improvements

In reply to Herbert Xu

From: Rik Snel <[email protected]>

Just some minor comment nits.

- little-endian is better than low-endian
- and since it is called essiv everywere it should also be essiv in the comments (and not ess_iv)

---
 drivers/md/dm-crypt.c |    8 ++++----
 1 files changed, 4 insertions(+), 4 deletions(-)
drivers/md/dm-crypt.c +4 -4
index 91d4081..06961f7 100644
@@ -99,12 +99,12 @@ static kmem_cache_t *_crypt_io_pool;
 /*
  * Different IV generation algorithms:
  *
- * plain: the initial vector is the 32-bit low-endian version of the sector
+ * plain: the initial vector is the 32-bit little-endian version of the sector
  *        number, padded with zeros if neccessary.
  *
- * ess_iv: "encrypted sector|salt initial vector", the sector number is
- *         encrypted with the bulk cipher using a salt as key. The salt
- *         should be derived from the bulk cipher's key via hashing.
+ * essiv: "encrypted sector|salt initial vector", the sector number is
+ *        encrypted with the bulk cipher using a salt as key. The salt
+ *        should be derived from the bulk cipher's key via hashing.
  *
  * plumb: unimplemented, see:
  * http://article.gmane.org/gmane.linux.kernel.device-mapper.dm-crypt/454
Signature · 5 lines
1.4.1.1


-- 
VGER BF report: U 0.496196
#13 lore raw

PATCH v2 2/6 crypto: benbi IV, big endian narrow block count for LRW-32-AES

In reply to Herbert Xu

From: Rik Snel <[email protected]>

LRW-32-AES needs a certain IV. This IV should be provided dm-crypt. The block cipher mode could, in principle generate the correct IV from the plain IV, but I think that it is cleaner to supply the right IV directly.

The sector -> narrow block calculation uses a shift for performance reasons. This shift is computed in .ctr and stored in cc->iv_gen_private (as a void*).

---
 drivers/md/dm-crypt.c |   56 ++++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 55 insertions(+), 1 deletions(-)
drivers/md/dm-crypt.c +55 -1
index 06961f7..df399d6 100644
@@ -106,6 +106,9 @@ static kmem_cache_t *_crypt_io_pool;
  *        encrypted with the bulk cipher using a salt as key. The salt
  *        should be derived from the bulk cipher's key via hashing.
  *
+ * benbi: the 64-bit "big-endian 'narrow block'-count", starting at 1
+ * 	  (needed for LRW-32-AES and possible other narrow block modes)
+ *
  * plumb: unimplemented, see:
  * http://article.gmane.org/gmane.linux.kernel.device-mapper.dm-crypt/454
  */
@@ -200,6 +203,49 @@ static int crypt_iv_essiv_gen(struct cry
 	return 0;
 }
 
+static int crypt_iv_benbi_ctr(struct crypt_config *cc, struct dm_target *ti,
+			      const char *opts)
+{
+	unsigned int bs = crypto_blkcipher_blocksize(cc->tfm);
+	int log = long_log2(bs);
+
+	/* we need to calculate how far we must shift the sector count
+	 * to get the cipher block count, we use this shift in _gen */
+
+	if (1 << log != bs) {
+		ti->error = "cypher blocksize is not a power of 2";
+		return -EINVAL;
+	}
+
+	if (log > 9) {
+		ti->error = "cypher blocksize is > 512";
+		return -EINVAL;
+	}
+
+	if (crypto_blkcipher_ivsize(cc->tfm) < sizeof(u64)) {
+		ti->error = "cypher ivsize is < 8";
+		return -EINVAL;
+	}
+
+	cc->iv_gen_private = (void *)(9 - log);
+
+	return 0;
+}
+
+static void crypt_iv_benbi_dtr(struct crypt_config *cc)
+{
+	cc->iv_gen_private = NULL;
+}
+
+static int crypt_iv_benbi_gen(struct crypt_config *cc, u8 *iv, sector_t sector)
+{
+	memset(iv, 0, cc->iv_size - sizeof(u64)); /* rest is cleared below */
+	*(u64 *)(iv + cc->iv_size - sizeof(u64)) =
+		cpu_to_be64(((u64)sector << (u32)cc->iv_gen_private) + 1);
+
+	return 0;
+}
+
 static struct crypt_iv_operations crypt_iv_plain_ops = {
 	.generator = crypt_iv_plain_gen
 };
@@ -210,6 +256,11 @@ static struct crypt_iv_operations crypt_
 	.generator = crypt_iv_essiv_gen
 };
 
+static struct crypt_iv_operations crypt_iv_benbi_ops = {
+	.ctr	   = crypt_iv_benbi_ctr,
+	.dtr	   = crypt_iv_benbi_dtr,
+	.generator = crypt_iv_benbi_gen
+};
 
 static int
 crypt_convert_scatterlist(struct crypt_config *cc, struct scatterlist *out,
@@ -579,7 +630,8 @@ static int crypt_ctr(struct dm_target *t
 	cc->tfm = tfm;
 
 	/*
-	 * Choose ivmode. Valid modes: "plain", "essiv:<esshash>".
+	 * Choose ivmode. Valid modes: "plain", "essiv:<esshash>", "benbi".
+	 *
 	 * See comments at iv code
 	 */
 
@@ -589,6 +641,8 @@ static int crypt_ctr(struct dm_target *t
 		cc->iv_gen_ops = &crypt_iv_plain_ops;
 	else if (strcmp(ivmode, "essiv") == 0)
 		cc->iv_gen_ops = &crypt_iv_essiv_ops;
+	else if (strcmp(ivmode, "benbi") == 0)
+		cc->iv_gen_ops = &crypt_iv_benbi_ops;
 	else {
 		ti->error = "Invalid IV mode";
 		goto bad2;
Signature · 5 lines
1.4.1.1


-- 
VGER BF report: U 0.499935
#14 lore raw

PATCH v2 3/6 crypto: some common 128-bit block operations, nicely centralized

In reply to Herbert Xu

From: Rik Snel <[email protected]>

128bit is a common blocksize in linux kernel cryptography, so it helps to centralize some common operations. The data must be aligned at sizeof(int) for decent performance.

The code, while mostly trivial, is based on a header file mode_hdr.h in
http://fp.gladman.plus.com/AES/modes.vc8.19-06-06.zip

The original copyright (and GPL statement) of the original author, Dr Brian Gladman, is preserved.

---
 crypto/b128ops.h |   72 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 72 insertions(+), 0 deletions(-)
crypto/b128ops.h new file +72 -0
new file mode 100644
index 0000000..73d8a5f
@@ -0,0 +1,72 @@
+/* b128ops.h - common 128-bit block operations
+ *
+ * Copyright (c) 2003, Dr Brian Gladman, Worcester, UK.
+ * Copyright (c) 2006, Rik Snel <[email protected]>
+ *
+ * Based on Dr Brian Gladman's (GPL'd) work published at
+ * http://fp.gladman.plus.com/cryptography_technology/index.htm
+ * See the original copyright notice below.
+ *
+ * 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.
+ */
+/*
+ ---------------------------------------------------------------------------
+ Copyright (c) 2003, Dr Brian Gladman, Worcester, UK.   All rights reserved.
+
+ LICENSE TERMS
+
+ The free distribution and use of this software in both source and binary
+ form is allowed (with or without changes) provided that:
+
+   1. distributions of this source code include the above copyright
+      notice, this list of conditions and the following disclaimer;
+
+   2. distributions in binary form include the above copyright
+      notice, this list of conditions and the following disclaimer
+      in the documentation and/or other associated materials;
+
+   3. the copyright holder's name is not used to endorse products
+      built using this software without specific written permission.
+
+ ALTERNATIVELY, provided that this notice is retained in full, this product
+ may be distributed under the terms of the GNU General Public License (GPL),
+ in which case the provisions of the GPL apply INSTEAD OF those given above.
+
+ DISCLAIMER
+
+ This software is provided 'as is' with no explicit or implied warranties
+ in respect of its properties, including, but not limited to, correctness
+ and/or fitness for purpose.
+ ---------------------------------------------------------------------------
+ Issue Date: 13/06/2006
+*/
+
+#ifndef _LINUX_B128OPS_H
+#define _LINUX_B128OPS_H
+
+#include <linux/byteorder/swab.h>
+
+/* watch out: for good performance p and q must be aligned to 32bit
+ * boundaries on a 32bit machine and to 64bit boundaries on a 64bit
+ * machine. */
+inline void b128ops_mov(void *p, const void *q)
+{
+	((u64 *)p)[0] = ((u64 *)q)[0];
+	((u64 *)p)[1] = ((u64 *)q)[1];
+}
+
+inline void b128ops_xor(void *p, const void *q)
+{
+	((u64 *)p)[0] ^= ((u64 *)q)[0];
+	((u64 *)p)[1] ^= ((u64 *)q)[1];
+}
+
+inline void bswap64_block(void *d, const void *s, u32 n)
+{
+	while(n--) ((u64 *)d)[n] = __swab64(((u64 *)s)[n]);
+}
+
+#endif /* _LINUX_B128OPS_H */
Signature · 5 lines
1.4.1.1


-- 
VGER BF report: U 0.5
#15 lore raw

PATCH v2 4/6 crypto: table driven multiplications in GF(2^128), needed by LRW (and in the future ABL)

In reply to Herbert Xu

From: Rik Snel <[email protected]>

WARNING: untested on bigendian, please test.

A lot of cypher modes need multiplications in GF(2^128). LRW, ABL, GCM... I use functions from this library in my LRW implementation and I will also use them in my ABL (Arbitrary Block Length, an unencumbered (correct me if I am wrong, wide block cipher mode).

Elements of GF(2^128) must be presented as u64 * (specifically u64[2]), it encourages automatic and proper alignment.

The library contains support for two different representations of GF(2^128), see the comment in gf128mul.h. There different levels of optimization (memory/speed tradeoff).

The code is based on work by Dr Brian Gladman. Notable changes:
- deletion of two optimization modes
- change from u32 to u64 for faster handling on 64bit machines
- support for 'bbe' representation in addition to the, already implemented, 'lle' representation.
- move 'inline void' functions from header to 'static void' in the source file
- update to use the linux coding style conventions

The original can be found at:
http://fp.gladman.plus.com/AES/modes.vc8.19-06-06.zip

The copyright (and GPL statement) of the original author is preserved.

---
 crypto/Kconfig    |   11 +
 crypto/Makefile   |    1 
 crypto/gf128mul.c |  401 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 crypto/gf128mul.h |  196 ++++++++++++++++++++++++++
 4 files changed, 609 insertions(+), 0 deletions(-)
crypto/Kconfig +11 -0
index 1e2f39c..6b23c20 100644
@@ -128,6 +128,17 @@ config CRYPTO_TGR192
 	  See also:
 	  <http://www.cs.technion.ac.il/~biham/Reports/Tiger/>.
 
+config CRYPTO_GF128MUL
+	tristate "GF(2^128) multiplication functions (EXPERIMENTAL)"
+	depends on EXPERIMENTAL
+	default n
+	help
+	  Efficient table driven implementation of multiplications in the
+	  field GF(2^128). This is needed by some cypher modes. This
+	  option will be selected automatically if you select such a
+	  cipher mode. Only select this option by hand if you expect to load
+	  an external module that requires these functions.
+
 config CRYPTO_ECB
 	tristate "ECB support"
 	select CRYPTO_BLKCIPHER
crypto/Makefile +1 -0
index 7236620..bf0406b 100644
@@ -23,6 +23,7 @@ obj-$(CONFIG_CRYPTO_SHA256) += sha256.o
 obj-$(CONFIG_CRYPTO_SHA512) += sha512.o
 obj-$(CONFIG_CRYPTO_WP512) += wp512.o
 obj-$(CONFIG_CRYPTO_TGR192) += tgr192.o
+obj-$(CONFIG_CRYPTO_GF128MUL) += gf128mul.o
 obj-$(CONFIG_CRYPTO_ECB) += ecb.o
 obj-$(CONFIG_CRYPTO_CBC) += cbc.o
 obj-$(CONFIG_CRYPTO_DES) += des.o
crypto/gf128mul.c new file +401 -0

401 lines not on this page · raw message

crypto/gf128mul.h new file +196 -0

196 lines not on this page · raw message

Signature · 5 lines
1.4.1.1


-- 
VGER BF report: U 0.5
maintainer
#16 lore raw

Re: [PATCHv2 4/6] crypto: table driven multiplications in GF(2^128), needed by LRW (and in the future ABL)

Review

Quoted 10 lines · On Sat, Sep 02, 2006 at 03:00:25AM +0200, [email protected] wrote:
(quoted diff) +9 -0
+#define M80X	0x8080808080808080LLU
+#define M01X	0x0101010101010101LLU
+
+static void gf128mul_x_lle(u64 r[2], const u64 x[2])
+{
+	u64  _tt = gf128mul_table_lle[(x[1] >> 49) & 0x80];
+	r[1] =  ((x[1] >> 1) & ~M80X) | (((x[1] << 15) | (x[0] >> 49)) & M80X);
+	r[0] = (((x[0] >> 1) & ~M80X) |  ((x[0] << 15) & M80X)) ^ _tt;
+}

Hi Rik:

Sorry it took so long. But I've been trying to modify the code so that the same source is used for both BE and LE machines. I've finally accumulated enough time to finish it.

Unfortunately it seems that the end result doesn't quite agree with your test vectors :) In particular, the LE version of your mul_x and mul_x8 functions don't agree with mine.

Could you please compare the two versions and double-check them? I'm unsure why 15 was used above as a shift count. It would seem that 7 would seem to make more sense as endianness is byte-based not word-based.

I've attached my version of gf128mul which is based on your BE code.

The other main change I've made is to remove the need to allocate a contiguous 64K table in gf128mul. Requiring every tfm to allocate a contiguous 64K chunk of memory is not realistic on Linux.

I also added a be128/le128/u128 type to make 128-bit operations easier.

Thanks,

Signature · 7 lines
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
--

0c3bbb342495d510631b11c45a70d55fc83afe3f
crypto/Kconfig +10 -0
index 34f10d5..0a4ff51 100644
@@ -139,6 +139,16 @@ config CRYPTO_TGR192
 	  See also:
 	  <http://www.cs.technion.ac.il/~biham/Reports/Tiger/>.
 
+config CRYPTO_GF128MUL
+	tristate "GF(2^128) multiplication functions (EXPERIMENTAL)"
+	depends on EXPERIMENTAL
+	help
+	  Efficient table driven implementation of multiplications in the
+	  field GF(2^128).  This is needed by some cypher modes. This
+	  option will be selected automatically if you select such a
+	  cipher mode.  Only select this option by hand if you expect to load
+	  an external module that requires these functions.
+
 config CRYPTO_ECB
 	tristate "ECB support"
 	select CRYPTO_BLKCIPHER
crypto/Makefile +1 -0
index e94bb1b..76970de 100644
@@ -24,6 +24,7 @@ obj-$(CONFIG_CRYPTO_SHA256) += sha256.o
 obj-$(CONFIG_CRYPTO_SHA512) += sha512.o
 obj-$(CONFIG_CRYPTO_WP512) += wp512.o
 obj-$(CONFIG_CRYPTO_TGR192) += tgr192.o
+obj-$(CONFIG_CRYPTO_GF128MUL) += gf128mul.o
 obj-$(CONFIG_CRYPTO_ECB) += ecb.o
 obj-$(CONFIG_CRYPTO_CBC) += cbc.o
 obj-$(CONFIG_CRYPTO_DES) += des.o
crypto/gf128mul.c new file +466 -0

466 lines not on this page · raw message

include/crypto/gf128mul.h new file +198 -0

198 lines not on this page · raw message

#17 lore raw

Re: [PATCHv2 4/6] crypto: table driven multiplications in GF(2^128), needed by LRW (and in the future ABL)

Hello Herbert,

Quoted 5 lines · Herbert Xu

On Sat, Sep 02, 2006 at 03:00:25AM +0200, [email protected] wrote:

Sorry it took so long. But I've been trying to modify the code so that the same source is used for both BE and LE machines. I've finally accumulated enough time to finish it.

It's OK. The source will be more maintainable, but constantly converting between big and little-endian (on little endian machines) may have a significant performance impact (I will just test when your gf128 hits cryptodev-2.6, and complain if it is the case).

Two more remarks (errors in v2 of my patch): b128ops.h and gf128mul.h should be in include/ (so they can be used in modules) and the inline functions in b128ops.h should also be static.

Quoted 9 lines

Unfortunately it seems that the end result doesn't quite agree with your test vectors :) In particular, the LE version of your mul_x and mul_x8 functions don't agree with mine.

Could you please compare the two versions and double-check them? I'm unsure why 15 was used above as a shift count. It would seem that 7 would seem to make more sense as endianness is byte-based not word-based.

Quoted 1 line
Quoted 9 lines

Review

Quoted 9 lines
(quoted diff) +9 -0
+#define M80X	0x8080808080808080LLU
+#define M01X	0x0101010101010101LLU
+
+static void gf128mul_x_lle(u64 r[2], const u64 x[2])
+{
+	u64  _tt = gf128mul_table_lle[(x[1] >> 49) & 0x80];
+	r[1] =  ((x[1] >> 1) & ~M80X) | (((x[1] << 15) | (x[0] >> 49)) & M80X);
+	r[0] = (((x[0] >> 1) & ~M80X) |  ((x[0] << 15) & M80X)) ^ _tt;
+}

I'll try to explain why I think the above code is correct:
As in my comment in gf128mul.h, lle means the polynomials in gf127 are stored in little-little-endian format. So
10000000 00000000 .. 00000000 = 0x80 0x00 .. 0x00 = 1
01000000 00000000 .. 00000000 = 0x40 0x00 .. 0x00 = X^1 01010001 00000000 .. 10000000 = 0x51 0x00 .. 0x80 = X^1 + X^3 + X^7 + X^120 00000000 00000000 .. 00000001 = 0x00 0x00 .. 0x01 = X^127

The u64 type emulates a little endian 64bit processor (on my 32bit intel) so when we load the these examples in two 64bit little endian integers they are:
0x0000000000000080 0x0000000000000000 = 1 0x0000000000000040 0x0000000000000000 = X^1 0x0000000000000051 0x8000000000000000 = X^1 + X^3 + X^7 + X^120 0x0000000000000000 0x0100000000000000 = X^127

Let's multiply the third example by X, we should get
00101000 10000000 .. 01000000 = 0x28 0x80 .. 0x40 = X^2 + X^4 + X^8 + X^121

Represented as two little endian 64 bit values:
0x0000000000008028 0x4000000000000000

The above code implements this shift (efficiently?) by noting:
in each byte bit 1 moves to bit 0, bit 2 moves to bit 1, ..., bit 7 moves to bit 6 and all 7th bits are zeroed afterwards.
(this is done by ((x[1] >> 1) & ~M80X)), the 7th bits are set by moving the least significant bits of the bytes to the right position (15 bits to the left) and orring.

Let's look at the example: the first 8 in 0x0...008028 comes from the least significant bit of 0x00.00051. So the shift by 15 to get the 7th bit of every byte right is correct. (I have included a simple program to compare the different implementations)

Quoted 2 lines

I've attached my version of gf128mul which is based on your BE code.

Ok, will comment.

Quoted 4 lines

The other main change I've made is to remove the need to allocate a contiguous 64K table in gf128mul. Requiring every tfm to allocate a contiguous 64K chunk of memory is not realistic on Linux.

Ok.

Quoted 2 lines

I also added a be128/le128/u128 type to make 128-bit operations easier.

I assume it is: typedef struct { u64 a, u64 b } be128;
As long as compilers don't do u128 natively it is just a matter of taste.

Quoted 2 lines

[...]
+#define xx(p, q) __constant_be16_to_cpu(0x##p##q)

This seems to be the problem, the table is constructed wrongly. All the calculations take place as if we are on a big endian machine, so the table entries should never be swapped, so the above line should read

+#define xx(p, q) 0x##p##q

While investigating the problem, I wrote a small program to compare a bytewise implementation with Brian's and your implementation of mul_x, it only works in the lle implementation.

Once I found this problem, I stopped looking, so let me know if the test vectors still don't match up, then I will need to take a closer look.

Greetings,

Rik.

/* test program for mutiplying by X in GF(2^128) in lle representation
* on a little endian machine. */
/* GNU GPL >= v2 applies, (C) Brian Gladman, Herbert Xu, Rik Snel. */ #include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>
#include <byteswap.h>

typedef uint64_t u64;
typedef uint16_t u16;

typedef struct {
	u64 a;
	u64 b;
} be128;
#define gf128mul_dat(q) { \
        q(0x00), q(0x01), q(0x02), q(0x03), q(0x04), q(0x05), q(0x06), q(0x07),\
        q(0x08), q(0x09), q(0x0a), q(0x0b), q(0x0c), q(0x0d), q(0x0e), q(0x0f),\
        q(0x10), q(0x11), q(0x12), q(0x13), q(0x14), q(0x15), q(0x16), q(0x17),\
        q(0x18), q(0x19), q(0x1a), q(0x1b), q(0x1c), q(0x1d), q(0x1e), q(0x1f),\
        q(0x20), q(0x21), q(0x22), q(0x23), q(0x24), q(0x25), q(0x26), q(0x27),\
        q(0x28), q(0x29), q(0x2a), q(0x2b), q(0x2c), q(0x2d), q(0x2e), q(0x2f),\
        q(0x30), q(0x31), q(0x32), q(0x33), q(0x34), q(0x35), q(0x36), q(0x37),\
        q(0x38), q(0x39), q(0x3a), q(0x3b), q(0x3c), q(0x3d), q(0x3e), q(0x3f),\
        q(0x40), q(0x41), q(0x42), q(0x43), q(0x44), q(0x45), q(0x46), q(0x47),\
        q(0x48), q(0x49), q(0x4a), q(0x4b), q(0x4c), q(0x4d), q(0x4e), q(0x4f),\
        q(0x50), q(0x51), q(0x52), q(0x53), q(0x54), q(0x55), q(0x56), q(0x57),\
        q(0x58), q(0x59), q(0x5a), q(0x5b), q(0x5c), q(0x5d), q(0x5e), q(0x5f),\
        q(0x60), q(0x61), q(0x62), q(0x63), q(0x64), q(0x65), q(0x66), q(0x67),\
        q(0x68), q(0x69), q(0x6a), q(0x6b), q(0x6c), q(0x6d), q(0x6e), q(0x6f),\
        q(0x70), q(0x71), q(0x72), q(0x73), q(0x74), q(0x75), q(0x76), q(0x77),\
        q(0x78), q(0x79), q(0x7a), q(0x7b), q(0x7c), q(0x7d), q(0x7e), q(0x7f),\
        q(0x80), q(0x81), q(0x82), q(0x83), q(0x84), q(0x85), q(0x86), q(0x87),\
        q(0x88), q(0x89), q(0x8a), q(0x8b), q(0x8c), q(0x8d), q(0x8e), q(0x8f),\
        q(0x90), q(0x91), q(0x92), q(0x93), q(0x94), q(0x95), q(0x96), q(0x97),\
        q(0x98), q(0x99), q(0x9a), q(0x9b), q(0x9c), q(0x9d), q(0x9e), q(0x9f),\
        q(0xa0), q(0xa1), q(0xa2), q(0xa3), q(0xa4), q(0xa5), q(0xa6), q(0xa7),\
        q(0xa8), q(0xa9), q(0xaa), q(0xab), q(0xac), q(0xad), q(0xae), q(0xaf),\
        q(0xb0), q(0xb1), q(0xb2), q(0xb3), q(0xb4), q(0xb5), q(0xb6), q(0xb7),\
        q(0xb8), q(0xb9), q(0xba), q(0xbb), q(0xbc), q(0xbd), q(0xbe), q(0xbf),\
        q(0xc0), q(0xc1), q(0xc2), q(0xc3), q(0xc4), q(0xc5), q(0xc6), q(0xc7),\
        q(0xc8), q(0xc9), q(0xca), q(0xcb), q(0xcc), q(0xcd), q(0xce), q(0xcf),\
        q(0xd0), q(0xd1), q(0xd2), q(0xd3), q(0xd4), q(0xd5), q(0xd6), q(0xd7),\
        q(0xd8), q(0xd9), q(0xda), q(0xdb), q(0xdc), q(0xdd), q(0xde), q(0xdf),\
        q(0xe0), q(0xe1), q(0xe2), q(0xe3), q(0xe4), q(0xe5), q(0xe6), q(0xe7),\
        q(0xe8), q(0xe9), q(0xea), q(0xeb), q(0xec), q(0xed), q(0xee), q(0xef),\
        q(0xf0), q(0xf1), q(0xf2), q(0xf3), q(0xf4), q(0xf5), q(0xf6), q(0xf7),\
        q(0xf8), q(0xf9), q(0xfa), q(0xfb), q(0xfc), q(0xfd), q(0xfe), q(0xff) \
}

#define xxle(p,q) 0x##q##p /* assemble in little endian order */
#define xxbe(p,q) 0x##p##q /* assemble in big endian order */

#define xda_lle_le(i) ( \
    (i&0x80?xxle(e1,00):0)^(i&0x40?xxle(70,80):0)^ \
    (i&0x20?xxle(38,40):0)^(i&0x10?xxle(1c,20):0)^ \
    (i&0x08?xxle(0e,10):0)^(i&0x04?xxle(07,08):0)^ \
    (i&0x02?xxle(03,84):0)^(i&0x01?xxle(01,c2):0) \

)

#define xda_lle_be(i) ( \
    (i&0x80?xxbe(e1,00):0)^(i&0x40?xxbe(70,80):0)^ \
    (i&0x20?xxbe(38,40):0)^(i&0x10?xxbe(1c,20):0)^ \
    (i&0x08?xxbe(0e,10):0)^(i&0x04?xxbe(07,08):0)^ \
    (i&0x02?xxbe(03,84):0)^(i&0x01?xxbe(01,c2):0) \

)

static const u16 gf128mul_table_lle_le[256] = gf128mul_dat(xda_lle_le); static const u16 gf128mul_table_lle_be[256] = gf128mul_dat(xda_lle_be);

/* simple straightforward implementation, does not depend
* on machine endianness */

void mul_x_lle_simple(be128 *result, const be128 *ex) {
	unsigned char *r = (unsigned char*)result;
	const unsigned char *x = (unsigned char*)ex;
	u64 overflow = 0xE1*(x[15]&0x01); /* do we get X^128 ? */
	r[15] = x[15]>>1|x[14]<<7;
	r[14] = x[14]>>1|x[13]<<7;
	r[13] = x[13]>>1|x[12]<<7;
	r[12] = x[12]>>1|x[11]<<7;
	r[11] = x[11]>>1|x[10]<<7;
	r[10] = x[10]>>1|x[9]<<7;
	r[9] = x[9]>>1|x[8]<<7;
	r[8] = x[8]>>1|x[7]<<7;
	r[7] = x[7]>>1|x[6]<<7;
	r[6] = x[6]>>1|x[5]<<7;
	r[5] = x[5]>>1|x[4]<<7;
	r[4] = x[4]>>1|x[3]<<7;
	r[3] = x[3]>>1|x[2]<<7;
	r[2] = x[2]>>1|x[1]<<7;
	r[1] = x[1]>>1|x[0]<<7;
	r[0] = x[0]>>1|overflow;
}

/* for use on little endian machines; remove bswap_64's for usage
* on bigendian machines */

void mul_x_lle_herbert(be128 *r, const be128 *x) {
	u64 a = bswap_64(x->a);
	u64 b = bswap_64(x->b);
	u64 _tt = gf128mul_table_lle_be[(b << 7) & 0xff];

	r->b = bswap_64((b >> 1) | (a << 63));
	r->a = bswap_64((a >> 1) ^ (_tt << 48));
}

/* works on little endian machines, use above version without bswap_64's
* on big endian machines, should be faster than the above version
* on little endian machines */
#define M80X 0x8080808080808080LLU

void mul_x_lle_brian(be128 *r, const be128 *x) {
	u64  _tt = gf128mul_table_lle_le[(x->b >> 49) & 0x80];
	r->b =  ((x->b >> 1) & ~M80X) | (((x->b << 15) | (x->a >> 49)) & M80X);
	r->a = (((x->a >> 1) & ~M80X) |  ((x->a << 15) & M80X)) ^ _tt;
}
void debug(char *name, be128 *ex) {
	int i;
	unsigned char *x = (unsigned char*)ex;
	for (i = 0; i < 16; i++)
		printf("%02x ", x[i]);
	printf("%s\n", name);
}
int main(int argc, char **argv) {
	assert(sizeof(be128) == 128/8);
	char V[16] = {
		//0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
		//0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
		0x12, 0x34, 0x56, 0x78, 0x9A, 0xBC, 0xDE, 0xF0,
		0x12, 0x34, 0x56, 0x78, 0x9A, 0xBC, 0xDE, 0xF0,
	};
	char R[16];
	debug("V", (be128*)V);
	mul_x_lle_simple((be128*)R, (be128*)V);
	debug("XV_simple", (be128*)R);
	mul_x_lle_herbert((be128*)R, (be128*)V);
	debug("XV_herbert", (be128*)R);
	mul_x_lle_brian((be128*)R, (be128*)V);
	debug("XV_brian", (be128*)R);
	exit(0);
}
Signature · 1 line
Nothing is ever a total loss; it can always serve as a bad example.
maintainer
#18 lore raw

Re: [PATCHv2 4/6] crypto: table driven multiplications in GF(2^128), needed by LRW (and in the future ABL)

Hi Rik:

Quoted 5 lines · [email protected] wrote:

It's OK. The source will be more maintainable, but constantly converting between big and little-endian (on little endian machines) may have a significant performance impact (I will just test when your gf128 hits cryptodev-2.6, and complain if it is the case).

BTW, the tcrypt speed test for lrw doesn't work for me.

Quoted 3 lines

Two more remarks (errors in v2 of my patch): b128ops.h and gf128mul.h should be in include/ (so they can be used in modules) and the inline functions in b128ops.h should also be static.

Yep they're in include/crypto with all the functions being static inline.

Quoted 5 lines

This seems to be the problem, the table is constructed wrongly. All the calculations take place as if we are on a big endian machine, so the table entries should never be swapped, so the above line should read

+#define xx(p, q) 0x##p##q

Yes you're quite right. That was the problem. I'll push this into mm as soon as I get the speed tests fixed.

Thanks!

Signature · 4 lines
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
#19 lore raw

Re: [PATCHv2 4/6] crypto: table driven multiplications in GF(2^128), needed by LRW (and in the future ABL)

Hello Herbert,

Quoted 6 lines · Herbert Xu
Quoted 4 lines

It's OK. The source will be more maintainable, but constantly converting between big and little-endian (on little endian machines) may have a significant performance impact (I will just test when your gf128 hits cryptodev-2.6, and complain if it is the case).

BTW, the tcrypt speed test for lrw doesn't work for me.

Did you try my patch: [PATCH] adding speed_test_template for lrw(aes) which I sent on Sep 23?

Quoted 8 lines
Quoted 5 lines

This seems to be the problem, the table is constructed wrongly. All the calculations take place as if we are on a big endian machine, so the table entries should never be swapped, so the above line should read

+#define xx(p, q) 0x##p##q

Yes you're quite right. That was the problem. I'll push this into mm as soon as I get the speed tests fixed.

Ok, that's good news.

Greetings,

Rik.

Signature · 1 line
Nothing is ever a total loss; it can always serve as a bad example.
maintainer
#20 lore raw

Re: [PATCHv2 4/6] crypto: table driven multiplications in GF(2^128), needed by LRW (and in the future ABL)

Quoted 3 lines · On Tue, Nov 28, 2006 at 10:17:39PM +0100, [email protected] wrote:

Did you try my patch: [PATCH] adding speed_test_template for lrw(aes) which I sent on Sep 23?

Aha, that got buried in my mailbox. I'll push it out soon.

Cheers,

Signature · 4 lines
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
#21 lore raw

PATCH v2 5/6 LRW, Liskov Rivest Wagner, a tweakable narrow block cipher mode

In reply to Herbert Xu

From: Rik Snel <[email protected]>

Main module, this implements the Liskov Rivest Wagner block cipher mode in the new blockcipher API. The implementation is based on ecb.c.

The LRW-32-AES specification I used can be found at:
http://grouper.ieee.org/groups/1619/email/pdf00017.pdf

It implements the optimization specified as optional in the specification, and in addition it uses optimized multiplication routines from gf128mul.c.

Since gf128mul.[ch] is not tested on bigendian, this cipher mode may currently fail badly on bigendian machines.

---

Note: I rerolled the loop because it turned out that I had unrolled it wrong. (I noticed it after I added the long testvector; a cypherblock was split in two by a page boundary and the reconstructed block was discarded because of an error in the unrolling).

 crypto/Kconfig  |   13 ++
 crypto/Makefile |    1 
 crypto/lrw.c    |  291 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 305 insertions(+), 0 deletions(-)
crypto/Kconfig +13 -0
index 6b23c20..dfdfe08 100644
@@ -156,6 +156,19 @@ config CRYPTO_CBC
 	  CBC: Cipher Block Chaining mode
 	  This block cipher algorithm is required for IPSec.
 
+config CRYPTO_LRW
+	tristate "LRW support (EXPERIMENTAL)"
+	depends on EXPERIMENTAL
+	select CRYPTO_BLKCIPHER
+	select CRYPTO_GF128MUL
+	default n
+	help
+	  LRW: Liskov Rivest Wagner, a tweakable, non malleable, non movable
+	  narrow block cipher mode. Use it with cipher specification string
+	  aes-lrw-benbi, the key must be 256, 320 or 384. The first 128, 192
+	  or 256 bits in the key are used for AES and the rest is used to tie
+	  each cipher block to its logical position.
+
 config CRYPTO_DES
 	tristate "DES and Triple DES EDE cipher algorithms"
 	select CRYPTO_ALGAPI
crypto/Makefile +1 -0
index bf0406b..e2e57be 100644
@@ -26,6 +26,7 @@ obj-$(CONFIG_CRYPTO_TGR192) += tgr192.o
 obj-$(CONFIG_CRYPTO_GF128MUL) += gf128mul.o
 obj-$(CONFIG_CRYPTO_ECB) += ecb.o
 obj-$(CONFIG_CRYPTO_CBC) += cbc.o
+obj-$(CONFIG_CRYPTO_LRW) += lrw.o
 obj-$(CONFIG_CRYPTO_DES) += des.o
 obj-$(CONFIG_CRYPTO_BLOWFISH) += blowfish.o
 obj-$(CONFIG_CRYPTO_TWOFISH) += twofish.o
crypto/lrw.c new file +291 -0

291 lines not on this page · raw message

Signature · 5 lines
1.4.1.1


-- 
VGER BF report: U 0.5
#22 lore raw

PATCH v2 6/6 LRW testvectors in tcrypt.[ch]

In reply to Herbert Xu

From: Rik Snel <[email protected]>

Do modprobe tcrypt mode=10 to check the included test vectors, they are
from: http://grouper.ieee.org/groups/1619/email/pdf00017.pdf and from
http://www.mail-archive.com/[email protected]/msg00173.html.

To make the last test vector fit, I had to increase the buffer size of input and result to 512 bytes.

---
 crypto/tcrypt.c |   12 +
 crypto/tcrypt.h |  513 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 521 insertions(+), 4 deletions(-)
crypto/tcrypt.c +12 -0
index 840ab8b..0fd14c3 100644
@@ -906,6 +906,10 @@ static void do_test(void)
 			    AES_CBC_ENC_TEST_VECTORS);
 		test_cipher("cbc(aes)", DECRYPT, aes_cbc_dec_tv_template,
 			    AES_CBC_DEC_TEST_VECTORS);
+		test_cipher("lrw(aes)", ENCRYPT, aes_lrw_enc_tv_template,
+			    AES_LRW_ENC_TEST_VECTORS);
+		test_cipher("lrw(aes)", DECRYPT, aes_lrw_dec_tv_template,
+			    AES_LRW_DEC_TEST_VECTORS);
 
 		//CAST5
 		test_cipher("ecb(cast5)", ENCRYPT, cast5_enc_tv_template,
@@ -1052,6 +1056,10 @@ static void do_test(void)
 			    AES_CBC_ENC_TEST_VECTORS);
 		test_cipher("cbc(aes)", DECRYPT, aes_cbc_dec_tv_template,
 			    AES_CBC_DEC_TEST_VECTORS);
+		test_cipher("lrw(aes)", ENCRYPT, aes_lrw_enc_tv_template,
+			    AES_LRW_ENC_TEST_VECTORS);
+		test_cipher("lrw(aes)", DECRYPT, aes_lrw_dec_tv_template,
+			    AES_LRW_DEC_TEST_VECTORS);
 		break;
 
 	case 11:
@@ -1191,6 +1199,10 @@ static void do_test(void)
 				  aes_speed_template);
 		test_cipher_speed("cbc(aes)", DECRYPT, sec, NULL, 0,
 				  aes_speed_template);
+		test_cipher_speed("lrw(aes)", ENCRYPT, sec, NULL, 0,
+				  aes_speed_template);
+		test_cipher_speed("lrw(aes)", DECRYPT, sec, NULL, 0,
+				  aes_speed_template);
 		break;
 
 	case 201:
crypto/tcrypt.h +509 -4

536 lines not on this page · raw message

Signature · 5 lines
1.4.1.1


-- 
VGER BF report: U 0.497913