Subject: Question about: 4.1.1 Integer representation

From: Frédéric Kayser <[email-masked]>
Date: Fri, 18 Oct 2013 10:01:25 +0200

Hello,
I have a pretty dumb question regarding integer representation isn't it easier to grasp expressed as binary masking and right shifts?
This should be the same
I % 128  becomes  I & 127
I / 128 becomes  I >> 7

And wouldn't it be way easier and faster to record/reconstruct such integers by moving all the flags (most significant bits) of each byte in front of the code?

I < 128
0xxxxxxx
I < 16.384
10xxxxxx xxxxxxxx  (compared to 1yyyyyyy 0yyyyyyy groups of 7 least significant bits first)
I < 2.097.152
110xxxxx xxxxxxxx xxxxxxxx  (compared to 1yyyyyyy 1yyyyyyy 0yyyyyyy groups of 7 least significant bits first)
I < 268.435.456
1110xxxx xxxxxxxx xxxxxxxx xxxxxxxx  (compared to 1yyyyyyy 1yyyyyyy 1yyyyyyy 0yyyyyyy groups of 7 least significant bits first)
…

Where xxx…xxx is simply the binary representation of I

The first part looks like unary coding and the overall form of this encoding is a 7, 7, ∞ start-step-code or a base 128 Elias γ′ code, do you really want to keep the universal nature of such a code or cap it?

Regards
-- 
Frédéric Kayser

---

From: Roberto Peon <[email-masked]>
Date: Fri, 18 Oct 2013 09:09:54 -0700

Yes, the binary operations are equivalent to the arithmetic operations
currently specified.
I originally had the binary operators in there, but guessed that those
familiar with binary operators would do the mapping as you have done, but
that for those for whom binary operators was foreign, if would still be
understandable.

A fair bit of efficiency is gained by allowing the n-bit prefix to encode
values since most values for within that first byte.
The rest of the int is in a well known and well supported format.
-=R
On Oct 18, 2013 1:03 AM, "Frédéric Kayser" <[email-masked]> wrote:

> Hello,
> I have a pretty dumb question regarding integer representation isn't it
> easier to grasp expressed as binary masking and right shifts?
> This should be the same
> I % 128  becomes  I & 127
> I / 128 becomes  I >> 7
>
> And wouldn't it be way easier and faster to record/reconstruct such
> integers by moving all the flags (most significant bits) of each byte in
> front of the code?
>
> I < 128
> 0xxxxxxx
> I < 16.384
> 1110xxxx xxxxxxxx xxxxxxxx xxxxxxxx  (compared
> to 1yyyyyyy 1yyyyyyy 1yyyyyyy 0yyyyyyy groups of 7 least significant bits
> first)
> …
>
> The first part looks like unary coding and the overall form of this
> encoding is a 7, 7, ∞ start-step-code or a base 128 Elias γ′ code, do you
> really want to keep the universal nature of such a code or cap it?
>
> Regards
> --
> Frédéric Kayser
>

---

From: Martin Thomson <[email-masked]>
Date: Fri, 18 Oct 2013 09:47:26 -0700

> The rest of the int is in a well known and well supported format.

That's the key.  Lower efficiency for larger values is acceptable if
you can get more into a single byte.  That is 255 values in the first
byte before continuations kick in, against 127 values.  Most values we
have fit into that first byte and we want to keep it that way.

---

From: Frédéric Kayser <[email-masked]>
Date: Mon, 21 Oct 2013 02:18:31 +0200

Hello,
let me express it a bit differently "the well known and well supported format" is an universal integer encoding (closely related to a 7, 7, ∞ start-step-stop code) this means it can encode any integer of unknown size including ridiculously large ones.
Know how is a server supposed to react if it receives a malicious header that states that the next field is FF FF FF FF FF FF FF FF 7F bytes long (thats 2^56 + 255 if I'm not wrong)? Naive implementations will probably have a shock trying to decode this in a fixed size 32-bits int (add a couple of FF and it overruns a 64-bits int) or allocating memory for the field in question, others may discard it, but at which point take the cut between legitimate large values and malicious ones? My concern is that every 8+ or whatever+ is a potential memory bomb if its not capped at some point.

My initial concern was rather a speed concern (read micro-optimization to speed-up decoding) concerning "the well known and well supported format" since a capped version of such a code could be processed faster, encoding is always relatively fast decoding is a bit more tricky since the bits recorded first are groups of 7 least significant bits whereas a real start-step-stop code would keep the natural bit order and would not require bit shifts (just byte swaps eventually).

Regards
-- 
Frédéric Kayser

---

From: Roberto Peon <[email-masked]>
Date: Sun, 20 Oct 2013 17:23:50 -0700

If any value is too large, the connection should be torn down.
The definition of 'too large' depends utterly on details that we cannot
predict.
For many SoC or embedded implementations, this may be 4k.
For better provisioned clients, this could be gigabytes or terabytes.

This problem already exists in SPDY, and is dealt with in the venerable
tradition of deciding if the request is sane, and if not, dealing with it :)

As for speed-- for the data frames we don't use this kind of encoding-- the
overhead of a fixed encoding is small there.
For a compressor, this isn't as true-- the overhead of a fixed encoding is
much higher.
In any case, the vast majority of the time, there will be zero speed
difference since the first byte is all that is necessary to encode the
index/length.
-=R

On Sun, Oct 20, 2013 at 5:18 PM, Frédéric Kayser <[email-masked]> wrote:

> Hello,
> let me express it a bit differently "the well known and well supported
> format" is an universal integer encoding (closely related to a 7, 7, ∞
> start-step-stop code) this means it can encode any integer of unknown size
> including ridiculously large ones.
> Know how is a server supposed to react if it receives a malicious header
> that states that the next field is FF FF FF FF FF FF FF FF 7F bytes long
> (thats 2^56 + 255 if I'm not wrong)? Naive implementations will probably
> have a shock trying to decode this in a fixed size 32-bits int (add a
> couple of FF and it overruns a 64-bits int) or allocating memory for the
> field in question, others may discard it, but at which point take the cut
> between legitimate large values and malicious ones? My concern is that
> every 8+ or whatever+ is a potential memory bomb if its not capped at some
> point.
>
> My initial concern was rather a speed concern (read micro-optimization to
> speed-up decoding) concerning "the well known and well supported format"
> since a capped version of such a code could be processed faster, encoding
> is always relatively fast decoding is a bit more tricky since the bits
> recorded first are groups of 7 least significant bits whereas a
> real start-step-stop code would keep the natural bit order and would not
> require bit shifts (just byte swaps eventually).
>
> Regards
> --
> Frédéric Kayser
>
> Roberto Peon wrote:
>
>> 110xxxxx xxxxxxxx xxxxxxxx  (compared
>> to 1yyyyyyy 1yyyyyyy 0yyyyyyy groups of 7 least significant bits first)
>> I < 268.435.456

---

From: James M Snell <[email-masked]>
Date: Sun, 20 Oct 2013 17:58:41 -0700

While this is true, it would likely be worthwhile to include a short
word of caution in the spec. For example, any >64bit value is not
likely to be very sane.

On Sun, Oct 20, 2013 at 5:23 PM, Roberto Peon <[email-masked]> wrote:
>> have a shock trying to decode this in a fixed size 32-bits int (add a couple
>> of FF and it overruns a 64-bits int) or allocating memory for the field in
>> question, others may discard it, but at which point take the cut between
>> legitimate large values and malicious ones? My concern is that every 8+ or
>> whatever+ is a potential memory bomb if its not capped at some point.
>>
>> since a capped version of such a code could be processed faster, encoding is
>> always relatively fast decoding is a bit more tricky since the bits recorded
>> first are groups of 7 least significant bits whereas a real start-step-stop
>> code would keep the natural bit order and would not require bit shifts (just
>> byte swaps eventually).
>>
>> Regards
>> --
>> Frédéric Kayser
>>
>> Roberto Peon wrote:
>>
>>> 110xxxxx xxxxxxxx xxxxxxxx  (compared to 1yyyyyyy 1yyyyyyy 0yyyyyyy
>>> groups of 7 least significant bits first)
>>> I < 268.435.456
>>> 1110xxxx xxxxxxxx xxxxxxxx xxxxxxxx  (compared to 1yyyyyyy 1yyyyyyy
>>> 1yyyyyyy 0yyyyyyy groups of 7 least significant bits first)
>>> …
>>>

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 21 Oct 2013 07:20:58 +0200

> The definition of 'too large' depends utterly on details that we cannot

And we already have the case with chunks in HTTP/1.1 which can cause a
connection to be suddenly broken because an implementation cannot parse
too large a value.

Cheers,
Willy

---

From: Fred Akalin <[email-masked]>
Date: Sun, 20 Oct 2013 23:24:56 -0700

I think it's worth mentioning explicit upper bounds in the spec. Something
like any decoded varint must fit in 32 bits. Since settings are 32-bit
values, that implies that max context size is also 32 bits, which gives a
hard upper bound on the number of table entries (27 bits). We can probably
give better upper bounds for max header name length and value length, too,
right?

On Sun, Oct 20, 2013 at 5:23 PM, Roberto Peon <[email-masked]> wrote:

> As for speed-- for the data frames we don't use this kind of encoding--
> the overhead of a fixed encoding is small there.

---

From: Martin Thomson <[email-masked]>
Date: Mon, 21 Oct 2013 10:23:10 -0700

On 20 October 2013 23:24, Fred Akalin <[email-masked]> wrote:
> like any decoded varint must fit in 32 bits.

I don't think that it makes sense to have a single maximum.  Fitting
the result into 32bits might be a nice goal, but that requires that
you use only 6 octets of encoded length and make sure that it fits the
mask 0xff 0x80 0xC0 0xff 0xff 0x0f.  Or maybe 0xff 0x80 0xC0 0xff 0xff
0x0f7 if you are sign-bit averse.  But only if that last byte has the
0x08 or 0x04 bit set.  That is yucky.  The alternative leaves you
vulnerable to other attacks, especially the one where you get a long
series of 0x80 bytes.

https://github.com/http2/http2-spec/pull/291

---

From: James M Snell <[email-masked]>
Date: Mon, 21 Oct 2013 12:49:36 -0700

Offering some sound advice in the security considerations is certainly
worthwhile.

---

From: Fred Akalin <[email-masked]>
Date: Mon, 21 Oct 2013 14:03:46 -0700

I'm not sure I see the problem. While decoding a varint, you have to keep
track of amount to right-shift the low 7 bits of the next octet. You can
then check if doing so would overflow 32 bits, and abort if so.

---

From: Martin Thomson <[email-masked]>
Date: Mon, 21 Oct 2013 14:15:18 -0700

> then check if doing so would overflow 32 bits, and abort if so.

If you want to use all the 32 bits, then you have to check what bits are set.

The bigger problem is the extra 2^N-1 you are required to add (255 for
an 8-bit prefix), which will cause an overflow if you aren't careful.
Hence the tricky little mask I used...

---

From: Mike Bishop <[email-masked]>
Date: Mon, 21 Oct 2013 21:20:05 +0000

Particularly if this were to be used for a typed header, 32 bits would be insufficient to hold a date or the size of a multi-GB download.  64 bits seems sufficient currently, but it might still be worth letting this be implementation-dependent.  This seems like another area where you might not want to tell a malicious attacker precisely what tripped you up.

However, for all current purposes in the compression spec, 32 bits is probably more than sufficient.

From: Fred Akalin [mailto:[email-masked]]
Sent: Monday, October 21, 2013 2:04 PM
To: Martin Thomson
Cc: Roberto Peon; Frédéric Kayser; HTTP Working Group
Subject: Re: Security concern about open range integers (was: Question about: 4.1.1 Integer representation)

I'm not sure I see the problem. While decoding a varint, you have to keep track of amount to right-shift the low 7 bits of the next octet. You can then check if doing so would overflow 32 bits, and abort if so.

On Mon, Oct 21, 2013 at 10:23 AM, Martin Thomson <[email-masked]<mailto:[email-masked]>> wrote:

---

From: Fred Akalin <[email-masked]>
Date: Mon, 21 Oct 2013 14:22:11 -0700

> If you want to use all the 32 bits, then you have to check what bits are

I guess, but that doesn't seem too onerous?

> Hence the tricky little mask I used...

Unless I'm grossly misunderstanding the format, the varint format is
little-endian, so you fill in the lower bits first, so this shouldn't be a
concern.

I guess this argues for providing pseudocode for decoding a varint as well
as encoding it. To make things a little more concrete, here's the decoding
code from my JS implementation
https://github.com/akalin-chromium/httpbis-header-compression/blob/master/header_decoder.js
,
and I've highlighted the single place where one would insert the additional
check:

// Decodes the next integer based on the representation described in
// 4.1.1. N is the number of bits of the prefix as described in 4.1.1.
Decoder.prototype.decodeNextInteger_ = function(N) {
  var I = 0;
  var hasMore = true;
  var shift = N;

  if (N > 0) {
    var nextMarker = (1 << N) - 1;
    var nextOctet = this.decodeNextOctet_();
    I = nextOctet & nextMarker;
    hasMore = (I == nextMarker);
  }

  while (hasMore) {
    var nextOctet = this.decodeNextOctet_();
    // Check the high bit. (Remember that / in JavaScript is
    // floating-point division).
    hasMore = ((nextOctet & 0x80) != 0);
    *// If "(nextOctet % 128) << shift" won't fit in 32 bits, abort.*
    I += (nextOctet % 128) << shift;
    shift += 7;
  }

  return I;
};

---

From: Fred Akalin <[email-masked]>
Date: Mon, 21 Oct 2013 15:55:11 -0700

> little-endian, so you fill in the lower bits first, so this shouldn't be a

Egg on my face! I did misunderstand the format (my decoder was erroneous).

I still contend that checking for overflow is straightforward, although
doing it via masks seems too tricky.

---

From: Martin Thomson <[email-masked]>
Date: Mon, 21 Oct 2013 16:08:59 -0700

On 21 October 2013 15:55, Fred Akalin <[email-masked]> wrote:
> although doing it via masks seems too tricky.

That's the great thing with our specifications.  You can do it however you want.

Personally, I wouldn't ever want to go anywhere near 2^32 or even 2^31
for header field name or value lengths.  So my overflow detection
would be far cruder even than that.  I'd accumulate to a 32-bit value
and blow up if the n-th byte (maybe the 4th) had the first bit set.
No risk that way.

Greater risks come to those who want to sail closer to the reef, of course.