Address Falko Strenzke's comments

[johngray-dev]

Falko suggests we fix the following:

I would like to propose a simplified way to achieve the security notions related to non-separability of composite signatures defined in draft-hale-pquip-hybrid-signature-spectrums. For this purpose I would like to start with a brief analysis what is the implied threat and under which circumstances it applies. I am including PQUIP here as I think this topic has relevance for all protocols. Background

1. The threat: signature downgrade attacks A signature downgrade attack on a message signed using a composite signature scheme means that at least one signatures was removed after the signing process. The recipient receives only a subset of the signatures. Let us for simplicity restrict the discussion to composite schemes with two component algorithms. In this case, the sender created the signature S₁,₂ = Sign(PrivKey₁,₂,m) which would be verifiable as valid = Verify(PubKey₁,₂, S₁,₂, m). After the downgrade attack that strips off the signature of the 2nd component scheme the recipient receives S₁ = Sign(PrivKey₁,m) which is verifiable as valid = Verify(PubKey₁, S₁, m). The first conclusion we can draw is that a signature downgrade attack is not a security problem, but only an availability problem: If the recipient accepts signatures of a scheme for which signature forgery is possible at that time, this is a problem in itself that is not influenced at all by whether downgrade attacks are possible or not. The only negative effect of such a downgrade attack is given when the recipient has a policy where he accepts messages signed only with scheme 1 and at a later point in time scheme 1 is considered insecure but scheme 2 still is secure. Then he suffers the loss of the ability to verify the signature on m. Had downgrade attacks been ruled out by the design of the composite scheme, then under remaining availability/blocking attacks, the recipient would have indicated to the sender that he didn’t receive a validly signed message and the transfer of the message could have been repeated.
2. Authentic public keys The second important aspect that we have to consider, is that in order for signature downgrade attacks to be applicable to the composite scheme in a certain “communication system”, there must exist PubKey₁ that is accepted by the recipient as authentic for the sender additionally to the PubKey₁,₂. This raises the question how a PubKey₁ that is taken as authentic can come into existence. Here, we leave open how the authenticity of a public key is technically realized. It could be through the issuance of an X.509 certificate (which is applicable for us here of course) or a trust list. There two possibilities: a) PubKey₁ existed before the creation of PubKey₁,₂ as an authentic public key and was reused when the composite key was created. b) PubKey₁ is exported/extracted from the PubKey₁,₂ and then endowed with authenticity. The entity which can endow the public key with authenticity might be the holder of that key himself or a different entity. We can thus draw the following conclusion: In order for an authentic PubKey₁ to exist additionally to PubKey₁,₂ either of the following has to happen: I) The holder of the initially existing key (either PubKey₁ or PubKey₁,₂) has to reuse the existing (component) key for the creation of the other key and forwards it to the entity that endows the new public key with authenticity (in case that entity is different from the keyholder) II) Another actor extracts the PubKey₁ from PubKey₁,₂ and achieves that PubKey₁ it is endowed with authenticity. Thus, if one wants to rule out signature downgrade attacks against a composite scheme, one simply has to specify that what is described under I) is not allowed. What is described under II) is achieving authenticity for a public key to be associated with another entity, i.e. normally through fraudulent identification or impersonation for a different entity. Being able to do so of course implies the ability of impersonation attacks based on the “injected” public key which are much stronger than signature downgrade attacks. For the prevention of II) we rely on public CAs, Web of Trust, and verifying key servers. Application to draft-ounsworth-pq-composite-sigs From the above we can thus conclude that if draft-ounsworth-pq-composite-sigs would specify that I) is not allowed, no further measures would be needed against the signature downgrade attacks. Note that if the holder of the key (or his client application) violates this requirement, he is still not facing a security problem, but only a potential availability problem, as discussed under point 1. I think forbidding key reuse in this sense would be the favorable solution to any algorithmic measures. We should keep in mind that composite schemes such as the ones specified by LAMPS are defined per protocol and thus will likely not be integrated into cryptographic libraries. This would mean complication in each application implementing the respective protocol and thus potentially increase the risk of security or interoperability relevant errors. Composite signatures are a quite simple construction with straightforward security features, as long as the composite algorithms are consistently treated as black boxes and never allow any direct “addressing” of the component schemes. On this background I also recommend to remove all features from draft-ounsworth-pq-composite-sigs that violate this restriction. Specifically, that concerns the sentence In the absence of an application profile specifying otherwise, compliant applications MUST output “Valid signature” (true) if and only if all component signatures were successfully validated, and “Invalid signature” (false) otherwise. Instead, verification of all signatures should be mandatory without any exception.

I replied to him with the following saying we would clarify the text because I totally agree with what he is saying:

Thanks Falko for these comments. I have to admit when I read through for first comment (not allowing a component key to be used for another key), I was thinking we had already stated this, because it was never our intent that separate copies of component keys could be used that way. However, I tried to find where we said this, and I couldn’t find it, so thanks for pointing this out! We will definitely add some text to clarify this into the draft.

In regards to you second suggestion, I agree with you. Leaving the text “In the absence of an application profile” in there implies it is not mandatory and an application could decide to do whatever it wanted. This is definitely not what we were intending in the -10 version. That fragment was probably left over from an older version of the draft. We want to make sure it is very clear that all component signatures MUST be validated for the “blackbox” composite signature algorithm to be considered valid.

So I believe this should resolve the issue: “Compliant applications MUST output “Valid signature” (true) if and only if all component signatures were successfully validated, and “Invalid signature” (false) otherwise.”

Cheers,

John Gray

[johngray-dev]

This has been addressed in version -11 of the draft.