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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.