Skip to contentSkip to conversation

crypto: CTR DRBG - performance improvements

PATCH In review Stephan Mueller 2 participants 6 messages Jun 14, 2016 – Jun 15, 2016 Crypto API

lore
Share & tools
lore
#0 lore raw

v2 cover crypto: CTR DRBG - performance improvements

Hi,

The following patch set is aimed to increase the performance of the CTR DRBG, especially when assembler implementations of the CTR AES mode are available.

The patch set increases the performance by 10% for random numbers of 16 bytes and reaches 450% for random numbers reaching 4096 bytes (larger random numbers will even have more performance gains). The performance gains were measured when using ctr-aes-aesni.

Note, when using the C implementation of the CTR mode (cipher/ctr.c), the performance of the CTR DRBG is slightly worse than it is now, but still it is much faster than the Hash or HMAC DRBGs.

The patch set is CAVS tested.

Changes v2:
* the alignment patch is updated to use the alignment of the underlying TFM

Stephan Mueller (4):
crypto: CTR DRBG - use CTR AES instead of ECB AES
crypto: DRBG - use aligned buffers
crypto: CTR DRBG - use full CTR AES for update
crypto: CTR DRBG - avoid duplicate maintenance of key

 crypto/Kconfig        |   1 +
 crypto/drbg.c         | 252 +++++++++++++++++++++++++++++++++-----------------
 include/crypto/drbg.h |  12 +++
 3 files changed, 181 insertions(+), 84 deletions(-)
Signature · 1 line
2.5.5
#1 lore raw

PATCH v2 1/4 crypto: CTR DRBG - use CTR AES instead of ECB AES

The CTR DRBG derives its random data from the CTR that is encrypted with AES.

This patch now changes the CTR DRBG implementation such that the CTR AES mode is employed. This allows the use of steamlined CTR AES implementation such as ctr-aes-aesni.

Unfortunately there are the following subtile changes we need to apply when using the CTR AES mode:

- the CTR mode increments the counter after the cipher operation, but the CTR DRBG requires the increment before the cipher op. Hence, the crypto_inc is applied to the counter (drbg->V) once it is recalculated.

- the CTR mode wants to encrypt data, but the CTR DRBG is interested in the encrypted counter only. The full CTR mode is the XOR of the encrypted counter with the plaintext data. To access the encrypted counter, the patch uses a NULL data vector as plaintext to be "encrypted".

---
 crypto/Kconfig        |   1 +
 crypto/drbg.c         | 193 ++++++++++++++++++++++++++++++++++++--------------
 include/crypto/drbg.h |   9 +++
 3 files changed, 149 insertions(+), 54 deletions(-)
crypto/Kconfig +1 -0
index 1d33beb..c903f18 100644
@@ -1567,6 +1567,7 @@ config CRYPTO_DRBG_HASH
 config CRYPTO_DRBG_CTR
 	bool "Enable CTR DRBG"
 	select CRYPTO_AES
+	depends on CRYPTO_CTR
 	help
 	  Enable the CTR DRBG variant as defined in NIST SP800-90A.
 
crypto/drbg.c +139 -54

268 lines not on this page · raw message

include/crypto/drbg.h +9 -0
index d961b2b..b2fe15d 100644
@@ -43,6 +43,7 @@
 #include <linux/random.h>
 #include <linux/scatterlist.h>
 #include <crypto/hash.h>
+#include <crypto/skcipher.h>
 #include <linux/module.h>
 #include <linux/crypto.h>
 #include <linux/slab.h>
@@ -115,6 +116,14 @@ struct drbg_state {
 	 /* some memory the DRBG can use for its operation */
 	unsigned char *scratchpad;
 	void *priv_data;	/* Cipher handle */
+
+	struct crypto_skcipher *ctr_handle;	/* CTR mode cipher handle */
+	struct skcipher_request *ctr_req;	/* CTR mode request handle */
+	__u8 *ctr_null_value_buf;		/* CTR mode unaligned buffer */
+	__u8 *ctr_null_value;			/* CTR mode aligned zero buf */
+	struct completion ctr_completion;	/* CTR mode async handler */
+	int ctr_async_err;			/* CTR mode async error */
+
 	bool seeded;		/* DRBG fully seeded? */
 	bool pr;		/* Prediction resistance enabled? */
 	struct work_struct seed_work;	/* asynchronous seeding support */
Signature · 1 line
2.5.5
#2 lore raw

PATCH v2 2/4 crypto: DRBG - use aligned buffers

In reply to Stephan Mueller

Hardware cipher implementation may require aligned buffers. All buffers that potentially are processed with a cipher are now aligned.

At the time of the allocation of the memory, we have not yet allocated the cipher implementations. Hence, we cannot obtain the alignmask for the used cipher yet. Therefore, the DRBG code uses an alignment which should satisfy all cipher implementations.

---
 crypto/drbg.c         | 44 ++++++++++++++++++++++++--------------------
 include/crypto/drbg.h |  3 +++
 2 files changed, 27 insertions(+), 20 deletions(-)
crypto/drbg.c +24 -20
index 4ee1a9c..8ac3ea1 100644
@@ -1139,11 +1139,11 @@ static inline void drbg_dealloc_state(struct drbg_state *drbg)
 	if (!drbg)
 		return;
 	kzfree(drbg->V);
-	drbg->V = NULL;
+	drbg->Vbuf = NULL;
 	kzfree(drbg->C);
-	drbg->C = NULL;
-	kzfree(drbg->scratchpad);
-	drbg->scratchpad = NULL;
+	drbg->Cbuf = NULL;
+	kzfree(drbg->scratchpadbuf);
+	drbg->scratchpadbuf = NULL;
 	drbg->reseed_ctr = 0;
 	drbg->d_ops = NULL;
 	drbg->core = NULL;
@@ -1179,12 +1179,18 @@ static inline int drbg_alloc_state(struct drbg_state *drbg)
 		goto err;
 	}
 
-	drbg->V = kmalloc(drbg_statelen(drbg), GFP_KERNEL);
-	if (!drbg->V)
-		goto err;
-	drbg->C = kmalloc(drbg_statelen(drbg), GFP_KERNEL);
-	if (!drbg->C)
+	ret = drbg->d_ops->crypto_init(drbg);
+	if (ret < 0)
 		goto err;
+
+	drbg->Vbuf = kmalloc(drbg_statelen(drbg) + ret, GFP_KERNEL);
+	if (!drbg->Vbuf)
+		goto fini;
+	drbg->V = PTR_ALIGN(drbg->Vbuf, ret + 1);
+	drbg->Cbuf = kmalloc(drbg_statelen(drbg) + ret, GFP_KERNEL);
+	if (!drbg->Cbuf)
+		goto fini;
+	drbg->C = PTR_ALIGN(drbg->Cbuf, ret + 1);
 	/* scratchpad is only generated for CTR and Hash */
 	if (drbg->core->flags & DRBG_HMAC)
 		sb_size = 0;
@@ -1198,13 +1204,16 @@ static inline int drbg_alloc_state(struct drbg_state *drbg)
 		sb_size = drbg_statelen(drbg) + drbg_blocklen(drbg);
 
 	if (0 < sb_size) {
-		drbg->scratchpad = kzalloc(sb_size, GFP_KERNEL);
-		if (!drbg->scratchpad)
-			goto err;
+		drbg->scratchpadbuf = kzalloc(sb_size + ret, GFP_KERNEL);
+		if (!drbg->scratchpadbuf)
+			goto fini;
+		drbg->scratchpad = PTR_ALIGN(drbg->scratchpadbuf, ret + 1);
 	}
 
 	return 0;
 
+fini:
+	drbg->d_ops->crypto_fini(drbg);
 err:
 	drbg_dealloc_state(drbg);
 	return ret;
@@ -1472,10 +1481,6 @@ static int drbg_instantiate(struct drbg_state *drbg, struct drbg_string *pers,
 		if (ret)
 			goto unlock;
 
-		ret = -EFAULT;
-		if (drbg->d_ops->crypto_init(drbg))
-			goto err;
-
 		ret = drbg_prepare_hrng(drbg);
 		if (ret)
 			goto free_everything;
@@ -1499,8 +1504,6 @@ static int drbg_instantiate(struct drbg_state *drbg, struct drbg_string *pers,
 	mutex_unlock(&drbg->drbg_mutex);
 	return ret;
 
-err:
-	drbg_dealloc_state(drbg);
 unlock:
 	mutex_unlock(&drbg->drbg_mutex);
 	return ret;
@@ -1585,7 +1588,8 @@ static int drbg_init_hash_kernel(struct drbg_state *drbg)
 	sdesc->shash.tfm = tfm;
 	sdesc->shash.flags = 0;
 	drbg->priv_data = sdesc;
-	return 0;
+
+	return crypto_shash_alignmask(tfm);
 }
 
 static int drbg_fini_hash_kernel(struct drbg_state *drbg)
@@ -1705,7 +1709,7 @@ static int drbg_init_sym_kernel(struct drbg_state *drbg)
 	drbg->ctr_null_value = (u8 *)PTR_ALIGN(drbg->ctr_null_value_buf,
 					       alignmask + 1);
 
-	return 0;
+	return alignmask;
 }
 
 static void drbg_kcapi_symsetkey(struct drbg_state *drbg,
include/crypto/drbg.h +3 -0
index b2fe15d..61580b1 100644
@@ -108,13 +108,16 @@ struct drbg_test_data {
 struct drbg_state {
 	struct mutex drbg_mutex;	/* lock around DRBG */
 	unsigned char *V;	/* internal state 10.1.1.1 1a) */
+	unsigned char *Vbuf;
 	/* hash: static value 10.1.1.1 1b) hmac / ctr: key */
 	unsigned char *C;
+	unsigned char *Cbuf;
 	/* Number of RNG requests since last reseed -- 10.1.1.1 1c) */
 	size_t reseed_ctr;
 	size_t reseed_threshold;
 	 /* some memory the DRBG can use for its operation */
 	unsigned char *scratchpad;
+	unsigned char *scratchpadbuf;
 	void *priv_data;	/* Cipher handle */
 
 	struct crypto_skcipher *ctr_handle;	/* CTR mode cipher handle */
Signature · 1 line
2.5.5
#3 lore raw

PATCH v2 3/4 crypto: CTR DRBG - use full CTR AES for update

In reply to Stephan Mueller

The CTR DRBG update function performs a full CTR AES operation including the XOR with "plaintext" data. Hence, remove the XOR from the code and use the CTR mode to do the XOR.

---
 crypto/drbg.c | 30 +++++++++++++-----------------
 1 file changed, 13 insertions(+), 17 deletions(-)
crypto/drbg.c +13 -17
index 8ac3ea1..8ceb716 100644
@@ -258,7 +258,10 @@ static int drbg_kcapi_sym(struct drbg_state *drbg, unsigned char *outval,
 			  const struct drbg_string *in);
 static int drbg_init_sym_kernel(struct drbg_state *drbg);
 static int drbg_fini_sym_kernel(struct drbg_state *drbg);
-static int drbg_kcapi_sym_ctr(struct drbg_state *drbg, u8 *outbuf, u32 outlen);
+static int drbg_kcapi_sym_ctr(struct drbg_state *drbg,
+			      u8 *inbuf, u32 inbuflen,
+			      u8 *outbuf, u32 outlen);
+#define DRBG_CTR_NULL_LEN 128
 
 /* BCC function for CTR DRBG as defined in 10.4.3 */
 static int drbg_ctr_bcc(struct drbg_state *drbg,
@@ -481,8 +484,6 @@ static int drbg_ctr_update(struct drbg_state *drbg, struct list_head *seed,
 	unsigned char *temp = drbg->scratchpad;
 	unsigned char *df_data = drbg->scratchpad + drbg_statelen(drbg) +
 				 drbg_blocklen(drbg);
-	unsigned char *temp_p, *df_data_p; /* pointer to iterate over buffers */
-	unsigned int len = 0;
 
 	if (3 > reseed)
 		memset(df_data, 0, drbg_statelen(drbg));
@@ -510,18 +511,11 @@ static int drbg_ctr_update(struct drbg_state *drbg, struct list_head *seed,
 			goto out;
 	}
 
-	ret = drbg_kcapi_sym_ctr(drbg, temp, drbg_statelen(drbg));
+	ret = drbg_kcapi_sym_ctr(drbg, df_data, drbg_statelen(drbg),
+				 temp, drbg_statelen(drbg));
 	if (ret)
 		return ret;
 
-	/* 10.2.1.2 step 4 */
-	temp_p = temp;
-	df_data_p = df_data;
-	for (len = 0; len < drbg_statelen(drbg); len++) {
-		*temp_p ^= *df_data_p;
-		df_data_p++; temp_p++;
-	}
-
 	/* 10.2.1.2 step 5 */
 	memcpy(drbg->C, temp, drbg_keylen(drbg));
 	ret = crypto_skcipher_setkey(drbg->ctr_handle, drbg->C,
@@ -561,7 +555,8 @@ static int drbg_ctr_generate(struct drbg_state *drbg,
 	}
 
 	/* 10.2.1.5.2 step 4.1 */
-	ret = drbg_kcapi_sym_ctr(drbg, buf, len);
+	ret = drbg_kcapi_sym_ctr(drbg, drbg->ctr_null_value, DRBG_CTR_NULL_LEN,
+				 buf, len);
 	if (ret)
 		return ret;
 
@@ -1657,7 +1652,6 @@ static void drbg_skcipher_cb(struct crypto_async_request *req, int error)
 	complete(&drbg->ctr_completion);
 }
 
-#define DRBG_CTR_NULL_LEN 128
 static int drbg_init_sym_kernel(struct drbg_state *drbg)
 {
 	struct crypto_cipher *tfm;
@@ -1733,14 +1727,16 @@ static int drbg_kcapi_sym(struct drbg_state *drbg, unsigned char *outval,
 	return 0;
 }
 
-static int drbg_kcapi_sym_ctr(struct drbg_state *drbg, u8 *outbuf, u32 outlen)
+static int drbg_kcapi_sym_ctr(struct drbg_state *drbg,
+			      u8 *inbuf, u32 inlen,
+			      u8 *outbuf, u32 outlen)
 {
 	struct scatterlist sg_in;
 
-	sg_init_one(&sg_in, drbg->ctr_null_value, DRBG_CTR_NULL_LEN);
+	sg_init_one(&sg_in, inbuf, inlen);
 
 	while (outlen) {
-		u32 cryptlen = min_t(u32, outlen, DRBG_CTR_NULL_LEN);
+		u32 cryptlen = min_t(u32, inlen, outlen);
 		struct scatterlist sg_out;
 		int ret;
 
Signature · 1 line
2.5.5
#4 lore raw

PATCH v2 4/4 crypto: CTR DRBG - avoid duplicate maintenance of key

In reply to Stephan Mueller

The TFM object maintains the key for the CTR DRBG.

---
 crypto/drbg.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)
crypto/drbg.c +1 -2
index 8ceb716..ded8638 100644
@@ -517,8 +517,7 @@ static int drbg_ctr_update(struct drbg_state *drbg, struct list_head *seed,
 		return ret;
 
 	/* 10.2.1.2 step 5 */
-	memcpy(drbg->C, temp, drbg_keylen(drbg));
-	ret = crypto_skcipher_setkey(drbg->ctr_handle, drbg->C,
+	ret = crypto_skcipher_setkey(drbg->ctr_handle, temp,
 				     drbg_keylen(drbg));
 	if (ret)
 		goto out;
Signature · 1 line
2.5.5
maintainer
#5 lore raw
In reply to Stephan Mueller
Quoted 17 lines · Stephan Mueller

Hi,

The following patch set is aimed to increase the performance of the CTR DRBG, especially when assembler implementations of the CTR AES mode are available.

The patch set increases the performance by 10% for random numbers of 16 bytes and reaches 450% for random numbers reaching 4096 bytes (larger random numbers will even have more performance gains). The performance gains were measured when using ctr-aes-aesni.

Note, when using the C implementation of the CTR mode (cipher/ctr.c), the performance of the CTR DRBG is slightly worse than it is now, but still it is much faster than the Hash or HMAC DRBGs.

The patch set is CAVS tested.

Quoted 8 lines

Changes v2:
* the alignment patch is updated to use the alignment of the underlying TFM

Stephan Mueller (4):
crypto: CTR DRBG - use CTR AES instead of ECB AES
crypto: DRBG - use aligned buffers
crypto: CTR DRBG - use full CTR AES for update
crypto: CTR DRBG - avoid duplicate maintenance of key

All applied. Thanks!

Signature · 3 lines
Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt