[RFC PATCH] akcipher: Introduce verify2 for public key algorithms

[RFC PATCH] akcipher: Introduce verify2 for public key algorithms

[Vitaly Chikunov]

Current akcipher .verify() just decrypts signature to uncover message
hash, which is then verified in upper level public_key_verify_signature
by memcmp with the expected signature value, which is never passed into
verify().

This approach is incompatible with ECDSA algorithms, because, to verify
a signature ECDSA algorithm also needs a hash value as input; also, hash
is used in ECDSA (together with a signature divided into halves `r||s`),
not to produce hash, but to produce a number, which is then compared to
`r` (first part of the signature) to determine if the signature is
correct.  Thus, for ECDSA, nor requirements of .verify() itself, nor its
output expectations in public_key_verify_signature aren't satisfied.

Make alternative .verify2() call which gets hash value and produce
complete signature check (without any output, thus max_size() call will
not be needed for verify2() operation).

If .verify2() call is present, it should be used in place of .verify().

Signed-off-by: Vitaly Chikunov <vt@altlinux.org>
---
 crypto/asymmetric_keys/public_key.c | 57 ++++++++++++++++++++++++-------------
 include/crypto/akcipher.h           | 54 +++++++++++++++++++++++++++++++++--
 2 files changed, 89 insertions(+), 22 deletions(-)

diff --git a/crypto/asymmetric_keys/public_key.c b/crypto/asymmetric_keys/public_key.c
index 3bc090b8adef..51dc1c858c7c 100644
--- a/crypto/asymmetric_keys/public_key.c
+++ b/crypto/asymmetric_keys/public_key.c
@@ -242,6 +242,7 @@ int public_key_verify_signature(const struct public_key *pkey,
 	char alg_name[CRYPTO_MAX_ALG_NAME];
 	void *output;
 	unsigned int outlen;
+	int verify2;
 	int ret;
 
 	pr_devel("==>%s()\n", __func__);
@@ -279,14 +280,23 @@ int public_key_verify_signature(const struct public_key *pkey,
 	if (ret)
 		goto error_free_req;
 
-	ret = -ENOMEM;
-	outlen = crypto_akcipher_maxsize(tfm);
-	output = kmalloc(outlen, GFP_KERNEL);
-	if (!output)
-		goto error_free_req;
-
+	verify2 = crypto_akcipher_have_verify2(req);
+	if (!verify2) {
+		/* verify2 does not need output buffer */
+		ret = -ENOMEM;
+		outlen = crypto_akcipher_maxsize(tfm);
+		output = kmalloc(outlen, GFP_KERNEL);
+		if (!output)
+			goto error_free_req;
+
+		sg_init_one(&digest_sg, output, outlen);
+	} else {
+		/* dummy init digest_sg */
+		memset(&digest_sg, 0, sizeof(digest_sg));
+		output = NULL;
+		outlen = 0;
+	}
 	sg_init_one(&sig_sg, sig->s, sig->s_size);
-	sg_init_one(&digest_sg, output, outlen);
 	akcipher_request_set_crypt(req, &sig_sg, &digest_sg, sig->s_size,
 				   outlen);
 	crypto_init_wait(&cwait);
@@ -294,18 +304,27 @@ int public_key_verify_signature(const struct public_key *pkey,
 				      CRYPTO_TFM_REQ_MAY_SLEEP,
 				      crypto_req_done, &cwait);
 
-	/* Perform the verification calculation.  This doesn't actually do the
-	 * verification, but rather calculates the hash expected by the
-	 * signature and returns that to us.
-	 */
-	ret = crypto_wait_req(crypto_akcipher_verify(req), &cwait);
-	if (ret)
-		goto out_free_output;
-
-	/* Do the actual verification step. */
-	if (req->dst_len != sig->digest_size ||
-	    memcmp(sig->digest, output, sig->digest_size) != 0)
-		ret = -EKEYREJECTED;
+	if (!verify2) {
+		/* Perform the verification calculation.  This doesn't actually
+		 * do the verification, but rather calculates the hash expected
+		 * by the signature and returns that to us.
+		 */
+		ret = crypto_wait_req(crypto_akcipher_verify(req), &cwait);
+		if (ret)
+			goto out_free_output;
+
+		/* Do the actual verification step. */
+		if (req->dst_len != sig->digest_size ||
+		    memcmp(sig->digest, output, sig->digest_size) != 0)
+			ret = -EKEYREJECTED;
+	} else {
+		/* Perform full verification in one call. */
+		req->digest = sig->digest;
+		req->digest_len = sig->digest_size;
+		ret = crypto_wait_req(crypto_akcipher_verify2(req), &cwait);
+		if (ret)
+			goto out_free_output;
+	}
 
 out_free_output:
 	kfree(output);
diff --git a/include/crypto/akcipher.h b/include/crypto/akcipher.h
index d6aba84ed2c4..f1ad67474bc1 100644
--- a/include/crypto/akcipher.h
+++ b/include/crypto/akcipher.h
@@ -28,6 +28,8 @@
  *		result.
  *		In case of error where the dst sgl size was insufficient,
  *		it will be updated to the size required for the operation.
+ * @digest:	Digest for verify2.
+ * @digest_len:	Size of the digest.
  * @__ctx:	Start of private context data
  */
 struct akcipher_request {
@@ -36,6 +38,8 @@ struct akcipher_request {
 	struct scatterlist *dst;
 	unsigned int src_len;
 	unsigned int dst_len;
+	u8 *digest;
+	u8 digest_len;
 	void *__ctx[] CRYPTO_MINALIGN_ATTR;
 };
 
@@ -60,6 +64,8 @@ struct crypto_akcipher {
  *		algorithm. In case of error, where the dst_len was insufficient,
  *		the req->dst_len will be updated to the size required for the
  *		operation
+ * @verify2:	Function performs a verify operation as defined by public key
+ *		algorithm.
  * @encrypt:	Function performs an encrypt operation as defined by public key
  *		algorithm. In case of error, where the dst_len was insufficient,
  *		the req->dst_len will be updated to the size required for the
@@ -96,6 +102,7 @@ struct crypto_akcipher {
 struct akcipher_alg {
 	int (*sign)(struct akcipher_request *req);
 	int (*verify)(struct akcipher_request *req);
+	int (*verify2)(struct akcipher_request *req);
 	int (*encrypt)(struct akcipher_request *req);
 	int (*decrypt)(struct akcipher_request *req);
 	int (*set_pub_key)(struct crypto_akcipher *tfm, const void *key,
@@ -400,11 +407,13 @@ static inline int crypto_akcipher_sign(struct akcipher_request *req)
  * crypto_akcipher_verify() - Invoke public key verify operation
  *
  * Function invokes the specific public key verify operation for a given
- * public key algorithm
+ * public key algorithm: basically it does (rsa) decrypt of signature
+ * producing decrypted hash into dst, which should be compared by a caller
+ * with expected hash value.
  *
- * @req:	asymmetric key request
+ * @req:	asymmetric key request (without hash)
  *
- * Return: zero on success; error code in case of error
+ * Return: zero on decryption success; error code in case of error
  */
 static inline int crypto_akcipher_verify(struct akcipher_request *req)
 {
@@ -418,6 +427,45 @@ static inline int crypto_akcipher_verify(struct akcipher_request *req)
 }
 
 /**
+ * crypto_akcipher_verify2() - Invoke public key verify operation
+ *
+ * Function performs complete public key verify operation for a given
+ * public key algorithm
+ *
+ * @req:	asymmetric key request (with hash)
+ *
+ * Return: zero on verification success; error code in case of error
+ */
+static inline int crypto_akcipher_verify2(struct akcipher_request *req)
+{
+	struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
+	struct akcipher_alg *alg = crypto_akcipher_alg(tfm);
+	int ret;
+
+	ret = alg->verify2(req);
+	crypto_stat_akcipher_verify(req, ret);
+	return ret;
+}
+
+/**
+ * crypto_akcipher_have_verify2() - Check for existence of public key verify2
+ * operation
+ *
+ * Function checks for existence of verify2 call for the public key algorithm
+ *
+ * @req:	asymmetric key request (with hash)
+ *
+ * Return: non-zero is verify2 call exists; zero if it does not
+ */
+static inline int crypto_akcipher_have_verify2(struct akcipher_request *req)
+{
+	struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
+	struct akcipher_alg *alg = crypto_akcipher_alg(tfm);
+
+	return !!alg->verify2;
+}
+
+/**
  * crypto_akcipher_set_pub_key() - Invoke set public key operation
  *
  * Function invokes the algorithm specific set key function, which knows
-- 
2.11.0

Re: [RFC PATCH] akcipher: Introduce verify2 for public key algorithms

[Herbert Xu]

Vitaly Chikunov <vt@altlinux.org> wrote:
> Current akcipher .verify() just decrypts signature to uncover message
> hash, which is then verified in upper level public_key_verify_signature
> by memcmp with the expected signature value, which is never passed into
> verify().
> 
> This approach is incompatible with ECDSA algorithms, because, to verify
> a signature ECDSA algorithm also needs a hash value as input; also, hash
> is used in ECDSA (together with a signature divided into halves `r||s`),
> not to produce hash, but to produce a number, which is then compared to
> `r` (first part of the signature) to determine if the signature is
> correct.  Thus, for ECDSA, nor requirements of .verify() itself, nor its
> output expectations in public_key_verify_signature aren't satisfied.
> 
> Make alternative .verify2() call which gets hash value and produce
> complete signature check (without any output, thus max_size() call will
> not be needed for verify2() operation).
> 
> If .verify2() call is present, it should be used in place of .verify().
> 
> Signed-off-by: Vitaly Chikunov <vt@altlinux.org>

We should convert all existing users to this interface and not
have both verify/verify2 forever.

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 PATCH] akcipher: Introduce verify2 for public key algorithms

[Tudor.Ambarus]

Hi,

On 12/11/2018 06:59 PM, Vitaly Chikunov wrote:
> Current akcipher .verify() just decrypts signature to uncover message
> hash, which is then verified in upper level public_key_verify_signature
> by memcmp with the expected signature value, which is never passed into
> verify().
> 
> This approach is incompatible with ECDSA algorithms, because, to verify

I would love to have ECDSA in kernel but unfortunately it hasn't reached kernel
because there is no in-kernel user for it. Do we have an agreement that we will
add support for it? If not, who will benefit of these patches?

Thanks,
ta

Re: [RFC PATCH] akcipher: Introduce verify2 for public key algorithms

[Vitaly Chikunov]

Tudor,

On Thu, Dec 13, 2018 at 10:26:53AM +0000, Tudor.Ambarus@microchip.com wrote:
> 
> On 12/11/2018 06:59 PM, Vitaly Chikunov wrote:
> > Current akcipher .verify() just decrypts signature to uncover message
> > hash, which is then verified in upper level public_key_verify_signature
> > by memcmp with the expected signature value, which is never passed into
> > verify().
> > 
> > This approach is incompatible with ECDSA algorithms, because, to verify
> 
> I would love to have ECDSA in kernel but unfortunately it hasn't reached kernel
> because there is no in-kernel user for it. Do we have an agreement that we will
> add support for it? If not, who will benefit of these patches?

I will post patchset for EC-RDSA support (which is slightly different from
ECDSA, but is the same algorithm family). This is intended for use in IMA.

Even though EC-RDSA is different from ECDSA it will require the same changes
that I propose in these RFCs. Basically, after EC-RDSA is implemented and
hooked into IMA it will be much easier to implement ECDSA.

An additional use case is future possibility to implement other signature
schemes out of tree, which is currently not possible because API is very
RSA-centric.

Thanks,

> 
> Thanks,
> ta

Re: [RFC PATCH] akcipher: Introduce verify2 for public key algorithms

[Vitaly Chikunov]

On Thu, Dec 13, 2018 at 06:12:33PM +0800, Herbert Xu wrote:
> Vitaly Chikunov <vt@altlinux.org> wrote:
> > Current akcipher .verify() just decrypts signature to uncover message
> > hash, which is then verified in upper level public_key_verify_signature
> > by memcmp with the expected signature value, which is never passed into
> > verify().
> > 
> > This approach is incompatible with ECDSA algorithms, because, to verify
> > a signature ECDSA algorithm also needs a hash value as input; also, hash
> > is used in ECDSA (together with a signature divided into halves `r||s`),
> > not to produce hash, but to produce a number, which is then compared to
> > `r` (first part of the signature) to determine if the signature is
> > correct.  Thus, for ECDSA, nor requirements of .verify() itself, nor its
> > output expectations in public_key_verify_signature aren't satisfied.
> > 
> > Make alternative .verify2() call which gets hash value and produce
> > complete signature check (without any output, thus max_size() call will
> > not be needed for verify2() operation).
> > 
> > If .verify2() call is present, it should be used in place of .verify().
> > 
> > Signed-off-by: Vitaly Chikunov <vt@altlinux.org>
> 
> We should convert all existing users to this interface and not
> have both verify/verify2 forever.

This will be hard to do since there is at least tree device that use
this interface (and who know how much out of tree):

  drivers$ git grep cra_name.*rsa
  crypto/caam/caampkc.c:          .cra_name = "rsa",
  crypto/ccp/ccp-crypto-rsa.c:            .cra_name = "rsa",
  crypto/qat/qat_common/qat_asym_algs.c:          .cra_name = "rsa",

Interface seems to be designed that verify() call is interchangeable
with encrypt().

Two verify does not seem that bad since there is common code for the old
interface that removes code duplication and simplifies driver
implementation (RSA drivers only need to implement encrypt).

But, I would remove scatterlist from the new interface. Signature
verification is not some multi-block encryption. And basically,
public_key_verify_signature just doing sg_init_one for both required
src/dst buffers.

ps. And also, in the future, I would allow akcipher to access `struct
public_key` and `struct public_key_signature` so it could distinguish
when the key is already validated and skip expensive validation other
time verify2 is used with the same key. Or maybe flag 'key validation is
needed' should be maintained outside of akcipher and passed to it in the
request.

> 
> 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 PATCH] akcipher: Introduce verify2 for public key algorithms

[David Howells]

Vitaly Chikunov <vt@altlinux.org> wrote:

> This will be hard to do since there is at least tree device that use
> this interface (and who know how much out of tree):
> 
>   drivers$ git grep cra_name.*rsa
>   crypto/caam/caampkc.c:          .cra_name = "rsa",
>   crypto/ccp/ccp-crypto-rsa.c:            .cra_name = "rsa",
>   crypto/qat/qat_common/qat_asym_algs.c:          .cra_name = "rsa",
> 
> Interface seems to be designed that verify() call is interchangeable
> with encrypt().
> 
> Two verify does not seem that bad since there is common code for the old
> interface that removes code duplication and simplifies driver
> implementation (RSA drivers only need to implement encrypt).

You could move the comparison into core crypto code if it's makes more sense
than moving the comparison to the crypto algorithm ->verify() call.  It makes
more sense than the upper layers having to cover the differences between the
algo modules.

David