[PATCH 0/8] DRBG: efficiency patches

[PATCH 0/8] DRBG: efficiency patches

[Stephan Mueller]

Hi,

The following patch set contains random fixes to increase the efficiency of
the DRBG. Changes include the removal of unneeded memset(0) and sanity
checks. All changes do not weaken the implementation as only code is
removed that is clearly covered by other code paths.

In addition, the cpu_to_be kernel function together with a type cast is
used to convert an integer into its string representation. This patch
increases the speed of the DRBG by 10%.

Stephan Mueller (8):
  DRBG: replace int2byte with cpu_to_be
  DRBG: kzfree does not need a check for NULL pointer
  DRBG: remove superflowous checks
  DRBG: remove superflowous memset(0)
  DRBG: use kmalloc instead of kzalloc for V and C
  DRBG: remove unnecessary sanity checks
  DRBG: remove configuration of fixed values
  DRBG: remove unnecessary sanity check for shadow state

 crypto/drbg.c         | 130 ++++++++++++++++----------------------------------
 include/crypto/drbg.h |  19 +++-----
 2 files changed, 46 insertions(+), 103 deletions(-)

-- 
1.9.3

[PATCH 1/8] DRBG: replace int2byte with cpu_to_be

[Stephan Mueller]

The DRBG requires the conversion of an integer into a string
representation of that integer. The previous implementation converted
the given integer byte-wise. However, the kernel offers the cpu_to_be
function which already re-arranges the memory representation of an
integer such that it applies when interpreting the same memory as
character string.

The change therefore uses an integer-cast / union of the target
character array together with the cpu_to_be function to convert an
integer into its string representation.

Tests show that the Hash and CTR DRBG implementations (the HMAC DRBG
does not require such conversion) is about 10% faster (or requires less
computing power, respectively).

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 crypto/drbg.c | 34 ++++++++++++++++++----------------
 1 file changed, 18 insertions(+), 16 deletions(-)

diff --git a/crypto/drbg.c b/crypto/drbg.c
index ff975d9..73d21e5 100644
--- a/crypto/drbg.c
+++ b/crypto/drbg.c
@@ -302,20 +302,19 @@ static bool drbg_fips_continuous_test(struct drbg_state *drbg,
  * Convert an integer into a byte representation of this integer.
  * The byte representation is big-endian
  *
- * @buf buffer holding the converted integer
  * @val value to be converted
- * @buflen length of buffer
+ * @buf buffer holding the converted integer -- caller must ensure that
+ *      buffer size is at least 32 bit
  */
 #if (defined(CONFIG_CRYPTO_DRBG_HASH) || defined(CONFIG_CRYPTO_DRBG_CTR))
-static inline void drbg_int2byte(unsigned char *buf, uint64_t val,
-				 size_t buflen)
+static inline void drbg_cpu_to_be32(__u32 val, unsigned char *buf)
 {
-	unsigned char *byte;
-	uint64_t i;
+	struct s {
+		__u32 conv;
+	};
+	struct s *conversion = (struct s *) buf;
 
-	byte = buf + (buflen - 1);
-	for (i = 0; i < buflen; i++)
-		*(byte--) = val >> (i * 8) & 0xff;
+	conversion->conv = cpu_to_be32(val);
 }
 
 /*
@@ -483,10 +482,10 @@ static int drbg_ctr_df(struct drbg_state *drbg,
 	/* 10.4.2 step 2 -- calculate the entire length of all input data */
 	list_for_each_entry(seed, seedlist, list)
 		inputlen += seed->len;
-	drbg_int2byte(&L_N[0], inputlen, 4);
+	drbg_cpu_to_be32(inputlen, &L_N[0]);
 
 	/* 10.4.2 step 3 */
-	drbg_int2byte(&L_N[4], bytes_to_return, 4);
+	drbg_cpu_to_be32(bytes_to_return, &L_N[4]);
 
 	/* 10.4.2 step 5: length is L_N, input_string, one byte, padding */
 	padlen = (inputlen + sizeof(L_N) + 1) % (drbg_blocklen(drbg));
@@ -517,7 +516,7 @@ static int drbg_ctr_df(struct drbg_state *drbg,
 		 * holds zeros after allocation -- even the increment of i
 		 * is irrelevant as the increment remains within length of i
 		 */
-		drbg_int2byte(iv, i, 4);
+		drbg_cpu_to_be32(i, iv);
 		/* 10.4.2 step 9.2 -- BCC and concatenation with temp */
 		ret = drbg_ctr_bcc(drbg, temp + templen, K, &bcc_list);
 		if (ret)
@@ -862,7 +861,7 @@ static int drbg_hash_df(struct drbg_state *drbg,
 
 	/* 10.4.1 step 3 */
 	input[0] = 1;
-	drbg_int2byte(&input[1], (outlen * 8), 4);
+	drbg_cpu_to_be32((outlen * 8), &input[1]);
 
 	/* 10.4.1 step 4.1 -- concatenation of data for input into hash */
 	drbg_string_fill(&data, input, 5);
@@ -1023,7 +1022,10 @@ static int drbg_hash_generate(struct drbg_state *drbg,
 {
 	int len = 0;
 	int ret = 0;
-	unsigned char req[8];
+	union {
+		unsigned char req[8];
+		__u64 req_int;
+	} u;
 	unsigned char prefix = DRBG_PREFIX3;
 	struct drbg_string data1, data2;
 	LIST_HEAD(datalist);
@@ -1053,8 +1055,8 @@ static int drbg_hash_generate(struct drbg_state *drbg,
 		     drbg->scratchpad, drbg_blocklen(drbg));
 	drbg_add_buf(drbg->V, drbg_statelen(drbg),
 		     drbg->C, drbg_statelen(drbg));
-	drbg_int2byte(req, drbg->reseed_ctr, sizeof(req));
-	drbg_add_buf(drbg->V, drbg_statelen(drbg), req, 8);
+	u.req_int = cpu_to_be64(drbg->reseed_ctr);
+	drbg_add_buf(drbg->V, drbg_statelen(drbg), u.req, 8);
 
 out:
 	memset(drbg->scratchpad, 0, drbg_blocklen(drbg));
-- 
1.9.3

[PATCH 2/8] DRBG: kzfree does not need a check for NULL pointer

[Stephan Mueller]

The kzfree function already performs the NULL pointer check. Therefore,
the DRBG code does not need to implement such check.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 crypto/drbg.c | 18 ++++++------------
 1 file changed, 6 insertions(+), 12 deletions(-)

diff --git a/crypto/drbg.c b/crypto/drbg.c
index 73d21e5..8a95ca8 100644
--- a/crypto/drbg.c
+++ b/crypto/drbg.c
@@ -1153,8 +1153,7 @@ static int drbg_seed(struct drbg_state *drbg, struct drbg_string *pers,
 	drbg->reseed_ctr = 1;
 
 out:
-	if (entropy)
-		kzfree(entropy);
+	kzfree(entropy);
 	return ret;
 }
 
@@ -1163,19 +1162,15 @@ static inline void drbg_dealloc_state(struct drbg_state *drbg)
 {
 	if (!drbg)
 		return;
-	if (drbg->V)
-		kzfree(drbg->V);
+	kzfree(drbg->V);
 	drbg->V = NULL;
-	if (drbg->C)
-		kzfree(drbg->C);
+	kzfree(drbg->C);
 	drbg->C = NULL;
-	if (drbg->scratchpad)
-		kzfree(drbg->scratchpad);
+	kzfree(drbg->scratchpad);
 	drbg->scratchpad = NULL;
 	drbg->reseed_ctr = 0;
 #ifdef CONFIG_CRYPTO_FIPS
-	if (drbg->prev)
-		kzfree(drbg->prev);
+	kzfree(drbg->prev);
 	drbg->prev = NULL;
 	drbg->fips_primed = false;
 #endif
@@ -1295,8 +1290,7 @@ static int drbg_make_shadow(struct drbg_state *drbg, struct drbg_state **shadow)
 	return 0;
 
 err:
-	if (tmp)
-		kzfree(tmp);
+	kzfree(tmp);
 	return ret;
 }
 
-- 
1.9.3

[PATCH 3/8] DRBG: remove superflowous checks

[Stephan Mueller]

The crypto_init and crypto_fini functions are always implemented. Thus,
there is no need for a protecting check.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 crypto/drbg.c | 16 ++++++----------
 1 file changed, 6 insertions(+), 10 deletions(-)

diff --git a/crypto/drbg.c b/crypto/drbg.c
index 8a95ca8..89d732b 100644
--- a/crypto/drbg.c
+++ b/crypto/drbg.c
@@ -1381,11 +1381,9 @@ static int drbg_generate(struct drbg_state *drbg,
 		shadow->seeded = false;
 
 	/* allocate cipher handle */
-	if (shadow->d_ops->crypto_init) {
-		len = shadow->d_ops->crypto_init(shadow);
-		if (len)
-			goto err;
-	}
+	len = shadow->d_ops->crypto_init(shadow);
+	if (len)
+		goto err;
 
 	if (shadow->pr || !shadow->seeded) {
 		pr_devel("DRBG: reseeding before generation (prediction "
@@ -1467,8 +1465,7 @@ static int drbg_generate(struct drbg_state *drbg,
 #endif
 
 err:
-	if (shadow->d_ops->crypto_fini)
-		shadow->d_ops->crypto_fini(shadow);
+	shadow->d_ops->crypto_fini(shadow);
 	drbg_restore_shadow(drbg, &shadow);
 	return len;
 }
@@ -1562,11 +1559,10 @@ static int drbg_instantiate(struct drbg_state *drbg, struct drbg_string *pers,
 		return ret;
 
 	ret = -EFAULT;
-	if (drbg->d_ops->crypto_init && drbg->d_ops->crypto_init(drbg))
+	if (drbg->d_ops->crypto_init(drbg))
 		goto err;
 	ret = drbg_seed(drbg, pers, false);
-	if (drbg->d_ops->crypto_fini)
-		drbg->d_ops->crypto_fini(drbg);
+	drbg->d_ops->crypto_fini(drbg);
 	if (ret)
 		goto err;
 
-- 
1.9.3

[PATCH 4/8] DRBG: remove superflowous memset(0)

[Stephan Mueller]

Remove memset(0) which is not needed due to the kzalloc of the memory.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 crypto/drbg.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

diff --git a/crypto/drbg.c b/crypto/drbg.c
index 89d732b..d13f588 100644
--- a/crypto/drbg.c
+++ b/crypto/drbg.c
@@ -728,11 +728,9 @@ static int drbg_hmac_update(struct drbg_state *drbg, struct list_head *seed,
 	LIST_HEAD(seedlist);
 	LIST_HEAD(vdatalist);
 
-	if (!reseed) {
-		/* 10.1.2.3 step 2 */
-		memset(drbg->C, 0, drbg_statelen(drbg));
+	if (!reseed)
+		/* 10.1.2.3 step 2 -- memset(0) of C is implicit with kzalloc */
 		memset(drbg->V, 1, drbg_statelen(drbg));
-	}
 
 	drbg_string_fill(&seed1, drbg->V, drbg_statelen(drbg));
 	list_add_tail(&seed1.list, &seedlist);
-- 
1.9.3

[PATCH 5/8] DRBG: use kmalloc instead of kzalloc for V and C

[Stephan Mueller]

When allocating V, C, the zeroization is only needed when
allocating a new instance of the DRBG, i.e. when performing an
initial seeding. For all other allocations, the memcpy implemented in
drbg_copy_drbg ensures that the memory is filled with the correct
information.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 crypto/drbg.c | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)

diff --git a/crypto/drbg.c b/crypto/drbg.c
index d13f588..997c510 100644
--- a/crypto/drbg.c
+++ b/crypto/drbg.c
@@ -1142,6 +1142,11 @@ static int drbg_seed(struct drbg_state *drbg, struct drbg_string *pers,
 		pr_devel("DRBG: using personalization string\n");
 	}
 
+	if (!reseed) {
+		memset(drbg->V, 0, drbg_statelen(drbg));
+		memset(drbg->C, 0, drbg_statelen(drbg));
+	}
+
 	ret = drbg->d_ops->update(drbg, &seedlist, reseed);
 	if (ret)
 		goto out;
@@ -1186,14 +1191,14 @@ static inline int drbg_alloc_state(struct drbg_state *drbg)
 	if (!drbg)
 		return -EINVAL;
 
-	drbg->V = kzalloc(drbg_statelen(drbg), GFP_KERNEL);
+	drbg->V = kmalloc(drbg_statelen(drbg), GFP_KERNEL);
 	if (!drbg->V)
 		goto err;
-	drbg->C = kzalloc(drbg_statelen(drbg), GFP_KERNEL);
+	drbg->C = kmalloc(drbg_statelen(drbg), GFP_KERNEL);
 	if (!drbg->C)
 		goto err;
 #ifdef CONFIG_CRYPTO_FIPS
-	drbg->prev = kzalloc(drbg_blocklen(drbg), GFP_KERNEL);
+	drbg->prev = kmalloc(drbg_blocklen(drbg), GFP_KERNEL);
 	if (!drbg->prev)
 		goto err;
 	drbg->fips_primed = false;
-- 
1.9.3

[PATCH 6/8] DRBG: remove unnecessary sanity checks

[Stephan Mueller]

The drbg_make_shadow function contains sanity checks which are not
needed as the function is invoked at times where it is ensured that the
checked-for variables are available.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 crypto/drbg.c | 9 ---------
 1 file changed, 9 deletions(-)

diff --git a/crypto/drbg.c b/crypto/drbg.c
index 997c510..f74859d 100644
--- a/crypto/drbg.c
+++ b/crypto/drbg.c
@@ -1263,15 +1263,6 @@ static int drbg_make_shadow(struct drbg_state *drbg, struct drbg_state **shadow)
 	int ret = -ENOMEM;
 	struct drbg_state *tmp = NULL;
 
-	if (!drbg || !drbg->core || !drbg->V || !drbg->C) {
-		pr_devel("DRBG: attempt to generate shadow copy for "
-			 "uninitialized DRBG state rejected\n");
-		return -EINVAL;
-	}
-	/* HMAC does not have a scratchpad */
-	if (!(drbg->core->flags & DRBG_HMAC) && NULL == drbg->scratchpad)
-		return -EINVAL;
-
 	tmp = kzalloc(sizeof(struct drbg_state), GFP_KERNEL);
 	if (!tmp)
 		return -ENOMEM;
-- 
1.9.3

[PATCH 7/8] DRBG: remove configuration of fixed values

[Stephan Mueller]

SP800-90A mandates several hard-coded values. The old drbg_cores allows
the setting of these values per DRBG implementation. However, due to the
hard requirement of SP800-90A, these values are now returned globally
for each DRBG.

The ability to set such values per DRBG is therefore removed.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 crypto/drbg.c         | 33 ---------------------------------
 include/crypto/drbg.h | 19 ++++++-------------
 2 files changed, 6 insertions(+), 46 deletions(-)

diff --git a/crypto/drbg.c b/crypto/drbg.c
index f74859d..a556180 100644
--- a/crypto/drbg.c
+++ b/crypto/drbg.c
@@ -117,27 +117,18 @@ static const struct drbg_core drbg_cores[] = {
 	{
 		.flags = DRBG_CTR | DRBG_STRENGTH128,
 		.statelen = 32, /* 256 bits as defined in 10.2.1 */
-		.max_addtllen = 35,
-		.max_bits = 19,
-		.max_req = 48,
 		.blocklen_bytes = 16,
 		.cra_name = "ctr_aes128",
 		.backend_cra_name = "ecb(aes)",
 	}, {
 		.flags = DRBG_CTR | DRBG_STRENGTH192,
 		.statelen = 40, /* 320 bits as defined in 10.2.1 */
-		.max_addtllen = 35,
-		.max_bits = 19,
-		.max_req = 48,
 		.blocklen_bytes = 16,
 		.cra_name = "ctr_aes192",
 		.backend_cra_name = "ecb(aes)",
 	}, {
 		.flags = DRBG_CTR | DRBG_STRENGTH256,
 		.statelen = 48, /* 384 bits as defined in 10.2.1 */
-		.max_addtllen = 35,
-		.max_bits = 19,
-		.max_req = 48,
 		.blocklen_bytes = 16,
 		.cra_name = "ctr_aes256",
 		.backend_cra_name = "ecb(aes)",
@@ -147,36 +138,24 @@ static const struct drbg_core drbg_cores[] = {
 	{
 		.flags = DRBG_HASH | DRBG_STRENGTH128,
 		.statelen = 55, /* 440 bits */
-		.max_addtllen = 35,
-		.max_bits = 19,
-		.max_req = 48,
 		.blocklen_bytes = 20,
 		.cra_name = "sha1",
 		.backend_cra_name = "sha1",
 	}, {
 		.flags = DRBG_HASH | DRBG_STRENGTH256,
 		.statelen = 111, /* 888 bits */
-		.max_addtllen = 35,
-		.max_bits = 19,
-		.max_req = 48,
 		.blocklen_bytes = 48,
 		.cra_name = "sha384",
 		.backend_cra_name = "sha384",
 	}, {
 		.flags = DRBG_HASH | DRBG_STRENGTH256,
 		.statelen = 111, /* 888 bits */
-		.max_addtllen = 35,
-		.max_bits = 19,
-		.max_req = 48,
 		.blocklen_bytes = 64,
 		.cra_name = "sha512",
 		.backend_cra_name = "sha512",
 	}, {
 		.flags = DRBG_HASH | DRBG_STRENGTH256,
 		.statelen = 55, /* 440 bits */
-		.max_addtllen = 35,
-		.max_bits = 19,
-		.max_req = 48,
 		.blocklen_bytes = 32,
 		.cra_name = "sha256",
 		.backend_cra_name = "sha256",
@@ -186,36 +165,24 @@ static const struct drbg_core drbg_cores[] = {
 	{
 		.flags = DRBG_HMAC | DRBG_STRENGTH128,
 		.statelen = 20, /* block length of cipher */
-		.max_addtllen = 35,
-		.max_bits = 19,
-		.max_req = 48,
 		.blocklen_bytes = 20,
 		.cra_name = "hmac_sha1",
 		.backend_cra_name = "hmac(sha1)",
 	}, {
 		.flags = DRBG_HMAC | DRBG_STRENGTH256,
 		.statelen = 48, /* block length of cipher */
-		.max_addtllen = 35,
-		.max_bits = 19,
-		.max_req = 48,
 		.blocklen_bytes = 48,
 		.cra_name = "hmac_sha384",
 		.backend_cra_name = "hmac(sha384)",
 	}, {
 		.flags = DRBG_HMAC | DRBG_STRENGTH256,
 		.statelen = 64, /* block length of cipher */
-		.max_addtllen = 35,
-		.max_bits = 19,
-		.max_req = 48,
 		.blocklen_bytes = 64,
 		.cra_name = "hmac_sha512",
 		.backend_cra_name = "hmac(sha512)",
 	}, {
 		.flags = DRBG_HMAC | DRBG_STRENGTH256,
 		.statelen = 32, /* block length of cipher */
-		.max_addtllen = 35,
-		.max_bits = 19,
-		.max_req = 48,
 		.blocklen_bytes = 32,
 		.cra_name = "hmac_sha256",
 		.backend_cra_name = "hmac(sha256)",
diff --git a/include/crypto/drbg.h b/include/crypto/drbg.h
index 831d786..3d8e73a 100644
--- a/include/crypto/drbg.h
+++ b/include/crypto/drbg.h
@@ -82,15 +82,6 @@ typedef uint32_t drbg_flag_t;
 struct drbg_core {
 	drbg_flag_t flags;	/* flags for the cipher */
 	__u8 statelen;		/* maximum state length */
-	/*
-	 * maximum length of personalization string or additional input
-	 * string -- exponent for base 2
-	 */
-	__u8 max_addtllen;
-	/* maximum bits per RNG request -- exponent for base 2*/
-	__u8 max_bits;
-	/* maximum number of requests -- exponent for base 2 */
-	__u8 max_req;
 	__u8 blocklen_bytes;	/* block size of output in bytes */
 	char cra_name[CRYPTO_MAX_ALG_NAME]; /* mapping to kernel crypto API */
 	 /* kernel crypto API backend cipher name */
@@ -156,18 +147,20 @@ static inline __u8 drbg_keylen(struct drbg_state *drbg)
 
 static inline size_t drbg_max_request_bytes(struct drbg_state *drbg)
 {
-	/* max_bits is in bits, but buflen is in bytes */
-	return (1 << (drbg->core->max_bits - 3));
+	/* SP800-90A requires the limit 2**19 bits, but we return bytes */
+	return (1 << 16);
 }
 
 static inline size_t drbg_max_addtl(struct drbg_state *drbg)
 {
-	return (1UL<<(drbg->core->max_addtllen));
+	/* SP800-90A requires 2**35 bytes additional info str / pers str */
+	return (1UL<<35);
 }
 
 static inline size_t drbg_max_requests(struct drbg_state *drbg)
 {
-	return (1UL<<(drbg->core->max_req));
+	/* SP800-90A requires 2**48 maximum requests before reseeding */
+	return (1UL<<48);
 }
 
 /*
-- 
1.9.3

[PATCH 8/8] DRBG: remove unnecessary sanity check for shadow state

[Stephan Mueller]

During creation of the DRBG shadow state, it is ensured that the DRBG
state structure is already allocated. Thus, a sanity check for verifying
that the structure is allocated is removed.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 crypto/drbg.c | 3 ---
 1 file changed, 3 deletions(-)

diff --git a/crypto/drbg.c b/crypto/drbg.c
index a556180..f009939 100644
--- a/crypto/drbg.c
+++ b/crypto/drbg.c
@@ -1155,9 +1155,6 @@ static inline int drbg_alloc_state(struct drbg_state *drbg)
 	int ret = -ENOMEM;
 	unsigned int sb_size = 0;
 
-	if (!drbg)
-		return -EINVAL;
-
 	drbg->V = kmalloc(drbg_statelen(drbg), GFP_KERNEL);
 	if (!drbg->V)
 		goto err;
-- 
1.9.3

Re: [PATCH 0/8] DRBG: efficiency patches

[Herbert Xu]

On Sun, Aug 17, 2014 at 05:37:04PM +0200, Stephan Mueller wrote:
> Hi,
> 
> The following patch set contains random fixes to increase the efficiency of
> the DRBG. Changes include the removal of unneeded memset(0) and sanity
> checks. All changes do not weaken the implementation as only code is
> removed that is clearly covered by other code paths.
> 
> In addition, the cpu_to_be kernel function together with a type cast is
> used to convert an integer into its string representation. This patch
> increases the speed of the DRBG by 10%.
> 
> Stephan Mueller (8):
>   DRBG: replace int2byte with cpu_to_be
>   DRBG: kzfree does not need a check for NULL pointer
>   DRBG: remove superflowous checks
>   DRBG: remove superflowous memset(0)
>   DRBG: use kmalloc instead of kzalloc for V and C
>   DRBG: remove unnecessary sanity checks
>   DRBG: remove configuration of fixed values
>   DRBG: remove unnecessary sanity check for shadow state

All applied.  Thanks!
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt