[PATCH 0/3] crypto: more rsa-pkcs1pad fixes

[PATCH 0/3] crypto: more rsa-pkcs1pad fixes

[Eric Biggers]

This series fixes two more bugs in rsa-pkcs1pad.

Eric Biggers (3):
  crypto: rsa-pkcs1pad - correctly get hash from source scatterlist
  crypto: rsa-pkcs1pad - fix buffer overread in
    pkcs1pad_verify_complete()
  crypto: rsa-pkcs1pad - use clearer variable names

 crypto/rsa-pkcs1pad.c | 33 ++++++++++++++++++---------------
 1 file changed, 18 insertions(+), 15 deletions(-)

-- 
2.34.1

[PATCH 1/3] crypto: rsa-pkcs1pad - correctly get hash from source scatterlist

[Eric Biggers]

From: Eric Biggers <ebiggers@google.com>

Commit c7381b012872 ("crypto: akcipher - new verify API for public key
algorithms") changed akcipher_alg::verify to take in both the signature
and the actual hash and do the signature verification, rather than just
return the hash expected by the signature as was the case before.  To do
this, it implemented a hack where the signature and hash are
concatenated with each other in one scatterlist.

Obviously, for this to work correctly, akcipher_alg::verify needs to
correctly extract the two items from the scatterlist it is given.
Unfortunately, it doesn't correctly extract the hash in the case where
the signature is longer than the RSA key size, as it assumes that the
signature's length is equal to the RSA key size.  This causes a prefix
of the hash, or even the entire hash, to be taken from the *signature*.

It is unclear whether the resulting scheme has any useful security
properties.

Fix this by correctly extracting the hash from the scatterlist.

Fixes: c7381b012872 ("crypto: akcipher - new verify API for public key algorithms")
Cc: <stable@vger.kernel.org> # v5.2+
Signed-off-by: Eric Biggers <ebiggers@google.com>
---
 crypto/rsa-pkcs1pad.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/crypto/rsa-pkcs1pad.c b/crypto/rsa-pkcs1pad.c
index 1b3545781425..7b223adebabf 100644
--- a/crypto/rsa-pkcs1pad.c
+++ b/crypto/rsa-pkcs1pad.c
@@ -495,7 +495,7 @@ static int pkcs1pad_verify_complete(struct akcipher_request *req, int err)
 			   sg_nents_for_len(req->src,
 					    req->src_len + req->dst_len),
 			   req_ctx->out_buf + ctx->key_size,
-			   req->dst_len, ctx->key_size);
+			   req->dst_len, req->src_len);
 	/* Do the actual verification step. */
 	if (memcmp(req_ctx->out_buf + ctx->key_size, out_buf + pos,
 		   req->dst_len) != 0)
-- 
2.34.1

[PATCH 2/3] crypto: rsa-pkcs1pad - fix buffer overread in pkcs1pad_verify_complete()

[Eric Biggers]

From: Eric Biggers <ebiggers@google.com>

Before checking whether the expected digest_info is present, we need to
check that there are enough bytes remaining.

Fixes: a49de377e051 ("crypto: Add hash param to pkcs1pad")
Cc: Tadeusz Struk <tadeusz.struk@linaro.org>
Cc: <stable@vger.kernel.org> # v4.6+
Signed-off-by: Eric Biggers <ebiggers@google.com>
---
 crypto/rsa-pkcs1pad.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/crypto/rsa-pkcs1pad.c b/crypto/rsa-pkcs1pad.c
index 7b223adebabf..6cd24b4b9b9e 100644
--- a/crypto/rsa-pkcs1pad.c
+++ b/crypto/rsa-pkcs1pad.c
@@ -476,6 +476,8 @@ static int pkcs1pad_verify_complete(struct akcipher_request *req, int err)
 	pos++;
 
 	if (digest_info) {
+		if (digest_info->size > dst_len - pos)
+			goto done;
 		if (crypto_memneq(out_buf + pos, digest_info->data,
 				  digest_info->size))
 			goto done;
-- 
2.34.1

[PATCH 3/3] crypto: rsa-pkcs1pad - use clearer variable names

[Eric Biggers]

From: Eric Biggers <ebiggers@google.com>

The new convention for akcipher_alg::verify makes it unclear which
values are the lengths of the signature and digest.  Add local variables
to make it clearer what is going on.

Also rename the digest_size variable in pkcs1pad_sign(), as it is
actually the digest *info* size, not the digest size which is different.

Signed-off-by: Eric Biggers <ebiggers@google.com>
---
 crypto/rsa-pkcs1pad.c | 31 ++++++++++++++++---------------
 1 file changed, 16 insertions(+), 15 deletions(-)

diff --git a/crypto/rsa-pkcs1pad.c b/crypto/rsa-pkcs1pad.c
index 6cd24b4b9b9e..8a3054a43735 100644
--- a/crypto/rsa-pkcs1pad.c
+++ b/crypto/rsa-pkcs1pad.c
@@ -385,15 +385,15 @@ static int pkcs1pad_sign(struct akcipher_request *req)
 	struct pkcs1pad_inst_ctx *ictx = akcipher_instance_ctx(inst);
 	const struct rsa_asn1_template *digest_info = ictx->digest_info;
 	int err;
-	unsigned int ps_end, digest_size = 0;
+	unsigned int ps_end, digest_info_size = 0;
 
 	if (!ctx->key_size)
 		return -EINVAL;
 
 	if (digest_info)
-		digest_size = digest_info->size;
+		digest_info_size = digest_info->size;
 
-	if (req->src_len + digest_size > ctx->key_size - 11)
+	if (req->src_len + digest_info_size > ctx->key_size - 11)
 		return -EOVERFLOW;
 
 	if (req->dst_len < ctx->key_size) {
@@ -406,7 +406,7 @@ static int pkcs1pad_sign(struct akcipher_request *req)
 	if (!req_ctx->in_buf)
 		return -ENOMEM;
 
-	ps_end = ctx->key_size - digest_size - req->src_len - 2;
+	ps_end = ctx->key_size - digest_info_size - req->src_len - 2;
 	req_ctx->in_buf[0] = 0x01;
 	memset(req_ctx->in_buf + 1, 0xff, ps_end - 1);
 	req_ctx->in_buf[ps_end] = 0x00;
@@ -441,6 +441,8 @@ static int pkcs1pad_verify_complete(struct akcipher_request *req, int err)
 	struct akcipher_instance *inst = akcipher_alg_instance(tfm);
 	struct pkcs1pad_inst_ctx *ictx = akcipher_instance_ctx(inst);
 	const struct rsa_asn1_template *digest_info = ictx->digest_info;
+	const unsigned int sig_size = req->src_len;
+	const unsigned int digest_size = req->dst_len;
 	unsigned int dst_len;
 	unsigned int pos;
 	u8 *out_buf;
@@ -487,20 +489,19 @@ static int pkcs1pad_verify_complete(struct akcipher_request *req, int err)
 
 	err = 0;
 
-	if (req->dst_len != dst_len - pos) {
+	if (digest_size != dst_len - pos) {
 		err = -EKEYREJECTED;
 		req->dst_len = dst_len - pos;
 		goto done;
 	}
 	/* Extract appended digest. */
 	sg_pcopy_to_buffer(req->src,
-			   sg_nents_for_len(req->src,
-					    req->src_len + req->dst_len),
+			   sg_nents_for_len(req->src, sig_size + digest_size),
 			   req_ctx->out_buf + ctx->key_size,
-			   req->dst_len, req->src_len);
+			   digest_size, sig_size);
 	/* Do the actual verification step. */
 	if (memcmp(req_ctx->out_buf + ctx->key_size, out_buf + pos,
-		   req->dst_len) != 0)
+		   digest_size) != 0)
 		err = -EKEYREJECTED;
 done:
 	kfree_sensitive(req_ctx->out_buf);
@@ -536,14 +537,15 @@ static int pkcs1pad_verify(struct akcipher_request *req)
 	struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
 	struct pkcs1pad_ctx *ctx = akcipher_tfm_ctx(tfm);
 	struct pkcs1pad_request *req_ctx = akcipher_request_ctx(req);
+	const unsigned int sig_size = req->src_len;
+	const unsigned int digest_size = req->dst_len;
 	int err;
 
-	if (WARN_ON(req->dst) ||
-	    WARN_ON(!req->dst_len) ||
-	    !ctx->key_size || req->src_len < ctx->key_size)
+	if (WARN_ON(req->dst) || WARN_ON(!digest_size) ||
+	    !ctx->key_size || sig_size < ctx->key_size)
 		return -EINVAL;
 
-	req_ctx->out_buf = kmalloc(ctx->key_size + req->dst_len, GFP_KERNEL);
+	req_ctx->out_buf = kmalloc(ctx->key_size + digest_size, GFP_KERNEL);
 	if (!req_ctx->out_buf)
 		return -ENOMEM;
 
@@ -556,8 +558,7 @@ static int pkcs1pad_verify(struct akcipher_request *req)
 
 	/* Reuse input buffer, output to a new buffer */
 	akcipher_request_set_crypt(&req_ctx->child_req, req->src,
-				   req_ctx->out_sg, req->src_len,
-				   ctx->key_size);
+				   req_ctx->out_sg, sig_size, ctx->key_size);
 
 	err = crypto_akcipher_encrypt(&req_ctx->child_req);
 	if (err != -EINPROGRESS && err != -EBUSY)
-- 
2.34.1

Re: [PATCH 1/3] crypto: rsa-pkcs1pad - correctly get hash from source scatterlist

[Vitaly Chikunov]

Eric,

On Fri, Jan 14, 2022 at 12:19:37AM -0800, Eric Biggers wrote:
> From: Eric Biggers <ebiggers@google.com>
> 
> Commit c7381b012872 ("crypto: akcipher - new verify API for public key
> algorithms") changed akcipher_alg::verify to take in both the signature
> and the actual hash and do the signature verification, rather than just
> return the hash expected by the signature as was the case before.  To do
> this, it implemented a hack where the signature and hash are
> concatenated with each other in one scatterlist.
> 
> Obviously, for this to work correctly, akcipher_alg::verify needs to
> correctly extract the two items from the scatterlist it is given.
> Unfortunately, it doesn't correctly extract the hash in the case where
> the signature is longer than the RSA key size, as it assumes that the
> signature's length is equal to the RSA key size.  This causes a prefix
> of the hash, or even the entire hash, to be taken from the *signature*.
> 
> It is unclear whether the resulting scheme has any useful security
> properties.
> 
> Fix this by correctly extracting the hash from the scatterlist.
> 
> Fixes: c7381b012872 ("crypto: akcipher - new verify API for public key algorithms")
> Cc: <stable@vger.kernel.org> # v5.2+
> Signed-off-by: Eric Biggers <ebiggers@google.com>
> ---
>  crypto/rsa-pkcs1pad.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/crypto/rsa-pkcs1pad.c b/crypto/rsa-pkcs1pad.c
> index 1b3545781425..7b223adebabf 100644
> --- a/crypto/rsa-pkcs1pad.c
> +++ b/crypto/rsa-pkcs1pad.c
> @@ -495,7 +495,7 @@ static int pkcs1pad_verify_complete(struct akcipher_request *req, int err)
>  			   sg_nents_for_len(req->src,
>  					    req->src_len + req->dst_len),
>  			   req_ctx->out_buf + ctx->key_size,
> -			   req->dst_len, ctx->key_size);
> +			   req->dst_len, req->src_len);

Reviewed-by: Vitaly Chikunov <vt@altlinux.org>

Reviewing this I noticed that while req->src_len is checked in
pkcs1pad_verify() to be not shorter than ctx->key_size it's never
checked to be not longer. Signatures longer than RSA modulus N (which is
ctx->key_size) are still invalid (RFC8017 8.2.2). (So, assumption they
are equal was in accord with the standard, but not with the current
codebase.)

I suggest to add this check too while we at it.

There was such check before, but it was removed in a49de377e051 ("crypto:
Add hash param to pkcs1pad") for an unknown reason:

  -    if (!ctx->key_size || req->src_len != ctx->key_size)
  +    if (!ctx->key_size || req->src_len < ctx->key_size)
           return -EINVAL;

Thanks,

>  	/* Do the actual verification step. */
>  	if (memcmp(req_ctx->out_buf + ctx->key_size, out_buf + pos,
>  		   req->dst_len) != 0)
> -- 
> 2.34.1

Re: [PATCH 1/3] crypto: rsa-pkcs1pad - correctly get hash from source scatterlist

[Eric Biggers]

On Sat, Jan 15, 2022 at 08:08:12AM +0300, Vitaly Chikunov wrote:
> Eric,
> 
> On Fri, Jan 14, 2022 at 12:19:37AM -0800, Eric Biggers wrote:
> > From: Eric Biggers <ebiggers@google.com>
> > 
> > Commit c7381b012872 ("crypto: akcipher - new verify API for public key
> > algorithms") changed akcipher_alg::verify to take in both the signature
> > and the actual hash and do the signature verification, rather than just
> > return the hash expected by the signature as was the case before.  To do
> > this, it implemented a hack where the signature and hash are
> > concatenated with each other in one scatterlist.
> > 
> > Obviously, for this to work correctly, akcipher_alg::verify needs to
> > correctly extract the two items from the scatterlist it is given.
> > Unfortunately, it doesn't correctly extract the hash in the case where
> > the signature is longer than the RSA key size, as it assumes that the
> > signature's length is equal to the RSA key size.  This causes a prefix
> > of the hash, or even the entire hash, to be taken from the *signature*.
> > 
> > It is unclear whether the resulting scheme has any useful security
> > properties.
> > 
> > Fix this by correctly extracting the hash from the scatterlist.
> > 
> > Fixes: c7381b012872 ("crypto: akcipher - new verify API for public key algorithms")
> > Cc: <stable@vger.kernel.org> # v5.2+
> > Signed-off-by: Eric Biggers <ebiggers@google.com>
> > ---
> >  crypto/rsa-pkcs1pad.c | 2 +-
> >  1 file changed, 1 insertion(+), 1 deletion(-)
> > 
> > diff --git a/crypto/rsa-pkcs1pad.c b/crypto/rsa-pkcs1pad.c
> > index 1b3545781425..7b223adebabf 100644
> > --- a/crypto/rsa-pkcs1pad.c
> > +++ b/crypto/rsa-pkcs1pad.c
> > @@ -495,7 +495,7 @@ static int pkcs1pad_verify_complete(struct akcipher_request *req, int err)
> >  			   sg_nents_for_len(req->src,
> >  					    req->src_len + req->dst_len),
> >  			   req_ctx->out_buf + ctx->key_size,
> > -			   req->dst_len, ctx->key_size);
> > +			   req->dst_len, req->src_len);
> 
> Reviewed-by: Vitaly Chikunov <vt@altlinux.org>
> 
> Reviewing this I noticed that while req->src_len is checked in
> pkcs1pad_verify() to be not shorter than ctx->key_size it's never
> checked to be not longer. Signatures longer than RSA modulus N (which is
> ctx->key_size) are still invalid (RFC8017 8.2.2). (So, assumption they
> are equal was in accord with the standard, but not with the current
> codebase.)
> 
> I suggest to add this check too while we at it.
> 
> There was such check before, but it was removed in a49de377e051 ("crypto:
> Add hash param to pkcs1pad") for an unknown reason:
> 
>   -    if (!ctx->key_size || req->src_len != ctx->key_size)
>   +    if (!ctx->key_size || req->src_len < ctx->key_size)
>            return -EINVAL;
> 
> Thanks,
> 

Yes, after sending this out I was looking at the PKCS#1 v1.5 encoding
specification, and I had noticed that too:

     "1.  Length checking: If the length of the signature S is not k
          octets, output 'invalid signature' and stop."

I agree that we should enforce that too, although it's curious that commit
a49de377e051 removed that check.  Hopefully that was just a mistake and not
something that someone was actually relying on.  I'll send a separate patch for
that; I think it should be separate from this patch.

- Eric