[PATCH v3 0/3] crypto: drbg - revamp locking

[PATCH v3 0/3] crypto: drbg - revamp locking

[Stephan Mueller]

Hi,

the current implementation of the DRBG generates a shadow copy of its
DRBG state for each incoming request. The idea is that only a short
term lock is needed to spawn the shadow copy. The drawback is that
if multiple parallel requests come in, the generated DRBG shadow
states only differ by a high-resolution timer that was mixed in during
the shadow state generation.

This patch now removes this shadow state and introduces a mutex
to serialize all requests to one DRBG instance.

The patch was fully CAVS tested and demonstrates that the DRBG still
complies with the standard.

Changes v2:
* fix return code check of drbg_generate in drbg_generate_long
* move mutex_init to drbg_kcapi_init to ensure the mutex is initialized
  only during the instantiation of a DRBG and during a reset
* merge the patch for replacing the spinlock with a mutex and the removal
  of the shadow copy generation as both patches cannot stand alone and would
  therefore break bisection
* drop patch that fixes the memory release (Herbert: you mentioned the patch
  is applied but it is not yet in the repo -- this patch is vital as otherwise
  AES192 now breaks without the shadow copy operation)

Changes v3:
* patch for fixing the return code handling in drbg_generate_long did not
  cover all code paths -- now the issue should be truly fixed

Stephan Mueller (3):
  crypto: drbg - fix drbg_generate return val check
  crypto: drbg - replace spinlock with mutex
  crypto: drbg - leave cipher handles operational

 crypto/drbg.c         | 166 +++++++++++---------------------------------------
 include/crypto/drbg.h |   4 +-
 2 files changed, 36 insertions(+), 134 deletions(-)

-- 
2.1.0

[PATCH v3 1/3] crypto: drbg - fix drbg_generate return val check

[Stephan Mueller]

The drbg_generate returns 0 in success case. That means that
drbg_generate_long will always only generate drbg_max_request_bytes at
most. Longer requests will be truncated to drbg_max_request_bytes.

Reported-by: Herbert Xu <herbert@gondor.apana.org.au>
Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 crypto/drbg.c | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)

diff --git a/crypto/drbg.c b/crypto/drbg.c
index b69409c..3f62440 100644
--- a/crypto/drbg.c
+++ b/crypto/drbg.c
@@ -1442,19 +1442,19 @@ static int drbg_generate_long(struct drbg_state *drbg,
 			      unsigned char *buf, unsigned int buflen,
 			      struct drbg_string *addtl)
 {
-	int len = 0;
+	unsigned int len = 0;
 	unsigned int slice = 0;
 	do {
-		int tmplen = 0;
+		int err = 0;
 		unsigned int chunk = 0;
 		slice = ((buflen - len) / drbg_max_request_bytes(drbg));
 		chunk = slice ? drbg_max_request_bytes(drbg) : (buflen - len);
-		tmplen = drbg_generate(drbg, buf + len, chunk, addtl);
-		if (0 >= tmplen)
-			return tmplen;
-		len += tmplen;
+		err = drbg_generate(drbg, buf + len, chunk, addtl);
+		if (0 > err)
+			return err;
+		len += chunk;
 	} while (slice > 0 && (len < buflen));
-	return len;
+	return 0;
 }
 
 /*
-- 
2.1.0

[PATCH v3 2/3] crypto: drbg - replace spinlock with mutex

[Stephan Mueller]

The creation of a shadow copy is intended to only hold a short term
lock. But the drawback is that parallel users have a very similar DRBG
state which only differs by a high-resolution time stamp.

The DRBG will now hold a long term lock. Therefore, the lock is changed
to a mutex which implies that the DRBG can only be used in process
context.

The lock now guards the instantiation as well as the entire DRBG
generation operation. Therefore, multiple callers are fully serialized
when generating a random number.

As the locking is changed to use a long-term lock to avoid such similar
DRBG states, the entire creation and maintenance of a shadow copy can be
removed.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 crypto/drbg.c         | 144 +++++++++-----------------------------------------
 include/crypto/drbg.h |   4 +-
 2 files changed, 27 insertions(+), 121 deletions(-)

diff --git a/crypto/drbg.c b/crypto/drbg.c
index 3f62440..3683bb3 100644
--- a/crypto/drbg.c
+++ b/crypto/drbg.c
@@ -1181,7 +1181,6 @@ static inline int drbg_alloc_state(struct drbg_state *drbg)
 		if (!drbg->scratchpad)
 			goto err;
 	}
-	spin_lock_init(&drbg->drbg_lock);
 	return 0;
 
 err:
@@ -1189,79 +1188,6 @@ err:
 	return ret;
 }
 
-/*
- * Strategy to avoid holding long term locks: generate a shadow copy of DRBG
- * and perform all operations on this shadow copy. After finishing, restore
- * the updated state of the shadow copy into original drbg state. This way,
- * only the read and write operations of the original drbg state must be
- * locked
- */
-static inline void drbg_copy_drbg(struct drbg_state *src,
-				  struct drbg_state *dst)
-{
-	if (!src || !dst)
-		return;
-	memcpy(dst->V, src->V, drbg_statelen(src));
-	memcpy(dst->C, src->C, drbg_statelen(src));
-	dst->reseed_ctr = src->reseed_ctr;
-	dst->seeded = src->seeded;
-	dst->pr = src->pr;
-#ifdef CONFIG_CRYPTO_FIPS
-	dst->fips_primed = src->fips_primed;
-	memcpy(dst->prev, src->prev, drbg_blocklen(src));
-#endif
-	/*
-	 * Not copied:
-	 * scratchpad is initialized drbg_alloc_state;
-	 * priv_data is initialized with call to crypto_init;
-	 * d_ops and core are set outside, as these parameters are const;
-	 * test_data is set outside to prevent it being copied back.
-	 */
-}
-
-static int drbg_make_shadow(struct drbg_state *drbg, struct drbg_state **shadow)
-{
-	int ret = -ENOMEM;
-	struct drbg_state *tmp = NULL;
-
-	tmp = kzalloc(sizeof(struct drbg_state), GFP_KERNEL);
-	if (!tmp)
-		return -ENOMEM;
-
-	/* read-only data as they are defined as const, no lock needed */
-	tmp->core = drbg->core;
-	tmp->d_ops = drbg->d_ops;
-
-	ret = drbg_alloc_state(tmp);
-	if (ret)
-		goto err;
-
-	spin_lock_bh(&drbg->drbg_lock);
-	drbg_copy_drbg(drbg, tmp);
-	/* only make a link to the test buffer, as we only read that data */
-	tmp->test_data = drbg->test_data;
-	spin_unlock_bh(&drbg->drbg_lock);
-	*shadow = tmp;
-	return 0;
-
-err:
-	kzfree(tmp);
-	return ret;
-}
-
-static void drbg_restore_shadow(struct drbg_state *drbg,
-				struct drbg_state **shadow)
-{
-	struct drbg_state *tmp = *shadow;
-
-	spin_lock_bh(&drbg->drbg_lock);
-	drbg_copy_drbg(tmp, drbg);
-	spin_unlock_bh(&drbg->drbg_lock);
-	drbg_dealloc_state(tmp);
-	kzfree(tmp);
-	*shadow = NULL;
-}
-
 /*************************************************************************
  * DRBG interface functions
  *************************************************************************/
@@ -1287,13 +1213,7 @@ static int drbg_generate(struct drbg_state *drbg,
 			 struct drbg_string *addtl)
 {
 	int len = 0;
-	struct drbg_state *shadow = NULL;
 	LIST_HEAD(addtllist);
-	struct drbg_string timestamp;
-	union {
-		cycles_t cycles;
-		unsigned char char_cycles[sizeof(cycles_t)];
-	} now;
 
 	if (0 == buflen || !buf) {
 		pr_devel("DRBG: no output buffer provided\n");
@@ -1304,15 +1224,9 @@ static int drbg_generate(struct drbg_state *drbg,
 		return -EINVAL;
 	}
 
-	len = drbg_make_shadow(drbg, &shadow);
-	if (len) {
-		pr_devel("DRBG: shadow copy cannot be generated\n");
-		return len;
-	}
-
 	/* 9.3.1 step 2 */
 	len = -EINVAL;
-	if (buflen > (drbg_max_request_bytes(shadow))) {
+	if (buflen > (drbg_max_request_bytes(drbg))) {
 		pr_devel("DRBG: requested random numbers too large %u\n",
 			 buflen);
 		goto err;
@@ -1321,7 +1235,7 @@ static int drbg_generate(struct drbg_state *drbg,
 	/* 9.3.1 step 3 is implicit with the chosen DRBG */
 
 	/* 9.3.1 step 4 */
-	if (addtl && addtl->len > (drbg_max_addtl(shadow))) {
+	if (addtl && addtl->len > (drbg_max_addtl(drbg))) {
 		pr_devel("DRBG: additional information string too long %zu\n",
 			 addtl->len);
 		goto err;
@@ -1332,46 +1246,34 @@ static int drbg_generate(struct drbg_state *drbg,
 	 * 9.3.1 step 6 and 9 supplemented by 9.3.2 step c is implemented
 	 * here. The spec is a bit convoluted here, we make it simpler.
 	 */
-	if ((drbg_max_requests(shadow)) < shadow->reseed_ctr)
-		shadow->seeded = false;
+	if ((drbg_max_requests(drbg)) < drbg->reseed_ctr)
+		drbg->seeded = false;
 
 	/* allocate cipher handle */
-	len = shadow->d_ops->crypto_init(shadow);
+	len = drbg->d_ops->crypto_init(drbg);
 	if (len)
 		goto err;
 
-	if (shadow->pr || !shadow->seeded) {
+	if (drbg->pr || !drbg->seeded) {
 		pr_devel("DRBG: reseeding before generation (prediction "
 			 "resistance: %s, state %s)\n",
 			 drbg->pr ? "true" : "false",
 			 drbg->seeded ? "seeded" : "unseeded");
 		/* 9.3.1 steps 7.1 through 7.3 */
-		len = drbg_seed(shadow, addtl, true);
+		len = drbg_seed(drbg, addtl, true);
 		if (len)
 			goto err;
 		/* 9.3.1 step 7.4 */
 		addtl = NULL;
 	}
 
-	/*
-	 * Mix the time stamp into the DRBG state if the DRBG is not in
-	 * test mode. If there are two callers invoking the DRBG at the same
-	 * time, i.e. before the first caller merges its shadow state back,
-	 * both callers would obtain the same random number stream without
-	 * changing the state here.
-	 */
-	if (!drbg->test_data) {
-		now.cycles = random_get_entropy();
-		drbg_string_fill(&timestamp, now.char_cycles, sizeof(cycles_t));
-		list_add_tail(&timestamp.list, &addtllist);
-	}
 	if (addtl && 0 < addtl->len)
 		list_add_tail(&addtl->list, &addtllist);
 	/* 9.3.1 step 8 and 10 */
-	len = shadow->d_ops->generate(shadow, buf, buflen, &addtllist);
+	len = drbg->d_ops->generate(drbg, buf, buflen, &addtllist);
 
 	/* 10.1.1.4 step 6, 10.1.2.5 step 7, 10.2.1.5.2 step 7 */
-	shadow->reseed_ctr++;
+	drbg->reseed_ctr++;
 	if (0 >= len)
 		goto err;
 
@@ -1391,7 +1293,7 @@ static int drbg_generate(struct drbg_state *drbg,
 	 * case somebody has a need to implement the test of 11.3.3.
 	 */
 #if 0
-	if (shadow->reseed_ctr && !(shadow->reseed_ctr % 4096)) {
+	if (drbg->reseed_ctr && !(drbg->reseed_ctr % 4096)) {
 		int err = 0;
 		pr_devel("DRBG: start to perform self test\n");
 		if (drbg->core->flags & DRBG_HMAC)
@@ -1410,8 +1312,6 @@ static int drbg_generate(struct drbg_state *drbg,
 			 * are returned when reusing this DRBG cipher handle
 			 */
 			drbg_uninstantiate(drbg);
-			drbg_dealloc_state(shadow);
-			kzfree(shadow);
 			return 0;
 		} else {
 			pr_devel("DRBG: self test successful\n");
@@ -1425,8 +1325,7 @@ static int drbg_generate(struct drbg_state *drbg,
 	 */
 	len = 0;
 err:
-	shadow->d_ops->crypto_fini(shadow);
-	drbg_restore_shadow(drbg, &shadow);
+	drbg->d_ops->crypto_fini(drbg);
 	return len;
 }
 
@@ -1449,7 +1348,9 @@ static int drbg_generate_long(struct drbg_state *drbg,
 		unsigned int chunk = 0;
 		slice = ((buflen - len) / drbg_max_request_bytes(drbg));
 		chunk = slice ? drbg_max_request_bytes(drbg) : (buflen - len);
+		mutex_lock(&drbg->drbg_mutex);
 		err = drbg_generate(drbg, buf + len, chunk, addtl);
+		mutex_unlock(&drbg->drbg_mutex);
 		if (0 > err)
 			return err;
 		len += chunk;
@@ -1477,10 +1378,11 @@ static int drbg_generate_long(struct drbg_state *drbg,
 static int drbg_instantiate(struct drbg_state *drbg, struct drbg_string *pers,
 			    int coreref, bool pr)
 {
-	int ret = -ENOMEM;
+	int ret = -EOPNOTSUPP;
 
 	pr_devel("DRBG: Initializing DRBG core %d with prediction resistance "
 		 "%s\n", coreref, pr ? "enabled" : "disabled");
+	mutex_lock(&drbg->drbg_mutex);
 	drbg->core = &drbg_cores[coreref];
 	drbg->pr = pr;
 	drbg->seeded = false;
@@ -1501,7 +1403,7 @@ static int drbg_instantiate(struct drbg_state *drbg, struct drbg_string *pers,
 		break;
 #endif /* CONFIG_CRYPTO_DRBG_CTR */
 	default:
-		return -EOPNOTSUPP;
+		goto unlock;
 	}
 
 	/* 9.1 step 1 is implicit with the selected DRBG type */
@@ -1516,7 +1418,7 @@ static int drbg_instantiate(struct drbg_state *drbg, struct drbg_string *pers,
 
 	ret = drbg_alloc_state(drbg);
 	if (ret)
-		return ret;
+		goto unlock;
 
 	ret = -EFAULT;
 	if (drbg->d_ops->crypto_init(drbg))
@@ -1526,10 +1428,13 @@ static int drbg_instantiate(struct drbg_state *drbg, struct drbg_string *pers,
 	if (ret)
 		goto err;
 
+	mutex_unlock(&drbg->drbg_mutex);
 	return 0;
 
 err:
 	drbg_dealloc_state(drbg);
+unlock:
+	mutex_unlock(&drbg->drbg_mutex);
 	return ret;
 }
 
@@ -1544,10 +1449,10 @@ err:
  */
 static int drbg_uninstantiate(struct drbg_state *drbg)
 {
-	spin_lock_bh(&drbg->drbg_lock);
+	mutex_lock(&drbg->drbg_mutex);
 	drbg_dealloc_state(drbg);
 	/* no scrubbing of test_data -- this shall survive an uninstantiate */
-	spin_unlock_bh(&drbg->drbg_lock);
+	mutex_unlock(&drbg->drbg_mutex);
 	return 0;
 }
 
@@ -1562,9 +1467,9 @@ static inline void drbg_set_testdata(struct drbg_state *drbg,
 {
 	if (!test_data || !test_data->testentropy)
 		return;
-	spin_lock_bh(&drbg->drbg_lock);
+	mutex_lock(&drbg->drbg_mutex);;
 	drbg->test_data = test_data;
-	spin_unlock_bh(&drbg->drbg_lock);
+	mutex_unlock(&drbg->drbg_mutex);
 }
 
 /***************************************************************
@@ -1717,6 +1622,7 @@ static int drbg_kcapi_init(struct crypto_tfm *tfm)
 	bool pr = false;
 	int coreref = 0;
 
+	mutex_init(&drbg->drbg_mutex);
 	drbg_convert_tfm_core(crypto_tfm_alg_driver_name(tfm), &coreref, &pr);
 	/*
 	 * when personalization string is needed, the caller must call reset
diff --git a/include/crypto/drbg.h b/include/crypto/drbg.h
index 5186f75..a43a7ed 100644
--- a/include/crypto/drbg.h
+++ b/include/crypto/drbg.h
@@ -49,7 +49,7 @@
 #include <crypto/internal/rng.h>
 #include <crypto/rng.h>
 #include <linux/fips.h>
-#include <linux/spinlock.h>
+#include <linux/mutex.h>
 #include <linux/list.h>
 
 /*
@@ -104,7 +104,7 @@ struct drbg_test_data {
 };
 
 struct drbg_state {
-	spinlock_t drbg_lock;	/* lock around DRBG */
+	struct mutex drbg_mutex;	/* lock around DRBG */
 	unsigned char *V;	/* internal state 10.1.1.1 1a) */
 	/* hash: static value 10.1.1.1 1b) hmac / ctr: key */
 	unsigned char *C;
-- 
2.1.0

[PATCH v3 3/3] crypto: drbg - leave cipher handles operational

[Stephan Mueller]

As the DRBG does not operate on shadow copies of the DRBG instance
any more, the cipher handles only need to be allocated once during
initalization time and deallocated during uninstantiate time.

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

diff --git a/crypto/drbg.c b/crypto/drbg.c
index 3683bb3..1ceb76c 100644
--- a/crypto/drbg.c
+++ b/crypto/drbg.c
@@ -1249,11 +1249,6 @@ static int drbg_generate(struct drbg_state *drbg,
 	if ((drbg_max_requests(drbg)) < drbg->reseed_ctr)
 		drbg->seeded = false;
 
-	/* allocate cipher handle */
-	len = drbg->d_ops->crypto_init(drbg);
-	if (len)
-		goto err;
-
 	if (drbg->pr || !drbg->seeded) {
 		pr_devel("DRBG: reseeding before generation (prediction "
 			 "resistance: %s, state %s)\n",
@@ -1325,7 +1320,6 @@ static int drbg_generate(struct drbg_state *drbg,
 	 */
 	len = 0;
 err:
-	drbg->d_ops->crypto_fini(drbg);
 	return len;
 }
 
@@ -1424,9 +1418,10 @@ static int drbg_instantiate(struct drbg_state *drbg, struct drbg_string *pers,
 	if (drbg->d_ops->crypto_init(drbg))
 		goto err;
 	ret = drbg_seed(drbg, pers, false);
-	drbg->d_ops->crypto_fini(drbg);
-	if (ret)
+	if (ret) {
+		drbg->d_ops->crypto_fini(drbg);
 		goto err;
+	}
 
 	mutex_unlock(&drbg->drbg_mutex);
 	return 0;
@@ -1450,6 +1445,7 @@ unlock:
 static int drbg_uninstantiate(struct drbg_state *drbg)
 {
 	mutex_lock(&drbg->drbg_mutex);
+	drbg->d_ops->crypto_fini(drbg);
 	drbg_dealloc_state(drbg);
 	/* no scrubbing of test_data -- this shall survive an uninstantiate */
 	mutex_unlock(&drbg->drbg_mutex);
-- 
2.1.0

Re: [PATCH v3 0/3] crypto: drbg - revamp locking

[Herbert Xu]

On Sat, Apr 18, 2015 at 07:35:11PM +0200, Stephan Mueller wrote:
> Hi,
> 
> the current implementation of the DRBG generates a shadow copy of its
> DRBG state for each incoming request. The idea is that only a short
> term lock is needed to spawn the shadow copy. The drawback is that
> if multiple parallel requests come in, the generated DRBG shadow
> states only differ by a high-resolution timer that was mixed in during
> the shadow state generation.
> 
> This patch now removes this shadow state and introduces a mutex
> to serialize all requests to one DRBG instance.
> 
> The patch was fully CAVS tested and demonstrates that the DRBG still
> complies with the standard.

All applied.
-- 
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

Re: [PATCH v3 0/3] crypto: drbg - revamp locking

[Stephan Mueller]

Am Sonntag, 19. April 2015, 13:49:31 schrieb Herbert Xu:

Hi Herbert,

> On Sat, Apr 18, 2015 at 07:35:11PM +0200, Stephan Mueller wrote:
> > Hi,
> > 
> > the current implementation of the DRBG generates a shadow copy of its
> > DRBG state for each incoming request. The idea is that only a short
> > term lock is needed to spawn the shadow copy. The drawback is that
> > if multiple parallel requests come in, the generated DRBG shadow
> > states only differ by a high-resolution timer that was mixed in during
> > the shadow state generation.
> > 
> > This patch now removes this shadow state and introduces a mutex
> > to serialize all requests to one DRBG instance.
> > 
> > The patch was fully CAVS tested and demonstrates that the DRBG still
> > complies with the standard.
> 
> All applied.

Thanks -- can you please push your tree? There is one more mutex_init missing: 
in drbg_healthcheck.

This missing mutex_init will cause a segfault when booting the kernel with 
fips=1

-- 
Ciao
Stephan

Re: [PATCH v3 0/3] crypto: drbg - revamp locking

[Herbert Xu]

On Sun, Apr 19, 2015 at 05:35:23PM +0200, Stephan Mueller wrote:
>
> Thanks -- can you please push your tree? There is one more mutex_init missing: 
> in drbg_healthcheck.

I've got that fixed in my tree already but yes I will push it soon
once my test is complete.

Cheers,
-- 
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