Christmas Carol: XML Signatures

TL;DR:

• XML signatures are trouble, because they are ridiculously hard to implement right.
• XML signatures in PHP are double trouble, because of lack of decent libraries.
• .NET security libraries are mildly annoying, because they cannot read RSA private keys from a PEM file, which are the standard form of storing RSA private keys.

Background

My team currently maintains a project that provides single sign-on for 3^rd party web sites. These days, single sign-on appears in many places on the web: 3^rd party web page displays “login with your Facebook account” button, you click on it, Facebook verifies your identity, and sends secure message to the 3^rd party web site assuring that you have been authenticated. In my case, the authenticator is not Facebook, but our company’s platform.

I tried to implement a sample 3^rd party site using PHP and SAML. I chose PHP because my home web site uses it, and because our server is implemented in .NET, so by using PHP on the other side, I can prove cross-platform interoperability.

SAML Request is a Simple GET

I relatively quickly finished the SAML request part: it amounts to a large GET request where the XML is compressed and signed with the 3^rd party’s private key. The request and the signature are supplied as separate request parameters. The URL has its share of long namespaces and long URL-encoded nonsense, but this is all relatively benign.

https://sso.platform.com/AuthService/Saml?SAMLRequest=base64blob&SigAlg=http%3A%2F%2Fwww.w3.org%2F2000%2F09%2Fxmldsig%23rsa-sha1&Signature=anotherBase64Blob

To verify that the SAML request came from an authorized partner, the SSO platform needs to look up the Issuer field from the request, find corresponding partner public key in its database and verify the cryptographic signature using standard library.

SAML Response has an XML Signature

SAML response tells the partner whether the user was authenticated or not. It can take multiple forms, but in my particular case, it is a POST containing an XML document. Authenticity of the information within the document is verified by an XML Signature.

Creating XML Signature

Creating an XML signature involves many more steps than simply digitally signing a bunch of bytes. As most other things designed by W3C and OASIS, XML signature has so many variants and options on top of standard RSA signatures, that it is basically impossible to get right without a library, and writing that library is not an easy task.

XML signature allows to sign many “references” at once. In theory, a reference can be any URI. In practice, it is either the entire current document (empty URI), or a fragment of the current document ("#fragmentID"). Each reference is canonicalized and then its “digest” (cryptographic hash) is computed. The digest is a regular SHA1 or SHA256 hash, this step does not use any secret keys.

In the second step, all digests are gathered in a <SignedInfo> structure. Additionally, it may also contain the issuer’s public RSA key, or even an entire X509 certificate. Besides RSA key, a certificate contains issuer information such as location and name, and may be signed by a trusted Certificate Authority. SignedInfo is then canonicalized, and digitally signed with the issuer’s private key. The SignedInfo with the digests and the signature are added to the original XML document, making it signed.

Note that SignedInfo may not contain any key information at all, in which case the verifier will have to find the issuer’s public key from other sources, e.g., from a database of known issuers. Even if SignedInfo does contain a key, the verifier must ascertain that this key indeed comes from the issuer and not from some malicious middle man.

To verify an XML signature, one must:

1. Ensure that the issuer public key is valid by tracing the certificate to a trusted authority, or by checking a database of known issuer keys.
2. Canonicalize the SignedInfo node.
3. Verify that digital signature of the SignedInfo node is valid.
4. Canonicalize each reference, compute its digest and verify that it matches the digest provided in SignedInfo.

If all of the above checks out, the document is authentic and has not been tampered with.

The Nightmare of Canonicalization

Note that the document text may (and probably will) be sent in a non-canonicalized form. So, there is a pretty good chance that what was digitally signed is not what you see in the document. For the signature verification to succeed, both the issuer and the verifier must perform the canonicalization process, and they must do it exactly in the same way, or the digests won’t match.

The canonicalization algorithm is, to put it mildly, non trivial. To makes things easier for us, “exclusive canonicalization” is defined as “Canonical XML” with a couple of “exceptions”. Canonical XML is a hefty algorithm by itself: it converts self-closed tags (<tag />) to open-close tag pairs (<tag></tag>), deals with white space, attribute order, propagating namespaces, and the like. Exclusive canonicalization adds a paragraph or two of refinements that should be applied under simple conditions like “if the prefix has not yet been rendered by any output ancestor, or the nearest output ancestor of its parent element that visibly utilizes the namespace prefix does not have a namespace node in the node-set with the same namespace prefix and value as N.

A “non-normative implementation” provided in the standard works in “many straightforward cases”, but, by the standard author’s own admission is “constrained”.

PHP Libraries and Online Signature Verifiers

I found two PHP libraries that purport to implement XML signature verification:

1. robrichards/xmlseclibs: the use case in the documentation shows how to create XML signature, but not how to verify it. There is a “verify()” method, but it is not quite clear how to use it.
2. Marcel Tyszkiewicz’s php-XMLDigitalSignature. It also has a verfiy() method, but the examples only verify signatures that have just been created. It is not quite clear (even after looking at the source code for some time), how to verify a signature that came from someone else.

There is also FR3D/XmlDSig, which is a wrapper around xmlseclibs. Its code has a straightforward verify() method that does uses xmlseclib’s verify().

However, even with this library, I could not verify the signatures, because it turns out that our server was not doing the canonicalization right.

XML Signature Verifiers

To sanity check my documents, I wrote a console verifier program using .NET framework (perhaps more about it later).

I found two online verifiers.

1. https://www.aleksey.com/xmlsec/xmldsig-verifier.html works well with documents signed in their entirety (ReferenceUri=""), but fails if signature is only applied to a portion of the document (ReferenceUri="#mySignedElement"). Offline .NET version can handle both cases fine.
2. https://demo.bloombase.com/demo/spitfire/soa/verify.jsp does not seem to work at all: it failed to verify any document which was recognized as good by other verifiers.

Bottom Line

Frankly, guys, this is ridiculous. Signature verification should not involve so much complexity. “Keep it simple” principle was violated big time here. And I still did not achieve nirvana by verifying my signatures in PHP, although the FR3D library does look promising.
CodeProject