From: "Markus F.X.J. Oberhumer" <markus@oberhumer.com>
To: Herbert Xu <herbert@gondor.apana.org.au>,
Linux Crypto Mailing List <linux-crypto@vger.kernel.org>
Cc: Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
Nitin Gupta <nitingupta910@gmail.com>,
Andrew Morton <akpm@linux-foundation.org>,
Linus Torvalds <torvalds@linux-foundation.org>,
Sergey Senozhatsky <senozhatsky@chromium.org>,
Dave Rodgman <dave.rodgman@arm.com>
Subject: Re: [PATCH] lib/lzo: Avoid output overruns when compressing
Date: Mon, 24 Feb 2025 17:20:56 +0100 [thread overview]
Message-ID: <67BC9C68.5090300@oberhumer.com> (raw)
In-Reply-To: <Z7rGXJSX57gEfXPw@gondor.apana.org.au>
LZO declares "*out_len" as output parameter because
#define lzo1x_worst_compress(x) ((x) + ((x) / 16) + 64 + 3 + 2)
~Markus
On 2025-02-23 07:55, Herbert Xu wrote:
> The compression code in LZO never checked for output overruns.
> Fix this by checking for end of buffer before each write.
>
> Fixes: 64c70b1cf43d ("Add LZO1X algorithm to the kernel")
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
>
> diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
> index 47d6d43ea957..5d2f2f851694 100644
> --- a/lib/lzo/lzo1x_compress.c
> +++ b/lib/lzo/lzo1x_compress.c
> @@ -18,10 +18,10 @@
> #include <linux/lzo.h>
> #include "lzodefs.h"
>
> -static noinline size_t
> +static noinline int
> lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
> - unsigned char *out, size_t *out_len,
> - size_t ti, void *wrkmem, signed char *state_offset,
> + unsigned char **out, unsigned char *op_end,
> + size_t *tp, void *wrkmem, signed char *state_offset,
> const unsigned char bitstream_version)
> {
> const unsigned char *ip;
> @@ -30,8 +30,9 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
> const unsigned char * const ip_end = in + in_len - 20;
> const unsigned char *ii;
> lzo_dict_t * const dict = (lzo_dict_t *) wrkmem;
> + size_t ti = *tp;
>
> - op = out;
> + op = *out;
> ip = in;
> ii = ip;
> ip += ti < 4 ? 4 - ti : 0;
> @@ -116,25 +117,41 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
> if (t != 0) {
> if (t <= 3) {
> op[*state_offset] |= t;
> + if (!HAVE_OP(4))
> + return LZO_E_OUTPUT_OVERRUN;
> COPY4(op, ii);
> op += t;
> } else if (t <= 16) {
> + if (!HAVE_OP(1))
> + return LZO_E_OUTPUT_OVERRUN;
> *op++ = (t - 3);
> + if (!HAVE_OP(16))
> + return LZO_E_OUTPUT_OVERRUN;
> COPY8(op, ii);
> COPY8(op + 8, ii + 8);
> op += t;
> } else {
> if (t <= 18) {
> + if (!HAVE_OP(1))
> + return LZO_E_OUTPUT_OVERRUN;
> *op++ = (t - 3);
> } else {
> size_t tt = t - 18;
> + if (!HAVE_OP(1))
> + return LZO_E_OUTPUT_OVERRUN;
> *op++ = 0;
> while (unlikely(tt > 255)) {
> tt -= 255;
> + if (!HAVE_OP(1))
> + return LZO_E_OUTPUT_OVERRUN;
> *op++ = 0;
> }
> + if (!HAVE_OP(1))
> + return LZO_E_OUTPUT_OVERRUN;
> *op++ = tt;
> }
> + if (!HAVE_OP(t))
> + return LZO_E_OUTPUT_OVERRUN;
> do {
> COPY8(op, ii);
> COPY8(op + 8, ii + 8);
> @@ -151,6 +168,8 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
> if (unlikely(run_length)) {
> ip += run_length;
> run_length -= MIN_ZERO_RUN_LENGTH;
> + if (!HAVE_OP(4))
> + return LZO_E_OUTPUT_OVERRUN;
> put_unaligned_le32((run_length << 21) | 0xfffc18
> | (run_length & 0x7), op);
> op += 4;
> @@ -243,10 +262,14 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
> ip += m_len;
> if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
> m_off -= 1;
> + if (!HAVE_OP(2))
> + return LZO_E_OUTPUT_OVERRUN;
> *op++ = (((m_len - 1) << 5) | ((m_off & 7) << 2));
> *op++ = (m_off >> 3);
> } else if (m_off <= M3_MAX_OFFSET) {
> m_off -= 1;
> + if (!HAVE_OP(1))
> + return LZO_E_OUTPUT_OVERRUN;
> if (m_len <= M3_MAX_LEN)
> *op++ = (M3_MARKER | (m_len - 2));
> else {
> @@ -254,14 +277,22 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
> *op++ = M3_MARKER | 0;
> while (unlikely(m_len > 255)) {
> m_len -= 255;
> + if (!HAVE_OP(1))
> + return LZO_E_OUTPUT_OVERRUN;
> *op++ = 0;
> }
> + if (!HAVE_OP(1))
> + return LZO_E_OUTPUT_OVERRUN;
> *op++ = (m_len);
> }
> + if (!HAVE_OP(2))
> + return LZO_E_OUTPUT_OVERRUN;
> *op++ = (m_off << 2);
> *op++ = (m_off >> 6);
> } else {
> m_off -= 0x4000;
> + if (!HAVE_OP(1))
> + return LZO_E_OUTPUT_OVERRUN;
> if (m_len <= M4_MAX_LEN)
> *op++ = (M4_MARKER | ((m_off >> 11) & 8)
> | (m_len - 2));
> @@ -282,11 +313,17 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
> m_len -= M4_MAX_LEN;
> *op++ = (M4_MARKER | ((m_off >> 11) & 8));
> while (unlikely(m_len > 255)) {
> + if (!HAVE_OP(1))
> + return LZO_E_OUTPUT_OVERRUN;
> m_len -= 255;
> *op++ = 0;
> }
> + if (!HAVE_OP(1))
> + return LZO_E_OUTPUT_OVERRUN;
> *op++ = (m_len);
> }
> + if (!HAVE_OP(2))
> + return LZO_E_OUTPUT_OVERRUN;
> *op++ = (m_off << 2);
> *op++ = (m_off >> 6);
> }
> @@ -295,14 +332,16 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
> ii = ip;
> goto next;
> }
> - *out_len = op - out;
> - return in_end - (ii - ti);
> + *out = op;
> + *tp = in_end - (ii - ti);
> + return LZO_E_OK;
> }
>
> static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
> unsigned char *out, size_t *out_len,
> void *wrkmem, const unsigned char bitstream_version)
> {
> + unsigned char * const op_end = out + *out_len;
> const unsigned char *ip = in;
> unsigned char *op = out;
> unsigned char *data_start;
> @@ -326,14 +365,17 @@ static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
> while (l > 20) {
> size_t ll = min_t(size_t, l, m4_max_offset + 1);
> uintptr_t ll_end = (uintptr_t) ip + ll;
> + int err;
> +
> if ((ll_end + ((t + ll) >> 5)) <= ll_end)
> break;
> BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS);
> memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t));
> - t = lzo1x_1_do_compress(ip, ll, op, out_len, t, wrkmem,
> - &state_offset, bitstream_version);
> + err = lzo1x_1_do_compress(ip, ll, &op, op_end, &t, wrkmem,
> + &state_offset, bitstream_version);
> + if (err != LZO_E_OK)
> + return err;
> ip += ll;
> - op += *out_len;
> l -= ll;
> }
> t += l;
> @@ -342,20 +384,32 @@ static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
> const unsigned char *ii = in + in_len - t;
>
> if (op == data_start && t <= 238) {
> + if (!HAVE_OP(1))
> + return LZO_E_OUTPUT_OVERRUN;
> *op++ = (17 + t);
> } else if (t <= 3) {
> op[state_offset] |= t;
> } else if (t <= 18) {
> + if (!HAVE_OP(1))
> + return LZO_E_OUTPUT_OVERRUN;
> *op++ = (t - 3);
> } else {
> size_t tt = t - 18;
> + if (!HAVE_OP(1))
> + return LZO_E_OUTPUT_OVERRUN;
> *op++ = 0;
> while (tt > 255) {
> tt -= 255;
> + if (!HAVE_OP(1))
> + return LZO_E_OUTPUT_OVERRUN;
> *op++ = 0;
> }
> + if (!HAVE_OP(1))
> + return LZO_E_OUTPUT_OVERRUN;
> *op++ = tt;
> }
> + if (!HAVE_OP(t))
> + return LZO_E_OUTPUT_OVERRUN;
> if (t >= 16) do {
> COPY8(op, ii);
> COPY8(op + 8, ii + 8);
> @@ -368,6 +422,8 @@ static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
> } while (--t > 0);
> }
>
> + if (!HAVE_OP(3))
> + return LZO_E_OUTPUT_OVERRUN;
> *op++ = M4_MARKER | 1;
> *op++ = 0;
> *op++ = 0;
> diff --git a/lib/lzo/lzo1x_decompress_safe.c b/lib/lzo/lzo1x_decompress_safe.c
> index c94f4928e188..4d5a1b58a4a0 100644
> --- a/lib/lzo/lzo1x_decompress_safe.c
> +++ b/lib/lzo/lzo1x_decompress_safe.c
> @@ -21,7 +21,6 @@
> #include "lzodefs.h"
>
> #define HAVE_IP(x) ((size_t)(ip_end - ip) >= (size_t)(x))
> -#define HAVE_OP(x) ((size_t)(op_end - op) >= (size_t)(x))
> #define NEED_IP(x) if (!HAVE_IP(x)) goto input_overrun
> #define NEED_OP(x) if (!HAVE_OP(x)) goto output_overrun
> #define TEST_LB(m_pos) if ((m_pos) < out) goto lookbehind_overrun
> diff --git a/lib/lzo/lzodefs.h b/lib/lzo/lzodefs.h
> index b60851fcf6ce..8b1a46993acf 100644
> --- a/lib/lzo/lzodefs.h
> +++ b/lib/lzo/lzodefs.h
> @@ -19,6 +19,7 @@
> */
> #define LZO_VERSION 1
>
> +#define HAVE_OP(x) ((size_t)(op_end - op) >= (size_t)(x))
> #define COPY4(dst, src) \
> put_unaligned(get_unaligned((const u32 *)(src)), (u32 *)(dst))
> #if defined(CONFIG_X86_64) || defined(CONFIG_ARM64)
>
--
Markus Oberhumer, <markus@oberhumer.com>, http://www.oberhumer.com/
next prev parent reply other threads:[~2025-02-24 16:26 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-02-23 6:55 [PATCH] lib/lzo: Avoid output overruns when compressing Herbert Xu
2025-02-23 8:40 ` Sergey Senozhatsky
2025-02-27 1:47 ` Herbert Xu
2025-02-24 16:20 ` Markus F.X.J. Oberhumer [this message]
2025-02-26 13:00 ` David Sterba
2025-02-27 1:46 ` Herbert Xu
2025-02-27 2:08 ` [v2 PATCH] crypto: lzo - Fix compression buffer overrun Herbert Xu
2025-02-27 9:04 ` [v3 " Herbert Xu
2025-02-28 13:21 ` David Sterba
2025-02-27 3:16 ` [PATCH] lib/lzo: Avoid output overruns when compressing David Sterba
2025-02-28 5:24 ` Sergey Senozhatsky
2025-02-28 12:43 ` Ard Biesheuvel
2025-02-28 13:55 ` Sergey Senozhatsky
2025-02-28 14:02 ` David Sterba
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=67BC9C68.5090300@oberhumer.com \
--to=markus@oberhumer.com \
--cc=akpm@linux-foundation.org \
--cc=dave.rodgman@arm.com \
--cc=herbert@gondor.apana.org.au \
--cc=linux-crypto@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=nitingupta910@gmail.com \
--cc=senozhatsky@chromium.org \
--cc=torvalds@linux-foundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox