Subject: Re: [TLS] Length of a variable-length vector: Could it be an odd multiple?

From: =JeffH <[email-masked]>
Date: Fri, 22 Jan 2016 16:43:11 -0800

ON Fri, 22 Jan 2016 15:53:27 Benjamin Kaduk noted:
 > On 01/22/2016 03:26 PM, =JeffH wrote:
 > > On 01/22/2016 12:29 PM, =JeffH wrote:
 > >> [ fixed pitch font advised here ]
 > >
 > > the below is corrected to use "byte count" rather than "index" or
 > > "indicies" (and to ditch the tabs)..
 > >
 > >
 > > > On 01/22/2016 09:42 AM, =JeffH wrote:
 > > > > [ resending from different account - my work addr ends up in spam
 > > > > bucket for many it seems ]
 > > > >
 > > > > On 1/20/16, 11:01 AM, "Benjamin Kaduk" <[email-masked]> wrote:
 > > > > >On 01/20/2016 12:47 PM, Hodges, Jeff wrote:
 > > > > >> On 1/13/16, 12:53 PM, "Benjamin Kaduk" <[email-masked]> wrote:
 > > > > >>> On 01/13/2016 02:44 PM, Jong-Shian Wu wrote:
 >>>>>>>> I have a question about the even-vs-odd restrictions on the
 >>>>>>>> length of a valid variable-length vector defined in TLS
 >>>>>>>> specification  after reading the section 4.3 of RFC 5246
 >>>>>>>> [1] which states that: "The length of an encoded vector
 >>>>>>>> must be an even multiple of the length of a single element
 >>>>>>>> (for example, a 17-byte vector of uint16 would be
 >>>>>>>> illegal)."
 >>>>>>>>
 >>>>>>> It means "whole-number" as opposed to fractional, i.e., there
 >>>>>>> should not be unused "junk bytes" at the end.
 >>>>>>
 >>>>>> In case it's helpful, here's a suggested re-write of that
 >>>>>> quoted sentence above..
 > > > > >>
 > > > > >> The length of an encoded variable-length vector must be an
 > > > > >> exact multiple of the length of a single element. For example,
 > > > > >> an encoded 17-byte vector of uint16 would be illegal, and an
 > > > > >> encoded variable-length vector of four 32 byte elements,
 > > > > >> having a ceiling of 2^16-1, will be 130 bytes long overall
 > > > > >> (2 byte length field followed by 128 bytes of data).
 > > > > >
 > > > > >Wouldn't the ceiling more properly be 2^16-4 in that case?
 > > > >
 > > > > hm, I'm not sure -- what would be the rationale? The exact multiple
 > > > > criteria? but 2^16 / 32 = 2048 while (2^16-4) / 32 = 2047.875
 > > >
 > > > Ah, I seem to have conflated bits and bytes due to reading too quickly
 > > > and should have said (2^16-32), as Ilari alluded to with "or rounding
 > > > thereof to integral multiple of
 > > > elements".
 > >
 > > hm, but in this case it seems that a variable-length vector declared
 > > with a length range of <0..2^16-1> would exactly accommodate up to
 > > 2048 32-byte elements..
 > >
 > > opaque Foo[32] ;
 > >
 > > Foo fooSequence<0..2^16-1>; /* will accommodate up to 2048
 > > Foo instances */
 > >
 > > ..because it has a zero-based byte count, as in this example..
 > >
 > >
 > > opaque Array<0..2^2-1> ; /* should accommodate
 > > 2^2 = 4 1-byte elements */
 > >
 > > /*
 > > Array with 4
 > > elements in memory: [ xx xx xx xx ]
 > > byte count (hex): 0 1 2 3 3 = 2^2-1
 > >
 > > byte count (binary): 00 01 10 11
 > >
 > > */
 > >
 > >
 > > ..yes? or am I missing something?
 >
 > You are missing something.
 >
 > The encoded length represents the actual number of bytes that will
 > follow, so that a zero-length array with maximum length 2^16-1 is
 > encoded as just 00 00. So, even though the index into the array starts
 > at zero, the actual length "starts at" 1, just like in C.

Ok, thanks, yes, I was confusing byte count with indices.

To test my understanding:

Given..

    opaque Foo[32] ;

    Foo fooSequence<0..2^16-32> ;

..fooSequence will accommodate up to 2047 Foo instances, and the length 
prefix of fooSequence will itself be two bytes long, yes?

AFAICT, though, from [1] (and prior TLS specs), it seems legit to declare 
fooSequence like so..

  Foo fooSequence<0..2^16-1> ;

..with the expectation that a correct implementation will allow only 2047 
Foo instances to be encoded into a fooSequence on the wire, yes ?

Also, if one actually needs to be able to accommodate up to _2048_ Foo 
instances, and can tolerate having the length prefix be three bytes long, 
then one could declare fooSequence as..

    Foo fooSequence<0..2^16>;

..or..

    Foo fooSequence<0..2^24-1>;

..yes?

thanks again,

=JeffH

[1] https://tools.ietf.org/html/draft-ietf-tls-tls13-11#section-4.3

---

From: Benjamin Kaduk <[email-masked]>
Date: Fri, 22 Jan 2016 18:50:32 -0600

On 01/22/2016 06:43 PM, =JeffH wrote:
> ..fooSequence will accommodate up to 2047 Foo instances, and the
> length prefix of fooSequence will itself be two bytes long, yes?
>

Yes.

>
> AFAICT, though, from [1] (and prior TLS specs), it seems legit to
> declare fooSequence like so..
>
> ..with the expectation that a correct implementation will allow only
> 2047 Foo instances to be encoded into a fooSequence on the wire, yes ?
>

I believe a correct implementation would do so, yes, though I am not
quite enough of a spec lawyer to be able to state that authoritatively. 
The <0..2^16-32> form is perhaps friendlier to the reader.

> instances, and can tolerate having the length prefix be three bytes
> long, then one could declare fooSequence as..
>

Yes.  (The latter form might permit an attacker to force a peer to
consume a lot of memory processing a request, of course.)

-Ben