Computational analysis of EDHOC Sig-Sig - improvement suggestions for transcript hashes

[emanjon]

Following our last email and in preparation for the IETF 114, we would like to offer a suggestion from our computational analysis of EDHOC. I will first state the suggestion and then give some motivation and justification.

Suggestion: Include the authentication credentials in the transcript hash computation.

Namely, we suggest modifying the transcript hashes TH_3 and TH_4 to include the credential of the peer that authenticate themselves. More precisely, we propose that protocol participants compute:

TH_3 = H(TH_2, (PAD_2, G_Y, ID_CRED_R, SIGNATURE_2, EAD_2, C_R, CRED_R)) instead of
TH_3 = H(TH_2, (PAD_2, G_Y, ID_CRED_R, SIGNATURE_2, EAD_2, C_R))

Similarly, we propose that the computation of TH_4 becomes

TH_4 = H(TH_3, (PAD_3, ID_CRED_I, SIGNATURE_3, EAD_3, CRED_I)) instead of
TH_4 = H(TH_3, (PAD_3, ID_CRED_I, SIGNATURE_3, EAD_3))

The philosophy behind this proposal is to make explicit the identity of the peer that authenticated themselves, even if those identities are not sent. (One can think of this as expanding TH to include the actual identity credentials, which the sent ID_CRED values hint to but do not uniquely determine). This is to simplify arguing agreement on the communication peer.

Motivation and justification:

• We analysed EDHOC in the Multi-Stage Key exchange model, following the work [Dow21] of Dowling et al.

• We suggest the change above as an improvement towards ensuring explicit authentication, which we observed when analysing the following excerpt from the draft (draft-14, section 3.5.3):

  "As stated in Section 3.1 of [I-D.ietf-cose-rfc8152bis-struct], applications MUST NOT assume that 'kid' values are unique, and several keys associated with a 'kid' may need to be checked before the correct one is found. Applications might use additional information such as 'kid context' or lower layers to determine which key to try first. Applications should strive to make ID_CRED_x as unique as possible, since the recipient may otherwise have to try several keys."

We modelled the above statement conservatively and considered that any ID_CRED might reference multiple identities and associated credentials. A potential consequence of this modelling is that there may be ambiguity about the identity of the peer who authenticated themselves, which needs careful consideration. For instance, if ID_CRED_R refers to both CRED_R and CRED_R', the initiator that tries multiple public keys could conclude that it is talking to R'. If this occurs, the protocol would still come to completion since the transcript hash won't change.

The standard unforgeability notion of signature schemes would not necessarily prevent such a scenario [1], and our analysis relies on strictly stronger notions. Concretely we require that signature schemes in EDHOC provide explicit ownership. In our model and proof, we had to rely on the relatively strong notion of "Malicious Universal Exclusive Ownership" to capture explicit authentication for EDHOC as currently specified. To the best of our knowledge, M-S-UEO was only studied and proven for Ed25519 as implemented in Libsodium[Bre20]. Therefore, relying on a weaker notion, "Universal Exclusive Ownership", is desirable.

Adding the credentials in the transcript hash would prevent identity mis-binding attacks since divergence in the identity of the authenticated host would lead to diverging transcript hashes and, therefore, different derived keys. Furthermore, we can rely on weaker notions of explicit ownership from a proof standpoint. Fortunately, Ed25519 provides explicit ownership [Bre20], and [Po05] already showed that the inclusion of the credentials along with the message in the signing process, as is done already in EDHOC, provides explicit ownership and prevents ambiguity. For ECDSA, care must be taken in the implementation so that this construction guarantees exclusive ownership. Overall, we assume that CBOR encoding is unambiguous.

We would very much appreciate your feedback and thoughts on the discussion above, and we are happy to answer any questions you might have.

Kind regards,
Marc Ilunga (and Felix Günther)

[1] The need for a notion strictly stronger than standard EUF-CMA security for signature schemes also arises in the basic SIGMA protocol with the MAC under the signature. One needs that signature scheme is not only unforgeable for a random key but for all keys. Otherwise, an attacker may carry an identity mis-binding attack.
[Dow21] Dowling et al. "A Cryptographic Analysis of the TLS 1.3 Handshake Protocol", https://eprint.iacr.org/2020/1044.pdf
[Po05] Pornin and Stern, "Digital Signatures Do Not Guarantee Exclusive Ownership", https://link.springer.com/chapter/10.1007/11496137_10
[Bre20] Brendel et al. "The Provable Security of Ed25519: Theory and Practice", https://eprint.iacr.org/2020/823.pdf

https://mailarchive.ietf.org/arch/msg/lake/BTxPdJl0Z8ylSe1P7i0BFx1T_0o/

[charlie-j]

Hi!

When reading:

"As stated in Section 3.1 of [I-D.ietf-cose-rfc8152bis-struct], applications MUST NOT assume that 'kid' values are unique, and several keys associated with a 'kid' may need to be checked before the correct one is found. Applications might use additional information such as 'kid context' or lower layers to determine which key to try first. Applications should strive to make ID_CRED_x as unique as possible, since the recipient may otherwise have to try several keys."

I understood that a kid would map to multiple keys, but all of those keys would be owned by the same party. From what I understand, the attack described here only occurs when one kid maps to keys owned by distinct parties.
Which is the correct interpretation? And should the second case actually be allowed?

(I think the update proposed is no matter what a good idea though, it strictly improves things)

[emanjon]

My interpretation of COSE is that one kid might map to keys owned by distinct parties. Seems hard to guarantee anything about kids unless there is a single authority that controls all the kids. as soon as there are several authorities there might be collisions. That all the keys with a certain kid belongs to a single party would require that a single authority determines all the kids or that some additional header parameter like kid_context is used. I think the whole reason that kid_context was introduced was to separate between different authorities determining kids.

Maybe it would be good to clarify things in I-D.ietf-cose-rfc8152bis-struct

[emanjon]

(think the update proposed is no matter what a good idea though, it strictly improves things)

Thanks for this quick feedback!

[emanjon]

I sent a mail to COSE suggesting that this should maybe be clarified

https://mailarchive.ietf.org/arch/msg/cose/WfEA8SHlLtK8yxFxmrb0PiDnsys/

[charlie-j]

I am trying to precisely detail step by step the missbinding attack to understand how to improve our symbolic models and capture it, and I am not precisely able to. My first idea would require to be able to alter the signature under the xor, is this indeed the needed capability? Marc, could you give the details on how it would be carried out?

[emanjon]

Below is my mail to LAKE on the topic

Your suggested change seems like a relatively easy thing to do:

OLD: TH_3 = H(TH_2, PLAINTEXT_2)
NEW: TH_3 = H(TH_2, PLAINTEXT_2, CRED_R)

where

PLAINTEXT_2 = ( PAD_2, ID_CRED_R, Signature_or_MAC_2, EAD_2 )

and where the message to be signed is

[ "Signature1", << ID_CRED_R >>, << TH_2, CRED_R, ? EAD_2 >>, MAC_2 ]

where

MAC_2 = EDHOC-KDF( PRK_3e2m, 2, << ID_CRED_R, TH_2, CRED_R, ? EAD_2 >>, mac_length_2 )

(and similar for TH_4)

I have not read the papers you refer to yet but if I understand you correctly, the problem is that signature schemes in general provides quite weak properties and even if CRED_R is already included in MAC_2 and in the external_aad of the signature, that is not enough, i.e., depending on the signature scheme an attacker might be able to find two identities CRED_R and CRED_R' such that Signature_or_MAC_2 is the same for the two identities.

Does the issue only apply to authentication with signature keys or also to authentication with Static Diffie-Hellman keys?

This seems like a change we should do.

[emanjon]

I am trying to precisely detail step by step the missbinding attack to understand how to improve our symbolic models and capture it, and I am not precisely able to.
Seems hard to do something in practice as any change to CRED_R changes the 32 byte pseudorandom value MAC_2.

[emanjon]

The MAC-then-Sign version of SIGMA-I is proven to be secure. If the above attack is possible in EDHOC it seems interesting to make a comparision between EDHOC SIG-SIG and SIGMA-I:

• Is there any protocol differences beween EDHOC SIG-SIG and SIGMA?
• Is there different assumptions on the cryptographic functions or in the definition of "secure"?
• Is the SIGMA-I proof wrong?

[MarcIlunga]

Hi all,
Thanks for the feedback so far! I will try and answer the question raised above.
First of all, I realised we wrote several things in the email but let me reiterate the main points:

• The identity mis-binding attack that we presented (and that I will flesh out below) only applies the basic MAC-Then-SIGn version of SIGMA as described in https://link.springer.com/chapter/10.1007/3-540-45708-9_10. It served as a starting point to reason about the precise guarantees we need from the signature scheme.
• Fortunately: the actual instantiation in EHDOC seems to prevent the attack (thanks to including the credentials under the signature and not just the MAC. However, from a proof perspective, we are unable to properly show a reduction unless we assume even more about the signature schemes.
• The suggestion allows us to easily reduce the security to a weaker security notion that is likely provided by concrete use of the signatures in EDHOC.

Identity mis-binding attack on MAC-then-SIGn and unforgeability requirements.

The MAC-then-Sign version of SIGMA-I is proven to be secure. If the above attack is possible in EDHOC, it seems interesting to make a comparision between EDHOC SIG-SIG and SIGMA-I:

• Is there any protocol differences beween EDHOC SIG-SIG and SIGMA?
• Is there different assumptions on the cryptographic functions or in the definition of "secure"?
• Is the SIGMA-I proof wrong?

Indeed MAC-then-Sign is proven secure, but the attack concerns the particularity of having the MAC under the signature, which is not completely considered in the previous analysis. Quoting the above paper (https://link.springer.com/chapter/10.1007/3-540-45708-9_10):

Lemma 1. If sig is a secure signature scheme and mac is a secure message authentication function, then it is infeasible for an attacker to find different messages $M$ and $M'$ such that for a randomly chosen secret mac-key $k_1$ the attacker
can compute $SIG (MAC_k (M))$ even after seeing $SIG (MAC_k (M))$.

However, in the context of an identity mis-binding attack, we are concerned about the possibility of computing $\sigma = SIG( sk', MAC_k (M')) = SIG(sk, MAC_k (M))$. Where $sk'$ is adversarially chosen, which hints at Duplicate Signature Key Selection (DSKS)-like attacks. See: https://www.cryptologie.net/article/495/cryptographic-signatures-surprising-pitfalls-and-letsencrypt/

Based on the existing SIGMA analysis, the requirement for the signature scheme is unforgeability. Namely, the signature is unforgeable "on the average," i.e. for a random key. However, this does not exclude the possibility of "weak" keys, which are, for instance, a key pair $(sk, pk)$ such that $pk$ verifies any message and signature pair, i.e. $\forall m, \sigma: \mathrm{Vrf}(pk, m, \sigma) = true$. This notion of a "weak" key is not really necessary since the signature is still unforgeable.
If SIGMA is instantiated with such a pathological signature scheme, which is still unforgeable, then the attacker can carry an identity mis-binding that proceeds as follows:

• Alice -> Bob : $g^x$
• Bob -> Eve(interception) : $Bob, g^y, \sigma = SIG (sk_B, mac_B)$
• Eve : creates a special $(sk', pk')$
• E -> A : $Eve, g^y, \sigma$
• A -> B : $Alice , \sigma$
  In the end, Alice thinks she talks to Eve, and Bob thinks he talks to Alice.

Why doesn't this attack work on the "normal" SIGMA? With the MAC under the signature, peers do not have a notion of verifying a MAC and do so only implicitly via a successful signature verification. In the "normal" SIGMA, the MAC is explicitly verified; hence the attack above doesn't work even with a pathological signature scheme.

Obviously, EDHOC doesn't quite use such a pathological scheme; however, this shows that this case has to be carefully analysed, hence the suggestion for the transcript hashes.

[emanjon]

So does this identity misbinding attack mean that IKEv1 and IKEv2 does not provide authentication, aliveness, peer awareness, etc?

[MarcIlunga]

Hi @emanjon apologies for the delayed response, as I am coming towards the end of my thesis project I need to finalize my writing…
Anyhow, regarding IKE protocols, this is a good question… Ultimately, this would depend on the concrete instantiation of the signature scheme.
My fairly limited understanding of IKE is that the type of attack we describe above also apply. However, the adversary is likely to need to modify the communication transcript when injecting their certificate. This is where my limited knowledge of IKE limits what I can say about the actual impact. Perhaps, an attacker may abuse bit string representations to forge a certificate that seemingly does not modify the traffic on the wire?

From a theoretical perspective, at least, it appears that we require some notion of exclusive ownership to prove security of the MAc-then-SIGn, this also depends on how it is instantiated. The EDHOC instantiation seems to do the right thing.

[MarcIlunga]

@charlie-j, Also apologies for providing the requested details, late. I wondered whether you had the chance to analyze this issue and what results you get from your formal modeling.

[charlie-j]

Our model did in fact already cover such weak keys for signatures, and in the case of EDHOC such attack is impossible, from what I understand mostly because the attacker cannot perform a MiTM as it cannot compute the encryption keys of the multiple messages.

Only in message 2, which is not integrity protected, could the attacker hope to change the signature such that if it was able to go by xoring from the ID_CRED_R to an ID pointing to some weak key, the signature check would go through for some other identity. But then the hash transcript would change and the key exchange would never go further, as the initiator would then produce a message encrypted with a key that neither the attacker nor the reponder can compute.

[MarcIlunga]

Dear @charlie-j , thanks for the feedback and the insights on how your formal model captured weak keys.
I believe, however, that we are describing slightly different attacks. At a high level, the type of attack we consider does not really involve a PITM attack. In particular, the attack doesn't modify the transcript; hence nor do the transcript hash changes, or the key derived thereafter; at least as they are currently specified in draft 14.

More precisely, from the assumption that ID_CRED may hint at multiple credentials and associated public keys. The verification process would look something like the following pseudo-code(here for the initiator)

for (pk, id) in credentials[ID_CRED_R]:
   compute MAC_2 for id
   Verify SIGNATURE_2 with pk
   Set peer to id if verification succesful

If the adversary would register a specially weak key $pk*$ such that $pk* \in$ credentials[ID_CRED_R] and assuming that $pk*$ somehow gets precedence on the real $pk_R$ this attack would work if the signature scheme would be vulnerable.
Though we describe attacks on plaintext communication; this is cheating just shows that the attacker knows ID_CRED_R.
I hope this clarifies things a bit.
Marc

[charlie-j]

I did understand your attack, and I was trying to essentially lift the attack you are describing to one that does not require the multiple CRED_R for one ID_CRED_R assumption.

I was trying to do that, because under the multiple ID_CRED assumption, the authentication property becomes weird. If we ask for authentication over the ID_CRED and the attacker can register its own pk for an honnest ID_CRED, this already breaks authentication. If we ask for authentication over the pks, then in your attack, the initiator is simply using an attacker key, for which we have no guarantees, and it is thus not breaking the authentication property.

[MarcIlunga]

I did understand your attack, and I was trying to essentially lift the attack you are describing to one that does not require the multiple CRED_R for one ID_CRED_R assumption.

Apologies, I misunderstood the previous message.

But we had a similar observation if using unique ID_CRED. These attacks don't really work.
In the end, we could rely on strong universal exclusive ownership of the signature to show explicit authentication. Although we also had to tweak the explicit authentication guarantees slightly, the reduction would need something stronger than S-UEO. To the best of our knowledge, it is not provided by the signature. Maybe except Ed25519 if it is implemented according to the way Libsodium does it.

But adding the credentials to the transcript hashes strengthen the guarantees.

[charlie-j]

No worries, I was unclear.
We seem to agree overall!

[gselander]

No disagreement and the PR #318 is included in edhoc-16