[PATCH] crypto: DRBG - reduce number of setkey calls

[PATCH] crypto: DRBG - reduce number of setkey calls

[Stephan Mueller]

The CTR DRBG code always set the key for each sym cipher invocation even
though the key has not been changed.

The patch ensures that the setkey is only invoked when a new key is
generated by the DRBG.

With this patch, the CTR DRBG performance increases by more than 150%.

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

diff --git a/crypto/drbg.c b/crypto/drbg.c
index 0a3538f..0aca2b9 100644
--- a/crypto/drbg.c
+++ b/crypto/drbg.c
@@ -252,8 +252,10 @@ MODULE_ALIAS_CRYPTO("drbg_nopr_ctr_aes192");
 MODULE_ALIAS_CRYPTO("drbg_pr_ctr_aes128");
 MODULE_ALIAS_CRYPTO("drbg_nopr_ctr_aes128");
 
-static int drbg_kcapi_sym(struct drbg_state *drbg, const unsigned char *key,
-			  unsigned char *outval, const struct drbg_string *in);
+static void drbg_kcapi_symsetkey(struct drbg_state *drbg,
+				 const unsigned char *key);
+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);
 
@@ -270,6 +272,7 @@ static int drbg_ctr_bcc(struct drbg_state *drbg,
 	drbg_string_fill(&data, out, drbg_blocklen(drbg));
 
 	/* 10.4.3 step 2 / 4 */
+	drbg_kcapi_symsetkey(drbg, key);
 	list_for_each_entry(curr, in, list) {
 		const unsigned char *pos = curr->buf;
 		size_t len = curr->len;
@@ -278,7 +281,7 @@ static int drbg_ctr_bcc(struct drbg_state *drbg,
 			/* 10.4.3 step 4.2 */
 			if (drbg_blocklen(drbg) == cnt) {
 				cnt = 0;
-				ret = drbg_kcapi_sym(drbg, key, out, &data);
+				ret = drbg_kcapi_sym(drbg, out, &data);
 				if (ret)
 					return ret;
 			}
@@ -290,7 +293,7 @@ static int drbg_ctr_bcc(struct drbg_state *drbg,
 	}
 	/* 10.4.3 step 4.2 for last block */
 	if (cnt)
-		ret = drbg_kcapi_sym(drbg, key, out, &data);
+		ret = drbg_kcapi_sym(drbg, out, &data);
 
 	return ret;
 }
@@ -425,6 +428,7 @@ static int drbg_ctr_df(struct drbg_state *drbg,
 	/* 10.4.2 step 12: overwriting of outval is implemented in next step */
 
 	/* 10.4.2 step 13 */
+	drbg_kcapi_symsetkey(drbg, temp);
 	while (generated_len < bytes_to_return) {
 		short blocklen = 0;
 		/*
@@ -432,7 +436,7 @@ static int drbg_ctr_df(struct drbg_state *drbg,
 		 * implicit as the key is only drbg_blocklen in size based on
 		 * the implementation of the cipher function callback
 		 */
-		ret = drbg_kcapi_sym(drbg, temp, X, &cipherin);
+		ret = drbg_kcapi_sym(drbg, X, &cipherin);
 		if (ret)
 			goto out;
 		blocklen = (drbg_blocklen(drbg) <
@@ -488,6 +492,7 @@ static int drbg_ctr_update(struct drbg_state *drbg, struct list_head *seed,
 		ret = drbg_ctr_df(drbg, df_data, drbg_statelen(drbg), seed);
 		if (ret)
 			goto out;
+		drbg_kcapi_symsetkey(drbg, drbg->C);
 	}
 
 	drbg_string_fill(&cipherin, drbg->V, drbg_blocklen(drbg));
@@ -500,7 +505,7 @@ static int drbg_ctr_update(struct drbg_state *drbg, struct list_head *seed,
 		crypto_inc(drbg->V, drbg_blocklen(drbg));
 		/*
 		 * 10.2.1.2 step 2.2 */
-		ret = drbg_kcapi_sym(drbg, drbg->C, temp + len, &cipherin);
+		ret = drbg_kcapi_sym(drbg, temp + len, &cipherin);
 		if (ret)
 			goto out;
 		/* 10.2.1.2 step 2.3 and 3 */
@@ -517,6 +522,7 @@ static int drbg_ctr_update(struct drbg_state *drbg, struct list_head *seed,
 
 	/* 10.2.1.2 step 5 */
 	memcpy(drbg->C, temp, drbg_keylen(drbg));
+	drbg_kcapi_symsetkey(drbg, drbg->C);
 	/* 10.2.1.2 step 6 */
 	memcpy(drbg->V, temp + drbg_keylen(drbg), drbg_blocklen(drbg));
 	ret = 0;
@@ -546,6 +552,7 @@ static int drbg_ctr_generate(struct drbg_state *drbg,
 		ret = drbg_ctr_update(drbg, addtl, 2);
 		if (ret)
 			return 0;
+		drbg_kcapi_symsetkey(drbg, drbg->C);
 	}
 
 	/* 10.2.1.5.2 step 4.1 */
@@ -554,7 +561,7 @@ static int drbg_ctr_generate(struct drbg_state *drbg,
 	while (len < buflen) {
 		int outlen = 0;
 		/* 10.2.1.5.2 step 4.2 */
-		ret = drbg_kcapi_sym(drbg, drbg->C, drbg->scratchpad, &data);
+		ret = drbg_kcapi_sym(drbg, drbg->scratchpad, &data);
 		if (ret) {
 			len = ret;
 			goto out;
@@ -1653,13 +1660,21 @@ static int drbg_fini_sym_kernel(struct drbg_state *drbg)
 	return 0;
 }
 
-static int drbg_kcapi_sym(struct drbg_state *drbg, const unsigned char *key,
-			  unsigned char *outval, const struct drbg_string *in)
+static void drbg_kcapi_symsetkey(struct drbg_state *drbg,
+				 const unsigned char *key)
 {
 	struct crypto_cipher *tfm =
 		(struct crypto_cipher *)drbg->priv_data;
 
 	crypto_cipher_setkey(tfm, key, (drbg_keylen(drbg)));
+}
+
+static int drbg_kcapi_sym(struct drbg_state *drbg, unsigned char *outval,
+			  const struct drbg_string *in)
+{
+	struct crypto_cipher *tfm =
+		(struct crypto_cipher *)drbg->priv_data;
+
 	/* there is only component in *in */
 	BUG_ON(in->len < drbg_blocklen(drbg));
 	crypto_cipher_encrypt_one(tfm, outval, in->buf);
-- 
2.5.5

[RFC] DRBG: which shall be default?

[Stephan Mueller]

Hi Herbert,

with that patch, the CTR DRBG is the fasted DRBG by orders of magnitude -- 
about 2 times faster than the HMAC DRBG (current default) and 1.5 times faster 
than the Hash DRBG.

However, I am not too fond of the CTR DRBG due to the following that I already 
mentioned some days ago. Quote:

"""
the DF/BCC function in the DRBG is critical as I think it looses entropy 
IMHO. When you seed the DRBG with, say 256 or 384 bits of data, the BCC acts 
akin a MAC by taking the 256 or 384 bits and collapse it into one AES block of 
128 bits. Then he DF function expands this one block into the DRBG internal 
state including the AES key of 256 / 384 bits depending on the type of AES you 
use. So, if you have 256 bits of entropy in the seed, you have 128 bits left 
after the BCC operation.
"""


The current default of the HMAC DRBG is the leanest and cleanest, but it is 
also the slowest.

The fastest DRBG is the one that has the most complex state maintenance and I 
do not like parts of it.


Hence my question: shall we leave the HMAC DRBG as default or shall we use the 
CTR DRBG as default?

Ciao
Stephan

Re: [RFC] DRBG: which shall be default?

[Herbert Xu]

On Tue, May 31, 2016 at 01:23:21PM +0200, Stephan Mueller wrote:
>
> Hence my question: shall we leave the HMAC DRBG as default or shall we use the 
> CTR DRBG as default?

I don't really care one way or another.

BTW why did you use the crypto_cipher aes interface instead of
the crypto_skcipher ctr(aes) interface which would likely make
your code run many orders-of-magnitude faster, especially with
aesni-intel?

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

Re: [RFC] DRBG: which shall be default?

[Stephan Mueller]

Am Donnerstag, 2. Juni 2016, 16:40:12 schrieb Herbert Xu:

Hi Herbert,

> On Tue, May 31, 2016 at 01:23:21PM +0200, Stephan Mueller wrote:
> > Hence my question: shall we leave the HMAC DRBG as default or shall we use
> > the CTR DRBG as default?
> 
> I don't really care one way or another.
> 
> BTW why did you use the crypto_cipher aes interface instead of
> the crypto_skcipher ctr(aes) interface which would likely make
> your code run many orders-of-magnitude faster, especially with
> aesni-intel?

I considered such approach, but the crux is the following: for the CTR DRBG 
generate function, our state is 16 bytes (i.e. the AES block length). Out of 
those 16 bytes, we generate the random number by encrypting that block, 
incrementing the block by one and encrypt it again. In essence what we do here 
is the stream cipher part of the CTR mode which generates the data stream we 
use to XOR the input data with.

The skcipher API, however, wants to encrypt an entire input data stream. That 
means the skcipher API requires the length of the input data stream to 
generate an equally sized output data stream. But that is not what we have 
here -- there is no input data. I.e. the skcipher API invokes the CTR mode for 
the stream cipher and performs the final XOR of the CTR stream with the input 
data.

Currently I would not see a way how to access the CTR mode stream cipher part 
only via the skcipher API.

Ciao
Stephan

Re: [RFC] DRBG: which shall be default?

[Herbert Xu]

On Thu, Jun 02, 2016 at 11:31:22AM +0200, Stephan Mueller wrote:
>
> The skcipher API, however, wants to encrypt an entire input data stream. That 
> means the skcipher API requires the length of the input data stream to 
> generate an equally sized output data stream. But that is not what we have 
> here -- there is no input data. I.e. the skcipher API invokes the CTR mode for 
> the stream cipher and performs the final XOR of the CTR stream with the input 
> data.

Just use an input stream of zeros.

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

Re: [RFC] DRBG: which shall be default?

[Stephan Mueller]

Am Donnerstag, 2. Juni 2016, 17:42:11 schrieb Herbert Xu:

Hi Herbert,

> On Thu, Jun 02, 2016 at 11:31:22AM +0200, Stephan Mueller wrote:
> > The skcipher API, however, wants to encrypt an entire input data stream.
> > That means the skcipher API requires the length of the input data stream
> > to generate an equally sized output data stream. But that is not what we
> > have here -- there is no input data. I.e. the skcipher API invokes the
> > CTR mode for the stream cipher and performs the final XOR of the CTR
> > stream with the input data.
> 
> Just use an input stream of zeros.

I am working on it. During the analysis, I saw, however, that the DRBG 
increments the counter before the encryption whereas the the CTR mode 
increments it after the encryption.

I could of course adjust the handling in the code, but this would be a real 
hack IMHO.

Ciao
Stephan

Re: [RFC] DRBG: which shall be default?

[Herbert Xu]

On Thu, Jun 02, 2016 at 02:06:55PM +0200, Stephan Mueller wrote:
>
> I am working on it. During the analysis, I saw, however, that the DRBG 
> increments the counter before the encryption whereas the the CTR mode 
> increments it after the encryption.
> 
> I could of course adjust the handling in the code, but this would be a real 
> hack IMHO.

Changing the order of increment is equivalent to changing the IV, no?

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

Re: [RFC] DRBG: which shall be default?

[Stephan Mueller]

Am Mittwoch, 8. Juni 2016, 10:41:40 schrieb Herbert Xu:

Hi Herbert,

> On Thu, Jun 02, 2016 at 02:06:55PM +0200, Stephan Mueller wrote:
> > I am working on it. During the analysis, I saw, however, that the DRBG
> > increments the counter before the encryption whereas the the CTR mode
> > increments it after the encryption.
> > 
> > I could of course adjust the handling in the code, but this would be a
> > real
> > hack IMHO.
> 
> Changing the order of increment is equivalent to changing the IV, no?

I finally got it working. All I needed to do is to add a crypto_inc(V) after a 
recalculation of V.

The performance with ctr-aes-aesni on 64 bit is as follows -- I used my LRNG 
implementation for testing for which I already have performance measurements:

- generating smaller lengths (I tested up to 128 bytes) of random numbers 
(which is the vast majority of random numbers to be generated), the 
performance is even worse by 10 to 15%

- generating larger lengths (tested with 4096 bytes) of random numbers, the 
performance increases by 3%

Using ctr(aes-aesni) on 32 bit, the numbers are generally worse by 5 to 10%.

So, with these numbers, I would conclude that switching to the CTR mode is not 
worthwhile.

Ciao
Stephan

Re: [RFC] DRBG: which shall be default?

[Stephan Mueller]

Am Mittwoch, 8. Juni 2016, 09:56:42 schrieb Stephan Mueller:

Hi Stephan,

> Am Mittwoch, 8. Juni 2016, 10:41:40 schrieb Herbert Xu:
> 
> Hi Herbert,
> 
> > On Thu, Jun 02, 2016 at 02:06:55PM +0200, Stephan Mueller wrote:
> > > I am working on it. During the analysis, I saw, however, that the DRBG
> > > increments the counter before the encryption whereas the the CTR mode
> > > increments it after the encryption.
> > > 
> > > I could of course adjust the handling in the code, but this would be a
> > > real
> > > hack IMHO.
> > 
> > Changing the order of increment is equivalent to changing the IV, no?
> 
> I finally got it working. All I needed to do is to add a crypto_inc(V) after
> a recalculation of V.

One addition: my NULL vector is 128 bytes in size.
> 
> The performance with ctr-aes-aesni on 64 bit is as follows -- I used my LRNG
> implementation for testing for which I already have performance
> measurements:
> 
> - generating smaller lengths (I tested up to 128 bytes) of random numbers
> (which is the vast majority of random numbers to be generated), the
> performance is even worse by 10 to 15%
> 
> - generating larger lengths (tested with 4096 bytes) of random numbers, the
> performance increases by 3%
> 
> Using ctr(aes-aesni) on 32 bit, the numbers are generally worse by 5 to 10%.
> 
> So, with these numbers, I would conclude that switching to the CTR mode is
> not worthwhile.
> 
> Ciao
> Stephan
> --
> To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html


Ciao
Stephan

Re: [RFC] DRBG: which shall be default?

[Herbert Xu]

On Wed, Jun 08, 2016 at 09:56:42AM +0200, Stephan Mueller wrote:
>
> The performance with ctr-aes-aesni on 64 bit is as follows -- I used my LRNG 
> implementation for testing for which I already have performance measurements:
> 
> - generating smaller lengths (I tested up to 128 bytes) of random numbers 
> (which is the vast majority of random numbers to be generated), the 
> performance is even worse by 10 to 15%
> 
> - generating larger lengths (tested with 4096 bytes) of random numbers, the 
> performance increases by 3%
> 
> Using ctr(aes-aesni) on 32 bit, the numbers are generally worse by 5 to 10%.

ctr(aes-aesni) is not the same thing as ctr-aes-aesni, the former
being just another way of doing what you were doing.  So did you
actually test the real optimised version which is ctr-aes-aesni?

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

Re: [RFC] DRBG: which shall be default?

[Stephan Mueller]

Am Mittwoch, 8. Juni 2016, 16:00:55 schrieb Herbert Xu:

Hi Herbert,

> On Wed, Jun 08, 2016 at 09:56:42AM +0200, Stephan Mueller wrote:
> > The performance with ctr-aes-aesni on 64 bit is as follows -- I used my
> > LRNG implementation for testing for which I already have performance
> > measurements:
> > 
> > - generating smaller lengths (I tested up to 128 bytes) of random numbers
> > (which is the vast majority of random numbers to be generated), the
> > performance is even worse by 10 to 15%
> > 
> > - generating larger lengths (tested with 4096 bytes) of random numbers,
> > the
> > performance increases by 3%
> > 
> > Using ctr(aes-aesni) on 32 bit, the numbers are generally worse by 5 to
> > 10%.
> ctr(aes-aesni) is not the same thing as ctr-aes-aesni, the former
> being just another way of doing what you were doing.  So did you
> actually test the real optimised version which is ctr-aes-aesni?

Indeed, I used ctr(aes-aesni) instead of ctr-aes-aesni according to the refcnt 
in /proc/crypto. The reason was that I used the sync skcipher API which 
naturally excludes the ctr-aes-aesni.

When changing it to really use ctr-aes-aesni, I get: between 450% performance 
gains (for 4096 bytes -- 780 MB/s(!)) and 4% gain (for 16 bytes).

Though, on 32 bit with ctr(aes-aesni) -- which is a blkcipher -- I get a 
performance degradation of 10% (4096 bytes) and 20% (16 bytes).

Any ideas on how to handle the blkcipher in a better way?

Ciao
Stephan

Re: [RFC] DRBG: which shall be default?

[Herbert Xu]

On Wed, Jun 08, 2016 at 10:58:37AM +0200, Stephan Mueller wrote:
>
> Indeed, I used ctr(aes-aesni) instead of ctr-aes-aesni according to the refcnt 
> in /proc/crypto. The reason was that I used the sync skcipher API which 
> naturally excludes the ctr-aes-aesni.
> 
> When changing it to really use ctr-aes-aesni, I get: between 450% performance 
> gains (for 4096 bytes -- 780 MB/s(!)) and 4% gain (for 16 bytes).
> 
> Though, on 32 bit with ctr(aes-aesni) -- which is a blkcipher -- I get a 
> performance degradation of 10% (4096 bytes) and 20% (16 bytes).
> 
> Any ideas on how to handle the blkcipher in a better way?

You should always use ctr-aes-aesni, ctr(aes-aesni) makes no sense.

So I don't quite understand why you need to handle blkcipher, does
ctr-aes-aesni not work on 32-bit?

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

Re: [RFC] DRBG: which shall be default?

[Stephan Mueller]

Am Mittwoch, 8. Juni 2016, 17:03:54 schrieb Herbert Xu:

Hi Herbert,

> On Wed, Jun 08, 2016 at 10:58:37AM +0200, Stephan Mueller wrote:
> > Indeed, I used ctr(aes-aesni) instead of ctr-aes-aesni according to the
> > refcnt in /proc/crypto. The reason was that I used the sync skcipher API
> > which naturally excludes the ctr-aes-aesni.
> > 
> > When changing it to really use ctr-aes-aesni, I get: between 450%
> > performance gains (for 4096 bytes -- 780 MB/s(!)) and 4% gain (for 16
> > bytes).
> > 
> > Though, on 32 bit with ctr(aes-aesni) -- which is a blkcipher -- I get a
> > performance degradation of 10% (4096 bytes) and 20% (16 bytes).
> > 
> > Any ideas on how to handle the blkcipher in a better way?
> 
> You should always use ctr-aes-aesni, ctr(aes-aesni) makes no sense.
> 
> So I don't quite understand why you need to handle blkcipher, does
> ctr-aes-aesni not work on 32-bit?

No, it does not:

#ifdef CONFIG_X86_64
}, {
        .cra_name               = "__ctr-aes-aesni",
        .cra_driver_name        = "__driver-ctr-aes-aesni",
...
}, {
        .cra_name               = "ctr(aes)",
        .cra_driver_name        = "ctr-aes-aesni",


==> ctr-aes-aesni is not available in 32 bit. Only aes-aesni is available in 
32 bit so the system defaults to ctr(aes-aesni).

Note, in my tests I use a generic code that requests ctr(aes). I am not arch-
specific in the code. The discussion above is the analysis of the kernel 
crypto API's decisions.

Ciao
Stephan

Re: [RFC] DRBG: which shall be default?

[Herbert Xu]

On Wed, Jun 08, 2016 at 11:07:42AM +0200, Stephan Mueller wrote:
>
> No, it does not:
> 
> #ifdef CONFIG_X86_64

Well there is no fundamental reason why we can't do it on 32-bit.
Even if we just did the counter increment in C this would still
beat ctr(aes-aesni) by many orders of magnitude.

So if you really care about the performance on x86-32 then perhaps
you should send a patch to implement ctr-aes-aesni for it.

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

Re: [RFC] DRBG: which shall be default?

[Stephan Mueller]

Am Mittwoch, 8. Juni 2016, 17:15:00 schrieb Herbert Xu:

Hi Herbert, Tadeusz,

> On Wed, Jun 08, 2016 at 11:07:42AM +0200, Stephan Mueller wrote:
> > No, it does not:
> > 
> > #ifdef CONFIG_X86_64
> 
> Well there is no fundamental reason why we can't do it on 32-bit.
> Even if we just did the counter increment in C this would still
> beat ctr(aes-aesni) by many orders of magnitude.

I would think that the performance boost on 64 bit should warrant an official 
patch set.
> 
> So if you really care about the performance on x86-32 then perhaps
> you should send a patch to implement ctr-aes-aesni for it.

Maybe Intel can shed some light on this:

Tadeusz, can you please help me understand why the ctr-aes-aesni is only 
defined for 64 bit?

Thanks
Stephan

Re: [PATCH] crypto: DRBG - reduce number of setkey calls

[Herbert Xu]

On Tue, May 31, 2016 at 01:11:57PM +0200, Stephan Mueller wrote:
> The CTR DRBG code always set the key for each sym cipher invocation even
> though the key has not been changed.
> 
> The patch ensures that the setkey is only invoked when a new key is
> generated by the DRBG.
> 
> With this patch, the CTR DRBG performance increases by more than 150%.
> 
> Signed-off-by: Stephan Mueller <smueller@chronox.de>

Patch 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