Subject: Re: [CDNi] URI Signing open issues

From: Phil Sorber <[email-masked]>
Date: Wed, 1 Aug 2018 20:28:20 -0600

On Mon, Jul 30, 2018 at 4:32 PM Chris Lemmons <[email-masked]> wrote:

> > The host shouldn't be specified upstream.
>
> I can buy this argument. I can think of some strange CDN
> architectures, but none that really justify adding complexity here. I
> think I agree that path is sufficient. What about the "Secure" flag?
> An implementation may wish to require that renewals happen over https.
> For example, if the initial signature is handed out via TLS and the
> renewal is always handled over HTTP, leakage of the URI is much less
> likely to happen without the intervention of the client. Without the
> flag, it's acceptable to switch to http after having started with an
> https connection. The signer is likely to "prohibit" this if
> neccessary by putting "https" in the regex. But there's no way for the
> cookie-maker to know that.
>
> Is it possible that we're simply making this way too hard? I dislike
> the duplication, but a claim that looked like: "cdnicp":
> "Path=/foo/bar/baz; Domain=special.example.com; Secure" would be
> infinitely flexible and dead simple to implement. Signers should have
> sufficient information to fill it out (usually, by leaving the
> "Domain" off, as you have mentioned). And it's forward compatible, so
> if browsers start supporting some fancy new parameter in the future,
> signers can start putting it in the cookies. But it's cookie-specific
> and duplicates the path.
>
> > I was recently pointed to the POSIX standard
>
> Yeah, I almost suggested POSIX BREs or EREs for the format.
> Unfortunately, even the BREs are susceptible to catastrophic
> backtracking. BREs support backreferences, and backreferences require
> a backtracking solution. There's a useful discussion here:
> https://swtch.com/~rsc/regexp/regexp2.html. Look at "Digression: POSIX
> Submatching".
>
> > We cannot specify a library for implementers. [...] It was not intended
> for implementers of the spec to implement their own Regular Expression
> library.
>
> Right. We're not picking one, but we probably shouldn't pick something
> that doesn't have any implementations. BRE, ERE, RE2, and PCRE all
> meet that requirement.
>

And what about section 2.13 Pattern Matching Notation?

>
> I like the specification for BREs the best. It's well specified and it
> feels possible to implement it. Unfortunately, it cannot be
> implemented in linear time as it stands. However, I believe
> backreferences are the only feature of BREs that cannot. There does
> exist at least one implementation of [BE]RE that allows the detection
> of backreferences and allows you to exclude them as well as running in
> time linear on the input ( https://github.com/laurikari/tre ). There
> may be others.
>
> Is there a specific use-case for backreferences in the urls? I can
> kinda guess at something like: http://[^/]*/code/(foo|bar|baz)/\1.[ch]
> . That would prohibit something like http://example.com/code/foo/bar.h
> from matching. I like flexibility wherever possible, but I think the
> cost here is too high.
>
> On Mon, Jul 30, 2018 at 12:36 PM Phil Sorber <[email-masked]> wrote:
> >
> > On Sun, Jul 29, 2018 at 10:42 PM Chris Lemmons <[email-masked]>
> wrote:
> >>
> >> > Perhaps we could also offer a path depth. cdnicpd that is an integer
> of the directory depth to use of the actual resource being requested. So
> for example:
> >> >
> >> > http://cdni.example/foo/bar/baz/movie/fragments/1.ts
> >> >
> >> > and a cdnicpd of 4 would give you a cookie path of /foo/bar/baz/movie.
> >>
> >> Interesting. So the target path would depend on the presenter of the
> >> token, not the signer? That seems backward to me, but since the signer
> >> has control of the possible valid options, it might work. So, if I
> >> understand, a token with depth of 2 and a regex of
> >> "https?://[^/]*/(foo|bar)/movies/.*" applied to
> >> "http://host.example.com/foo/movies/a" would renew at
> >> "Path=/foo/movies". And "http://host.example.com/bar/movies/b" would
> >> renew at "Path=/bar/movies".
> >>
> >> I don't like the idea that the token doesn't renew at the same path
> >> each time. And it's strange to support "multiple entry points" like
> >> this, but then limit it to entry points at the same depth. It also
> >> doesn't let us know what host to use for renewal.
> >>
> >> Spitballing a bit, but what if we used capture groups in the regex to
> >> supply the data? That has the advantage of not requiring any
> >> additional claims, but the disadvantage of not working for any
> >> container except regex. (But practically speaking, regex is probably
> >> the only choice for token renewal, unless it's repeated access to a
> >> single resource.
> >>
> >> You could say
> "https?://(?P<h>[^/:])(:[0-9]*)?/(?P<p>(/premium/channel[1-4]|/free)/.*"
> >> and it would pull out the "h" and "p" components for the renewal. It
> >> makes the regex much less comprehensible, though. And regexen really
> >> doesn't need that. :/
> >>
> >> Any solution to the target path problem needs to support at least
> >> specifying the host and the path. And it would be nice if it also
> >> specified the "secure" parameter by some mechanism, for those who wish
> >> to require that tokens be presented over encrypted connections.
> >
> >
> > The host shouldn't be specified upstream. If you are redirecting to a
> cache with a host name that the uCDN can't poissibly know, that would be
> problematic.
> >
> > I feel like a lot of this is on the dCDN to interact with the client. It
> knows it's architecture, and it should do what it needs to to make the
> signalling work. I think the path is important information from the uCDN
> because it's essentially information about the content that the dCDN
> doesn't have. I think you are over complicating this issue.
> >
> >>
> >>
> >> > We chose PCRE because it is much better specified than RE2.
> >>
> >> I totally get that. Neither of them is really specified in sufficient
> >> detail, imo. But PCRE certainly uses more words. RE2 mostly relies on
> >> the reader knowing what things do in PCRE, which isn't really great.
> >>
> >> > You can use RE2 as an implementer if you wanted to.
> >>
> >> No, I really can't. The draft as it stands requires that you implement
> >>
> >> the whole thing. And it wouldn't be sufficient to change the draft
> >> since unadvertised interop issues would inevitably arise. The point of
> >> having a spec that describes URI Signing is to allow interop between
> >> parties without requiring that they pre-negotiate which components
> >> will be supported. And while it's possible that some of the claims
> >> won't be processible by all compliant CDNs, it would significantly
> >> hamper implementations if they have to negotiate what subset of PCRE
> >> is acceptable.
> >>
> >> >  PCRE also has a DFA mode, which i believe addresses your concerns.
> >>
> >> Same problem here. A token signer can't reasonably guess what dialect
> >> of PCRE is going to be used to interpret the regex. Every regex should
> >> be processed by every CDN in the same way. Failing to do this has
> >> security concerns, since uris that may not be intended to match can
> >> and those that are intended to match may not.
> >
> >
> > There is always going to be some amount of integration issues that both
> a uCDN and dCDN will need to work out.
> >
> >>
> >>
> >> Given that we need to have a single, documented dialect of a regex,
> >> we're mostly picking a mandatory library for implementers. It's worth
> >> considering that as well.
> >
> >
> > I disagree. We cannot specify a library for implementers. That simply
> won't pass muster.
> >
> > I was recently pointed to the POSIX standard that has both a basic glob
> pattern matching (IEEE 1003.1-2017 sec 2.13) and a more robust regular
> expression pattern matching (IEEE 1003.1-2017 sec 9).
> >
> > We removed a URI Pattern Match that is similar to the sec 2.13 version
> because we didn't want to re-invent the wheel poorly. Section 2.13 is the
> spec for the wheel so maybe we should reconsider that approach and just use
> that.
> >
> >>
> >>
> >> If we require PCRE without mitigation, we're building the ReDoS attacks
> in.
> >>
> >> Is the purpose of picking PCRE that it's better specified and
> >> therefore easier for implementers to build their own implementations?
> >> Or that it's better documented for users to write regexes that match?
> >
> >
> > It was not intended for implementers of the spec to implement their own
> Regular Expression library.
>

---

From: Chris Lemmons <[email-masked]>
Date: Thu, 2 Aug 2018 07:40:44 -0600

Pattern matching is an interesting option there, but probably too
limited. Either you incorporate the restrictions in 2.13.3, in order
to limit the glob so it does not match '/': http://example.com/foo/*
does not match http://example.com/foo/bar/baz. Or you don't
incorporate them and stick with 2.13.2, so that
http://example.com/foo/*.ts matches
http://example.com/foo/secretplace/secrets.xml#nowhere.ts. Also, if
you incorporate the file restrictions, you get weird stuff like
requiring read privileges on a uri, which doesn't make a whole lot of
sense. I guess you could try to add your own restrictions in a similar
section. Something like: glob doesn't match '/', unless it occurs at
the end of a pattern. But then you're firmly in "bespoke pattern
matching" territory.

Looking at all the options, so far, the only two options that meet the
criteria I think we need are RE2 and ERE. Of those, the ERE is the
most well specified. Additionally, EREs don't support backreferences
(though implementers should beware, some libraries appear to support
them as an extension) and are implementable in time bounded linearly
on the input. (And compile in time quadratic to the regex... I think.)
Would ERE work for the regexes?
On Wed, Aug 1, 2018 at 8:28 PM Phil Sorber <[email-masked]> wrote:
>> > We cannot specify a library for implementers. [...] It was not intended for implementers of the spec to implement their own Regular Expression library.
>>
>> > On Sun, Jul 29, 2018 at 10:42 PM Chris Lemmons <[email-masked]> wrote:
>> >>
>> >> > Perhaps we could also offer a path depth. cdnicpd that is an integer of the directory depth to use of the actual resource being requested. So for example:
>> >> >
>> >> You could say "https?://(?P<h>[^/:])(:[0-9]*)?/(?P<p>(/premium/channel[1-4]|/free)/.*"
>> > The host shouldn't be specified upstream. If you are redirecting to a cache with a host name that the uCDN can't poissibly know, that would be problematic.
>> >
>> > I feel like a lot of this is on the dCDN to interact with the client. It knows it's architecture, and it should do what it needs to to make the signalling work. I think the path is important information from the uCDN because it's essentially information about the content that the dCDN doesn't have. I think you are over complicating this issue.
>> >
>> >>
>> >>
>> > There is always going to be some amount of integration issues that both a uCDN and dCDN will need to work out.
>> >
>> >>
>> >>
>> > I disagree. We cannot specify a library for implementers. That simply won't pass muster.
>> >
>> > I was recently pointed to the POSIX standard that has both a basic glob pattern matching (IEEE 1003.1-2017 sec 2.13) and a more robust regular expression pattern matching (IEEE 1003.1-2017 sec 9).
>> >
>> > We removed a URI Pattern Match that is similar to the sec 2.13 version because we didn't want to re-invent the wheel poorly. Section 2.13 is the spec for the wheel so maybe we should reconsider that approach and just use that.
>> >
>> >>
>> >>
>> >> If we require PCRE without mitigation, we're building the ReDoS attacks in.
>> >>
>> > It was not intended for implementers of the spec to implement their own Regular Expression library.