Re: Security concern about open range integers (was: Question about: 4.1.1 Integer representation)

On Mon, Oct 21, 2013 at 2:15 PM, Martin Thomson <martin.thomson@gmail.com>wrote:

> On 21 October 2013 14:03, Fred Akalin <akalin@google.com> wrote:
> > 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.
>
> If you want to use all the 32 bits, then you have to check what bits are
> set.
>

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


> 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...
>

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;
};