Subject: [CDNi] URI Signing open issues

From: Phil Sorber <[email-masked]>
Date: Fri, 20 Jul 2018 09:04:46 -0700

As a document editor:

These are the open issues remaining:

   - https://github.com/PSUdaemon/URISigningSpec/pull/44
   - https://github.com/PSUdaemon/URISigningSpec/pull/46
   - https://github.com/PSUdaemon/URISigningSpec/pull/47

My hope is to get these resolved soon (~2 weeks) and have a draft pushed
that will be ready to ask the working group about last call.

Thanks.

---

From: Chris Lemmons <[email-masked]>
Date: Mon, 23 Jul 2018 08:38:27 -0600

The CDNI Base claim and its related container solve two specific problems:
 - If you're returning a cookie, you need to know which path, host,
and parameters to provide.
 - It would be really nice not to have to provide the exact same
information twice.

As a bonus:
 - Some basic protection from regex complexity attacks.

My reasoning is this: I need somewhere to put a path and an optional
host. A URI seems the most sane solution, but then you have to get
into how to omit the various parts. I'm definitely open to suggestions
on how this could be handled. Three simple alternatives come to mind:
 - Use a specific delimiter to split the base claim, like colon:
"http:myhost.example.net:/path/to/folder". This looks too much like a
URI to me, when it definitely isn't, but it's admittedly much easier
to parse. Perhaps a different delimiter would help some.
 - Split the claim into three parts: { "cdnibs": "http", "cdnibh":
"myhost.example.net", "cdnibp": "/path/to/folder" }. Three claims
feels too "heavy" in terms of claims-to-importance, but other than
length, it's not much of a downside.
 - Split the claim data into three parts: "cdnib": { "scheme": "http",
"host": "myhost.example.net", "path": "/path/to/folder" }. I like this
the least. All our other claims are strings, and that rather
significantly simplifies implementation.

Once I have a path and possibly a host, I also have what is almost
certainly a limit on where the token will be used. After all, there's
really no reason to pass a path or a host as a limit on the token
renewal if you intend the token to be used elsewhere. (There's a
corner case where you intend the token to access some sort of "root
document" once, but repeatedly request documents from a separate
directory. If this is the use case, though, it can be covered with the
full-strength regex.) For most purposes, it will be enough to simply
limit the token to accessing directories that the cookie allows.
Providing a `b:` container encourages simplicity and significantly
reduces the size of the token when chaining is in use.

The `b:` container allows the token to be much smaller in the common case.

The other issue is this: PCRE is very susceptible to ReDoS attacks.
This attack can be mounted by any attacker in possession of a signing
key. While signers SHOULD take pains to protect their keys, the
reality of the Internet is that bad things do sometimes happen. And
that's separate from the concern that in a self-service environment
where people can configure their own "space" on a CDN, an authorized
user might be malicious.

We could consider going a bit further on the ReDoS protection, though.
What if we switched from PCRE to RE2? Neither one of them is a
documented standard, so it feels slightly strange to require one, but
at least it's possible to implement RE2 such that it returns in time
linear to the input. It is a bit more limited than PCRE, so you don't
get (for example) backreferences. RE2 has several implementations,
including C and C++ bindings, similarly to PCRE. (It's also got
bindings for a bunch of additional languages.)

That leaves us with three important questions:
 - Should we add a Base claim, to support cookies, and if so, what
format should it have?
 - Should we add a `b:` container, to optimize the container when
using chaining?
 - Should we switch from PCRE to RE2 (or similar)?

On Fri, Jul 20, 2018 at 10:05 AM Phil Sorber <[email-masked]> wrote:
> https://github.com/PSUdaemon/URISigningSpec/pull/44
> https://github.com/PSUdaemon/URISigningSpec/pull/46
> https://github.com/PSUdaemon/URISigningSpec/pull/47
>
> My hope is to get these resolved soon (~2 weeks) and have a draft pushed that will be ready to ask the working group about last call.
>
> Thanks.
> _______________________________________________
> CDNi mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cdni

---

From: Phil Sorber <[email-masked]>
Date: Sat, 28 Jul 2018 18:15:58 -0600

>  - Should we add a Base claim, to support cookies, and if so, what

I was hoping for something a little more straight forward, such as a cdnicp
claim that is a string that contains the path element that should be used.

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.

>  - Should we add a `b:` container, to optimize the container when

IMO, no we should not.

>  - Should we switch from PCRE to RE2 (or similar)?

We chose PCRE because it is much better specified than RE2.

See:

https://www.pcre.org/original/doc/html/pcrepattern.html

vs

https://github.com/google/re2/wiki/Syntax

The choice was more about the language than the implementation. You can use
RE2 as an implementer if you wanted to. It wouldn't support backreferences
and look arounds, but it would work in 99% of the cases needed to implement
the draft. PCRE also has a DFA mode, which i believe addresses your
concerns.

It's probably worth a mention in the security considerations section of the
draft to say that you should be careful with what regex's you allow and
that eliminating specific features like backreferences for security would
be within the spirit of the draft.

---

From: Chris Lemmons <[email-masked]>
Date: Sun, 29 Jul 2018 16:41:26 -0600

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

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.

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

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.

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?

---

From: Phil Sorber <[email-masked]>
Date: Mon, 30 Jul 2018 12:36:02 -0600

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.

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

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

> 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: Mon, 30 Jul 2018 16:31:44 -0600

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

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:
> 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.
>
>>
>>
> It was not intended for implementers of the spec to implement their own Regular Expression library.