Subject: Re: [Secdispatch] [Lwip] (protocol flows) Re: [Ace] EDHOC standardization

From: John Mattsson <[email-masked]>
Date: Mon, 18 Feb 2019 09:06:16 +0000

Hi Rene,

These are interesting ideas. As you say, EDHOC is currently optimized for a minimum number of messages and bytes. Spreading out the bytes and computations could be beneficial in some applications. EDHOC is currently based on SIGMA-I. The four-message variant would be based on SIGMA-R with basically the same security properties. The difference would be that SIGMA-I protects the initiator identity against active attackers and the non-initiator identity against passive attackers. SIGMA-R does the opposite. I think protection models are needed in practice, but could also be solved by letting the initiator telling the other party to start SIGMA-I.

Party U                                                       Party V
|              C_U, CIPHER_SUITEs_U, CIPHER_SUITE_U, X_U            |
+------------------------------------------------------------------>|
|                             message_1                             |
|                                                                   |
|                           C_U, C_V, X_V                           |
|<------------------------------------------------------------------+
|                             message_2                             |
|                                                                   |
|          C_V, AE(K_3; ID_CRED_U, Sig(U; CRED_U, aad_3) )          |
+------------------------------------------------------------------>|
|                             message_3                             |
|                                                                   |
|          C_U, AE(K_4; ID_CRED_V, Sig(V; CRED_V, aad_4) )          |
|<------------------------------------------------------------------+
|                             message_4                             |

I get the following message sizes for EDHOC when I apply SIGMA-R to
version -11 of EDHOC.

========================================================================
Flight                                #1      #2     #3     #4     Total
------------------------------------------------------------------------
DTLS 1.3 RPK + ECDHE                 150     373    213              736
DTLS 1.3 PSK + ECDHE                 187     190     57              434
DTLS 1.3 PSK                         137     150     57              344
------------------------------------------------------------------------
EDHOC RPK + ECDHE (SIGMA-I)           39     120     85              244
EDHOC RPK + ECDHE (SIGMA-R)           39      37     85     84       245
EDHOC PSK + ECDHE                     44      46     11              101
========================================================================

Regarding computations, I guess the main difference when it comes to asymmetrical crypto computations would be that Party V can compute a shared secret in between flight #2 and flight #3. Or are the any additional benefits?

SIGMA-I:

Party U                                                       Party V
                                                                    
generate a key pair
+-------------------------------#1--------------------------------->|
                          generate a key pair (can be done before #1)
                                              compute a shared secret
                                                                 sign
|<------------------------------#2----------------------------------+
compute a shared secret
verify
sign
+-------------------------------#3--------------------------------->|
                                                               verify

SIGMA-R:

Party U                                                       Party V
                                                                    
generate a key pair
+-------------------------------#1--------------------------------->|
                          generate a key pair (can be done before #1)
              compute a shared secret (can be done between #2 and #3)
|<------------------------------#2----------------------------------+
compute a shared secret
sign
+-------------------------------#3--------------------------------->|
                                                               verify
                                                                 sign
|<------------------------------#4----------------------------------+
verify

The optimization to split up the ECDSA Signature (R, S) and send R in the beginning is interesting, but as far as I understand, this only works for ECDSA and there is no similar trick for Ed25519 as both R and S depends on the message M.

SIGMA-I:

Party U                                                       Party V
|           C_U, CIPHER_SUITEs_U, CIPHER_SUITE_U, X_U, R_U          |
+------------------------------------------------------------------>|
|                             message_1                             |
|                                                                   |
|          C_U, C_V, X_V, AE(K_2; ID_CRED_V, R_U, S_U )             |
|<------------------------------------------------------------------+
|                             message_2                             |
|                                                                   |
|                  C_V, AE(K_3; ID_CRED_U, S_V )                    |
+------------------------------------------------------------------>|
|                             message_3                             |

SIGMA-R:

Party U                                                       Party V
|             C_U, CIPHER_SUITEs_U, CIPHER_SUITE_U, X_U, R_U        |
+------------------------------------------------------------------>|
|                             message_1                             |
|                                                                   |
|                        C_U, C_V, X_V, R_V                         |
|<------------------------------------------------------------------+
|                             message_2                             |
|                                                                   |
|                     C_V, AE(K_3; ID_CRED_U, S_U)                  |
+------------------------------------------------------------------>|
|                             message_3                             |
|                                                                   |
|                    C_U, AE(K_4; ID_CRED_V, S_V )                  |
|<------------------------------------------------------------------+
|                             message_4                             |

======================================================================================
Flight                                              #1      #2     #3     #4     Total
--------------------------------------------------------------------------------------
DTLS 1.3 RPK + ECDHE                               150     373    213              736
DTLS 1.3 PSK + ECDHE                               187     190     57              434
DTLS 1.3 PSK                                       137     150     57              344
--------------------------------------------------------------------------------------
EDHOC RPK + ECDHE (SIGMA-I)                         39     120     85              244
EDHOC RPK + ECDHE (SIGMA-R)                         39      37     85     84       245
EDHOC RPK + ECDHE (SIGMA-I)(ECDSA split S and R)    71     120     53              244
EDHOC RPK + ECDHE (SIGMA-R)(ECDSA split S and R)    71      69     53     52       245
EDHOC PSK + ECDHE                                   44      46     11              101
======================================================================================

I think these are interesting discussion topics. I will make an issue about them on GitHub.

Cheers,
John

Rene Stuik <[email-masked]>; wrote:

>Hi John:
>
>When comparing protocols, it would be useful to protocol flows 
>optimization, as follows:
>a) optimized for parallelized online computations;
>b) optimized for minimization of message flows.
>See also slide 6 of my CFRG-83 presentation of March 30, 2012 
>(slides-83-cfrg-05 attached; I could not find CFRG records online).
>
>The current draft-selander-ace-cose-ecdhe-10 document considers 
>optimization b), which minimizes the number of message flows, but does 
>require each party to compute the shared key consecutively, rather than 
>in parallel (as in optimization a).
>
>With option a), if one really wishes to squeeze as much info into a 
>128-octet datagram, one can already send A's ephemeral ECDSA signature 
>key in message flow 1, thereby cutting down the
>size of the second message flow of the Sigma protocol depicted in Fig. 1 
>(https://tools.ietf.org/html/draft-selander-ace-cose-ecdhe-10#page-11) 
>by 32 octets. This tackles the 120-octet byte count for the second flow 
>of Fig. 1 quite simply, while leading to a 4-pass protocol flow (with 
>roughly 70/70/55/55 bytes in flows 1/2/3/4).
>
>Obviously, this presents a trade-off, but quite well be worth it in 
>settings where online key computations are quite slow on some platforms 
>and where scheduling (e.g., with TSCH) can now be done with less 
>consideration of the individual computational capabilities of devices 
>(since now one does not need to build-in a worst-case 2 x "key 
>computation back-off" for least capable devices, but can just use the 1x 
>contingency for this).
>
>The parallel version is depicted below.
>
>Party U Party V | C_U, X_U, ALG_1, UAD_1, R_Sig(U;...) | 
>+--------------------------------------------------------------------->| 
>| message_1 | | | | C_U, C_V, X_V, ALG_2, R_Sig(V; ...) | 
>|<---------------------------------------------------------------------+ 
>| message_2 | | | | S_U, AEAD(K_3; ID_CRED_U, s_Sig(U; CRED_U, aad_3), 
>PAD_3) | 
>+--------------------------------------------------------------------->+ 
>| message_3 |
>| | | S_V, AEAD(K_2; ID_CRED_V, s_Sig(V; CRED_V, aad_2), UAD_2)| | 
>+<---------------------------------------------------------------------| 
>| message_4 | 
>============================================================================>== 
>
>
>Flight                                #1         #2        #3    #4 	Total
>---------------------------------------------------------------------------->--
>DTLS 1.3 RPK + ECDHE                 143        364       212     -   	721
>TLS 1.3  RPK + ECDHE                 129        322       194     -   	645
>EDHOC    RPK + ECDHE                  37        120        85     -   	242
>--> EDHOC parallel flow		      70         70        55     55    250