Re: [Lake] Computational analysis of EDHOC Sig-Sig - improvement suggestions for transcript hashes

[John Mattsson <[e-mail]>]

Dear Marc and Felix,

Thanks you very much for your detailed analysis and feedback.

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.

I created an issue and a PR in the LAKE WG Github.

https://github.com/lake-wg/edhoc/issues/317
https://github.com/lake-wg/edhoc/pull/318

Cheers,
John

From: Lake <[e-mail]> on behalf of Ilunga Tshibumbu Mukendi Marc <[e-mail]>
Date: Friday, 8 July 2022 at 11:48
To: [e-mail] <[e-mail]>
Subject: [Lake] Computational analysis of EDHOC Sig-Sig - improvement suggestions for transcript hashes

Dear Mališa, dear all,

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<https://protect2.fireeye.com/v1/url?k=31323334-501cfaf3-313273af-454445554331-f6f777553d837518&q=1&e=eea177da-76f6-472b-9dd2-2652afccf5e1&u=https%3A%2F%2Feprint.iacr.org%2F2020%2F1044.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://protect2.fireeye.com/v1/url?k=31323334-501cfaf3-313273af-454445554331-507a7da6a666bbed&q=1&e=eea177da-76f6-472b-9dd2-2652afccf5e1&u=https%3A%2F%2Feprint.iacr.org%2F2020%2F823.pdf>