[PATCH] Add missing bound checks for software 842 decompressor

[PATCH] Add missing bound checks for software 842 decompressor

[Joan Bruguera]

The software 842 decompressor receives, through the initial value of the
'olen' parameter, the capacity of the buffer pointed to by 'out'. If this
capacity is insufficient to decode the compressed bitstream, -ENOSPC
should be returned.

However, the bounds checks are missing for index references (for those
ops. where decomp_ops includes a I2, I4 or I8 subop.), and also for
OP_SHORT_DATA. Due to this, sw842_decompress can write past the capacity
of the 'out' buffer.

The case for index references can be triggered by compressing data that
follows a 16-byte periodic pattern (excluding special cases which are
better encoded by OP_ZEROS) and passing a 'olen' somewhat smaller than the
original length.
The case for OP_SHORT_DATA can be triggered by compressing an amount of
data that is not a multiple of 8, and then a slightly smaller 'olen' that
can't fit those last <8 bytes.

Following is a small test module to demonstrate the issue.

-

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/sw842.h>

static unsigned char workspace[1000000] = { 0 }; // Hacky

static void test_bound(const char *name, unsigned ibound, unsigned dbound)
{
	uint8_t in[ibound], out[ibound * 4], decomp[ibound /* Overallocated */];
	unsigned clen = ibound * 4, dlen = dbound, i;
	int ret;

	for (i = 0; i < ibound; i ++)
		in[i] = i % 16; // 0, 1, 2, ..., 14, 15, 0, 1, 2, ...
	for (i = dbound; i < ibound; i++)
		decomp[i] = 0xFF; // Place guard bytes

	ret = sw842_compress(in, ibound, out, &clen, workspace);
	BUG_ON(ret != 0);

	ret = sw842_decompress(out, clen, decomp, &dlen);
	if (ret != -ENOSPC) {
		printk(KERN_ERR "%s: Expected ENOSPC to be returned\n", name);
	}
	for (i = dbound; i < ibound; i++) {
		if (decomp[i] != 0xFF) {
			printk(KERN_ERR "%s: Guard overwritten\n", name);
			break;
		}
	}
}

int init_module(void)
{
	test_bound("Index reference test", 256, 64);
	test_bound("Short data test", 12, 8);
	return -ECANCELED; // Do not leave this test module hanging around
}

void cleanup_module(void)
{
}

MODULE_LICENSE("GPL");
MODULE_SOFTDEP("pre: 842");

Signed-off-by: Joan Bruguera <joanbrugueram@gmail.com>
---
 lib/842/842_decompress.c | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/lib/842/842_decompress.c b/lib/842/842_decompress.c
index 582085ef8b4..c29fbfc9d08 100644
--- a/lib/842/842_decompress.c
+++ b/lib/842/842_decompress.c
@@ -202,6 +202,9 @@ static int __do_index(struct sw842_param *p, u8 size, u8 bits, u64 fsize)
 			 (unsigned long)total,
 			 (unsigned long)beN_to_cpu(&p->ostart[offset], size));
 
+	if (size > p->olen)
+		return -ENOSPC;
+
 	memcpy(p->out, &p->ostart[offset], size);
 	p->out += size;
 	p->olen -= size;
@@ -345,6 +348,9 @@ int sw842_decompress(const u8 *in, unsigned int ilen,
 			if (!bytes || bytes > SHORT_DATA_BITS_MAX)
 				return -EINVAL;
 
+			if (bytes > p.olen)
+				return -ENOSPC;
+
 			while (bytes-- > 0) {
 				ret = next_bits(&p, &tmp, 8);
 				if (ret)
-- 
2.27.0

Re: [PATCH] Add missing bound checks for software 842 decompressor

[Joan Bruguera]

Any feedback?

- Joan

On 05.06.20 17:44, Joan Bruguera wrote:
> The software 842 decompressor receives, through the initial value of the
> 'olen' parameter, the capacity of the buffer pointed to by 'out'. If this
> capacity is insufficient to decode the compressed bitstream, -ENOSPC
> should be returned.
> 
> However, the bounds checks are missing for index references (for those
> ops. where decomp_ops includes a I2, I4 or I8 subop.), and also for
> OP_SHORT_DATA. Due to this, sw842_decompress can write past the capacity
> of the 'out' buffer.
> 
> The case for index references can be triggered by compressing data that
> follows a 16-byte periodic pattern (excluding special cases which are
> better encoded by OP_ZEROS) and passing a 'olen' somewhat smaller than the
> original length.
> The case for OP_SHORT_DATA can be triggered by compressing an amount of
> data that is not a multiple of 8, and then a slightly smaller 'olen' that
> can't fit those last <8 bytes.
> 
> Following is a small test module to demonstrate the issue.
> 
> -
> 
> #include <linux/module.h>
> #include <linux/kernel.h>
> #include <linux/sw842.h>
> 
> static unsigned char workspace[1000000] = { 0 }; // Hacky
> 
> static void test_bound(const char *name, unsigned ibound, unsigned dbound)
> {
> 	uint8_t in[ibound], out[ibound * 4], decomp[ibound /* Overallocated */];
> 	unsigned clen = ibound * 4, dlen = dbound, i;
> 	int ret;
> 
> 	for (i = 0; i < ibound; i ++)
> 		in[i] = i % 16; // 0, 1, 2, ..., 14, 15, 0, 1, 2, ...
> 	for (i = dbound; i < ibound; i++)
> 		decomp[i] = 0xFF; // Place guard bytes
> 
> 	ret = sw842_compress(in, ibound, out, &clen, workspace);
> 	BUG_ON(ret != 0);
> 
> 	ret = sw842_decompress(out, clen, decomp, &dlen);
> 	if (ret != -ENOSPC) {
> 		printk(KERN_ERR "%s: Expected ENOSPC to be returned\n", name);
> 	}
> 	for (i = dbound; i < ibound; i++) {
> 		if (decomp[i] != 0xFF) {
> 			printk(KERN_ERR "%s: Guard overwritten\n", name);
> 			break;
> 		}
> 	}
> }
> 
> int init_module(void)
> {
> 	test_bound("Index reference test", 256, 64);
> 	test_bound("Short data test", 12, 8);
> 	return -ECANCELED; // Do not leave this test module hanging around
> }
> 
> void cleanup_module(void)
> {
> }
> 
> MODULE_LICENSE("GPL");
> MODULE_SOFTDEP("pre: 842");
> 
> Signed-off-by: Joan Bruguera <joanbrugueram@gmail.com>
> ---
>   lib/842/842_decompress.c | 6 ++++++
>   1 file changed, 6 insertions(+)
> 
> diff --git a/lib/842/842_decompress.c b/lib/842/842_decompress.c
> index 582085ef8b4..c29fbfc9d08 100644
> --- a/lib/842/842_decompress.c
> +++ b/lib/842/842_decompress.c
> @@ -202,6 +202,9 @@ static int __do_index(struct sw842_param *p, u8 size, u8 bits, u64 fsize)
>   			 (unsigned long)total,
>   			 (unsigned long)beN_to_cpu(&p->ostart[offset], size));
>   
> +	if (size > p->olen)
> +		return -ENOSPC;
> +
>   	memcpy(p->out, &p->ostart[offset], size);
>   	p->out += size;
>   	p->olen -= size;
> @@ -345,6 +348,9 @@ int sw842_decompress(const u8 *in, unsigned int ilen,
>   			if (!bytes || bytes > SHORT_DATA_BITS_MAX)
>   				return -EINVAL;
>   
> +			if (bytes > p.olen)
> +				return -ENOSPC;
> +
>   			while (bytes-- > 0) {
>   				ret = next_bits(&p, &tmp, 8);
>   				if (ret)
> 

Re: [PATCH] Add missing bound checks for software 842 decompressor

[Kees Cook]

On Sun, Aug 16, 2020 at 02:33:41AM +0200, Joan Bruguera wrote:
> Any feedback?

Hi!

I just happened to see this email. I think this should likely be
directed to the crypto (which also handled compress/decompress APIs)
list and the original author...

Additional notes below...

> - Joan
> 
> On 05.06.20 17:44, Joan Bruguera wrote:
> > The software 842 decompressor receives, through the initial value of the
> > 'olen' parameter, the capacity of the buffer pointed to by 'out'. If this
> > capacity is insufficient to decode the compressed bitstream, -ENOSPC
> > should be returned.
> > 
> > However, the bounds checks are missing for index references (for those
> > ops. where decomp_ops includes a I2, I4 or I8 subop.), and also for
> > OP_SHORT_DATA. Due to this, sw842_decompress can write past the capacity
> > of the 'out' buffer.

Eek. :(

> > 
> > The case for index references can be triggered by compressing data that
> > follows a 16-byte periodic pattern (excluding special cases which are
> > better encoded by OP_ZEROS) and passing a 'olen' somewhat smaller than the
> > original length.
> > The case for OP_SHORT_DATA can be triggered by compressing an amount of
> > data that is not a multiple of 8, and then a slightly smaller 'olen' that
> > can't fit those last <8 bytes.
> > 
> > Following is a small test module to demonstrate the issue.
> > 
> > -
> > 
> > #include <linux/module.h>
> > #include <linux/kernel.h>
> > #include <linux/sw842.h>
> > 
> > static unsigned char workspace[1000000] = { 0 }; // Hacky
> > 
> > static void test_bound(const char *name, unsigned ibound, unsigned dbound)
> > {
> > 	uint8_t in[ibound], out[ibound * 4], decomp[ibound /* Overallocated */];
> > 	unsigned clen = ibound * 4, dlen = dbound, i;
> > 	int ret;
> > 
> > 	for (i = 0; i < ibound; i ++)
> > 		in[i] = i % 16; // 0, 1, 2, ..., 14, 15, 0, 1, 2, ...
> > 	for (i = dbound; i < ibound; i++)
> > 		decomp[i] = 0xFF; // Place guard bytes
> > 
> > 	ret = sw842_compress(in, ibound, out, &clen, workspace);
> > 	BUG_ON(ret != 0);
> > 
> > 	ret = sw842_decompress(out, clen, decomp, &dlen);
> > 	if (ret != -ENOSPC) {
> > 		printk(KERN_ERR "%s: Expected ENOSPC to be returned\n", name);
> > 	}
> > 	for (i = dbound; i < ibound; i++) {
> > 		if (decomp[i] != 0xFF) {
> > 			printk(KERN_ERR "%s: Guard overwritten\n", name);
> > 			break;
> > 		}
> > 	}
> > }
> > 
> > int init_module(void)
> > {
> > 	test_bound("Index reference test", 256, 64);
> > 	test_bound("Short data test", 12, 8);
> > 	return -ECANCELED; // Do not leave this test module hanging around
> > }
> > 
> > void cleanup_module(void)
> > {
> > }
> > 
> > MODULE_LICENSE("GPL");
> > MODULE_SOFTDEP("pre: 842");

Can this test be added to the kernel source directly? It'd be nice to
add such a regression test.

> > 
> > Signed-off-by: Joan Bruguera <joanbrugueram@gmail.com>
> > ---
> >   lib/842/842_decompress.c | 6 ++++++
> >   1 file changed, 6 insertions(+)
> > 
> > diff --git a/lib/842/842_decompress.c b/lib/842/842_decompress.c
> > index 582085ef8b4..c29fbfc9d08 100644
> > --- a/lib/842/842_decompress.c
> > +++ b/lib/842/842_decompress.c
> > @@ -202,6 +202,9 @@ static int __do_index(struct sw842_param *p, u8 size, u8 bits, u64 fsize)
> >   			 (unsigned long)total,
> >   			 (unsigned long)beN_to_cpu(&p->ostart[offset], size));
> > +	if (size > p->olen)
> > +		return -ENOSPC;
> > +
> >   	memcpy(p->out, &p->ostart[offset], size);
> >   	p->out += size;
> >   	p->olen -= size;
> > @@ -345,6 +348,9 @@ int sw842_decompress(const u8 *in, unsigned int ilen,
> >   			if (!bytes || bytes > SHORT_DATA_BITS_MAX)
> >   				return -EINVAL;
> > +			if (bytes > p.olen)
> > +				return -ENOSPC;
> > +
> >   			while (bytes-- > 0) {
> >   				ret = next_bits(&p, &tmp, 8);
> >   				if (ret)
> > 

Reviewed-by: Kees Cook <keescook@chromium.org>


-- 
Kees Cook

Re: [PATCH] Add missing bound checks for software 842 decompressor

[Joan Bruguera]

On 19.08.20 22:19, Kees Cook wrote:
> On Sun, Aug 16, 2020 at 02:33:41AM +0200, Joan Bruguera wrote:
>> Any feedback?
> 
> Hi!
> 
> I just happened to see this email. I think this should likely be
> directed to the crypto (which also handled compress/decompress APIs)
> list and the original author...
> 
> Additional notes below...
> 

Thanks for the review, much appreciated.

>> - Joan
>>
>> On 05.06.20 17:44, Joan Bruguera wrote:
>>> The software 842 decompressor receives, through the initial value of the
>>> 'olen' parameter, the capacity of the buffer pointed to by 'out'. If this
>>> capacity is insufficient to decode the compressed bitstream, -ENOSPC
>>> should be returned.
>>>
>>> However, the bounds checks are missing for index references (for those
>>> ops. where decomp_ops includes a I2, I4 or I8 subop.), and also for
>>> OP_SHORT_DATA. Due to this, sw842_decompress can write past the capacity
>>> of the 'out' buffer.
> 
> Eek. :(

It isn't much exploitable though, since AFAICT, compressed data can only 
come from zram or pstore, not from userspace.

> 
>>>
>>> The case for index references can be triggered by compressing data that
>>> follows a 16-byte periodic pattern (excluding special cases which are
>>> better encoded by OP_ZEROS) and passing a 'olen' somewhat smaller than the
>>> original length.
>>> The case for OP_SHORT_DATA can be triggered by compressing an amount of
>>> data that is not a multiple of 8, and then a slightly smaller 'olen' that
>>> can't fit those last <8 bytes.
>>>
>>> Following is a small test module to demonstrate the issue.
>>>
>>> -
>>>
>>> #include <linux/module.h>
>>> #include <linux/kernel.h>
>>> #include <linux/sw842.h>
>>>
>>> static unsigned char workspace[1000000] = { 0 }; // Hacky
>>>
>>> static void test_bound(const char *name, unsigned ibound, unsigned dbound)
>>> {
>>> 	uint8_t in[ibound], out[ibound * 4], decomp[ibound /* Overallocated */];
>>> 	unsigned clen = ibound * 4, dlen = dbound, i;
>>> 	int ret;
>>>
>>> 	for (i = 0; i < ibound; i ++)
>>> 		in[i] = i % 16; // 0, 1, 2, ..., 14, 15, 0, 1, 2, ...
>>> 	for (i = dbound; i < ibound; i++)
>>> 		decomp[i] = 0xFF; // Place guard bytes
>>>
>>> 	ret = sw842_compress(in, ibound, out, &clen, workspace);
>>> 	BUG_ON(ret != 0);
>>>
>>> 	ret = sw842_decompress(out, clen, decomp, &dlen);
>>> 	if (ret != -ENOSPC) {
>>> 		printk(KERN_ERR "%s: Expected ENOSPC to be returned\n", name);
>>> 	}
>>> 	for (i = dbound; i < ibound; i++) {
>>> 		if (decomp[i] != 0xFF) {
>>> 			printk(KERN_ERR "%s: Guard overwritten\n", name);
>>> 			break;
>>> 		}
>>> 	}
>>> }
>>>
>>> int init_module(void)
>>> {
>>> 	test_bound("Index reference test", 256, 64);
>>> 	test_bound("Short data test", 12, 8);
>>> 	return -ECANCELED; // Do not leave this test module hanging around
>>> }
>>>
>>> void cleanup_module(void)
>>> {
>>> }
>>>
>>> MODULE_LICENSE("GPL");
>>> MODULE_SOFTDEP("pre: 842");
> 
> Can this test be added to the kernel source directly? It'd be nice to
> add such a regression test.
> 

I took a look and maybe it could go into the crypto self tests (in 
crypto/testmgr.c)... but I'm not really sure if it fits there, since 
this would be a regression test rather than the smoke tests that seem to 
make most of that file, and this bug requires adding a custom method 
testing whether the decompressor respects the output buffer size rather 
than a simple test with just a simple input / output data test vector.

Were thinking of that, something else (e.g. Linux Test Project), or just 
suggesting?

>>>
>>> Signed-off-by: Joan Bruguera <joanbrugueram@gmail.com>
>>> ---
>>>    lib/842/842_decompress.c | 6 ++++++
>>>    1 file changed, 6 insertions(+)
>>>
>>> diff --git a/lib/842/842_decompress.c b/lib/842/842_decompress.c
>>> index 582085ef8b4..c29fbfc9d08 100644
>>> --- a/lib/842/842_decompress.c
>>> +++ b/lib/842/842_decompress.c
>>> @@ -202,6 +202,9 @@ static int __do_index(struct sw842_param *p, u8 size, u8 bits, u64 fsize)
>>>    			 (unsigned long)total,
>>>    			 (unsigned long)beN_to_cpu(&p->ostart[offset], size));
>>> +	if (size > p->olen)
>>> +		return -ENOSPC;
>>> +
>>>    	memcpy(p->out, &p->ostart[offset], size);
>>>    	p->out += size;
>>>    	p->olen -= size;
>>> @@ -345,6 +348,9 @@ int sw842_decompress(const u8 *in, unsigned int ilen,
>>>    			if (!bytes || bytes > SHORT_DATA_BITS_MAX)
>>>    				return -EINVAL;
>>> +			if (bytes > p.olen)
>>> +				return -ENOSPC;
>>> +
>>>    			while (bytes-- > 0) {
>>>    				ret = next_bits(&p, &tmp, 8);
>>>    				if (ret)
>>>
> 
> Reviewed-by: Kees Cook <keescook@chromium.org>
> 
>