1 /* Copyright (c) 2004, Roger Dingledine.
2 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
3 * Copyright (c) 2007-2017, The Tor Project, Inc. */
4 /* See LICENSE for licensing information */
8 * \brief Common compression API.
19 #ifdef HAVE_NETINET_IN_H
20 #include <netinet/in.h>
26 #include "compress_lzma.h"
27 #include "compress_none.h"
28 #include "compress_zlib.h"
29 #include "compress_zstd.h"
31 /** Total number of bytes allocated for compression state overhead. */
32 static atomic_counter_t total_compress_allocation
;
35 /* These macros define the maximum allowable compression factor. Anything of
36 * size greater than CHECK_FOR_COMPRESSION_BOMB_AFTER is not allowed to
37 * have an uncompression factor (uncompressed size:compressed size ratio) of
38 * any greater than MAX_UNCOMPRESSION_FACTOR.
40 * Picking a value for MAX_UNCOMPRESSION_FACTOR is a trade-off: we want it to
41 * be small to limit the attack multiplier, but we also want it to be large
42 * enough so that no legitimate document --even ones we might invent in the
43 * future -- ever compresses by a factor of greater than
44 * MAX_UNCOMPRESSION_FACTOR. Within those parameters, there's a reasonably
45 * large range of possible values. IMO, anything over 8 is probably safe; IMO
46 * anything under 50 is probably sufficient.
48 #define MAX_UNCOMPRESSION_FACTOR 25
49 #define CHECK_FOR_COMPRESSION_BOMB_AFTER (1024*64)
52 /** Return true if uncompressing an input of size <b>in_size</b> to an input of
53 * size at least <b>size_out</b> looks like a compression bomb. */
55 tor_compress_is_compression_bomb
,(size_t size_in
, size_t size_out
))
57 if (size_in
== 0 || size_out
< CHECK_FOR_COMPRESSION_BOMB_AFTER
)
60 return (size_out
/ size_in
> MAX_UNCOMPRESSION_FACTOR
);
63 /** Guess the size that <b>in_len</b> will be after compression or
66 guess_compress_size(int compress
, compress_method_t method
,
67 compression_level_t compression_level
,
70 // ignore these for now.
71 (void)compression_level
;
72 if (method
== NO_METHOD
) {
73 /* Guess that we'll need an extra byte, to avoid a needless realloc
74 * for nul-termination */
75 return (in_len
< SIZE_MAX
) ? in_len
+ 1 : in_len
;
78 /* Always guess a factor of 2. */
82 if (in_len
< SIZE_T_CEILING
/2)
85 return MAX(in_len
, 1024);
88 /** Internal function to implement tor_compress/tor_uncompress, depending on
89 * whether <b>compress</b> is set. All arguments are as for tor_compress or
92 tor_compress_impl(int compress
,
93 char **out
, size_t *out_len
,
94 const char *in
, size_t in_len
,
95 compress_method_t method
,
96 compression_level_t compression_level
,
98 int protocol_warn_level
)
100 tor_compress_state_t
*stream
;
103 stream
= tor_compress_new(compress
, method
, compression_level
);
105 if (stream
== NULL
) {
106 log_warn(LD_GENERAL
, "NULL stream while %scompressing",
108 log_debug(LD_GENERAL
, "method: %d level: %d at len: %lu",
109 method
, compression_level
, (unsigned long)in_len
);
113 size_t in_len_orig
= in_len
;
114 size_t out_remaining
, out_alloc
;
117 out_remaining
= out_alloc
=
118 guess_compress_size(compress
, method
, compression_level
, in_len
);
119 *out
= outptr
= tor_malloc(out_remaining
);
121 const int finish
= complete_only
|| compress
;
124 switch (tor_compress_process(stream
,
125 &outptr
, &out_remaining
,
126 &in
, &in_len
, finish
)) {
127 case TOR_COMPRESS_DONE
:
128 if (in_len
== 0 || compress
) {
131 // More data is present, and we're decompressing. So we may need to
132 // reinitialize the stream if we are handling multiple concatenated
134 tor_compress_free(stream
);
135 stream
= tor_compress_new(compress
, method
, compression_level
);
136 if (stream
== NULL
) {
137 log_warn(LD_GENERAL
, "NULL stream while %scompressing",
143 case TOR_COMPRESS_OK
:
144 if (compress
|| complete_only
) {
145 log_fn(protocol_warn_level
, LD_PROTOCOL
,
146 "Unexpected %s while %scompressing",
147 complete_only
?"end of input":"result",
149 log_debug(LD_GENERAL
, "method: %d level: %d at len: %lu",
150 method
, compression_level
, (unsigned long)in_len
);
158 case TOR_COMPRESS_BUFFER_FULL
: {
159 if (!compress
&& outptr
< *out
+out_alloc
) {
160 // A buffer error in this case means that we have a problem
162 log_fn(protocol_warn_level
, LD_PROTOCOL
,
163 "Possible truncated or corrupt compressed data");
166 if (out_alloc
>= SIZE_T_CEILING
/ 2) {
167 log_warn(LD_GENERAL
, "While %scompressing data: ran out of space.",
172 tor_compress_is_compression_bomb(in_len_orig
, out_alloc
)) {
173 // This should already have been caught down in the backend logic.
175 tor_assert_nonfatal_unreached();
179 const size_t offset
= outptr
- *out
;
181 *out
= tor_realloc(*out
, out_alloc
);
182 outptr
= *out
+ offset
;
183 out_remaining
= out_alloc
- offset
;
186 case TOR_COMPRESS_ERROR
:
187 log_fn(protocol_warn_level
, LD_GENERAL
,
188 "Error while %scompressing data: bad input?",
190 goto err
; // bad data.
194 tor_assert_nonfatal_unreached();
200 *out_len
= outptr
- *out
;
201 if (compress
&& tor_compress_is_compression_bomb(*out_len
, in_len_orig
)) {
202 log_warn(LD_BUG
, "We compressed something and got an insanely high "
203 "compression factor; other Tors would think this was a "
204 "compression bomb.");
208 // NUL-terminate our output.
209 if (out_alloc
== *out_len
)
210 *out
= tor_realloc(*out
, out_alloc
+ 1);
211 (*out
)[*out_len
] = '\0';
223 tor_compress_free(stream
);
227 /** Given <b>in_len</b> bytes at <b>in</b>, compress them into a newly
228 * allocated buffer, using the method described in <b>method</b>. Store the
229 * compressed string in *<b>out</b>, and its length in *<b>out_len</b>.
230 * Return 0 on success, -1 on failure.
233 tor_compress(char **out
, size_t *out_len
,
234 const char *in
, size_t in_len
,
235 compress_method_t method
)
237 return tor_compress_impl(1, out
, out_len
, in
, in_len
, method
,
242 /** Given zero or more compressed strings of total length <b>in_len</b> bytes
243 * at <b>in</b>, uncompress them into a newly allocated buffer, using the
244 * method described in <b>method</b>. Store the uncompressed string in
245 * *<b>out</b>, and its length in *<b>out_len</b>. Return 0 on success, -1 on
248 * If any bytes are written to <b>out</b>, an extra byte NUL is always
249 * written at the end, but not counted in <b>out_len</b>. This is a
250 * safety feature to ensure that the output can be treated as a
251 * NUL-terminated string -- though of course, callers should check
254 * If <b>complete_only</b> is true, we consider a truncated input as a
255 * failure; otherwise we decompress as much as we can. Warn about truncated
256 * or corrupt inputs at <b>protocol_warn_level</b>.
259 tor_uncompress(char **out
, size_t *out_len
,
260 const char *in
, size_t in_len
,
261 compress_method_t method
,
263 int protocol_warn_level
)
265 return tor_compress_impl(0, out
, out_len
, in
, in_len
, method
,
267 complete_only
, protocol_warn_level
);
270 /** Try to tell whether the <b>in_len</b>-byte string in <b>in</b> is likely
271 * to be compressed or not. If it is, return the likeliest compression method.
272 * Otherwise, return UNKNOWN_METHOD.
275 detect_compression_method(const char *in
, size_t in_len
)
277 if (in_len
> 2 && fast_memeq(in
, "\x1f\x8b", 2)) {
279 } else if (in_len
> 2 && (in
[0] & 0x0f) == 8 &&
280 (ntohs(get_uint16(in
)) % 31) == 0) {
282 } else if (in_len
> 2 &&
283 fast_memeq(in
, "\x5d\x00\x00", 3)) {
285 } else if (in_len
> 3 &&
286 fast_memeq(in
, "\x28\xb5\x2f\xfd", 4)) {
289 return UNKNOWN_METHOD
;
293 /** Return 1 if a given <b>method</b> is supported; otherwise 0. */
295 tor_compress_supports_method(compress_method_t method
)
300 return tor_zlib_method_supported();
302 return tor_lzma_method_supported();
304 return tor_zstd_method_supported();
314 * Return a bitmask of the supported compression types, where 1<<m is
315 * set in the bitmask if and only if compression with method <b>m</b> is
319 tor_compress_get_supported_method_bitmask(void)
321 static unsigned supported
= 0;
322 if (supported
== 0) {
324 for (m
= NO_METHOD
; m
<= UNKNOWN_METHOD
; ++m
) {
325 if (tor_compress_supports_method(m
)) {
326 supported
|= (1u << m
);
333 /** Table of compression method names. These should have an "x-" prefix,
334 * if they are not listed in the IANA content coding registry. */
335 static const struct {
337 compress_method_t method
;
338 } compression_method_names
[] = {
339 { "gzip", GZIP_METHOD
},
340 { "deflate", ZLIB_METHOD
},
341 // We call this "x-tor-lzma" rather than "x-lzma", because we impose a
342 // lower maximum memory usage on the decoding side.
343 { "x-tor-lzma", LZMA_METHOD
},
344 { "x-zstd" , ZSTD_METHOD
},
345 { "identity", NO_METHOD
},
347 /* Later entries in this table are not canonical; these are recognized but
349 { "x-gzip", GZIP_METHOD
},
352 /** Return the canonical string representation of the compression method
353 * <b>method</b>, or NULL if the method isn't recognized. */
355 compression_method_get_name(compress_method_t method
)
358 for (i
= 0; i
< ARRAY_LENGTH(compression_method_names
); ++i
) {
359 if (method
== compression_method_names
[i
].method
)
360 return compression_method_names
[i
].name
;
365 /** Table of compression human readable method names. */
366 static const struct {
367 compress_method_t method
;
369 } compression_method_human_names
[] = {
370 { NO_METHOD
, "uncompressed" },
371 { GZIP_METHOD
, "gzipped" },
372 { ZLIB_METHOD
, "deflated" },
373 { LZMA_METHOD
, "LZMA compressed" },
374 { ZSTD_METHOD
, "Zstandard compressed" },
375 { UNKNOWN_METHOD
, "unknown encoding" },
378 /** Return a human readable string representation of the compression method
379 * <b>method</b>, or NULL if the method isn't recognized. */
381 compression_method_get_human_name(compress_method_t method
)
384 for (i
= 0; i
< ARRAY_LENGTH(compression_method_human_names
); ++i
) {
385 if (method
== compression_method_human_names
[i
].method
)
386 return compression_method_human_names
[i
].name
;
391 /** Return the compression method represented by the string <b>name</b>, or
392 * UNKNOWN_METHOD if the string isn't recognized. */
394 compression_method_get_by_name(const char *name
)
397 for (i
= 0; i
< ARRAY_LENGTH(compression_method_names
); ++i
) {
398 if (!strcmp(compression_method_names
[i
].name
, name
))
399 return compression_method_names
[i
].method
;
401 return UNKNOWN_METHOD
;
404 /** Return a string representation of the version of the library providing the
405 * compression method given in <b>method</b>. Returns NULL if <b>method</b> is
406 * unknown or unsupported. */
408 tor_compress_version_str(compress_method_t method
)
413 return tor_zlib_get_version_str();
415 return tor_lzma_get_version_str();
417 return tor_zstd_get_version_str();
425 /** Return a string representation of the version of the library, found at
426 * compile time, providing the compression method given in <b>method</b>.
427 * Returns NULL if <b>method</b> is unknown or unsupported. */
429 tor_compress_header_version_str(compress_method_t method
)
434 return tor_zlib_get_header_version_str();
436 return tor_lzma_get_header_version_str();
438 return tor_zstd_get_header_version_str();
446 /** Return the approximate number of bytes allocated for all
447 * supported compression schemas. */
449 tor_compress_get_total_allocation(void)
451 return atomic_counter_get(&total_compress_allocation
) +
452 tor_zlib_get_total_allocation() +
453 tor_lzma_get_total_allocation() +
454 tor_zstd_get_total_allocation();
457 /** Internal state for an incremental compression/decompression. The body of
458 * this struct is not exposed. */
459 struct tor_compress_state_t
{
460 compress_method_t method
; /**< The compression method. */
463 tor_zlib_compress_state_t
*zlib_state
;
464 tor_lzma_compress_state_t
*lzma_state
;
465 tor_zstd_compress_state_t
*zstd_state
;
466 } u
; /**< Compression backend state. */
469 /** Construct and return a tor_compress_state_t object using <b>method</b>. If
470 * <b>compress</b>, it's for compression; otherwise it's for decompression. */
471 tor_compress_state_t
*
472 tor_compress_new(int compress
, compress_method_t method
,
473 compression_level_t compression_level
)
475 tor_compress_state_t
*state
;
477 state
= tor_malloc_zero(sizeof(tor_compress_state_t
));
478 state
->method
= method
;
483 tor_zlib_compress_state_t
*zlib_state
=
484 tor_zlib_compress_new(compress
, method
, compression_level
);
486 if (zlib_state
== NULL
)
489 state
->u
.zlib_state
= zlib_state
;
493 tor_lzma_compress_state_t
*lzma_state
=
494 tor_lzma_compress_new(compress
, method
, compression_level
);
496 if (lzma_state
== NULL
)
499 state
->u
.lzma_state
= lzma_state
;
503 tor_zstd_compress_state_t
*zstd_state
=
504 tor_zstd_compress_new(compress
, method
, compression_level
);
506 if (zstd_state
== NULL
)
509 state
->u
.zstd_state
= zstd_state
;
519 atomic_counter_add(&total_compress_allocation
,
520 sizeof(tor_compress_state_t
));
528 /** Compress/decompress some bytes using <b>state</b>. Read up to
529 * *<b>in_len</b> bytes from *<b>in</b>, and write up to *<b>out_len</b> bytes
530 * to *<b>out</b>, adjusting the values as we go. If <b>finish</b> is true,
531 * we've reached the end of the input.
533 * Return TOR_COMPRESS_DONE if we've finished the entire
534 * compression/decompression.
535 * Return TOR_COMPRESS_OK if we're processed everything from the input.
536 * Return TOR_COMPRESS_BUFFER_FULL if we're out of space on <b>out</b>.
537 * Return TOR_COMPRESS_ERROR if the stream is corrupt.
539 tor_compress_output_t
540 tor_compress_process(tor_compress_state_t
*state
,
541 char **out
, size_t *out_len
,
542 const char **in
, size_t *in_len
,
545 tor_assert(state
!= NULL
);
546 const size_t in_len_orig
= *in_len
;
547 const size_t out_len_orig
= *out_len
;
548 tor_compress_output_t rv
;
550 switch (state
->method
) {
553 rv
= tor_zlib_compress_process(state
->u
.zlib_state
,
554 out
, out_len
, in
, in_len
,
558 rv
=tor_lzma_compress_process(state
->u
.lzma_state
,
559 out
, out_len
, in
, in_len
,
563 rv
= tor_zstd_compress_process(state
->u
.zstd_state
,
564 out
, out_len
, in
, in_len
,
568 rv
= tor_cnone_compress_process(out
, out_len
, in
, in_len
,
575 if (BUG((rv
== TOR_COMPRESS_OK
) &&
576 *in_len
== in_len_orig
&&
577 *out_len
== out_len_orig
)) {
579 "More info on the bug: method == %s, finish == %d, "
580 " *in_len == in_len_orig == %lu, "
581 "*out_len == out_len_orig == %lu",
582 compression_method_get_human_name(state
->method
), finish
,
583 (unsigned long)in_len_orig
, (unsigned long)out_len_orig
);
584 return TOR_COMPRESS_ERROR
;
589 return TOR_COMPRESS_ERROR
;
592 /** Deallocate <b>state</b>. */
594 tor_compress_free(tor_compress_state_t
*state
)
599 switch (state
->method
) {
602 tor_zlib_compress_free(state
->u
.zlib_state
);
605 tor_lzma_compress_free(state
->u
.lzma_state
);
608 tor_zstd_compress_free(state
->u
.zstd_state
);
616 atomic_counter_sub(&total_compress_allocation
,
617 sizeof(tor_compress_state_t
));
621 /** Return the approximate number of bytes allocated for <b>state</b>. */
623 tor_compress_state_size(const tor_compress_state_t
*state
)
625 tor_assert(state
!= NULL
);
627 size_t size
= sizeof(tor_compress_state_t
);
629 switch (state
->method
) {
632 size
+= tor_zlib_compress_state_size(state
->u
.zlib_state
);
635 size
+= tor_lzma_compress_state_size(state
->u
.lzma_state
);
638 size
+= tor_zstd_compress_state_size(state
->u
.zstd_state
);
648 /** Initialize all compression modules. */
650 tor_compress_init(void)
652 atomic_counter_init(&total_compress_allocation
);