Future proofing the protocol: transcript collisions resistance

[charlie-j]

Chosen prefix collisions are a particular kind of hash function collisions, where given two prefixes p1 and p2, the attacker is able to compute two bitstrings c1 and c2 such that h(p1 | c1) = h(p2 | c2). The consequences of such collisions over protocols have been explored in [1]. Computing such collisions is feasible on MD5 and SHA-1, and it is unknown whether it will or not be the case for SHA-256 in the coming years.

On the current version of the protocol, chosen prefix collisions lead to attacks on secrecy and authentication, as well as downgrade attacks on the ciphersuite. Such attacks can be prevented or mitigated by a set of small adjustment to the standard, and would at low cost improve the long term security of the protocol. Let us first detail the concrete chosen prefix collisions, before talking about the mitigations.

The attacker performs a Machine-In-The-Middle, where it will use a chosen-prefix collision attack to build a session where I and R are talking together and agree on the value of the hash of the transcript, but where each agent actually received the neutral DH group element (which is so that e^x=e).

The following transcripts are computed in such a run, where Trans_E is the expected shared transcript (displayed using variable names), and Trans_I and Trans_R are the transcripts produced by the attack, with values aligned with corresponding variable names of the expected transcript.

Trans_E :=  method |  suitesI  | G_X |  C_I  |  EAD_1  | G_Y | C_R 

Trans_I :=  zero   | "suitesI" | g^x | "C_I" | "EAD_1" |  e  | c2 | g^y | C_R 
Trans_R :=  zero   | "suitesI" |  e  | "C_I" |   c1    | g^y | "C_R"

We see that the attacker is using the arbitrary long fields EAD_1 and C_R to stuff the bitstring corresponding to the chosen-prefix collision. In this scenario, we remark that as the ciphersuites are part of the prefix, the attacker could also decide to show two distinct suitesI values to both participants, corresponding to a downgrade attack. As a last scenario, if the parsing of suitesI is loose, for instance accepting suites = [ 2* int / btstr ] / int instead of suites = [ 2* int ] / int, a value of the array can also be use to stuff the chosen-prefix collision bits.

Possible actions:

• add length restrictions over the EAD,C_R and C_I fields;
• enforce/recommend checking for low-order points when it has a low-ressource cost (and in general at least the identity element);
• enforce/recommend that the CBOR parsing must be strict.

[1]: https://hal.inria.fr/hal-01244855 Transcript Collision Attacks: Breaking Authentication in TLS, IKE, and SSH. Karthikeyan Bhargavan, Gaëtan Leurent

[chrysn]

I don't quite understand the possible actions. There is no definition of strict parsing in RFC8949, what is meant by that?

[chrysn]

Also, in terms of length restrictions: Which order of magnitude are we talking about? Few bytes? Megabytes? Gigabytes?

[charlie-j]

Strict parsing

What we mean for strict parsing is the following: If the standard specifies that some message is of CBOR type X, any received message that does not perfectly matches this type MUST be rejected.

As a concrete example, if instead of receiving for the suites value a message of the form [5,4,2], an agent receives a message of the form [5, SOME_LONG_BITSTRING,2], then the parsing step should fail and the protocol be discontinued. Otherwise, it means that the attacker can use the somehow loose parsing to include arbitrary long bitstrings inside the transcript that will be hashed.

Length restriction

We are talking of around a few hundred bytes. For instance, two colliding PGP certificates based on SHA-1 were derived thanks to 757 bytes collision suffixes [1]. We cannot say what could happen for SHA-256 (and as we said, whether it would ever be a true weakness), but an implementation forbidding anything over 100 bytes would be secure for a very long time.

A question over this is whether EADs are meant to be used to send over big values or not. As a good practice, big values should probably be authenticated simply by an independent MAC with a key derived at the end of EDHOC.

[1]: https://eprint.iacr.org/2020/014.pdf, SHA-1 is a Shambles, First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust, Gaëtan Leurent and Thomas Peyrin

[chrysn]

Strict parsing

This kind of strict parsing (i.e. that the message conforms to the CDDL described in the specification) is, as I understand, commonplace; I'd be surprised if the current spec even allows it.

There are places like ead_value, and possibly inside the COSE header maps of ID_CRED_x, where the protocol allows any value -- would strict parsing mean anything for them?

Length restriction

ID_CRED_x can IMO live with a restriction in that order of magnitude. For EAD, not sure (gut feeling, I'd like to have up to 1kB there); if there's some hashing inbetween that'd be fine with me (as long as the empty-EAD case stays cheap).

[charlie-j]

This kind of strict parsing (i.e. that the message conforms to the CDDL described in the specification) is, as I understand, commonplace; I'd be surprised if the current spec even allows it.

If it is already the case for the implementations, that's perfect, it could indeed indicate that this point does not need to be mentioned :) (maybe some implementer feedback can easily resolve this here?)

There are places like ead_value, and possibly inside the COSE header maps of ID_CRED_x, where the protocol allows any value -- would strict parsing mean anything for them?

Yes. It is let's call it as strict as possible, so when the specification is any, you do have to accept anything.

ID_CRED_x can IMO live with a restriction in that order of magnitude. For EAD, not sure (gut feeling, I'd like to have up to 1kB there); if there's some hashing in between that'd be fine with me (as long as the empty-EAD case stays cheap).

A solution could indeed be to include inside the transcript h(EAD) instead of EAD when the actual value is overly long, but this comes at the cost of some performance.

Of course, instead of a hard restriction, simply adding a sentence in the security considerations mentioning that bounding the length of the EAD can increase the long term security of the protocol could do the job. Then, an implementer could decide to enforce a length limit based on the use case.

[emanjon]

The techniques for collision attacks on MD5 and SHA-1 does not seem useful for SHA-256. If collision attacks were found for SHA-256, I think the recommendation would be to stop using SHA-256 even in constructions not requiring collision resistance such as is currently done with HMAC-SHA1. That said minimizing the damage of collision is a good idea if it can be done without other disadvantages.

• Length restrictions (a few hundred bytes) on EAD would be problematic, even 1kB seem too small.
• Length restrictions on C_I and C_R would be ok
• Strict parsing (CDDL and deterministic CBOR) is enforced by EDHOC. The specification expect implementations to refuse messages that are not deterministic (general CBOR does e.g. allow several encodings of integers). This should probably be checked with actual implementations. Any non-deterministic encoding is unsuitable for use in security protocols.
• Including h(EAD) would not be a problem I think.
• EDHOC implementations are already required to check that the ephemeral public keys are not the identity element, see Section 8.2 of the EDHOC specification.

(I did not understand if all or just one of the actions would be enough)

[charlie-j]

TLDR: bellow are a bit more details around this, but to sum-up, I guess the two simplest actions to take are the following ones:

• Length restriction over C_I and C_R of around 100 bytes
• Forbid the identity element as well as low-order points for the ephemeral public keys. For X25519 and X448, enforce the check that the resulting ECDH shared secret is not the all-zero string, as specified in [Section 6, RFC7748]. (I don't know what is the corresponding action for the other curves).

Which actions would be enough

I'm gonna sum-up the scenarios that lead to an attack bellow, all of them being under the assumption of chosen-prefix collisions:

• No length restriction over EAD_1 and C_R + no weak ephemeral DH check -> secrecy attack
• No length restriction over C_I and C_R + no weak ephemeral DH check -> secrecy attack
• Loose parsing + no weak ephemeral DH check -> downgrade + secrecy attack

So, the minimal low cost solutions (as we indeed do not want to make huge or costly changes to the standard given that this is not at all an immediate threat) seem to be:

• Length restriction over C_I and C_R of around 100 bytes.
• Weak ephemeral public keyschecks.

Those two actions together would then negates the attacks that we found. Only the second one would be enough, but I think there are curves for which it may be costly (to check), so doing both is anyway a good idea.

With those actions, enforcing a strict parsing is not needed, but it is anyhow a good idea that the standard already enforce it. (it is always a good thing to reduce the attacker possible actions, especially when it is at no-cost).

On the weak DH ephemeral public keys

The issue is when the attacker can give an element h to the responder such that h^y will be a predictable constant. This occurs both with the identity element, as well as some low-order points over the curves.

EDHOC implementations are already required to check that the ephemeral public keys are not the identity element, see Section 8.2 of the EDHOC specification.

What I found in section 8.2 is "Requirements for how to securely generate, validate, and process the ephemeral public keys depend on the elliptic curve. For X25519 and X448, the requirements are defined in {{RFC7748}}. For secp256r1, secp384r1, and secp521r1, the requirements are defined in Section 5 of {{SP-800-56A}}. For secp256r1, secp384r1, and secp521r1, at least partial public-key validation MUST be done.". I don't think this is enough to clearly forbid such behaviors. Maybe the mentioned specs do enforce an identity check, but they only mention as an optional feature to check for low-order points, which are also an issue.

From [RFC7748], the interesting bit is the following one:
"Protocol designers using Diffie-Hellman over the curves defined in this document must not assume "contributory behaviour". Specially, contributory behaviour means that both parties' private keys contribute to the resulting shared key. Since curve25519 and curve448 have cofactors of 8 and 4 (respectively), an input point of small order will eliminate any contribution from the other party's private key. This situation can be detected by checking for the all-zero output, which implementations MAY do, as specified in Section 6. However, a large number of existing implementations do not do this."

This part only specifies "MAY", which should become a MUST in our setting.

[gselander]

Starting at a different end: Does the order of elements being hashed have an impact?

Would replacing this:

TH_2 = H( H(message_1), G_Y, C_R )

with this:

TH_2 = H( G_Y, H(message_1), C_R )

or this:

TH_2 = H( G_Y, C_R, H(message_1) )

make any difference?

[gselander]

Maybe I misunderstand the attack, but it seems to be producing transcripts which masquerade as:

method | suitesI | G_X | C_I | EAD_1 | G_Y | C_R

But all individual fields above are type-length-value encoded by CBOR, so I didn't see how to produce

values aligned with corresponding variable names of the expected transcript

Perhaps a simple example?

[charlie-j]

Starting at a different end: Does the order of elements being hashed have an impact?

It does have an impact, but we would need to run some verifications to identify a valid order with any kind of confidence. We can try to look into it if this is a preferred solution. Should we?

[charlie-j]

Perhaps a simple example?

To produce a valid TLV encoding does take slightly more work, but the tag and length values that will make the fake transcript look like a valid encoding can be seen as part of the prefix over which the collisions are computed. So, to make the representation of EAD1 and C_R in the example a bit more precise, we get the following thing, assuming that the instantiation of a value for X as a TLV is denoted by <"tag identifier", data length, data>:

Trans_E :=  method |  suitesI  | G_X |  C_I  |  EAD_1  | G_Y | C_R 

Trans_I :=  zero   | "suitesI" | g^x | "C_I" | <"EAD_1",honest_length, honest_value> |  e  | <"C_R", length_of_c2+gy+honestCR, c2 | g^y | C_R >
Trans_R :=  zero   | "suitesI" |  e  | "C_I" |  <"EAD_1", length_of_c1, c1>          | g^y | <"C_R", honest_length,honest_CR>

(this questions were raised and answered inside the paper we cited in the first message of this thread, where the were concretely able to mount such attacks on some transcript similarly built)

[gselander]

We can try to look into it if this is a preferred solution. Should we?

In comparison to C_x length restrictions and weak ephemeral public keychecks, I believe this could be a preferred solution.

But before running any verification, please just comment if it makes sense that this kind of change could potentially have an impact on the chosen prefix collision attack. (By hashing G_Y first in TH_2, A doesn't know the value of G_Y in the prefix when it sends c2 to R.)

[charlie-j]

It definitely makes sense, first for the reason you mention, and additionally because by reordering, we are breaking the fact that H(H(mess1),G_Y,C_R) = H( mess1 || C_Y || C_R) (which was due to the length extension).
So, I would expect at least one of the reorderings to completely solve the chosen prefix attacks. My best bet would probably be on: TH_2 = H(C_R, G_Y, H(message_1))

[emanjon]

To make this complete, there are 6 permutations. Where 1 is the the one in the current draft. 2-3 does not seems promising, and 4-6 is likely improvements.

1. TH_2 = H( H(message_1), G_Y, C_R )
2. TH_2 = H( H(message_1), C_R, G_Y )
3. TH_2 = H( C_R, H(message_1), G_Y )

4. TH_2 = H( G_Y, H(message_1), C_R )
5. TH_2 = H( G_Y, C_R, H(message_1) )
6. TH_2 = H( C_R, G_Y, H(message_1) )

[charlie-j]

If there is any of those orderings between 2 to 6 that would be preferable for any kind of reason, tell me and I'll run it by our tools.
You can also give an order of preference, and I'll run them by the tools until we get a secure one for chosen-prefix collisions.

[emanjon]

I think there are similar from an implementation perspective. Some thoughts from my collegue Erik Thormarker that suggested changing the order in the first place:

4-6 should all thwart the attack, since the unpredictable G_Y comes before any data passed from A to R.

I prefer having G_Y first if they’re the same implementation wise. Then it is most clear to see that it stops the attack since that relies on the unpredictability of G_Y, and it also aligns with Bernstein’s suggested best practice that whatever is most unpredictable should come first https://mailarchive.ietf.org/arch/msg/cfrg/GRigAYvZ8-Z8qmxJ1jOiKR8eLyQ/. Keeping G_Y and C_R together also looks more natural to me. So I like option 5 best.

[gselander]

Option 5 seems like a good option.

@charlie-j If this is easy for you to test, would you please try it out?

[charlie-j]

On it!

[charlie-j]

We don't find any attack due to chosen-prefix collisions after reordering with option 5.

I've looked at the draft and came up with a commit, the change does appear to be minimal and corresponds to a very small commit: charlie-j@79ea8aa

[gselander]

@charlie-j Indeed, this is a small commit, and it looks good. Please make a PR.

[sftcd]

On 12/04/2022 18:13, charlie-j wrote: A solution could indeed be to include inside the transcript `h(EAD)` instead of `EAD` when the actual value is overly long, but this comes at the cost of some performance.

I'd guess use of EAD would be atypical (but may be wrong there) in which case one would be adding h(NULL) which is a fixed string and avoids overhead. Be good to confirm if that's right/wrong.

[gselander]

I think this issue was resolved with option 5 above, which includes EAD_1 in h(message_1). So I don't see that h(EAD) need to appear separate, and wonder if the comment is still relevant? (Maybe I misunderstood something.)

[emanjon]

Reopened as there is discussion. Might close soon again

My understanding is that length restrictions such as h(EAD) are not needed after the order was changes to
TH_2 = H( G_Y, C_R, H(message_1) )

[charlie-j]

Yes, the order change solved it, length restrictions were just one of the options.

[emanjon]

Closing again.