Workshop "Post Quantum Cryptography for XML Signature and XML Encryption Suites"

[simoneonofri]

A workshop for Post Quantum Cryptography for XML Signature and XML Encryption Suites to discuss experiences and the next steps.

Problem:

• XML Signature and XML Encryption need support for new Post-Quantum algorithms.

Use cases and requirements:

• There is an issue regarding using SAML, e.g., in the US public sector and institutional environments, with various cryptographic requirements.
• SAML's group is no longer available. However, SAML uses XMLDSign for signatures, and we can work on this.
• Given the use-case of SAML, a potential solution would be to migrate to other technology.
• But, as the issue is on XML Signature and Encryption, people highlighted that this is also used in other contexts, so the scope is broader

Investigation:

• During some conversations, we noticed that not all people consider Post-Quantum Cryptography for integrity an imminent threat.
• Similar need for updates happened in the past, and a workshop in 2007 was organized to facilitate the discussion.
• We also have the RFC 9231 to update the XML Signature and Encryption algorithms XML Security URIs registry.
• There is already some research on Post-quantum XML and SAML Single Sign-On.

From IETF 121 Dublin with <3

[cc'ing @twhalen, @plehegar, @ianbjacobs, @martinthomson, @mnot, @OR13, @pamelatech, @ve7jtb, @hlflanagan]

[plehegar]

For completeness: do we need to consider Web Crypto as part of this workshop?

[dontcallmedom]

(if this were expanded to consider Web Crypto, note that there are practical questions emerging from PQ support in WebRTC as well - in particular, around the size of keys required by PQ algorithms IIUC)

[simoneonofri]

@plehegar @dontcallmedom thank you for the pointers, if there is this kind of interest, this can be more a Post-Quantum Web/Quantum Safe Web.

@iherman We have also crypto algorithms in VC, even if there is already exist a CG Report Draft about it

I am adding to the discussion @souppaya, as we already discussed it in person, who have a broader point of view.

[jaromil]

Good point, @dontcallmedom. My wild guess is that the best candidate algorithm to adopt PQC in webRTC is FALCON. It is not yet standardized as a FIPS-, but it is a NIST competition winner fine-tuned to save bandwidth.

Another thing to consider is that, wherever BBS is used, a usable PQC replacement with zero-knowledge capabilities and reasonable sizes hasn't been discovered yet. PQC transition is important for long-term BBS credentials because BBS is based on EC cryptography (BLS12-381) and as such is an easy prey of quantum-based cryptographic attacks.

[martinthomson]

It's not clear to me why a workshop is needed here. There is ongoing work in the IETF to describe both "pure" PQ signature schemes as well as hybrid classical-PQ signature schemes for things like CMS, JOSE, and COSE. There are arguments for either or both that are playing out there. The requirements for XMLDSig are likely entirely consistent with these requirements.

The debate seems endless, but it will eventually resolve. A workshop in the W3C is unlikely to add clarity to the overall situation. It might even make things worse.

(As an aside, encryption is a much easier debate. For that, hybrids are already strongly recommended and somewhat more urgent given store-and-decrypt-later attacks. Again, those decisions can and should follow the decisions that the IETF makes.)

Web Crypto is separable. It also has a much easier answer: the algorithms that the IETF chooses to bless probably need to be supported. If there are hybrids needed, then a hybrid scheme can always be assembled from parts. Of course, if the hybrids enter wide use, there's a simple discussion to be had about whether to provide support for those schemes directly.

There's a whole separate thread about the use of a CRPQ to attack VCs or selective disclosure systems like BBS or other zero-knowledge proof systems. That's an area that need cryptologic research; I'm not aware of anything that is even remotely ready for standardization in that area (though I'm not a cryptographer).

[ve7jtb]

Hi Martin, The question is not really what algs, but if the W3C XML dsig https://www.w3.org/TR/xmldsig-core1/ and https://www.w3.org/TR/xmlenc-core1/ should be updated to be able to use newer algs. Currently for signing the options are: DSA RSA (PKCS#1 v1.5) ECDSA I think the last person to touch this was Donald Eastlake back around 2013. So the first question is who if anyone is going to be responsible for updating the specs once we have algs? We have SAML as a major consumer of this. Any updates to SAML implementations will take time to work there way out into deployments. There are other specifications that don’t have alternatives, such as switching to OpenID Connect. I don’t know what a workshop is going to tell us, other than that no one is likly working on a PQ plan for all the XML-based applications. John B.

…

On Nov 19, 2024, at 6:37 PM, Martin Thomson ***@***.***> wrote: It's not clear to me why a workshop is needed here. There is ongoing work in the IETF to describe both "pure" PQ signature schemes as well as hybrid classical-PQ signature schemes for things like CMS, JOSE, and COSE. There are arguments for either or both that are playing out there. The requirements for XMLDSig are likely entirely consistent with these requirements. The debate seems endless, but it will eventually resolve. A workshop in the W3C is unlikely to add clarity to the overall situation. It might even make things worse. (As an aside, encryption is a much easier debate. For that, hybrids are already strongly recommended and somewhat more urgent given store-and-decrypt-later attacks. Again, those decisions can and should follow the decisions that the IETF makes.) Web Crypto is separable. It also has a much easier answer: the algorithms that the IETF chooses to bless probably need to be supported. If there are hybrids needed, then a hybrid scheme can always be assembled from parts. Of course, if the hybrids enter wide use, there's a simple discussion to be had about whether to provide support for those schemes directly. There's a whole separate thread about the use of a CRPQ to attack VCs or selective disclosure systems like BBS or other zero-knowledge proof systems. That's an area that need cryptologic research; I'm not aware of anything that is even remotely ready for standardization in that area (though I'm not a cryptographer). — Reply to this email directly, view it on GitHub <#484 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAAPQJ2CUOS7QNI72XXLOWL2BOVTNAVCNFSM6AAAAABR53VJMKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDIOBWHAYDGOJXG4>. You are receiving this because you were mentioned.

[martinthomson]

@ve7jtb, that was exactly my point. I don't think that it's useful to run the same debate as is happening in the IETF for these formats. Let the IETF make good choices (and hopefully publish their rationale) before making the call. As I said, I can't conceive of any reason that XML would need to differ from JSON or CBOR security formats when it comes to signing. Running the same debate in parallel is only likely to produce worse outcomes.

[frumioj]

Yes, as @ve7jtb says:

1. We need whatever updates are needed to support both hybrids and "pure" PQC algorithms for W3C XML DigSig/Encryption specifications
2. SAML specifications would need an update to use the new W3C XML DigSig/Encryption specs.

Since there are no W3C or OASIS groups currently doing this work, how does that move forward?

[plehegar]

For XML DigSig, it seems to me that updating RFC 9231 might be enough for XML Signature. The 2013 REC points to RFC6931 and we could look into refreshing the normative references. XML Encryption does not point anywhere for new algorithms, so that one might need a deeper revision. Reaching out to Donald Eastlake would help here.

[d3e3e3]

Hi, There is actually a possible update to RFC 9231 in https://datatracker.ietf.org/doc/draft-eastlake-rfc9231bis-xmlsec-uris/ I would be happy to add algorithms to it.

[simoneonofri]

Thank you all for your comments.

@d3e3e3 thank you for the availability of XML Sig with the RFC 2931bis

In general, for XML Enc, since there are no references to RFC 4051, 6931, or 9231, do you think it should be updated, or are there better ways to support new algorithms?

[Honzaik]

Hello everyone,
If I may add my two cents as one of the authors of the PQ SAML/XML paper (https://eprint.iacr.org/2024/828).

Purely post-quantum signatures

As noted above, migrating to purely post-quantum signature algorithms in XML is trivial and requires only agreeing on identifiers.

Purely post-quantum encryption

Regarding purely post-quantum public key encryption, it is similarly trivial. However, during my proof-of-concept implementation in Java using Apache Santuario + BouncyCastle, I into a minor issue. I can elaborate on this further if needed, but the gist of it is that there are may be implementation annoyances due to the differences in the PKE and KEM interfaces.

Hybrid post-quantum signatures

As expressed in the paper, we can have the trivial solution using composite signatures (https://www.ietf.org/archive/id/draft-ietf-lamps-pq-composite-sigs-03.html) which makes the integration identical to the integration of purely post-quantum signatures. The downside of composites is that they do not allow what we call "backward compatibility" in the paper.

In the paper we came up with a SAML-specific alternative where we can create a signed SAML message that is compliant with the existing standard and provides optional post-quantum security (in terms of autheticity) and that SAML message may also be processed by classical-only verifiers since they ignore the post-quantum part.

However, there is no generic solution for other XML-based protocols. It is also important to note that the choice of solution is influenced by the structure of the PKI being used: Will it employ composite signatures within a single certificate, or will it consist of separate certificates—one classical and one post-quantum?

Hybrid post-quantum encryption

This topic is the least explored in the paper, and in our POC implementation we do the simple layered/cascading encryption.
In my opinion, the cleanest solution (from a cryptographer's point of view) would be to do something like KeyAgreement https://www.w3.org/TR/xmlenc-core1/#sec-Alg-KeyAgreement twice (one for Diffie-Hellman and one for a PQ KEM) and use a KDF that is a combiner, e.g., https://www.ietf.org/archive/id/draft-ietf-lamps-pq-composite-kem-05.html#name-kem-combiner but the standard needs to be updated to allow for this. This is essentially the same solution that is used in PQ TLS.

[alexstuart]

Hello @Honzaik, referring to your paper

we came up with a SAML-specific alternative where we can create a signed SAML message that is compliant with the existing standard and provides optional post-quantum security (in terms of autheticity) and that SAML message may also be processed by classical-only verifiers since they ignore the post-quantum part.

Mature SAML ecosystems will likely require a hybrid, backwards compatible solution to enable a smooth transition to the newer algorithms, so your proposal in sections 5.2.2 and 7.2.2 is really welcome. And while it's true that a classical-only verifier can ignore the post-quantum part, it appear that it requires embedding XPath in the XML, and an XPath interpreter in the consumer. It's unlikely to be a drop-in solution. I would appreciate the opportunity to discuss the paper and strategies for rollout.

[Honzaik]

Thank you for the insight @alexstuart , I am happy to discuss this further!
Using XPath is certainly not the only possible way how to achieve this, but I decided to use XPath because

• Although SAML prohibits XPath to be present in the XML signature (Sec. 5.4.4 in https://groups.oasis-open.org/higherlogic/ws/public/download/56776/sstc-saml-core-errata-2.0-wd-07.pdf), my intepretation is that this refers to the "standard" XML signature in SAML, which are (direct) children of AuthnRequest/Response/Assertion... So technically other XML signature elements are allowed to contain it.
• Since the PQ XML signature is already in a non-standard place (inside the Extensions), the requirements of Sec. 5.4.4 don't apply. My assumption is that standard verifier would ignore the PQ one since it is not a SAML signature according to the standard (it is in a non-standard location).
• The "augmented"/"PQ-aware" verifier needs to be modified anyway to know to verify this extra signature as well, so it can be also modified to support this XPath instruction. The PQ signature is not technically a standard SAML signature, but it is an XML signature that happens to sign the SAML message, so I'd verify it using an "XML signature verifier", that (presumably) knows how to handle XPath. Since I assume the XML signature verifier already supports XPath, it makes it that I don't need to modify it at all to instruct it to remove the classical signature as well before verification.

Note that I am by no means a SAML/XML expert so my interpretations might be wrong or different from real-world implementations, I base most of it from my experience of looking into the OpenSAML and Apache Santuario libraries.

TLDR; the XPath can be replaced by just instructing the verifier that "there is this extra signature and to be able to verify it you need to 1) do the enveloped transform (which removes the processed signature from the digest) and 2) remove the classical signature from the digest as well". I just decided that step 2) is easiest to express using XPath as its already part of the XML signature standard.

Of course, I am aware of the risks XPath poses to XML signatures (e.g. https://www.nds.rub.de/media/nds/veroeffentlichungen/2013/11/19/diss_somorovsky.pdf) so I'd prefer a solution that does not use it, but I have not been able to come up with a more "generalized" alternative (albeit the generalized solution is not so general as it has some assumptions).

[jiscfoo]

Hello everyone, If I may add my two cents as one of the authors of the PQ SAML/XML paper (https://eprint.iacr.org/2024/828).

@Honzaik Forgive me if I've misunderstood, but your paper appears to make no reference to SAML V2.0 Metadata Profile for Algorithm Support which gives the possibility of signalling support for different encryption & signing methods by relying parties in their metadata.

Would this not simplify (remove?) the need for the various parallel approaches in individual messages?

Edited to tag @Honzaik in reply

[Honzaik]

@jiscfoo Good point! I agree we should have mentioned in the paper that there is such mechanism. It is certainly one option how to solve this interoperability issue. However I think it assumes slightly different properties than we do in the paper.

Correct me if I am wrong as I haven't spent much time looking into that but

1. It assumes the metadata exchange protocol is supported by the SP/IdP. I am not sure how well the support looks like in reality. Nonetheless, we tried to come up with a solution where all components are presumably supported by the majority of implementations and we basically use just the core functionalities of SAML/XMLSig.
2. Even if both the SP/IdP supported the metadata protocol, we focus on the case where the IdP wants to have a "unified response" for everyone, i.e., "I sign everything with alg1 and alg2 and I am sure the receiver will process it". Here, it would need to tailor the response to the receiver based on the information received from the metadata. However, I agree this might seem like a non-realistic issue.
3. If I understand this correctly, this requires direct communication between the SP/IdP over some other secure channel (otherwise it can be e.g. downgrade attacked). We focus on the indirect POST binding case where the benefit is that the don't have to directly communicate. Of course, I guess you can technically send the metadata also over that binding but then it needs to be secured (against a malicious user) and we have the same problem.

[OR13]

I would not mix changes to message format / application layer hybrid constructs into the conversation, until after there is a way to do pure PQ algorithms in XML.

Perhaps under the section on xmss:
https://datatracker.ietf.org/doc/html/draft-eastlake-rfc9231bis-xmlsec-uris-05#name-xmss-and-xmssmt

http://www.w3.org/2021/04/xmldsig-more#ML-DSA-44
http://www.w3.org/2021/04/xmldsig-more#ML-DSA-65
http://www.w3.org/2021/04/xmldsig-more#ML-DSA-87
...
http://www.w3.org/2021/04/xmldsig-more#ML-KEM-512
http://www.w3.org/2021/04/xmldsig-more#ML-KEM-768
http://www.w3.org/2021/04/xmldsig-more#ML-KEM-1024