Potential bug with bad dictionary transform ? #275

New Issue

claunia · 2026-01-29T20:41:14Z

claunia commented

2026-01-29 20:41:14 +00:00

Originally created by @OlivierNV on GitHub (Mar 21, 2019).

It seems that the format would allow a dictionary transform that removes the first or last characters of a dictionary word such that the resulting word size has zero length.
This could also be combined with a custom distance table with a single zero-bit symbol such that the state machine hangs reading zero bits from the bitstream and producing zero bytes.

Would it make sense to update the specification to make it illegal to have a dictionary transform that results in a word length smaller than 2 ?

Originally created by @OlivierNV on GitHub (Mar 21, 2019). It seems that the format would allow a dictionary transform that removes the first or last characters of a dictionary word such that the resulting word size has zero length. This could also be combined with a custom distance table with a single zero-bit symbol such that the state machine hangs reading zero bits from the bitstream and producing zero bytes. Would it make sense to update the specification to make it illegal to have a dictionary transform that results in a word length smaller than 2 ?

claunia closed this issue

2026-01-29 20:41:14 +00:00

claunia commented

2026-01-29 20:41:15 +00:00

@eustas commented on GitHub (Mar 22, 2019):

This might be a useful addition to "Shared Brotli" spec.

If it is a real bug, then there will be no choice, but to update RFC, but otherwise, it is better to leave it untouched.

I'll try to describe, why this situation (infinite loop) is impossible. Would be very grateful, if you double-check.

main loop (simplified):
- read command
- read extra bits for insert length
- read extra bits for copy length
- read distance code
- read extra distance bits
necessary condition for infinite loop: no bits are read, no bytes are produced
consequently, insert length == 0; otherwise we will produce output, even if do not consume input
there should be no extra bits insert and copy length
0 distance code (use last distance) has very limited ability to reference to static dictionary, because distances that refer to dictionary are not stored in distance ringbuffer
- see testIntactDistanceRingBuffer tests
this means that only 6 command codes could be used:

  { 0x00, 0x00, -1, 0x02, 0x0000, 0x0004 },
  { 0x00, 0x00, -1, 0x03, 0x0000, 0x0005 },
  { 0x00, 0x00, -1, 0x03, 0x0000, 0x0006 },
  { 0x00, 0x00, -1, 0x03, 0x0000, 0x0007 },
  { 0x00, 0x00, -1, 0x03, 0x0000, 0x0008 },
  { 0x00, 0x00, -1, 0x03, 0x0000, 0x0009 },

In other words, 4 <= copy length <= 9
distance is encoded with zero or more extra bits
zero extra distance bits mean that either short code is used (distance is taken from ringbuffer), or direct distance code is used
with maximal direct distance is 120 (= 15 << 3)
transform = distance >> shift(copy length)
4 <= copy length <= 9 -> shift >= 10
consequently, transform is always 0 (identity transform)

In "Shared Brotli" shift might be smaller and transform table is different -> this bug might become possible to exploit.

@eustas commented on GitHub (Mar 22, 2019): This might be a useful addition to "Shared Brotli" spec. If it is a real bug, then there will be no choice, but to update RFC, but otherwise, it is better to leave it untouched. I'll try to describe, why this situation (infinite loop) is impossible. Would be very grateful, if you double-check. * main loop (simplified): * read command * read extra bits for insert length * read extra bits for copy length * read distance code * read extra distance bits * necessary condition for infinite loop: no bits are read, no bytes are produced * consequently, insert length == 0; otherwise we will produce output, even if do not consume input * there should be no extra bits insert and copy length * `0` distance code (use last distance) has very limited ability to reference to static dictionary, because distances that refer to dictionary are not stored in distance ringbuffer * see `testIntactDistanceRingBuffer` tests * this means that only 6 command codes could be used: ``` { 0x00, 0x00, -1, 0x02, 0x0000, 0x0004 }, { 0x00, 0x00, -1, 0x03, 0x0000, 0x0005 }, { 0x00, 0x00, -1, 0x03, 0x0000, 0x0006 }, { 0x00, 0x00, -1, 0x03, 0x0000, 0x0007 }, { 0x00, 0x00, -1, 0x03, 0x0000, 0x0008 }, { 0x00, 0x00, -1, 0x03, 0x0000, 0x0009 }, ``` * In other words, 4 <= copy length <= 9 * distance is encoded with zero or more extra bits * zero extra distance bits mean that either short code is used (distance is taken from ringbuffer), or direct distance code is used * with maximal direct distance is 120 (= 15 << 3) * transform = distance >> shift(copy length) * 4 <= copy length <= 9 -> shift >= 10 * consequently, transform is always 0 (identity transform) In "Shared Brotli" shift might be smaller and transform table is different -> this bug might become possible to exploit.

claunia commented

2026-01-29 20:41:15 +00:00

@eustas commented on GitHub (Mar 22, 2019):

+@lvandeve

@eustas commented on GitHub (Mar 22, 2019): +@lvandeve

claunia commented

2026-01-29 20:41:16 +00:00

@OlivierNV commented on GitHub (Mar 22, 2019):

Ah, did not realize that distances that refer to dictionary were not stored in ring buffer: in this case, yes, it would be difficult to produce a non-zero transform_idx without consuming any bits.

@OlivierNV commented on GitHub (Mar 22, 2019): Ah, did not realize that distances that refer to dictionary were not stored in ring buffer: in this case, yes, it would be difficult to produce a non-zero transform_idx without consuming any bits.

claunia commented

2026-01-29 20:41:16 +00:00

@lvandeve commented on GitHub (Mar 22, 2019):

Thanks for pointing out this very interesting detail :)

Indeed the amount of symbols read while decoding commands is bounded, even if of zero length, which can be seen in "10. Decoding Algorithm" in the specification:

https://tools.ietf.org/rfc/rfc7932.txt

@lvandeve commented on GitHub (Mar 22, 2019): Thanks for pointing out this very interesting detail :) Indeed the amount of symbols read while decoding commands is bounded, even if of zero length, which can be seen in "10. Decoding Algorithm" in the specification: https://tools.ietf.org/rfc/rfc7932.txt

claunia commented

2026-01-29 20:41:16 +00:00

@OlivierNV commented on GitHub (Mar 22, 2019):

Hmm. Actually, the distance ring buffer is persistent across meta-blocks, so it's possible to start a block with any arbitrary distance in the ring buffer, so the only thing necessary to exploit this would be an alphabet size of 1 such that only one command can be encoded using zero bits (zero insert length with dictionary copy using distance from ring buffer)

@OlivierNV commented on GitHub (Mar 22, 2019): Hmm. Actually, the distance ring buffer is persistent across meta-blocks, so it's possible to start a block with any arbitrary distance in the ring buffer, so the only thing necessary to exploit this would be an alphabet size of 1 such that only one command can be encoded using zero bits (zero insert length with dictionary copy using distance from ring buffer)

claunia commented

2026-01-29 20:41:17 +00:00

@eustas commented on GitHub (Mar 22, 2019):

Yes, distance ring buffer persists, but distance to dictionary (max [backward] distance) persists as well. So, as I mentioned earlier, it is impossible to put distance that refers to dictionary in distance ring buffer (except for initial 4).

@eustas commented on GitHub (Mar 22, 2019): Yes, distance ring buffer persists, but distance to dictionary (max [backward] distance) persists as well. So, as I mentioned earlier, it is impossible to put distance that refers to dictionary in distance ring buffer (except for initial 4).

claunia commented

2026-01-29 20:41:17 +00:00

@OlivierNV commented on GitHub (Mar 22, 2019):

Oh I see, the maximum distance value in the ring buffer is always a non-dictionary distance, so it's not possible to produce a dictionary transform distance code that would not require extra bits...
Regarding the bound for the amount of symbols being read per meta-block, the 16M bound is based on the assumption that at least one byte is produced by every command being read (with meta block length being limited to 16M).

@OlivierNV commented on GitHub (Mar 22, 2019): Oh I see, the maximum distance value in the ring buffer is always a non-dictionary distance, so it's not possible to produce a dictionary transform distance code that would not require extra bits... Regarding the bound for the amount of symbols being read per meta-block, the 16M bound is based on the assumption that at least one byte is produced by every command being read (with meta block length being limited to 16M).

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: starred/brotli#275