Subject: [Cellar] Security considerations: recursive elements

From: Michael Bradshaw <[email-masked]>
Date: Wed, 17 Jan 2018 12:33:17 -0800

The EBML and Matroska specs currently don't mention the possibility of a
stack overflow due to deeply nested recursive elements. Currently, there's
no limit on the recursion depth (unless I've overlooked it somewhere).

I think it would be worth adding to the security section of EBML that one
type of attack on an EBML Reader could include deep element recursion.

Additionally, I would like to see what people think about potentially
adding/suggesting an upper limit on recursion (either as a MUST or a MAY).
This could also include a lower limit too. For example, something like "a
parser SHOULD handle recursion up to X levels deep, and MAY abort the parse
if it reaches Y levels deep".

Thoughts from others?

---

From: Ashley Blewer <[email-masked]>
Date: Wed, 17 Jan 2018 15:38:51 -0500

I agree with this. +1

On Wed, Jan 17, 2018 at 3:33 PM, Michael Bradshaw <[email-masked]>
wrote:

> _______________________________________________
> Cellar mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cellar
>
>

---

From: Reto Kromer <[email-masked]>
Date: Wed, 17 Jan 2018 21:55:50 +0100

Michael Bradshaw wrote:

>Additionally, I would like to see what people think about
>potentially adding/suggesting an upper limit on recursion
>(either as a MUST or a MAY).

I don't think that a MUST is appropriate here.

Best regards, Reto

---

From: Jerome Martinez <[email-masked]>
Date: Wed, 17 Jan 2018 22:01:41 +0100

On 17/01/2018 21:33, Michael Bradshaw wrote:
> [...]
>
> For example, something like "a parser SHOULD handle recursion up to X 
> levels deep, and MAY abort the parse if it reaches Y levels deep".
>
> Thoughts from others?

an EBML parser can not dig in nested element without the corresponding 
dictionary (from DocType).
So IMO it is not like XML or JSON, because XML or JSON parser tries to 
read the nested elements, but n EBML parser does not try to read any 
element not in the dictionary (so the limit is the dictionary, usually 
can not be provided by the attacker.
It is lie JSON or XML only if the attacker can provide the dictionary.

And the JSON spec specifies no limit:
https://tools.ietf.org/html/rfc7159#section-9
"An implementation may set limits on the maximum depth of nesting"

There may be legitimate reason to have thousands of nesting level, and 
there is already a lot of debates about that with JSON (last tests I saw 
about that is ~100 levels for Ruby JSON default parser and ~1000 levels 
for Python JSON parser)

So the sentence should split security issues, from the input (the file 
itself) or the dictionary (e.g. matroska specs):
- a generic parser (reading the dictionary from input) MAY set limits on 
the maximum depth of nesting. An implementation MAY set limits on the 
length and contents.
- a specialized parser (e.g. Matroska parser) SHOULD handle recursion up 
to the maximum nesting level provided by the supported dictionary of the 
document, or 2 nesting levels, whichever is smaller (a specialized 
format could have only 1 nesting level but EBML needs at least 2, for 
DocType etc...). An alternative is to say to rely on the supported 
format security paragraph.

I am not in favor of writing a number, because there is no good number 
to provide, it depends too much of the content, I am in favor of doing 
like JSON sentences (without any number, but explicitly saying that 
limits are expected).
I hesitate in writing such kind of text in a "parser" section instead of 
security section, like the JSON RFC does.

---

From: Reto Kromer <[email-masked]>
Date: Wed, 17 Jan 2018 22:09:25 +0100

Jerome Martinez wrote:

>I am not in favor of writing a number, because there is no good
>number to provide,

Me neither.

>I hesitate in writing such kind of text in a "parser" section
>instead of security section, like the JSON RFC does.

I would suggest in the parser section.

Best regards, Reto

---

From: Michael Niedermayer <[email-masked]>
Date: Wed, 17 Jan 2018 23:31:56 +0100

> if it reaches Y levels deep".

If a limit is specified then theres a limit that every compliant parser
must support and which a compliant muxer can use.

If no such limit is specified then it is possible that in a system where
all parts are specification compliant and otherwise compatible it doesnt work.

So I think its more a question about what/when compatibility is guranteed
/ what compatibility we want the specification to gurantee
from that it follows if we need a limit in the specification/draft or not

[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

If a bugfix only changes things apparently unrelated to the bug with no
further explanation, that is a good sign that the bugfix is wrong.

---

From: Michael Bradshaw <[email-masked]>
Date: Wed, 17 Jan 2018 14:47:35 -0800

Thanks for the responses, all!

I agree that setting minimum/maximum recursion limits doesn't belong in the
EBML spec. I do think the EBML spec should have a note in the Security
Considerations that EBML Readers need to be cognizant of how they handle
recursive elements and should be resilient to deeply nested recursion
attacks (without giving particular recommendations for how that resilience
is achieved). But EBML itself shouldn't attempt to set any specific limits
on recursion depth.

The reason I suggested setting some kind of minimum/maximum recursion depth
(for Matroska specifically, not for EBML in general) is because of the
points Michael Niedermayer raises. Setting a minimum allows muxers to write
files with confidence that readers will be able to use/play the data being
written (so long as the minimum isn't exceeded). Setting a maximum let's
muxers know that if they exceed it, they run the risk of making a file that
some readers can't (fully) play.

Specifying recursion limits using the example language in my first email
("a parser SHOULD handle recursion up to X levels deep, and MAY abort the
parse if it reaches Y levels deep") for ChapterAtom and SimpleTag elements
would allow a muxing program to emit a warning to the user if the recursion
level exceeded Y (it's not a fatal error, but it would be nice to let the
user know their file has abnormally deep recursion that might not be
compatible with various parsers).

On Wed, Jan 17, 2018 at 2:31 PM, Michael Niedermayer <[email-masked]

---

From: Jerome Martinez <[email-masked]>
Date: Thu, 18 Jan 2018 08:42:42 +0100

On 17/01/2018 23:47, Michael Bradshaw wrote:
> I agree that setting minimum/maximum recursion limits doesn't belong 
> in the EBML spec. I do think the EBML spec should have a note in the 
> Security Considerations that EBML Readers need to be cognizant of how 
> they handle recursive elements

I missed the case of recursive elements, specified in EBML.
for a security section, I don't think that talking about a parser is 
right, reading https://tools.ietf.org/html/rfc3552 it seems to more 
about usage of the correct behavior of a protocol rather than badly 
implemented parser, I am more in favor of  something like "it is 
possible to have unlimited recursion, potential source of denial of 
service attacks" in security section and
"An implementation may set limits on the maximum depth of nesting" in a 
parser section (similar to JSON RFC).

> and should be resilient to deeply nested recursion attacks (without 
> giving particular recommendations for how that resilience is 
> achieved). But EBML itself shouldn't attempt to set any specific 
> limits on recursion depth.
>
> The reason I suggested setting some kind of minimum/maximum recursion 
> depth (for Matroska specifically, not for EBML in general) is because 
> of the points Michael Niedermayer raises. Setting a minimum allows 
> muxers to write files with confidence that readers will be able to 
> use/play the data being written (so long as the minimum isn't exceeded).

We don't talk anymore about security, and confidence depends on the 
underlying document e.g. for my EBML document x, I may need only 1 level 
beside the EBML header and it is fine with that, no need of more.
So:
- A minimum should not be in Security section (it is not about security)
- A minimum depends on the goal of the parser, e.g. a parser just 
checking top level element size and CRC for checking a file transfer is 
fine does not need more than 2 levels. Not all tools are video players.

> Setting a maximum let's muxers know that if they exceed it, they run 
> the risk of making a file that some readers can't (fully) play.

As far as I know, there is nothing mandatory: tags are not mandatory, a 
specific stream format is not mandatory, it would be a full new part if 
we say what a reader should play, with lot of debates (chapters 
mandatory? tags display mandatory? FFV1 mandatory? H.265 and its 
royalties mandatory? NTSC only or 8K? Subtitles support mandatory? color 
description mandatory? maximum length of a text in a tag? can we have a 
gap in streams?).
IMO we talk about a file format and not about what a reader expects to 
fully play.

>
> Specifying recursion limits using the example language in my first 
> email ("a parser SHOULD handle recursion up to X levels deep, and MAY 
> abort the parse if it reaches Y levels deep") for ChapterAtom and 
> SimpleTag elements would allow a muxing program to emit a warning to 
> the user if the recursion level exceeded Y (it's not a fatal error, 
> but it would be nice to let the user know their file has abnormally 
> deep recursion that might not be compatible with various parsers).

But a player may just ignore any chapter and tag elements and still play 
fine the file.
IMO expected supported elements of Matroska is a different document 
(e.g. a document about a reader capability? I usually see that with a 
"format compliance program", having lot of sample files), not in format 
description which is more general and does not say what element is 
mandatory, just how to store it.
I don't say that it is a bad idea, just that I don't think that saying 
minimal requirements or warnings about potentially unsupported nesting 
level should be in a bitstream specification permitting lot of optional 
parts.

Jérôme

---

From: Reto Kromer <[email-masked]>
Date: Thu, 18 Jan 2018 09:22:31 +0100

Michael Bradshaw wrote:

>Setting a maximum
>let's muxers know that if they exceed it, they run the risk of
>making a file that some readers can't (fully) play.

Sorry, I do not support the idea of fixing a maximum value here,
because, in my opinion, it's an useless limitation.

Best regards, Reto

---

From: Reto Kromer <[email-masked]>
Date: Thu, 18 Jan 2018 09:24:30 +0100

Jerome Martinez wrote:

>"An implementation may set limits on the maximum depth of
>nesting" in a parser section (similar to JSON RFC).

I agree, this is up to the single implementations.

>- A minimum depends on the goal of the parser, 

I strongly agree!

Best regards, Reto

---

From: Dave Rice <[email-masked]>
Date: Thu, 18 Jan 2018 09:26:57 -0500

> On Jan 18, 2018, at 3:22 AM, Reto Kromer <[email-masked]> wrote:
> 
> Michael Bradshaw wrote:
> 
>> Setting a maximum

Since Matroska uses an EBMLMaxSizeLength of 8, then after reserving space for the other required elements, then it’s feasible to have a valid Matroska file with a recursive Chapter Atom Element to the depth of 36,028,797,018,963,944. But Chapter Atom recursion to 36,028,797,018,963,945 is not possible in Matroska (maybe try another container for this requirement).
Dave Rice

---

From: "Peter B." <[email-masked]>
Date: Thu, 18 Jan 2018 16:41:21 +0100

> I agree, this is up to the single implementations.

Could it be useful to suggest (not define) a "reasonable" value for max
nesting depth there, instead of just saying it "could be limited by an
implementation"?

This might reduce implementation-specific interoperability fluctuations,
I guess.

Just an idea...
Pb

---

From: Michael Bradshaw <[email-masked]>
Date: Thu, 18 Jan 2018 09:53:12 -0800

On Wed, Jan 17, 2018 at 11:42 PM, Jerome Martinez <[email-masked]>
wrote:
> for a security section, I don't think that talking about a parser is right

The current EBML specification's Security Consideration section contains a
bulleted list for "Attacks on an EBML Reader" (where an "EBML Reader" is
explicitly defined as a "data parser[...]"). So if we shouldn't be talking
about security considerations for parsers, then that whole bulleted list
should be removed (which I'm opposed to doing). Perhaps I've misunderstood
your point here, though.

I am more in favor of  something like "it is possible to have unlimited
> recursion, potential source of denial of service attacks" in security
> section and

My apologies if my previous communications have been unclear, but this is
actually what I'm trying to advocate for, so I think we might agree more
than we realize. While I have been suggesting including minimum/maximum
levels, I think that using something like you've written here (and
completely omitting minimum/maximums) would still be a great improvement.

I do think that also including some kind of minimum/maximum levels could be
useful. I also think that if we do have them, they should use SHOULD/MAY
language instead of MUST. Using SHOULD/MAY would give guidance to
implementors on how they can maximize interoperability while still allowing
them total freedom (the implementation would still be conforming to the
spec even if it went against a SHOULD/MAY guidance).

> - A minimum should not be in Security section (it is not about security)

I agree that minimum or even maximum limits should not be placed in the
security section. They belong elsewhere in the Matroska specification
(exactly which section, I don't know). Sorry for not stating this more
clearly in my original email.

- A minimum depends on the goal of the parser, e.g. a parser just checking
> top level element size and CRC for checking a file transfer is fine does
> not need more than 2 levels. Not all tools are video players.

I'm not advocating for HOW the parsers should handle deep recursion (I
probably shouldn't have used the language "abort the parse" in my original
email; it was just meant to be a starting point for the conversation).
Handling it by skipping it is fine. If a particular element is not needed
for the goals of the application, the parser should certainly feel at
liberty to skip over it.

> fine the file.

Yes, the encoded media data can still be parsed/decoded and the media can
still be played. But part of playing a video is showing to the user the
chapter and tag information to the video. If the player ignores the chapter
or tag elements, then the playback experience is incomplete. Not all
players utilize the chapter and tag elements, but those that do will likely
have some kind of upper limit on the level of recursion they can
meaningfully handle.

---

From: Steve Lhomme <[email-masked]>
Date: Sun, 21 Jan 2018 18:10:59 +0100

(starting to reply from the bottom of the thread)

> should be removed (which I'm opposed to doing). Perhaps I've misunderstood

I agree with Michael, this is a legitimate attack and it should be
mentioned. Putting limits is a different topic that would probably go
in a different section of the specs.

> them total freedom (the implementation would still be conforming to the spec
> even if it went against a SHOULD/MAY guidance).

I agree with that too. EBMLMaxSizeLength was mentioned in the thread
and it would make sense to make a recursion limit per file in the EBML
header. That would let parsers know if they can handle the file or not
in advance and/or detect security attacks.

We could either have a default value for that element or none which
means there's no de-facto maximum.

It also not be an element but something more complex, since the amount
of recursion allowed may differ between elements (see nested tags vs
nested chapters). But it may be easier for the reader and the writer
to have only one limit for all.

In any case a default maximum valu would belong in the Matroska
specifications, not the EBML ones.

> clearly in my original email.

We all agree.

>> top level element size and CRC for checking a file transfer is fine does not
>> need more than 2 levels. Not all tools are video players.
>
>

Not if the ordered chapters are truncated by enforcing a bogus maximum.

> or tag elements, then the playback experience is incomplete. Not all players
> utilize the chapter and tag elements, but those that do will likely have
> some kind of upper limit on the level of recursion they can meaningfully
> handle.
>

-- 
Steve Lhomme
Matroska association Chairman

---

From: Steve Lhomme <[email-masked]>
Date: Sun, 21 Jan 2018 18:15:36 +0100

> some readers can't (fully) play.

On the writer's side it's easier to know the maximum depth it reached
when writing a particular file and write the exact maximum value at
the end of the muxing. Security-wise it's stricter than a loose
default maximum.

> Specifying recursion limits using the example language in my first email ("a
> if it reaches Y levels deep") for ChapterAtom and SimpleTag elements would
> allow a muxing program to emit a warning to the user if the recursion level
> exceeded Y (it's not a fatal error, but it would be nice to let the user
> know their file has abnormally deep recursion that might not be compatible
> with various parsers).
>
> On Wed, Jan 17, 2018 at 2:31 PM, Michael Niedermayer
> <[email-masked]> wrote:
>>

---

From: Steve Lhomme <[email-masked]>
Date: Sun, 21 Jan 2018 18:19:20 +0100

> must support and which a compliant muxer can use.

IMO it should be per-file and not mandatory (ie no default max).

> from that it follows if we need a limit in the specification/draft or not

IMO it should be left to the parser to know what to do. The thing it
knows is that there's something wrong with the depth of the file and
may decide not to go deeper than the limit or issue a warning to the
user or ask if the extra parsing should be done.

All the specs have to say is that the maximum depth indicate the EBML
depth the file should not go further from. Emphasis on the SHOULD.

---

From: Steve Lhomme <[email-masked]>
Date: Sun, 21 Jan 2018 18:22:35 +0100

2018-01-17 22:01 GMT+01:00 Jerome Martinez <[email-masked]>:
> So IMO it is not like XML or JSON, because XML or JSON parser tries to read
> the nested elements, but n EBML parser does not try to read any element not
> in the dictionary (so the limit is the dictionary, usually can not be
> provided by the attacker.
> There may be legitimate reason to have thousands of nesting level, and there
> is already a lot of debates about that with JSON (last tests I saw about
> that is ~100 levels for Ruby JSON default parser and ~1000 levels for Python
> JSON parser)
>
> - a generic parser (reading the dictionary from input) MAY set limits on the
> maximum depth of nesting. An implementation MAY set limits on the length and
> contents.

Yes, we need an element to specify that.

> - a specialized parser (e.g. Matroska parser) SHOULD handle recursion up to
> the maximum nesting level provided by the supported dictionary of the

Yes, and going further is left to implementation.

Parsers will need to handle the case where the element is not defined
too. So they can fallback to the rule in case the maximum is reached.

> document, or 2 nesting levels, whichever is smaller (a specialized format
> could have only 1 nesting level but EBML needs at least 2, for DocType
> etc...). An alternative is to say to rely on the supported format security
> paragraph.
>
> I am not in favor of writing a number, because there is no good number to
> provide, it depends too much of the content, I am in favor of doing like
> JSON sentences (without any number, but explicitly saying that limits are
> expected).

---

From: Luca Barbato <[email-masked]>
Date: Sun, 21 Jan 2018 18:40:21 +0100

> depth the file should not go further from. Emphasis on the SHOULD.

+1

---

From: hubblec4 <[email-masked]>
Date: Thu, 1 Feb 2018 01:52:59 +0100

Hi all

Late, but I also say yes, we need such an element for the maximum depth 
of nesting.

Am 21.01.2018 um 18:10 schrieb Steve Lhomme:
>>> right
Yes only one element is enough. We have only 2 nested elements and in 
pratice almost the top-level is used.
In the specs are nested Tags as an example present, but I have never 
seen an mkv in practice.
Nested chapters with a first lower level are used in practice.
The Matroska DVD-Menu system uses nested chapters and maximum of levels 
is 7.
(Each level of a chapter corresponds to a logical level in the DVD system)

I prefer an element in the Matroska header which is mandatory WITH an 
default value.
Why mandatory?
While I write my own Matroska parser it is every easy to have a 
mandatory element.
And with a default value the element can be omitted but in my program I 
have every time a valid "init"-value.
The default vaule can be 7.
All existing Matroska files without this new element could be handled 
safely.

>>> checking
Ordered chapters are used in top-level chapters only (expect VLC, with 
Matroska DVD-Menu system), so the file should play fine.

>> players