Adding some addition information here that was part of an email discussion which led to the bug report.

The current suspicion is that parenthesis are reserved characters in a URL and should have been percent-encoded, more on that in a moment.

The URL  http://10.65.8.143:1080/private/test(test).txt was entered in the browser's URL bar.

If the parenthesis need to be escaped who is responsible? The question arose did the browser percent-encode prior to generating the HTTP protocol request? Below are entries from the access log, note the parenthesis are not escaped when received by Apache. When mellon does a redirect to it's login handler it has escaped the parenthesis. 

10.65.193.22 - - [01/Jun/2017:20:03:00 +0530] "GET /private/test(test).txt HTTP/1.1" 303 464 "-" "Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Firefox/52.0"
10.65.193.22 - - [01/Jun/2017:20:03:00 +0530] "GET /mellon/login?ReturnTo=http%3A%2F%2F10.65.8.143%3A1080%2Fprivate%2Ftest%28test%29.txt&IdP=http%3A%2F%2F10.65.8.143%3A8080%2Fauth%2Frealms%2FAuth_Mellon HTTP/1.1" 303 1385 "-" "Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Firefox/52.0

The RelayState query parameter transmitted in the AuthnRequest to the IdP is this:

RelayState=3Dhttp%3A%2F%2F10.65.8.143%3A1080%2Fprivate%2Ftest(test).txt 

The presence of the unescaped parenthesis is apparently what is causing the invalid RelayState exception as seen in Keycloak.

One question we have to get to the bottom of is whether parenthesis are reserved characters in an HTTP URI scheme. Initial investigation by myself suggests parenthesis were *not* reserved in the early RFC's. However it does appear they were added to the reserved character set in rfc 3986 (January 2005).

If I'm reading the RFC's correctly one cannot just look at an RFC for URI's because scheme specific (e.g. HTTP) RFC's can add additional constraints on the format of a URI.

So the first order of business is to nail down exactly the RFC requirements. It is possible what we are seeing are different software components are operating with different notions of what the reserved character set is, but that is just a suspicion at the moment.

Created attachment 1284437 [details]
keycloak stack trace

Stack trace from keycloak when it thows an exception on the RelayState parameter.

If we need to identify the Java component which is analyzing the URL for validity and how that validity check is being performed we can probably identify it from this stack trace.

Adding some notes during debug analysis

in the function am_init_authn_request_common()
the return_to_url="https://jdennis-test.example.com/saml-test/test(test).txt"

this is then copied into the lasso login msg_relayState
LASSO_PROFILE(login)->msg_relayState = g_strdup(return_to_url);

Thus login->msg_relayState is identical to return_to_url

Then mellon calls

lasso_login_build_authn_request_msg(login)

Which builds the message according to the SAML binding which is in this case HTTP_Redirect, hence the message is embedded in the login->msg_url which is what we send to the IdP (e.g. RH-SSO). The msg_url that 
lasso_login_build_authn_request_msg() build is this:

https://jdennis-rhsso-7/auth/realms/test_realm/protocol/saml?SAMLRequest=jZJbSwMxEIX%2FypL3bXa3NxvaQu22UKgi9fLgSwnbkUY2yZqZ9fLvnWxRFEF9SpjMyZnvMFPUtm7UoqWj28FTC0jJq60dqu5hJtrglNdoUDltARVV6npxsVVFL1NN8OQrX4svkt8VGhECGe9EsilnYl8sz5erQTGZ9MfrSbkuzsejcjCa5PmKj36Zi%2BQOAnL%2FTLCcRYgtbBySdsSlLB%2Bn2Sgtspt8qIqhys7uRVIyg3GaOtWRqEEl5eMBnDOYhiOiT8dSM7AMoGuLkliw7%2B7yg0hGFJEsvUOITr8xVacmVbUh8Jka29SmMiSStQ8VdNHOxIOuESLAFWdgnuGzsviIJJq1FsI1hGdTwe1u%2B3P8OGoPXjVbQK%2FyVlqoa%2B9k45F2gE0cRcyncXrVZRXm%2F%2F3CAumDJj2VX9XT035cMvWmvPIM9haxrP4jlFgxh%2FSha1UUtEPD4TAum70sOW3iCCi0IOT8ZPl9C%2Bfv&RelayState=https%3A%2F%2Fjdennis-test.example.com%2Fsaml-test%2Ftest(test).txt&SigAlg=http%3A%2F%2Fwww.w3.org%2F2000%2F09%2Fxmldsig%23rsa-sha1&Signature=eSaajIat4sXBx9Tt%2Fp%2Bt9VtPgO1v1vitamshKPp42HjhbL%2F%2BY3gOsGA4ii4P3Sk%2FZe3ODwL22EEwvs4QnZ3T%2FjsJlw1CXNTZ5BQ8AHpuyt1GZBJytMasNfB%2BpUAI5kHdMjAFamZGWdVC9c4EnoYz9qNoFxOPN4XAOH7hyBXr4IybLbWtpS32iwR20Xf%2FRdtUXgm2DIO1ESQmcDTW9GaxMqzL7NFCp2IHBKAFSaWjE9Y82PEooQZLIKdsKgSgATJaazcp5ogKNYhEapRM0S7tFE3XjBSB4vu8pedI49l3zvDuT6OPp0QPYL3kdn2wRJMcblOYSUJLAHW9vB1wqNaCCA%3D%3D

Note it contains the following query parameter:

&RelayState=https%3A%2F%2Fjdennis-test.example.com%2Fsaml-test%2Ftest(test).txt

Which we believe is what is causing RH-SSO to reject the message due to the unescaped parenthesis.

Therefore the problem with escaping appears to be in the lasso library during the execution of the function lasso_login_build_authn_request_msg(login)

The call chain to the point where the RelayState is encoded as a URL query parameters is:

lasso_login_build_authn_request_msg
lasso_saml20_login_build_authn_request_msg
lasso_saml20_profile_build_request_msg
lasso_saml20_profile_build_redirect_request_msg
lasso_saml20_profile_build_http_redirect


which executes with this code:

unsigned_query = lasso_url_add_parameters(unsigned_query, 1, "RelayState",
			profile->msg_relayState, NULL);

and lasso_url_add_parameters() executes with this code:

	encoded_value = xmlURIEscapeStr((xmlChar*)value, NULL);

Thus the URI encoding of the RelayState is being performed with the call xmlURIEscapeStr() from libxml2

If I pre escape the URL by substituting %28 and %29 for the parens or remove the parens from the URL RH-SSO accepts the message.

Therefore I conclude xmlURIEscapeStr() is the culprit.

To further confirm xmlURIEscapeStr() is misbehaving I wrote this little test program in C called uri.c

// gcc -o uri.c uri -I /usr/include/libxml2 -lxml2
#include "stdio.h"
#include <libxml/uri.h>

int
main(int argc, char **argv) {
    xmlChar *uri = "http://10.65.8.143:1080/private/test(test).txt";
    xmlChar *escaped = NULL;

    escaped = xmlURIEscapeStr(uri, NULL);
    printf("escaped=%s\n", escaped);
}

And it emits this:

escaped=http%3A%2F%2F10.65.8.143%3A1080%2Fprivate%2Ftest(test).txt

So indeed xmlURIEscapeStr() is failing to escape the parens.

xmlURIEscapeStr is implemented in libxml2/uri.c which states it is
implementing RFC 2396 and indeed the code in uri.c looks identical to the logic outlined in RFC 2396.

But RFC 2396 dates back to 1998, nearly 2 decades ago.

RFC 2396 was obsoleted by RFC 3986 in 2005, 12 years ago.

RFC 3986 among other things added parens to the reserved character set in URI's, see section 2.2.

As far as I can tell the problem is located in libxml2's xmlURIEscapeStr() which is not following a 12 year old RFC (3986).

Reassigning this to libxml2.

Not sure why this got assigned to Daniel, John is the correct person to deal with mod_auth_mellon bugs (CCed).

and doh, I should have read the whole thread first ...

Opened an upstream bug with a proposed patch:
https://bugzilla.gnome.org/show_bug.cgi?id=784894

This would require us to change lasso to use this new function, or to import a variant of this function in lasso under a configure test until we can rebase libxml2.

Sorry I had no time to volunteer work on this.
John do you think you could take it ?

No problem, it's already in my queue. Thanks for your initial work.

I tried to fix libxml2 to be compliant with RFC 3986 and in the process realized parenthesis in a query component do not need to be escaped. Section 2.2 of that spec defines the set of reserved characters which includes parenthesis. But reserved characters is a general overarching concept. The escaping rules apply to specific parts of a URI, you really have to read the "Collected ABNF for URI" in Appendix A. Essentially a query component can contain pchar's which includes sub_delims which includes parenthesis. More on the libxml2 issue at the end of this comment.

The bottom line is parenthesis do not need escaping in query component, it's permissible to do so but not required.

A more careful reading of the original bug report shows Keycloak is not complaining about an invalid URL, rather it's complaining about failing the signature validation. How might that happen on an otherwise valid signed request? The answer lies in the SAML Binding specification:

https://docs.oasis-open.org/security/saml/v2.0/saml-bindings-2.0-os.pdf

Lines 620-623 on page 18 states:

"Further, note that URL-encoding is not canonical; that is, there are multiple
legal encodings for a given value. The relying party MUST therefore perform the
verification step using the original URL-encoded values it received on the query
string. It is not sufficient to re-encode the parameters after they have been
processed by software because the resulting encoding may not match the
signer's encoding."

It's also required when validating the signature to build the string ensuring the query parameters are in a specific order. But query parameters are not ordered therefore one must reconstruct the string to validate by locating each required parameter and inserting it in the required order. Unfortunately as shown in this Keycloak bug (https://issues.jboss.org/browse/KEYCLOAK-5318) the parameters are re-encoded which goes straight to the point of the warning cited above in the SAML Binding specification.

The RelayState value Keycloak received was this:

RelayState=https%3A%2F%2Fjdennis-test.example.com%2Fsaml-test%2Ftest(test).txt

But when Keycloak tries to validate the signature it's using this string:

RelayState=https%3A%2F%2Fjdennis-test.example.com%2Fsaml-test%2Ftest%28test%29.txt

because it re-encoded the value. But the signature was computed from the first version of the string, hence the signature verification is going to fail because it's not the same string.

The reason why percent-encoding the parenthesis works is because when Keycloak re-encodes it leaves the original percent-encoded values intact and as a consequence you end up validating the same string.

The libxml2 encoding issue:

I'm not sure what to do with this issue. As far as I can tell libxml2 produced a valid escaped URL. But that was sort of by accident rather than design. I think the libxml2 URL API is fundamentally broken and to some extent lasso's use of that API. Here is the problem in a nutshell:

To properly escape a part of a string when building a URI you MUST know the URI component because each URI component has different escaping rules.

Lasso builds url's by string concatenation, concatenating URI components after calling xmlURIEscapeStr(). But what URI component are you escaping? libxml2 does not seem to a 3986 component specific escaping API. It looks like the best you can do is to continue to use xmlURIEscapeStr() and add the necessary overrides in it's second parameter. But what are the necessary overrides? It's not easy to know, you have to compute it from the libxml2 sources (ugh). I believe when lasso calls xmlEscapeStr for a query component *value* it needs to add this exception string "$+,/:;?@"

Created attachment 1316476 [details]
Python script to dump characters requiring escaping

This is a tiny Python program I wrote to dump out what characters will be escaped in rfc-2396, rfc-3986, and what xmlEscapeURI will escape.

Although it appears libxml2's URL encoding is not RFC compliant and does not provide a usable API which would accommodate RFC compliant escaping of distinct URL components we are going to close this bug.

The URL escaping issue was actually a red herring, the root cause of the problem cited in this bug report was due to improper signature validation in Keycloak. The problem has been resolved in Keycloak therefore we don't need to implement any fix in libxml2.

However at some point libxml2 should address it's URL escaping issues, but I don't know how that can be done without an API change.