1 Introduction

The Extended Access Control (EAC) protocol establishes an authenticated key between a client’s smart card (also called chip in this context) and a server (or, terminal) over a public channel. For this, both parties run a sophisticated Diffie-Hellman key exchange protocol in which either party deploys its certified long-term key. While originally deployed in the German identity card systems [10] and referenced by the International Civil Aviation Organization for machine readable travel documents [24], the EAC protocol is increasingly adopted as a potent solution in related scenarios, for example to secure transactions [29] and for attribute-based physical access control with smart cards [28].

Especially for access control, if deployed in situations where user experience hinges on fast response times, reducing the latency is important. A concrete example, as discussed in a FIPS 201-2 workshop in 2015 [19], is turnstile access in subway stations. This requirement has led for instance to the development of the ISO/IEC 24727-6 and ANSI 504-1 standardized “Open Protocol for Access Control Identification and Ticketing with privacY” (OPACITY) for smart cards [33], which uses persistent binding for speeding up the key generation process. Unfortunately—and also underlining the importance of rigor—OPACITY has been shown to display cryptographic weaknesses [15].Footnote 1

In this paper we show that the EAC protocol can be augmented by a low-latency mode, called zero round-trip time (0RTT). This mode enables efficient re-establishment of secure channels for returning clients. A rigorous security proof for the resulting augmented protocol completes the enhancement. We emphasize that the design choices of the original EAC protocol are beyond our discussion here. Our goal is to show that a 0RTT version can be implemented based on the existing infrastructure.

1.1 Striving for Zero Round-Trip Time

The EAC protocol consists of two connected phases, the terminal authentication (TA), followed by the chip authentication (CA). Both steps require only a small number of message exchanges to establish a session key. At the same time, recent efforts in the area of key exchange protocols aim at modes of operations which allow for even faster data delivery. More precisely, it should be possible for a party to re-use cryptographic data from a previous connection to derive a fresh session key without further interaction, thus allowing the party to transmit data immediately. Such a mode is called zero round-trip time (0RTT).

The first proposal for a 0RTT-supporting protocol came from Google with its QUIC protocol [20]. The 0RTT mode allows the client to send data to a known server without having to wait for the server’s response. This idea was then quickly adopted for the drafts of the new TLS version 1.3, and has been included in the latest drafts in various versions [30,31,32]. Even on a network layer level, the Windows Networking Team recently announced to support 0RTT for TCP connections in order to reduce latency (see [11] for TCP Fast Open description).

The rough idea of the approach taken by QUIC and TLS (for the Diffie-Hellman version [30])Footnote 2 is that, upon the first encounter, the server also sends a semi-static public key \(g^s\) as part of the authenticated key exchange. Unlike an ephemeral key, which is used only within a single session, and a long-term key which spans over a large amount of sessions, such a semi-static key is valid for a very limited time only. This time period may range from a few seconds to a couple of days. In particular, the semi-static key may be used in multiple sessions.

The next time the client contacts the server, the client may combine a fresh ephemeral key \(g^c\) with the server’s semi-static key \(g^s\) to immediately compute a Diffie-Hellman key \(g^{cs}\) and derive an intermediate session key. The client can now send \(g^c\) and already deliver data secured under the intermediate session key, without round trip. For both QUIC and TLS the parties then continue the key exchange protocol to switch to full session keys.

It is obvious that the non-interactive derivation of the 0RTT session key comes at a price in terms of security: Since the server cannot contribute to such a key in a per-session manner, an adversary can replay the client’s protocol message and data to the server. This is inevitable, but accepted by the designers of QUIC and TLS 1.3 as worthwhile to achieve the desired level of efficiency.

1.2 Contribution

As briefly mentioned before, we show that the EAC protocol can also be augmented to support a 0RTT mode. Interestingly, the extension can be added on top with minimal changes to the original protocol. As in the proposal of QUIC and TLS 1.3 we let the terminal include an additional semi-static key \(\textit{pk}_T^\textsf {semi}\) in the regular EAC execution. The key is transmitted as part of the auxiliary data field of the original EAC description, and is thus also authenticated through the terminal’s signature in the TA phase.

In the full run of the EAC protocol the semi-static key is still ignored for the session key derivation. Instead, and as in the original EAC description, the chip then receives the terminal’s ephemeral key and derives a session key from its certified long-term key and this ephemeral key. The client authenticates through a message authentication code under the session key. In this regard, the slightly modified protocol complies with the original EAC protocol, using the auxiliary data field to transfer an additional key.

If a chip later wants to reconnect to a terminal for which it already holds the semi-static key, it only runs the CA phase again. But instead of receiving a fresh ephemeral key from the terminal, it uses the semi-static key to build the session key. Note that the semi-static key is already authenticated through the previous execution of the EAC protocol. Omitting the transmission of the terminal’s ephemeral key turns this step into a non-interactive protocol.

A straightforward idea to improve efficiency further may be to use the terminal’s ephemeral key once more for 0RTT, instead of using the semi-static key. The downside is that the terminal would need to store all ephemeral keys in a certain time frame. This is why, both we here as well as TLS [30], use semi-static keys instead. Nonetheless we discuss some potential variations of our basic designs in Sect. 4.

We then show that our EAC+0RTT protocol, which consists of the (augmented) EAC protocol run followed by any number of subsequent 0RTT EAC protocol executions, meets the common security properties of an authenticated key exchange protocol.

But we, of course, need to account for the possibility of replay attacks on the 0RTT data. Furthermore, it is convenient to model the possibly many 0RTT EAC handshakes following a single EAC execution in a so-called multi-stage setting. To this end we adopt the multi-stage extension of the Bellare-Rogaway model in [17].

The proof of security for the EAC+0RTT protocol does not rely on previous results. Nevertheless, we wish to mention the many security analyses of the German identity card protocols and certain eIDAS extensions [2,3,4,5, 13, 14, 22, 23, 27]. Also, we remark that general approaches to build low-latency protocols such as [21] cannot be applied in the context of the EAC protocol without major changes to the protocol.

2 Protocol Description

We next present the Extended Access Control protocol and its extension to support 0RTT. The 0RTT extension should be seen as a particular mode or sub protocol which co-exists with the original EAC protocol. In particular, many instances of 0RTT EAC may follow a single full EAC protocol run (until \(\textit{pk}_T^\textsf {semi}\) changes, in which case the terminal will most likely reject).

2.1 The Extended Access Protocol

The Extended Access Control protocol establishes a secure channel between a chip and a terminal. It is divided in two phases: the Terminal Authentication (TA) and Chip Authentication (CA) as depicted in Fig. 1. We integrate the 0RTT EAC protocol to the existing EAC protocol smoothly by using the pre-specified auxiliary data field in which any data can be sent in an authenticated manner to the chip during the TA phase. The auxiliary data field has originally been included to pass further information to the chip such as the current date, and the original EAC protocol ignores any such data if sent under an unknown object identifier. In our case, the terminal can utilize this field to transmit its semi-static key \(\textit{pk}_T^\textsf {semi}\) to the chip to enable future 0RTT EAC executions.

Terminal Authentication. The terminal authentication lets the chip C verify the terminal T’s identity and its permissions to access sensitive data. This is achieved via the certificate \(\textit{cert}_T\) held by T. This certificate contains not only the terminal’s signed public key but also its granted access rights. We assume that each certificate \(\textit{cert}\) contains some unique identifier \(\textit{certID}\) which can either be the serial number or an identifier like CertID or CertUID, and that \(\textit{certID}\) allows to determine the user identity. Furthermore, as mentioned earlier, the terminal authentication can be used to distribute the terminal’s public semi-static key to the chip, thereby permitting future 0RTT EAC executions.

Fig. 1.
figure 1

Terminal Authentication (TA) and Chip Authentication (CA). All operations are modulo q resp. over the elliptic curve. The gray part shows the 0RTT support inserted in the (optional) auxiliary data field.

Full size image

In a first step, the terminal sends its certificate for verification to the chip, which can then either abort, in case of an invalid certificate, or proceed by extracting the terminal’s public key \(\textit{pk}_T\) from the valid certificate. If the session was not aborted by C, T generates its ephemeral key pair \((\textit{epk}_T,\textit{esk}_T)\) and sends the compressed version of the ephemeral key \(\textit{epk}_T\) to C. This initiates a challenge-response mechanism. The chip replies with a nonce \(r_C\) chosen uniformly at random. The terminal authentication is complete, if the chip can then successfully verify the received signature \(s_T\leftarrow \textsf {Sig}(\textit{sk}_T,\textit{id}_C||r_C||\mathsf {Compr}(\textit{epk}_T) ||\textit{pk}_T^\textsf {semi})\) over the chip’s identity, chosen nonce and the compressed ephemeral key. Depending on whether the terminal offers support for 0RTT executions, the signature may contain the terminal’s semi-static public key \(\textit{pk}_T^\textsf {semi}\).

Chip Authentication. In the second part of the EAC protocol, the chip is authenticated to the terminal and a session key for subsequent encrypted and integrity-protected communications between chip and terminal is established. The chip transmits its credentials to the terminal and receives in response the ephemeral public key \(\textit{epk}_T\) (if the terminal did not abort due to an invalid certificate). After checking \(\textit{epk}_T\) against the compressed value received during the TA phase, the chip can compute the Diffie-Hellman value k from \(\textit{epk}_T\) and its own long-term secret key \(\textit{sk}_C\). Together with a uniformly random value \(r_C'\), the DH value k is used to derive an encryption key \(K_\text {enc}\), as well as two authentication keys \(K_\text {mac}, K_\text {mac}'\).Footnote 3 For final authentication, the chip uses \(K_\text {mac}'\) to compute a tag \(\tau \) over the ephemeral public key of the terminal. The tag is then transmitted to the terminal, alongside the random value \(r_C'\) used in the key derivation. The terminal is now able to derive the DH key k and subsequently the keys \((K_\text {enc},K_\text {mac},K_\text {mac}')\), where the session key \(\mathsf {K}\) is given by \((K_\text {enc},K_\text {mac})\). The terminal aborts the CA phase prematurely if it is not able to verify \(\tau \). Otherwise the session identifier and partner identifier are generated on both sides. If C has received a semi-static key, it saves this key along with the terminal’s certificate \(\textit{cert}_T\) for further reference. The EAC protocol execution is completed successfully if both parties terminate in accepting state.

2.2 The 0RTT EAC Protocol

Figure 2 shows the modified protocol supporting 0RTT between a chip C and a terminal T. The chip now holds additional information in form of the semi-static public key \(\textit{pk}_T^\textsf {semi}\), which it obtained during a previous EAC protocol interaction with T. In the 0RTT extension of the EAC protocol, C and T perform the following actions, corresponding to a non-interactive version of the CA protocol since the \(\textit{pk}_T^\textsf {semi}\) is used instead of \(\textit{epk}_T\). Thus, the extra communication round in the CA protocol in which T sends the (uncompressed) ephemeral key becomes obsolete.

At first, the chip C picks a random nonce \(r_C''\) and computes the DH shared value \(\textit{k}= \text {DH}_{D_C}(\textit{sk}_C,\textit{pk}_T^\textsf {semi})\). Using these two values, C then derives the keys \((K_\text {enc},K_\text {mac},K_\text {mac}')\) where, as in the EAC protocol, \(K_\text {mac}'\) is an additional authentication key used internally in the 0RTT EAC key exchange (see [14] for a discussion). The session key is then given by \(\mathsf {K}= (K_\text {enc},K_\text {mac})\). Finally, C computes the MAC-value over the semi-static public key

$$\begin{aligned} \tau = \textsf {MAC}(K_\text {mac}',\textit{pk}_T^\textsf {semi}) \end{aligned}$$

and sends its first (and only) flight of data to T consisting of

  • the authentication token \(\tau \),

  • the previously chosen nonce \(r_C''\),

  • its public key \(\textit{pk}_C\), as well as its certificate \(\textit{cert}_C\),

  • the domain parameter \(D_C\), and

  • early application data encrypted under the previously derived key.

Upon receiving the chip’s message, T verifies the validity of \(\textit{pk}_C\) and \(\textit{cert}_C\), and aborts if the verification is unsuccessful. Otherwise, T uses the public key, its semi-static secret \(\textit{sk}_T^\textsf {semi}\) and the random nonce \(r_C''\) to derive \(K_\text {mac}'\) and the 0RTT EAC session key \(\mathsf {K}\). T can then check the validity of the authentication token \(\tau \) and aborts if the tag cannot be verified. If \(\tau \) is valid, T decrypts the attached early application data. This completes the 0RTT EAC execution.

If the terminal does not support 0RTT, or the semi-static key provided by the chip is outdated or otherwise invalid, the process is aborted and the chip must initiate a fresh execution of the full EAC protocol in order to establish an authenticated secure channel with the terminal. There are, of course, several conceivable ways to recover from failures in the 0RTT handshake. Possible alternatives are described in Sect. 4.3.

Fig. 2.
figure 2

0RTT EAC. All operations are modulo q resp. over the elliptic curve. Note that the fields \(\mathsf {sid}\) and \(\mathsf {pid}\) are used within the security proof and describe partnered sessions and intended communication partners.

Full size image

2.3 Discussion

As mentioned before, the design choices of the original EAC protocol are beyond our discussion here. We demonstrated that a 0RTT version can be implemented based on the existing infrastructure. In particular, it is important that such a solution is “non-invasive” in the sense that it does not require major changes to the existing protocol but is added “on top”. Of course, any extension brings some modifications, e.g., in our case both the chip and the terminal must now implement the 0RTT EAC protocol and store semi-static keys. Yet, our proposal for the augmented EAC protocol complies with the original EAC description by using the auxiliary data field for the semi-static key. Furthermore, the 0RTT mode is identical to the plain execution of the CA phase, only that the semi-static key identifier is used instead of the one for the ephemeral key.

We also stress that we do not comment on the security-efficiency trade-off concerning 0RTT modes, but rather offer the option to have such a mode for the EAC protocol in principle. Whether chips and terminals eventually support this mode and tolerate for example the replay problem, is case dependent. Still, the examples of QUIC and TLS 1.3 indicate that, from an engineering perspective, the desire to have such modes exists, and we provide a potential technical solution for EAC.

Finally, let us point out that 0RTT transfers inherently include the small risk that the transmitted data cannot be recovered by the receiver, e.g., if the receiver has switched the semi-static key in the meantime. For common client-server scenarios the client may thus have to re-transmit the data. This problem is often outweighed by the efficiency gain in the regular cases. For smart card applications it may be preferable to have the terminal first signal its support of 0RTT and to communicate the current identifier of the semi-static key, thus saving the card from performing unnecessary operations. This can be done with the transmission of the certificate in the first step of the TA protocol, allowing the card to decide which mode to execute. Strictly speaking, this would effectively support a “lightweight 1RTT” protocol mode, still with significant efficiency advantages.

3 Overview over Security Analysis

Due to space restrictions we only give a brief overview over our security results. A comprehensive description of the model and the complete security proofs are available in the full version [6].

3.1 Game-Based Approach

The main theorem (Theorem 2) is proven by a technique commonly referred to as game-hopping. The proof is organized as a finite sequence of games \(G_0, G_1, \dots , G_k\) which are played between a challenger and an adversary. Informally, the transitions from one game to the next are small changes to the environment in which the adversary is situated, leading from a position where the winning probability of the attacker is unknown (game \(G_0\)) to a situation where this probability can be determined (game \(G_k\)). The overall goal is to bound the adversary’s advantage in winning the original security game \(G_0\) by the inverse of any polynomial in the security parameter.

3.2 Security Model

The security model is situated within the game-based approach of Bellare and Rogaway (\(\mathsf {BR}\) model) [1] in which an adversary with full control over the network, must be able to distinguish real session keys from independently drawn keys. To this end, the adversary can interact with protocol participants and instances via oracles. Details on these queries follow shortly.

A single execution of EAC between a chip and a terminal may be followed by multiple 0RTT handshakes between the parties. To model this situation, we adopt the notion of multi-stage key exchange as originally introduced in the related QUIC analysis of Fischlin and Günther [17]. This extension of the \(\mathsf {BR}\) model allows for multiple keys to be established within a single session. As opposed to the multi-stage setting encountered in e.g. QUIC, we can make use of a simplified setting here, since no key derived within a session is used to secure communications in further stages of the same session. Thus, all keys derived in a single session can be seen as independent.

Adversarial Interaction. To initiate a new session the adversary can call the \(\mathsf {NewSession}\) oracle, which takes a label to determine which of the two modes (full EAC or 0RTT EAC) to execute. The adversary can query the \(\mathsf {Send}\) oracle to send protocol message to an instance, immediately getting the party’s reply in return. The adversary is furthermore permitted to learn the long-term secret keys of parties through a \(\mathsf {Corrupt}\) oracle. Leakage of session keys and semi-static secret keys, which are used to derive 0RTT session keys, is modeled through \(\mathsf {Reveal}\) and \(\mathsf {RevealSemiStaticKey}\) queries, respectively.

To engage with the \(\mathsf {BR}\) game (cf. Definition 2), the adversary may perform \(\mathsf {Test}\) queries for some session(s) of the protocol, resulting in either the receipt of the corresponding session key or of an independently and uniformly chosen key, the choice made at random. In order to win the game, the adversary must now distinguish which kind of key it received.

Freshness of Session Keys. In order to avoid trivial attacks, some restrictions concerning the \(\mathsf {Test}\) queries apply. Foremost, the party of a tested session must not be corrupt, or else the adversary is trivially able to compute the session key. Analogously, neither the tested session key may have been revealed to the adversary nor the party’s semi-static secret key in case of the 0RTT mode. Since both communication parties are supposed to derive the same session key in a key exchange protocol, we must also rule out similar trivial attacks on the communication partner of a tested session. To keep track if one of these cases has occurred, a flag \(\mathsf {lost}\) is introduced with initial value \(\mathsf {false}\). Here, communication partners are usually identified through session identifiers which determine sessions belonging together.

Security Definitions. We follow the approach of Brzuska et al. [8, 9], and Fischlin and Günther [17], and separate the required security properties into \(\mathsf {Match}\) security and \(\mathsf {BR}\) security. The conditions on \(\mathsf {Match}\) security guarantee that the session identifiers enable the correct identification of partnered sessions, while partner identifiers \(\mathsf {pid}\) reflect the correct intended communication partners. \(\mathsf {Multi\text {-}Stage}~\mathsf {BR}\) security refers to Bellare-Rogaway-like key secrecy as discussed above, demanding that for each stage, session keys appear to be fresh random keys.

The subsequent analysis of the EAC+0RTT protocol is based on the following security notions as described in [16] and adapted to our particular setting:

Definition 1

( \(\mathsf {Match}\) security). Let n be the security parameter. Furthermore let \(\mathsf {KE}\) be a key exchange protocol and let \(\mathcal {A}\) be a PPT adversary interacting with \(\mathsf {KE}\) in the following game \(G_{\mathsf {KE},\mathcal {A}}^{\mathsf {Match}}(n)\):  

Setup.:

The challenger generates long-term public/private-key pairs with certificates for each participant \(U \in \mathcal {U}\).

Query.:

The adversary \(\mathcal {A}\) receives the generated public keys and has access to the queries \(\mathsf {NewSession}\), \(\mathsf {NewSemiStaticKey}\), \(\mathsf {Send}\), \(\mathsf {Reveal}\), \(\mathsf {RevealSemiStaticKey}\), and \(\mathsf {Corrupt}\).

Stop.:

At some point, the adversary stops with no output.

  We say that \(\mathcal {A}\) wins the game, denoted by \(G_{\mathsf {KE},\mathcal {A}}^{\mathsf {Match}}(n) = 1\), if at least one of the following conditions holds:

  1. 1.

    There exist two labels \(\mathsf {label}\), \(\mathsf {label}'\) and stages \(i,j \in \{1,\dots ,M\}\) such that \((\mathsf {label},i)\ne (\mathsf {label}',j)\) but \(\mathsf {sid}_i = \mathsf {sid}_j' \ne \bot \), \(\mathsf {label}.stage \ge i\), \(\mathsf {label}'.stage \ge j\) and \(\mathsf {st_{exec,{ i}}}\) \(\ne \mathsf {rejected}\), and \(\mathsf {st_{exec,{ j'}}}\) \( \ne \mathsf {rejected}\), but \(\mathsf {K}_i \ne \mathsf {K}'_i\). (Different session keys in partnered sessions, either within the same session at different stages or across two sessions.)

  2. 2.

    There exist two labels \(\mathsf {label}\), \(\mathsf {label}'\) such that \(\mathsf {sid}_i = \mathsf {sid}_j' \ne \bot \) for some stages \(i,j \in \{1,\dots \mathsf {M}\}\), \(\mathsf {role}= \mathsf {initiator}\), and \(\mathsf {role}' = \mathsf {responder}\), but \(\mathsf {label}.\mathsf {ownid}\ne \mathsf {label}'.\mathsf {pid}\) or \(\mathsf {label}.\mathsf {pid}\ne \mathsf {label}'.\mathsf {ownid}\). (Different intended partner.)

  3. 3.

    There exist at least three labels \(\mathsf {label}, \mathsf {label}'\) and \(\mathsf {label}''\) and stages i, j, k such that \((\mathsf {label},i)\), \((\mathsf {label}',j)\), \((\mathsf {label}'',k)\) are pairwise distinct, but \(\mathsf {sid}_i = \mathsf {sid}'_j = \mathsf {sid}''_k \ne \bot \) and for any two of the three sessions with role \(\mathsf {responder}\) and mode \(\textsf {0RTT}\) it holds that the owners are distinct. (More than two sessions share a session id for some stage and this event was not caused by a simple replay attack on the 0RTT protocol for the same responder.)

We say \(\mathsf {KE}\) is \(\mathsf {Match}\) -secure if for all PPT adversaries \(\mathcal {A}\) the following advantage function is negligible in the security parameter n: \(\mathsf {Adv}_{\mathsf {KE},\mathcal {A}}^{\mathsf {Match}} := \Pr \left[ G_{\mathsf {KE},\mathcal {A}}^{\mathsf {Match}}(n) = 1 \right] \).

Definition 2

(BR Key Secrecy). Let n be the security parameter. Furthermore let \(\mathsf {KE}\) be a key exchange protocol with key distribution \(\mathcal {D}\) and let \(\mathcal {A}\) be a PPT adversary interacting with \(\mathsf {KE}\) in the following game \(G_{\mathsf {KE},\mathcal {A}}^{\mathsf {BR},\mathcal {D}}(n)\):  

Setup.:

The challenger generates long-term public/private-key pairs and certificate for each participant \(U \in \mathcal {U}\), chooses the test bit  at random, and sets \(\mathsf {lost}\leftarrow \mathsf {false}\).

Query.:

The adversary \(\mathcal {A}\) receives the generated public keys and has access to the queries \(\mathsf {NewSession}\), \(\mathsf {NewSemiStaticKey}\), \(\mathsf {Send}\), \(\mathsf {Reveal}\), \(\mathsf {RevealSemiStaticKey}\), \(\mathsf {Corrupt}\), and \(\mathsf {Test}\).

Guess.:

At some point, \(\mathcal {A}\) stops and outputs a guess \(b_{\mathsf {guess}}\).

Finalize.:

The challenger sets the ‘lost’ flag to \(\mathsf {lost}\leftarrow \mathsf {true}\) if there exist two (not necessarily distinct) labels \(\mathsf {label}\), \(\mathsf {label}'\) and stages \(i,j \in \{1,\dots ,\mathsf {M}\}\) such that \(\mathsf {sid}_i = \mathsf {sid}'_j\), \(\mathsf {label}.\mathsf {st}_{\mathsf {key},i} = \mathsf {revealed}\), and \(\mathsf {label}'.\mathsf {tested}j = \mathsf {true}\). (Adversary has tested and revealed the key in a single session or in two partnered sessions.)

  \(\mathcal {A}\) wins the game, denoted by \(G_{\mathsf {KE},\mathcal {A}}^{\mathsf {BR},\mathcal {D}} = 1\), if \(b_{\mathsf {guess}}= b_{\mathsf {test}}\) and \(\mathsf {lost}= \mathsf {false}\). We say that \(\mathsf {Multi\text {-}Stage}~\mathsf {BR}\) key secrecy holds for \(\mathsf {KE}\) if for all PPT adversaries \(\mathcal {A}\) the advantage function

$$\begin{aligned} \mathsf {Adv}_{\mathsf {KE},\mathcal {A}}^{\mathsf {BR},\mathcal {D}}(n) := \Pr \left[ G_{\mathsf {KE},\mathcal {A}}^{\mathsf {BR},\mathcal {D}}(n) = 1 \right] - \frac{1}{2} \end{aligned}$$

is negligible in the security parameter n. A key exchange protocol \(\mathsf {KE}\) is further called \(\mathsf {Multi\text {-}Stage}~\mathsf {BR}\) -secure if \(\mathsf {KE}\) is both \(\mathsf {Match}\)-secure and \(\mathsf {BR}\) key secrecy for \(\mathsf {KE}\) holds.

We note that the winning conditions are independent of the forward secrecy property of the \(\mathsf {KE}\) protocol. Forward secrecy is already taken into account in the formulation of the \(\mathsf {Reveal}\) and \(\mathsf {Corrupt}\) queries and the finalization step of the game.

3.3 Cryptographic Assumptions

In the following we will provide definitions of the basic cryptographic assumptions underlying the security proof of the EAC+0RTT protocol. In particular, we introduce a double-sided (or symmetric) variant of the \(\mathsf {PRF}{\text {-}}\mathsf {ODH}\) assumption, further referred to as \(\mathsf {mmPRF}{\text {-}}\mathsf {ODH}\). We start by recalling what it means for signatures and certificates to be existentially unforgeable under chosen message attacks:

Definition 3

( \(\mathsf {EUF{\text { -}}CMA}\) assumption). Let n be the security parameter. Furthermore let \(\mathcal {S}= (\textsf {SKG},\textsf {Sig},\textsf {SVf})\) be a signature scheme and let \(\mathcal {A}\) be a PPT algorithm. We define the following \(\mathsf {EUF{\text { -}}CMA}\) security game \(G_{\textsf {Sig},\mathcal {A}}^{\mathsf {EUF{\text { -}}CMA}}(n)\):

 

Setup.:

Generate a key pair and give \(\textit{pk}\) to the adversary \(\mathcal {A}\).

Query Phase.:

In the next phase \(\mathcal {A}\) can adaptively query messages \(m_1, m_2, \dots ,m_q \in \{0,1\}^*\) with \(q \in \mathbb {N}\) arbitrary, which the signing oracle answers with \(\sigma _1\leftarrow \textsf {Sig}(\textit{sk}, m_1), \sigma _2\leftarrow \textsf {Sig}(\textit{sk}, m_2), \dots , \sigma _q\leftarrow \textsf {Sig}(\textit{sk},m_q)\).

Output.:

At some point, \(\mathcal {A}\) outputs a message \(m^*\) and a potential signature \(\sigma ^*\). Output 1 iff \(\textsf {SVf}(\textit{pk},m^*,\sigma ^*) = 1\) and \(m^*\ne m_i\) for all \(i=1,2,\dots ,q\).

 

We define the advantage function

$$\begin{aligned} \mathsf {Adv}_{\mathcal {S},\mathcal {A}}^{\mathsf {EUF{\text { -}}CMA}}(n):= & {} \Pr \left[ G_{\textsf {Sig},\mathcal {A}}^{\mathsf {EUF{\text { -}}CMA}}(n) = 1 \right] \end{aligned}$$

We say that a signature scheme \(\mathcal {S}\) is \(\mathsf {EUF{\text { -}}CMA}\) secure, if for any \(\mathcal {A}\) the advantage function is negligible (as a function in n).

The definitions for certification schemes work analogously. That is, a certification scheme consists of three algorithms \(\mathcal {C}=(\textsf {CKG},\textsf {CA},\textsf {CVf})\) for creating the authority’s key pair, the certification of a public key, and for verifying a public key with respect to a certificate. We allow for multiple certifications of the same public key but assume that each certification requests is accompanied by an identifier \(\mathsf {id}\) which will be included in \(\textit{certID}\). Then we can define unforgeability as for signatures, implying that the adversary cannot forge a valid certificate for a new public key or for a previously certified key under a new identity. We write \(\mathsf {Adv}_{\mathcal {C},\mathcal {A}}^{\mathsf {EUF{\text { -}}CMA}}\) for the advantage of an adversary in the \(\mathsf {EUF{\text { -}}CMA}\) game against a certification scheme. In the EAC protocol the authority’s public key is given by \(\textit{pk}_{\text {CVCA}}\) and the key generation, certificate creation and certificate verification are often described implicitly only.

Furthermore, we can define message authentication codes (MACs) \(\mathcal {M}= (\textsf {MKG},\textsf {MAC},\textsf {MVf})\) analogously, except that the key generation algorithm only outputs a single secret key and the adversary does not receive any initial input in the attack. We write \(\mathsf {Adv}_{\mathcal {M},\mathcal {A}}^{\mathsf {EUF{\text { -}}CMA}}\) for the advantage of an adversary \(\mathcal {A}\) in this game.

Finally, we need that the compression function \(\mathsf {Compr}\) is collision-resistant. That is, for an adversary \(\mathcal {A}\) it should be infeasible to find group elements \(X\ne Y\) such that \(\mathsf {Compr}(X)=\mathsf {Compr}(Y)\). We write \(\mathsf {Adv}_{\mathsf {Compr},\mathcal {A}}^{\mathsf {CR}}\) to denote the advantage of such an adversary \(\mathcal {A}\). We remark that we actually need a weaker requirement from \(\mathsf {Compr}\), resembling second preimage resistance, namely that for a random group element X it should be hard to find a colliding different Y, when given the discrete logarithm of X with respect to the group.

Next, we define our version of the \(\mathsf {PRF}{\text {-}}\mathsf {ODH}\) assumption as a slight extension to the original definition given in [25, 26]. In accordance with the systematic study of the \(\mathsf {PRF}{\text {-}}\mathsf {ODH}\) assumption by Brendel et al. [7], we term our notion \(\mathsf {mmPRF}{\text {-}}\mathsf {ODH}\), which corresponds to the strongest variant with multiple queries to both \(\mathsf {ODH}\) oracles.

Definition 4

( \(\mathsf {mmPRF}{\text {-}}\mathsf {ODH}\) assumption). Let \(\mathbb {G}= \langle g \rangle \) be a cyclic group of prime order q with generator g, and let \(\mathsf {PRF}:\mathbb {G}\times \{0,1\}^* \rightarrow \{0,1\}^\textit{n}\) be a pseudorandom function with keys \(K \in \mathbb {G}\), input strings \(x \in \{0,1\}^*\), and output strings \(y \in \{0,1\}^\textit{n}\), i.e., \(y \leftarrow \mathsf {PRF}(K, x)\).

We define the following \(\mathsf {mmPRF}{\text {-}}\mathsf {ODH}\) security game \(G_{\mathsf {PRF},\mathcal {A}}^{\mathsf {mmPRF}{\text {-}}\mathsf {ODH}}\) between a challenger \(\mathcal {C}\) and a probabilistic polynomial-time (PPT) adversary \(\mathcal {A}\).:

  • Setup. The challenger \(\mathcal {C}\) samples and provides \(\mathbb {G},g,\) and \(g^u\) to the adversary \(\mathcal {A}\).

  • Query Phase 1. \(\mathcal {A}\) can issue arbitrarily many queries to the following oracle \(\mathsf {ODH}_u\).

    • \(\mathsf {ODH}_u\) oracle. On a query of the form (A, x), the challenger first checks if \(A \notin \mathbb {G}\) and returns \(\bot \) if this is the case.

      Otherwise, it computes \(y \leftarrow \mathsf {PRF}(A^u, x)\) and returns y.

  • Challenge. Eventually, \(\mathcal {A}\) issues a challenge query \(x^\star \). On this query, \(\mathcal {C}\) samples  and a bit  uniformly at random. It then computes \({y^\star _0 = \mathsf {PRF}(g^{uv},x^\star )}\) and samples  uniformly random. The challenger returns \((g^v, y^\star _b)\) to \(\mathcal {A}\).

  • Query Phase 2. Next, \(\mathcal {A}\) may issue (arbitrarily many and interleaved) queries to the following oracles \(\mathsf {ODH}_u\) and \(\mathsf {ODH}_v\).

    • \(\mathsf {ODH}_u\) oracle. On a query of the form (A, x), the challenger first checks if \(A \notin \mathbb {G}\) or \((A, x) = (g^v, x^\star )\) and returns \(\bot \) if this is the case. Otherwise, it computes \(y \leftarrow \mathsf {PRF}(A^u, x)\) and returns y.

    • \(\mathsf {ODH}_v\) oracle. On a query of the form (B, x), the challenger first checks if \(B \notin \mathbb {G}\) or \((B, x) = (g^u, x^\star )\) and returns \(\bot \) if this is the case. Otherwise, it computes \(y \leftarrow \mathsf {PRF}(B^v, x)\) and returns y.

  • Guess. Eventually, \(\mathcal {A}\) stops and outputs a bit \(b^\prime \).

We say that the adversary wins the \(\mathsf {mmPRF}{\text {-}}\mathsf {ODH}\) game if \(b^\prime = b\) and define the advantage function

$$\begin{aligned} \mathsf {Adv}_{\mathsf {PRF},\mathcal {A}}^{\mathsf {mmPRF}{\text {-}}\mathsf {ODH}, \mathbb {G}}(\textit{n}) := 2\cdot \left( \Pr [b^\prime = b] - \frac{1}{2} \right) \end{aligned}$$

and, assuming a sequence of groups in dependency of the security parameter, we say that a pseudorandom function \(\mathsf {PRF}\) with keys from \((\mathbb {G}_\textit{n})_\textit{n}\) provides \(\mathsf {mmPRF}{\text {-}}\mathsf {ODH}\) security if for any \(\mathcal {A}\) the advantage \(\mathsf {Adv}_{\mathsf {PRF},\mathcal {A}}^{\mathsf {mmPRF}{\text {-}}\mathsf {ODH}}(\textit{n})\) is negligible in the security parameter \(\textit{n}\).

3.4 Analysis

Under the assumptions described above we can show that the EAC+0RTT protocol satisfies the required security properties:

Theorem 1

The EAC+0RTT protocol is \(\mathsf {Match}\)-secure. For any efficient adversary \(\mathcal {A}\) we have

$$\begin{aligned} \mathsf {Adv}_{\textsf {EAC},\mathcal {A}}^{\mathsf {Match}} \le q_p^2 \cdot \min \{2^{-|\mathsf {nonce}|},\tfrac{1}{q}\} \end{aligned}$$

where \(q_p\) is the maximum number of sub protocol executions, \(|\mathsf {nonce}|\) is the bit-length of each of the nonces \(r_C,r_C',r_C''\), and q is the order of the group from which (ephemeral) keys are chosen.

Similarly, we can show key secrecy, and even argue forward secrecy with respect to subsequent terminal corruptions. We note that forward secrecy with respect to chip corruptions is impossible to achieve for EAC since the chip does not generate ephemeral keys for executions but rather uses the long-term secrets:

Theorem 2

The EAC+0RTT protocol provides key secrecy (with \(\mathsf {responder}\) forward secrecy). That is, for any efficient adversary \(\mathcal {A}\) there exist efficient adversaries \(\mathcal {B}_3,\mathcal {B}_4,\mathcal {B}_5,\mathcal {B}_{10/11}\) such that

$$\begin{aligned} \mathsf {Adv}_{\mathsf {KE},\mathcal {A}}^{\mathsf {BR},\mathcal {D}}(n)&\le 3q_p^2\cdot \max \{ 2^{-|\mathsf {nonce}|},\tfrac{1}{q}\} + \mathsf {Adv}_{\mathsf {Compr},\mathcal {B}_3}^{\mathsf {CR}}\\&\qquad + \mathsf {Adv}_{\mathcal {C},\mathcal {B}_4}^{\mathsf {EUF{\text { -}}CMA}} + q_T\cdot \mathsf {Adv}_{\mathcal {S},\mathcal {B}_5}^{\mathsf {EUF{\text { -}}CMA}}\\&\qquad + 4q_p\cdot q_C\cdot \max \{q_p,q_\mathsf {sskid}\} \cdot \mathsf {Adv}_{\mathcal {B}_{10/11}}^{\mathsf {mmPRF}{\text {-}}\mathsf {ODH}} \end{aligned}$$

where \(q_p\) is the maximum number of sub protocol executions, \(q_s\) is the maximal number of sessions, \(q_C\) is the maximal number of chips, \(q_T\) is the maximal number of terminals, \(|\mathsf {nonce}|\) is the bit-length of each of the nonces \(r_C,r_C',r_C''\), and q is the order of the group from which (ephemeral) keys are chosen.

Remark 1

It may come as a surprise that the unforgeability of the MAC does not enter the security bound. This is due to the fact that we are “only” interested in key secrecy in the above theorem, stating that at most the intended partner can compute the session key and that seeing other session keys does not facilitate this task. The former is ensured by the certification of the chip’s long-term key and the fact that one cannot corrupt the chip. The latter is already captured by the \(\mathsf {mmPRF}{\text {-}}\mathsf {ODH}\) assumption, which states that learning related values of the PRF does not help to distinguish the challenge value from random.

Remark 2

Note that our analysis does not provide any form of key confirmation nor entity authentication. In fact, the final MAC can be seen as providing exactly these properties [18].

4 Variations

There exist several alternatives to implement 0RTT executions. For example, the 0RTT keys may be established either in the fashion of a Diffie-Hellman key exchange or—forgoing forward secrecy— rather from pre-shared keys (derived as additional key material in the previous round). It is also interesting to investigate different ways of handling negotiation failures in the 0RTT case. In the following, we therefore present different choices for the 0RTT flow.

4.1 Diffie-Hellman Variant

The 0RTT EAC extension presented in Sect. 2.2 is based on a Diffie-Hellman style key agreement. Similar implementations can also be found in Google’s QUIC protocol and in earlier draft versions of TLS 1.3 (draft 12 [30] and earlier).

4.2 Pre-shared Key Variant

From draft 13 [31] onward, TLS 1.3 replaces the DH-based variant of 0RTT handshakes by a pre-shared key (PSK) alternative. The pre-shared key is established either out of band or, more commonly, in a preceding interaction between server and client. Once a full handshake has been completed, the client receives a so-called PSK identity from the server. The PSK was derived in the initial handshake and can then be used by the client to derive keys for future (0RTT) handshakes. To initiate a 0RTT handshake, the client simply incorporates the early_data and pre_shared_key extension in the ClientHello, followed by the application data. After the successful processing of the data, the server then responds with the ServerHello and a forward-secret key is then derived as in the ordinary handshake.

In principle, one could also imagine a similar approach for the EAC protocol, using the pre-shared keying material instead of the shared Diffie-Hellman key. Note, however, that this may require further changes to the EAC protocol (for the additional keying material) and that, unlike the Diffie-Hellman version, this does not provide any (terminal) forward secrecy.

4.3 Error Handling

Zero round-trip time may not be supported by all servers, or there may occur errors in trying to decrypt the early data. Here we discuss how such problems are dealt with in other settings, and how one can proceed in the EAC case.

Google’s QUIC Protocol. From a design perspective, all handshakes in QUIC are also 0RTT handshakes, of which some may fail. The server replies with a ServerHello if all necessary information to complete the handshake was contained in the preceding ClientHello. If this was not the case, the server sends a rejection message encompassing information that allows the client to make progress in a next handshake attempt. The type and extent of information sent along with the rejection message can be chosen individually by the server but must not prevent clients from establishing a valid handshake within a reasonable time frame.

TLS 1.3 Draft 20. Upon receiving a 0RTT handshake request with encrypted early data, the server can answer in three ways: It may either disregard the 0RTT extension and return no response, causing the client to fall back to the standard 1RTT handshake. Or it may return the empty extension, thereby signalling to the client that prior validation checks were successful and that the server intends to process the received early data. Furthermore, the server may send a HelloRetryRequest to the client asking it to send a ClientHello without the early_data extension.

0RTT EAC. In case of failure, we expected the client to fall back to a full EAC protocol execution consisting of terminal and chip authentication. This may seem like an expensive step in view of performance, especially if the semi-static key used by the client is simply outdated. If the terminal does not support 0RTT, fall back to full EAC is clearly inevitable.

Furthermore, we emphasize that it is in general not possible for terminals to identify outdated keys. In order for a terminal to detect this (i.e., to distinguish unknown keys from outdated keys), it must keep at least the last used value of \(\textit{pk}_T^\textsf {semi}\) when updating to a new value \({\textit{pk}_T^\textsf {semi}}'\). Keeping state is commonly seen as not recommendable, if not infeasible, in most use cases. However, we note that a chip receives all the data it needs to initiate future 0RTT handshakes with a 0RTT-supporting terminal during the terminal authentication phase of the EAC protocol. Therefore, it is sufficient for the chip to carry out the TA phase before the 0RTT handshake can be re-tried. In light of this, it is also conceivable for terminals to proceed similarly to the mechanism deployed in the QUIC protocol and to reply with the current authenticated semi-static key, i.e., to send \(\textit{cert}_T, \textit{pk}_T^\textsf {semi}, s_T\) where \(s_T\leftarrow \textsf {Sig}(\textit{sk}_T, \textit{pk}_T^\textsf {semi})\).

5 Conclusion

The Extended Access Control (EAC) protocol is a universal solution for key establishment between two parties. In this work, we presented a 0RTT mode for the EAC protocol which allows to reduce the latency of recurring connections. It is noteworthy that this 0RTT mode can be added as an extension with minimal changes to the original protocol. We further showed that EAC+0RTT can be proven secure in the multi-stage setting of the Bellare-Rogaway model. Thus, the modified protocol still achieves the common security properties of an authenticated key exchange protocol.