Subject: Re: [CDNi] URI Signing open issues

From: Chris Lemmons <[email-masked]>
Date: Thu, 20 Sep 2018 11:12:52 -0600

So, to follow up on this, I've opened a few PRs, two of which are
relevant and notable:

https://github.com/PSUdaemon/URISigningSpec/pull/48
https://github.com/PSUdaemon/URISigningSpec/pull/49

I believe they solve the outstanding problems I of which I had made
note. POSIX ERE are well specified (maybe even better specified than
PCRE), a mature specification, and are designed intentionally to be
executable with less complexity than BRE or PCRE.

I'm not 100% sold on the path depth parameter, but it does appear to
solve all the use cases I can reasonably divine. And it has the
considerable virtue of being terse. Additionally, as long as you never
renew a cookie with a shorter depth than was provided, it shouldn't
wind up "leaking" into folders it wasn't intended for. (Though even if
it did, it's not a security concern, because the renewal depth is
really just telling the processor how to advise the client which
tokens it should present. The client _can_ present any token and the
processor has to handle it.)
On Thu, Aug 2, 2018 at 7:40 AM Chris Lemmons <[email-masked]> wrote:
>
> 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:
> >
> > 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.