Computational analysis of EDHOC STAT - improvement suggestions for K_3

[gselander]

Proposal to derive K_3 from PRK_4e3m instead of PRK_3e2m, to make K_3 dependent on the static key of the Initiator.

[charlie-j]

Wait... Isn' t that impossible? The responder needs to be able to decrypt message 3 in order to know G_I, and G_I is needed to compute PRK_4e3m. So the key K_3 used to decrypt message 3 cannot depend on G_I. Am I missing something?

[gselander]

I had the same comment. Please see slides 21ff in https://datatracker.ietf.org/meeting/114/materials/slides-114-lake-computational-analysis-of-edhoc-stat-stat-00

My interpretation was to partition PLAINTEXT_3 into, say,

PLAINTEXT_3A = ( ? PAD_3, ID_CRED_I / bstr / -24..23, ? EAD_3 )

PLAINTEXT_3B = Signature_or_MAC_3

KEYSTREAM_3A = EDHOC-KDF( PRK_3e2m, TBD, TH_3, plaintext_length ) K_3B = EDHOC-KDF( PRK_4e3m, TBD, TH_3, key_length ) IV_3B = EDHOC-KDF( PRK_4e3m, TBD, TH_3, iv_length )

CIPHERTEXT_3A = PLAINTEXT_3A XOR KEYSTREAM_3A

CIPHERTEXT_3B = AEAD encryption of PLAINTEXT_3B as is currently done in message_3, with K_3B/IV_3B and additional external_aad = PLAINTEXT_3A.

CIPHERTEXT_3 is the concatenation of CIPHERTEXT_3A and CIPHERTEXT_3B.

This would increase the size of message_3 with 1-2 bytes due to separate CBOR encoding of CIPHERTEXT_3A and CIPHERTEXT_3B.

I'm not sure this solves the problem though.

[emanjon]

Some quick thought on the PR and alternatives

OLD (draft-ietf-lake-edhoc-15)
AEAD ( PAD_3, ID_CRED_I, Signature_or_MAC_3, EAD_3 )

NEW ALT 1 (#325) (Adds 1-2 bytes)
ENC( PAD_3, ID_CRED_I, EAD_3 ) || AEAD( Signature_or_MAC_3 )

NEW ALT 2 (Adds 0 bytes)
ENC( PAD_3, ID_CRED_I, AEAD( Signature_or_MAC_3 ), EAD_3 )

NEW ALT 3 (Where mac_length_3 is inceased to a mimimum of at least 16 bytes) (Adds 0 bytes)
ENC( PAD_3, ID_CRED_I, Signature_or_MAC_3, EAD_3 )

In the SIGMA-I paper Krawczyk writes: "We stress that the encryption function (as applied in the third message) must be resistant to active attacks and therefore must combine some form of integrity protection."

ALT 1 uses IND-CPA encryption for PAD_3, ID_CRED_I, EAD_3 ALT 2 uses IND-CPA encryption for PAD_3, ID_CRED_I, EAD_3 ALT 2 uses IND-CPA encryption for PAD_3, ID_CRED_I, EAD_3, Signature_or_MAC_3

Needs to be analysed where authenticated encryption is needed. As pointed out be @charlie-j the suggested change weakenes the encryption of several fields.

[chrysn]

Constructions in which message_3 replaces the AEAD'd ID_CRED_I with one that is only XOR'd with a KEYSTREAM_3 could be problematic when it comes to attacks to reveal ID_CRED_I under very specific circumstances; https://github.com/lake-wg/edhoc/pull/325#issuecomment-1198352881 has details.

[emanjon]

As pointed out by Christian amsuss, identity protection against active attackers is a very important property. All the alternatives above only provides identity protection against passive attackers. Given that I don't think any of the discussed changes should be done. I think we do want identity protection against active attackers.

If 128-bit authentication is needed after message_3 then the best options seems to be to use a longer 16 bytes MAC_3. This is already included in some cipher suites but it always combined with 16 bytes MAC_2. One option would be to allow different lengths of MAC_2 and MAC_3, i.e. 8 byte MAC_2 and 16 byte MAC_3.

Not sure that 8 byte MAC_2 and 16 byte MAC_3 is worth specifying. Applications that want 128 byte authentication and are not restricted to 45 byte message_2 can use 16 byte MAC_2 and 16 byte MAC_3

[emanjon]

Summarizing some of the discussion in the PR

While CRED_I will eventually be integrity protected, implementing the whole processing of message_3 without side channels is hard. I don’t think we want to require that.

Also two different ID_CRED_I can according to COSE correspond to the same CRED_I so even an implementation without side channels would potentially leak info about the Initiator identity to an active attacker.

I think Krawczyk is correct in that the encryption needs to be AE.

A solution with two concatenated AEAD ciphertexts calculated using different keys seems possible but does not seem to have any advantages v compared to simply increase the length of MAC_3 in the current -15 solution.

[emanjon]

My current conclusion is that no changes should be done. Similar constructions was discussed in the past with similar conclusions. It is possible on a theoretical level with the assumption that all processing is done in one node and in constant-time. In practice the risks for side-channel attacks on confidentiality seems to big.

Another change could be to have different MAC lengths in message_2 and message_3 but this would likely only help in the analysed scenario where message_4 is used. Most deployments will not use message_4 so I don't think we should optimize for that.

Cipher suite 0,2 do provide the minimum security level that LAKE WG has agreed on (64 bit security against online attackers producing forged messages). Applications wanting 128 bit authentication can e.g. use cipher suite 1 or 3.

[gselander]

I agree with the conclusion, some additional high-level remarks:

1. The use of MACs in multiple messages to prove extended security level without increasing the message overhead, as shown by the team from ENS, is very promising. We should update the security considerations (after having understood the exact conditions) with the improved properties following a successfully verified message_4 and/or OSCORE message.

2. The particular change discussed here may not be the right trade-off. The proposed change is based on a reasoning about MAC length and security level, but those are not identical. Security level without further qualification may mean different things, but not uncommonly associated to offline attacks. The security consideration in Section 8.1 makes the intended security level more explicit:

Based on the cryptographic algorithms requirements (Section 8.3), EDHOC provides a minimum of 64-bit security against online brute force attacks and a minimum of 128-bit security against offline brute force attacks.

This formulation has been in the draft since -05 (Feb. 2021) without any comments so I assume none of the previous reviewers had any issue with this, neither with the property itself nor (to the best of current knowledge) its validity.

If this is correct, then the targeted security level of the protocol is reached. Improving this is of course welcome if the additional cost is small. But based on the comments above that doesn't seem to be the case. So it seems not to be a consensus to make the change.

@baptistecottier Any further comments are most welcome. It would be great if we could continue the discussion about 1. :-)

[baptistecottier]

In fact, what we have shown in our analysis is that the authenticated encryption in message_3 is in fact not authenticated as not relying on Initiator long-term credential. Hence, several solutions:

• Replace the authenticated encryption by an encryption -> less bytes communication with 64 bits Initiator authentication security
• Same as above but using a greater MAC size -> same message size but 128 bits initiator authentication security
• If authenticated encryption is needed, encrypt ID_CRED_I with classical encryption, and encrypt the remaining of the initial message with AEAD using a key derived from PRK_4e3m. -> 128 bits initiator authentication security with same message size and IND-CPA encryption (except for ID_CRED_I).

Hope it clarifies our work :).

[gselander]

@baptistecottier: The proposals you list unfortunately introduce some issues as discussed in #325, in particular a difficulty to implement identity protection securely, opening for timing side-channels.

If these concerns cannot be addressed I don’t think we have consensus for any of the proposals.

Another way to incorporate your input would be to maintain the current protocol and key schedule and add constraints or considerations that enables raising the theoretical level for online attack. For example:

A. Encourage the use of ciphersuite 1 and 3 instead of 0 and 2, respectively (mentioned above in this issue).

B. Define a ciphersuite with 8 byte MAC_2 and 16 byte MAC_3 (mentioned above in this issue)

C. Use the combined EDHOC and OSCORE message flow [1]. In this case the third flight from I to R contains two MACs: an OSCORE request containing EDHOC message_3. In other words a CoAP message where the payload contains

• message_3 (one MAC of minimum 64 bits)
• the OSCORE ciphertext calculated with an AEAD using a key obtained from EDHOC-Exporter, i.e. derived from PRK_out (another MAC of minimum 64 bits)

Edit: fixed the description where in the CoAP message the two MACs are located

One associated change in [1] is that EDHOC would need to be aborted in case the OSCORE MAC doesn’t verify. (Last paragraph before 3.3.1 of of [1]. That does not impact backward compatibility with OSCORE implementations in general since this processing is associated to the EDHOC option which is defined in that document.)

An OSCORE response (payload contains a ciphertext calculated with an AEAD using another key derived from PRK_out) as a fourth flight could provide additional properties in the other direction.

• Is it easy to prove that these measures provide added value in your metrics? This would be very valuable input to the current discussion.

Results on this topic can be absorbed as security considerations, for example the use of minimum 16 bytes MACs if possible in message_3 in case of STAT-STAT, or to use combined EDHOC / OSCORE in case of STAT-STAT with cipher suites 0 or 2.

[1] https://datatracker.ietf.org/doc/html/draft-ietf-core-oscore-edhoc

---

• Additionally, a separate comment about this:

In fact, what we have shown in our analysis is that the authenticated encryption in message_3 is in fact not authenticated as not relying on Initiator long-term credential

Note that the (Authenticated) Encryption is used in message_3 to give identity protection against attackers, not to authenticate the Initiator.

[gselander]

The argument with combined EDHOC / OSCORE message above could also be applied to the case with EDHOC message_3 and the application protocol message being separate messages. After message_3 has been verified by the Responder, the EDHOC context could be "put on hold" by the Responder (e.g. not persistently stored) pending the result of the verification of the application protocol message.

[gselander]

Closing this in favor of #340 as discussed in the interim.