Prefix constant string to M' and add statement about attack detection

[falko-strenzke]

In the current proposal M' is starting with the OID. My suggestion is to prefix a "magic" constant of length of 16 or 32 bytes to the OID.

The reason is the following: In the case that a signature stripping attack is executed where the PQ signature is stipped of, the reamaining traditional signature is valid for the message M'. This amounts to a EUF-CMA violation (under consideration of cross-algorithm chosen message oracle queries).
Prefixing the magic constant allows CMS implementations of the signature verification to perform attack detection by checking the start of the signed data to be equal to the magic string. Otherwise, the forged message cannot be detected and may cause harm in the receiving system.

The value of the attack detection mechanism should be mentioned in the text as well. In my view, it should be specified as a "SHOULD" feature.

[ilaril]

Alternatively, since RSA and ECDSA actually sign a hash, and everything else relevant has context inputs, one could do something like the follows to get actual strong non-separability (even for RSA and ECDSA):

Pure:

M' = Domain | 0 | len(ctx) | ctx | M

Prehashed:

M' = Domain | 1 | len(ctx) | ctx | HashOID | PH(M)

RSA:

RSA_signhash(cSHAKE256(M', ctx="sig-composite"))

ECDSA:

ECDSA_signhash(bytes2bits_be(cSHAKE256(M', ctx="sig-composite")))

Ed25519:

Ed25519ctx_sign(M', ctx="sig-composite")

Ed448:

Ed448_sign(M', ctx="sig-composite")

ML-DSA:

MLDSA_sign(M', ctx="sig-composite")

Some notes:

• The bytes2bits_be() is to ensure that ECDSA interprets the hash in the expected way.
• This aligns with the model presented in the meeting.

[johngray-dev]

Falko, the current version of composite signatures all use DER Encoded OIDs that start with HEX 060B6086480186FA6B50080 which could be considered the magic String you are talking about. So we think this already meets the requirement you are asking about. We acknowledge that the current OIDs will change, and will be assigned by IANA so it is likely they will become shorter. For example in the IANA registry, it would be something like 1.2.840.113549.1.9.16.3.xx (where xx is the composite algorithms). So 1.2.840.113549.1.9.16.3 can be considered the MAGIC string (DER encoded of course). See https://www.iana.org/assignments/smi-numbers/smi-numbers.xhtml#security-smime-3 . Does this satisfy your concern?

[ounsworth]

@falko-strenzke I do not understand this sentence:

Prefixing the magic constant allows CMS implementations of the signature verification to perform attack detection by checking the start of the signed data to be equal to the magic string.

This magic prefix that you are talking about is only added by the construction of M' inside the Composite Sign(). This would not be carried over the wire in a CMS message because equally the Composite Verify() will add it while constructing M'. So I do not understand this suggestion.

@ilaril we have considered this. Thank you for writing out what this would look like.

We decided against using the EdDSA ctx because many crypto libraries do not support this, and one of the design goals is to be able to use your existing (potentially certified / change-controlled) legacy crypto code as-is without modification. See #64

We could add a wrapper to RSA and ECDSA as you suggest to bind a ctx, but since we are already adding Domain into M', it's not clear to me that this is actually adding any new binding properties.

[falko-strenzke]

This magic prefix that you are talking about is only added by the construction of M' inside the Composite Sign(). This would not be carried over the wire in a CMS message because equally the Composite Verify() will add it while constructing M'. So I do not understand this suggestion.

Here the case of a stripping attack is relevant where the attacker removes the PQ signatures and leaves the traditional signature and changes the message to M'. The signature is then valid for M'. If M' starts with the magic sequence, that can be detected by the verifier.

[falko-strenzke]

Falko, the current version of composite signatures all use DER Encoded OIDs that start with HEX 060B6086480186FA6B50080 which could be considered the magic String you are talking about. So we think this already meets the requirement you are asking about. We acknowledge that the current OIDs will change, and will be assigned by IANA so it is likely they will become shorter. For example in the IANA registry, it would be something like 1.2.840.113549.1.9.16.3.xx (where xx is the composite algorithms). So 1.2.840.113549.1.9.16.3 can be considered the MAGIC string (DER encoded of course). See https://www.iana.org/assignments/smi-numbers/smi-numbers.xhtml#security-smime-3 . Does this satisfy your concern?

I don't think it does because
a) the prefix seems to be too short (currently 11 byte and you say could get shorter)
b) it is not chosen at random (anyone signing an OID with this prefix would run into an error)
c) I don't think there is any control that prevents the registration of OIDs with a different prefix in the future, e.g., proprietary OIDs

[ounsworth]

If M' starts with the magic sequence, that can be detected by the verifier.

This comment makes no sense to me.

The verifier takes as input Composite-ML-DSA.Sign (sk, M, ctx), and it has Domain hard-coded.

Then the verifier itself constructs M' = Domain || len(ctx) || ctx || M. Domain is a value hard-coded in the source code of the verifier, and pre-fixed to the message by the verifier. What possibly value is there in the verifier detecting something that it itself added? M' never goes over the wire.

[johngray-dev]

Ok. Thanks Falko. In regards to your comments:
a) What is your recommended length (16 or 32 bytes or anything in between?). Would using the byte representation of something like "CompositeAlgorithmSignatures2025" as a prefix be sufficient? It is 32 bytes. So we would have

M' = prefix || Domain || ctx.length || ctx || M

b) I'm not sure I understand. You mention using a magic constant, so where does the randomness come into play? If we used a random prefix, it would have to be stored as part of the signature itself so it could be verified.

c) Yes, I agree, different OIDs with a different prefix could be registered in the future. So having a prefix of specific length would prevent this.

So I think I agree that a prefix at least guarantees a constant value that is of a specific length (you say 16 - 32 bytes) which I guess is 128 bits to 256 bits. The only remaining question is why do we need this property? Can you give a detailed example to help us understand please?

[falko-strenzke]

If M' starts with the magic sequence, that can be detected by the verifier.

This comment makes no sense to me.

The verifier takes as input Composite-ML-DSA.Sign (sk, M, ctx), and it has Domain hard-coded.

Then the verifier itself constructs M' = Domain || len(ctx) || ctx || M. Domain is a value hard-coded in the source code of the verifier, and pre-fixed to the message by the verifier. What possibly value is there in the verifier detecting something that it itself added? M' never goes over the wire.

I wrote "... and changes the message to M'". This is why M' goes over the wire. Please look at the description I have given above. You are trying to map it to the verification of the composite algorithm, which is not relevant here. The relevant case is the alteration to a message-signature pair that is valid under the standalone-scheme verification. In that case the forged message M' starts with the "magic prefix" which can be detected by the verifier.

@ounsworth

[johngray-dev]

Hi Falko, I think the confusion is because you mention M' . In Composite M' is defined as the message format of the Composite.

M' = Domain || len(ctx) || ctx || M

It seems you are using M' to mean something slightly different. I've re-read you comment multiple times and am still trying to figure out what you mean.

"Here the case of a stripping attack is relevant where the attacker removes the PQ signatures and leaves the traditional signature and changes the message to M'. The signature is then valid for M'. If M' starts with the magic sequence, that can be detected by the verifier.:

So I'm trying to follow what you are saying.. You say the attacker removes the PQ signatures and leaves the traditional signature. So I think you mean:

instead of:
mldsaSig = ML-DSA.Sign( mldsaSK, M', ctx=Domain )
tradSig = Trad.Sign( tradSK, M' )

PQ is stripped out and we just have the following traditional component:
tradSig = Trad.Sign( tradSK, M' )

So I think you are saying a regular traditional verifier would verify the stripped traditional signature by having an attacker compute M' (from M) and handing the traditional stripped signature and the constructed message:
if not Trad.Verify( pk2, M', s2) then
output "Invalid signature"

The same thing could NOT be done with the ML-DSA PQ component because of the context.

"If M' starts with the magic sequence, that can be detected by the verifier"

• I don't understand how the traditional verifier would detect this, it would know nothing about the composite magic sequence (unless you are advocating that traditional verifiers be updated with this knowledge to detect this kind of attack?). The composite verifier would already fail because it would be expected 2 signature components and would only have 1.

So please help me understand if I'm on the right track, or give us a more detailed explanation of how this works. I am obviously missing something important that isn't obvious to me.

[falko-strenzke]

Hi Falko, I think the confusion is because you mention M' . In Composite M' is defined as the message format of the Composite.

M' = Domain || len(ctx) || ctx || M

It seems you are using M' to mean something slightly different. I've re-read you comment multiple times and am still trying to figure out what you mean.

No, the M' I refer to is the same one as you give above.

"Here the case of a stripping attack is relevant where the attacker removes the PQ signatures and leaves the traditional signature and changes the message to M'. The signature is then valid for M'. If M' starts with the magic sequence, that can be detected by the verifier.:

So I'm trying to follow what you are saying.. You say the attacker removes the PQ signatures and leaves the traditional signature. So I think you mean:

instead of: mldsaSig = ML-DSA.Sign( mldsaSK, M', ctx=Domain ) tradSig = Trad.Sign( tradSK, M' )

PQ is stripped out and we just have the following traditional component: tradSig = Trad.Sign( tradSK, M' )

Yes, that is the attack I am referring to.

So I think you are saying a regular traditional verifier would verify the stripped traditional signature by having an attacker compute M' (from M) and handing the traditional stripped signature and the constructed message: if not Trad.Verify( pk2, M', s2) then output "Invalid signature"

Yes, the attacker replaces M with M' in the message.

The same thing could NOT be done with the ML-DSA PQ component because of the context.

Exactly.

"If M' starts with the magic sequence, that can be detected by the verifier"

• I don't understand how the traditional verifier would detect this, it would know nothing about the composite magic sequence (unless you are advocating that traditional verifiers be updated with this knowledge to detect this kind of attack?).

Exaclty, the implementation of the verifier would have to be updated to know the magic sequence and classify a message starting with it as an attack message.

The composite verifier would already fail because it would be expected 2 signature components and would only have 1.

For the verifier of a composite signature, in principle the inverse attack was possible: The attacker lets the signer sign two messages M'_pq and M'_trad with the PQ and the traditional scheme standalone, respectively. He makes up these two message exactly in the way so that they will later be valid messages when the two signatures are interpreted as component signatures of the composite scheme. Now, for the traditional scheme there is no hinderance to have M'_trad signed. For the PQ scheme, having M'_pq signed is hindered by the fact that it would need to set a specific value of the context parameter, which the current version of draft-ietf-lamps-cms-ml-dsa does not allow: "When using ML-DSA as described in this document, the context string is not used." So this attack is not applicable if draft-ietf-lamps-cms-ml-dsa is not changed in this respect. If the draft would be changed to allow the arbitrary values of the context parameter for standalone ML-DSA, the magic prefix could also be used to detect fadulent messages during signing, since the two M'_... messages of the component signatures would have to start with that magic prefix.

[johngray-dev]

Thanks for the update Falco! Now we have the same understanding. So you want us to add the prefix to help mitigate a stripping attacked that will require an update to the classical verifier to do this detection. We would do this for all composite signature combinations (as well as any future combinations).

So if we add this:

M' = prefix || Domain || len(ctx) || ctx || M

where:
prefix = "CompositeAlgorithmSignatures2025" (encoded as 32 ASCII bytes)

As well as a couple sentences explaining why this has been added, I believe it will mitigate the issue and make you happy.

[falko-strenzke]

So if we add this:

M' = prefix || Domain || len(ctx) || ctx || M

where: prefix = "CompositeAlgorithmSignatures2025" (encoded as 32 ASCII bytes)

I am basically OK with this solution. The prefix string has sufficient entropy. To achieve even some degree of protocol domain separation, we could make the prefix "IetfCmsCompositeAlgorithmSignatures2025".

In my view, there is no need for an obligation to apply the detection of this prefix in a verified message (this cannot be enforced for existing implementations anyway), but should be presented as an optional measure to prevent the theoretical forgeries. So in my view the draft should incorporate a sentence mentioning the possibility of the attack detection via prefix detection.

As well as a couple sentences explaining why this has been added, I believe it will mitigate the issue and make you happy.

Yes, a short discussion of the principal forgery attacks and the role of the prefix detection (for instance in the security considerations section) would be good.

[johngray-dev]

Added prefix into the draft and added a note about it in the security considerations section