crypto: lib/mpi - Fix integer underflow in mpi_read_raw_from_sgl()
Subsystems (4)
PATCH 1/1 crypto: lib/mpi - Fix integer underflow in mpi_read_raw_from_sgl()
Yiming reports an integer underflow in mpi_read_raw_from_sgl() when subtracting "lzeros" from the unsigned "nbytes".
For this to happen, the scatterlist "sgl" needs to occupy more bytes than the "nbytes" parameter and the first "nbytes + 1" bytes of the scatterlist must be zero. Under these conditions, the while loop iterating over the scatterlist will count more zeroes than "nbytes", subtract the number of zeroes from "nbytes" and cause the underflow.
When commit 2d4d1eea540b ("lib/mpi: Add mpi sgl helpers") originally introduced the bug, it couldn't be triggered because all callers of mpi_read_raw_from_sgl() passed a scatterlist whose length was equal to "nbytes".
However since commit 63ba4d67594a ("KEYS: asymmetric: Use new crypto interface without scatterlists"), the underflow can now actually be triggered. When invoking a KEYCTL_PKEY_ENCRYPT system call with a larger "out_len" than "in_len" and filling the "in" buffer with zeroes, crypto_akcipher_sync_prep() will create an all-zero scatterlist used for both the "src" and "dst" member of struct akcipher_request and thereby fulfil the conditions to trigger the bug:
sys_keyctl()
keyctl_pkey_e_d_s()
asymmetric_key_eds_op()
software_key_eds_op()
crypto_akcipher_sync_encrypt()
crypto_akcipher_sync_prep()
crypto_akcipher_encrypt()
rsa_enc()
mpi_read_raw_from_sgl()To the user this will be visible as a DoS as the kernel spins forever, causing soft lockup splats as a side effect.
Fix it.
--- lib/crypto/mpi/mpicoder.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/crypto/mpi/mpicoder.c +1 -1
@@ -347,7 +347,7 @@ MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int nbytes) lzeros =0 ; len =0 ;while (nbytes >0 ) { -while (len && !*buff) { +while (len && !*buff && lzeros < nbytes) { lzeros++; len--; buff++;
Signature · 1 line
2.51.0
Quoted 36 lines · Lukas Wunner
Yiming reports an integer underflow in
mpi_read_raw_from_sgl()when subtracting "lzeros" from the unsigned "nbytes".For this to happen, the scatterlist "sgl" needs to occupy more bytes than the "nbytes" parameter and the first "nbytes + 1" bytes of the scatterlist must be zero. Under these conditions, the while loop iterating over the scatterlist will count more zeroes than "nbytes", subtract the number of zeroes from "nbytes" and cause the underflow.
When commit
2d4d1eea540b("lib/mpi: Add mpi sgl helpers") originally introduced the bug, it couldn't be triggered because all callers ofmpi_read_raw_from_sgl()passed a scatterlist whose length was equal to "nbytes".However since commit
63ba4d67594a("KEYS: asymmetric: Use new crypto interface without scatterlists"), the underflow can now actually be triggered. When invoking aKEYCTL_PKEY_ENCRYPTsystem call with a larger "out_len" than "in_len" and filling the "in" buffer with zeroes,crypto_akcipher_sync_prep()will create an all-zero scatterlist used for both the "src" and "dst" member of structakcipher_requestand thereby fulfil the conditions to trigger the bug:
sys_keyctl()keyctl_pkey_e_d_s() asymmetric_key_eds_op() software_key_eds_op() crypto_akcipher_sync_encrypt() crypto_akcipher_sync_prep() crypto_akcipher_encrypt() rsa_enc() mpi_read_raw_from_sgl()To the user this will be visible as a DoS as the kernel spins forever, causing soft lockup splats as a side effect.
Quoted 6 lines
Fix it.
Reported-by Yiming Qian <[email protected]> # off-listFixes 2d4d1eea540b ("lib/mpi: Add mpi sgl helpers")Signed-off-by Lukas Wunner <[email protected]>Cc [email protected] # v4.4+
Quoted 21 lines
--- lib/crypto/mpi/mpicoder.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)lib/crypto/mpi/mpicoder.c +1
-2@@ -347,7 +347,7 @@ MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int nbytes) lzeros =0 ; len =0 ;while (nbytes >0 ) { -while (len && !*buff) { +while (len && !*buff && lzeros < nbytes) { lzeros++; len--; buff++; --2.51.0
Quoted 2 lines · Lukas Wunner
Yiming reports an integer underflow in
mpi_read_raw_from_sgl()when subtracting "lzeros" from the unsigned "nbytes".
[...]
lib/crypto/mpi/mpicoder.c MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int nbytes) · line 353
Quoted 10 lines
+++
b/lib/crypto/mpi/mpicoder.clib/crypto/mpi/mpicoder.c +1
-1@@ -347,7 +347,7 @@ MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int nbytes) lzeros =0 ; len =0 ;while (nbytes >0 ) { -while (len && !*buff) { +while (len && !*buff && lzeros < nbytes) { lzeros++; len--; buff++;
As a side note, in 2018, commit 8a2a0dd35f2e ("crypto: caam - strip input zeros from RSA input buffer") copy-pasted a large portion of mpi_read_raw_from_sgl() into caam_rsa_count_leading_zeros() and duplicated the bug as well.
One year later, commit c3725f7ccc8c ("crypto: caam - fix pkcs1pad(rsa-caam, sha256) failure because of invalid input") fixed the bug in the duplicated function, but unfortunately not in the original mpi_read_raw_from_sgl(). The fix was identical to the one I'm proposing above.
Thanks,
Lukas
Quoted 35 lines · Lukas Wunner
Yiming reports an integer underflow in
mpi_read_raw_from_sgl()when subtracting "lzeros" from the unsigned "nbytes".For this to happen, the scatterlist "sgl" needs to occupy more bytes than the "nbytes" parameter and the first "nbytes + 1" bytes of the scatterlist must be zero. Under these conditions, the while loop iterating over the scatterlist will count more zeroes than "nbytes", subtract the number of zeroes from "nbytes" and cause the underflow.
When commit
2d4d1eea540b("lib/mpi: Add mpi sgl helpers") originally introduced the bug, it couldn't be triggered because all callers ofmpi_read_raw_from_sgl()passed a scatterlist whose length was equal to "nbytes".However since commit
63ba4d67594a("KEYS: asymmetric: Use new crypto interface without scatterlists"), the underflow can now actually be triggered. When invoking aKEYCTL_PKEY_ENCRYPTsystem call with a larger "out_len" than "in_len" and filling the "in" buffer with zeroes,crypto_akcipher_sync_prep()will create an all-zero scatterlist used for both the "src" and "dst" member of structakcipher_requestand thereby fulfil the conditions to trigger the bug:
sys_keyctl()keyctl_pkey_e_d_s() asymmetric_key_eds_op() software_key_eds_op() crypto_akcipher_sync_encrypt() crypto_akcipher_sync_prep() crypto_akcipher_encrypt() rsa_enc() mpi_read_raw_from_sgl()To the user this will be visible as a DoS as the kernel spins forever, causing soft lockup splats as a side effect.
Quoted 7 lines
Fix it.
Reported-by Yiming Qian <[email protected]> # off-listFixes 2d4d1eea540b ("lib/mpi: Add mpi sgl helpers")Signed-off-by Lukas Wunner <[email protected]>Cc [email protected] # v4.4+---
Applied to https://git.kernel.org/pub/scm/linux/kernel/git/ebiggers/linux.git/log/?h=libcrypto-fixes
This code (which has no tests...) is unnecessarily hard to understand, though. I haven't been able to fully understand the logic yet, but it looks like it still has bugs, including still reading past the given nbytes. It should be possible to replace it with something simpler and less error-prone.
- Eric
Quoted 3 lines · Eric Biggers
Quoted 2 lines · Lukas Wunner
Yiming reports an integer underflow in
mpi_read_raw_from_sgl()when subtracting "lzeros" from the unsigned "nbytes".
[...]
Quoted 6 lines
This code (which has no tests...) is unnecessarily hard to understand, though. I haven't been able to fully understand the logic yet, but it looks like it still has bugs, including still reading past the given nbytes. It should be possible to replace it with something simpler and less error-prone.
mpi_read_raw_from_sgl() skips over leading zero bytes in the scatterlist and then over leading zero bits in the first non-zero byte, before it starts copying data to the newly-allocated MPI.
One possible simplification is to use memchr_inv() to search for the first non-zero byte, instead of open coding it. See the patch below. If you think it's a step in the right direction, I can submit the patch in the next cycle.
-- >8 --
drivers/crypto/caam/caampkc.c +4 -6
@@ -17,6 +17,7 @@#include "sg_sw_sec4.h" #include "caampkc.h" #include <crypto/internal/engine.h> +#include <linux/count_zeros.h> #include <linux/dma-mapping.h> #include <linux/err.h> #include <linux/kernel.h>
@@ -219,12 +220,9 @@ static int caam_rsa_count_leading_zeros(struct scatterlist *sgl, lzeros =0 ; len =0 ;while (nbytes >0 ) { -/* do not strip more than given bytes */ -while (len && !*buff && lzeros < nbytes) { - lzeros++; - len--; - buff++; - } + lzeros =count_leading_zerobytes (buff,min (len, nbytes)); + len -= lzeros; + buff += lzeros;if (len && *buff)break ;
include/linux/count_zeros.h +11 -0
@@ -8,6 +8,7 @@#ifndef _LINUX_BITOPS_COUNT_ZEROS_H_#define _LINUX_BITOPS_COUNT_ZEROS_H_ +#include <linux/string.h> #include <asm/bitops.h> /**
@@ -50,4 +51,14 @@ static inline int count_trailing_zeros(unsigned long x) return (x != 0) ? __ffs(x) : COUNT_TRAILING_ZEROS_0; } +static inline size_t count_leading_zerobytes (const void *start,size_t len) +{ +void *first =memchr_inv (start,0 , len); + +if (!first) +return len; + +return first - start; +} +#endif /* _LINUX_BITOPS_COUNT_ZEROS_H_ */
lib/crypto/mpi/mpicoder.c +3 -5
@@ -347,11 +347,9 @@ MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int nbytes) lzeros =0 ; len =0 ;while (nbytes >0 ) { -while (len && !*buff && lzeros < nbytes) { - lzeros++; - len--; - buff++; - } + lzeros =count_leading_zerobytes (buff,min (len, nbytes)); + len -= lzeros; + buff += lzeros;if (len && *buff)break ;
Eric Biggers
maintainerQuoted 6 lines · Lukas Wunner
lib/crypto/mpi/mpicoder.c +0
-0@@ -347,11 +347,9 @@ MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int nbytes) lzeros =0 ;
lib/crypto/mpi/mpicoder.c MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int nbytes) · line 352
Quoted 10 lines
lib/crypto/mpi/mpicoder.c +3
-5len =0 ;while (nbytes >0 ) { -while (len && !*buff && lzeros < nbytes) { - lzeros++; - len--; - buff++; - } + lzeros =count_leading_zerobytes (buff,min (len, nbytes)); + len -= lzeros; + buff += lzeros;
Well, now you're passing an uninitialized pointer as a function parameter. (The loop body still operates on data from the previous iteration.) So no, that isn't a step forwards. This should be rewritten as a conventional loop and be switched to the scatterwalk API.
But this is really just a symptom of the larger issue with the pointless virtaddr => scatterlist => virtaddr conversion that is happening. And lib/crypto/mpi/ is broken in other ways too, e.g. it's not constant-time but is being used for RSA signing. And it has no tests.
This is on my TODO list to fix up at some point, but it's a big task. Secure bignum implementations aren't easy; userspace projects have spent a long time to get them right. So far I've instead been focusing on symmetric crypto, which is what actually matters in the kernel. If someone is using the broken kernel RSA signing UAPIs (which should never have been added), they hopefully know what they're getting...
- Eric
Quoted 61 lines · Lukas Wunner
Yiming reports an integer underflow in
mpi_read_raw_from_sgl()when subtracting "lzeros" from the unsigned "nbytes".For this to happen, the scatterlist "sgl" needs to occupy more bytes than the "nbytes" parameter and the first "nbytes + 1" bytes of the scatterlist must be zero. Under these conditions, the while loop iterating over the scatterlist will count more zeroes than "nbytes", subtract the number of zeroes from "nbytes" and cause the underflow.
When commit
2d4d1eea540b("lib/mpi: Add mpi sgl helpers") originally introduced the bug, it couldn't be triggered because all callers ofmpi_read_raw_from_sgl()passed a scatterlist whose length was equal to "nbytes".However since commit
63ba4d67594a("KEYS: asymmetric: Use new crypto interface without scatterlists"), the underflow can now actually be triggered. When invoking aKEYCTL_PKEY_ENCRYPTsystem call with a larger "out_len" than "in_len" and filling the "in" buffer with zeroes,crypto_akcipher_sync_prep()will create an all-zero scatterlist used for both the "src" and "dst" member of structakcipher_requestand thereby fulfil the conditions to trigger the bug:
sys_keyctl()keyctl_pkey_e_d_s() asymmetric_key_eds_op() software_key_eds_op() crypto_akcipher_sync_encrypt() crypto_akcipher_sync_prep() crypto_akcipher_encrypt() rsa_enc() mpi_read_raw_from_sgl()To the user this will be visible as a DoS as the kernel spins forever, causing soft lockup splats as a side effect.
Fix it.
Reported-by Yiming Qian <[email protected]> # off-listFixes 2d4d1eea540b ("lib/mpi: Add mpi sgl helpers")Signed-off-by Lukas Wunner <[email protected]>Cc [email protected] # v4.4+--- lib/crypto/mpi/mpicoder.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)lib/crypto/mpi/mpicoder.c +1
-1@@ -347,7 +347,7 @@ MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int nbytes) lzeros =0 ; len =0 ;while (nbytes >0 ) { -while (len && !*buff) { +while (len && !*buff && lzeros < nbytes) { lzeros++; len--; buff++;Signature · 1 line
2.51.0
BR, Jarkko