A Novel Forward-Secure Key Establishment Protocol from Physically Related Functions

Kuppusamy, Lakshmi; Shankar, B R; Lee, Cheng-Chi

doi:10.2478/ias-2025-0009

Full Article

1

Introduction

Authenticated Key Exchange (AKE) protocols enable two parties to establish secure communication over a public network. The main security objective of an AKE protocol is to make it computationally infeasible for an adversary eavesdropping on the communication to learn the session secret shared between the parties. Traditionally, public key cryptography is employed to design forward-secure AKE protocols. However, these methods often require computationally intensive operations and long-term cryptographic keys [1, 2], which pose challenges in resource-constrained environments. In contrast, symmetric keybased primitives are more suitable for such devices, but managing keys in these scenarios remains a significant issue. Cryptophasia in hardware refers to the phenomenon where two hardware devices can achieve authenticated key exchange. Accomplishing this without relying on costly cryptographic techniques would be highly beneficial for resource-limited devices. Physical protection techniques [3] can be adopted for the resource constrained devices to implement symmetric key based primitives for realizing secure and efficient communication. However the large scale adoption of such techniques is difficult due to cost and scalability issues [4, 5]. In addition, recent works [4, 6] exposed attacks [7] on the secure key management techniques implemented in non-volatile memories such as RAM.

Motivated by these issues, Chatterjee et al. [8, 9] proposed physically related functions (PReFs), a specialized hardware component realized using strong Physically Unclonable Functions (PUFs). Their primary goal is to design a secure AKE protocol relying solely on PReFs and hash functions, which was seen as impossible without conventional cryptography [10]. Their proposal embeds PReFs during device manufacturing, which allows the devices implement AKE protocol with the input/output pairs generated by the PReFs. In their basic AKE protocol [9], the session key is masked by the output of a PReF function embedded in one party's device, which is then transmitted to the other party. Since PReFs produce different outputs for the same input by design, the protocol uses Error Correcting Codes (ECC) [11] to reconcile the output differences between the devices and recover the correct session key. Further, they enhanced the PReF-based protocol to achieve forward secrecy by incorporating the elliptic curvebased Diffie-Hellman. From this, we observe that while PReFs can effectively replace long-term keys in traditional AKE-based key exchange protocols without compromising security, still public-key method was used to achieve forward security.

In this paper, we aim to fully eliminate traditional public key based approaches from the protocol proposed in [9]. In particular, we make the necessary changes to the design of Chaterjee et al. and present a forward-secure AKE protocol that primarily depends on PReFs, removing the need for both public key operations and long-term cryptographic keys. We show that our protocol is secure under the security models of [1, 2]. It is evident from Table 1 and Table 2 that our protocol in Figure 2 is better suited for resource constrained devices.

Table 1.

Comparison: SK, EPA, PR, EPM and MEx refer to symmetric key operations, elliptic curve point addition, pairing on elliptic curves, elliptic curve point multiplication and the number of exchanged messages respectively

Scheme	Computation Time in μs			Forward secrecy	Comm. overhead (bit)	storage
Scheme	Operations	Intel	ARM	Forward secrecy	Comm. overhead (bit)	storage
[14]	11 hash	≈ 3.41	≈ 49.55	yes	1088	yes
[15]	8 EPM & 6EPA & 2 hash	≈ 602.48	≈ 6830.25	no	4160	yes
[16]	3 RSA & 2 hash	≈ 1146.62	≈ 23283.01	yes	1536	yes
[17]	4 SK & 5 hash	≈ 1.95	≈ 25.905	yes	512	yes
[18]	6 hash	≈ 1.86	≈ 27.03	no	1280	yes
[19]	6 EPM & 2 EPA & 6 hash	≈ 452.48	≈ 5134.11	yes	1088	yes
[20]	3 RSA & 19 hash & 2 signature	≈ 578.87	≈ 11722.61	yes	6208	yes
[21]	10 EPM & 2 EPA & 2 PR & 4 hash	≈ 2207.86	≈ 25015	yes	2048	yes
[9]	4 EPM & 6 hash	≈ 101.86	≈ 1627.03	yes	1216	no
Ours	4 hash	≈ 1.24	≈ 18.02	yes	704	no

Table 2.

Comparison: SK, EPA, PR, EPM and MEx refer to symmetric key operations, elliptic curve point addition, pairing on elliptic curves, elliptic curve point multiplication and the number of exchanged messages respectively

Scheme	Computation Time in μs			Forward secrecy	Communication overhead (in bits)	storage
Scheme	Operations	Intel	ARM	Forward secrecy	Communication overhead (in bits)	storage
[24]	4 hash & 12 MAC & 10ENC	≈ 7.28	≈78.07	yes	7872	yes
[25]	8 Hash & 6 hash-to-point & 4 EPM	≈ 304.34	≈ 3463.07	yes	9312	yes
[26]	14 Hash & 20 hash-to-point & 8 EPM & 16 EPA & 4 PR	≈ 3527.5	≈ 39989.8	yes	9856	yes
[27]	6 Hash & 12 PRF & 3 GroupExp	≈ 579.9	≈ 11715.6	yes	1952	yes
[28]	12 Hash & 14 EPM & 4 EPA	≈ 1054.96	≈ 11968.2	yes	4160	yes
[29]	12 Hash & 4 Enc	≈ 4. 12	≈ 57.44	yes	2880	yes
[30]	8 hash	≈ 2.48	≈ 36.04	yes	1216	yes
Ours	4 hash	≈ 1.24	≈ 18.02	yes	704	no

Outline. In Section 2, our AKE protocol is presented along with the security analysis. Section 3 presents our proposal for dynamic networks and Section 4 concludes the paper. To ease readers, Supplementary A provides a brief introduction to PReFs and relevant definitions from [9] and a complete description of Chatterjee et al. protocol is reproduced in Section B.

2

A Forward Secure AKE Protocol from PReFs

Physically Related Functions introduced by Chatterjee et al. has the potential to become a standalone primitive in the design of key exchange protocols [8, 9]. Their PReF-based AKE protocol avoids secure storage by replacing PReFs for long-term keys (widely used to achieve authentication in key exchange protocols). However, it remains a challenging problem to design a AKE protocol that is forward secure and relies only on PReFs, error correction and collision resistant hash functions. Inspired by the approach of Chatterjee et al., we propose a PReF based AKE that is forward secure and does not require any public key cryptography techniques to achieve forward secrecy.

System model of the protocol for Static PReF Network. Let ℱ = {f_i : 𝒳 → 𝒴} be a function family, where 𝒳 = {0, 1}^m and 𝒴 = {0, 1}ⁿ are arbitrary sets. Let Alice and Bob are two parties who physically implement the functions f₁ and f₂ using their respective hardware devices D₁ and D₂. There is a trusted (semi-honest) party, such as a manufacturer, which performs the following actions before deploying devices D_i (for i = 1, …, T) in the static PReF network:

(a)
A (T, ε, ε′, δ )-ReF graph is constructed, represented by the functions (f₁, f₂, …, f_T) ∈ ℱ, where each function f_i is embedded in the corresponding device D_i (for i = 1, …, T).
(b)
For every pair of devices D_i and D_j, the party who is assumed to be trusted publish the related input set 𝒳_i,j on a cloud/ledger which is publicly accessible.

Alice and Bob (devices D₁ and D₂) agree on an input x from the publicly available related input set 𝒳_1,2 and compute the output y using their respective PReFs, f₁ and f₂. An adversary with access to f₀ cannot predict the output y, even if they have access to the PReF pairs 𝒳_1,0 and 𝒳_2,0, because $X_{1, 2} \cap X_{1, 0} = X_{1, 2} \cap X_{2, 0} = \emptyset .$ {{\cal X}_{1,2}} \cap {{\cal X}_{1,0}} = {{\cal X}_{1,2}} \cap {{\cal X}_{2,0}} = \emptyset .

We begin with a proposal of one-pass key exchange protocol based on PReF as illustrated in Figure 1. This protocol relies solely on the existence of the PReF network and the reconciliation of related outputs. To mitigate security vulnerabilities highlighted in [12], the protocol employs BCH-based error correction to reconcile the outputs of PReFs, and subsequently establishes the session key, as outlined in [9]. As depicted in Figure 1, two parties, 𝒟₁ and 𝒟₂ establish a session key upon executing the protocol. 𝒟₁ initiates the session as follows: 𝒟₁ randomly selects an input x from the input set 𝒳_1,2 and computes y₁ using the function f₁. Then, 𝒟₁ computes A based on y₁, a random value r, and the sessionspecific secret k_1,2. The values A and x are sent to 𝒟₂. Upon receiving A and x, 𝒟₂ computes y₂ using f₂(x) and then decodes A using y₂ and k_1,2 to retrieve r. Both devices then agree on r as the session key.

To ensure protection against replay, impersonation, and integrity attacks, a collision-resistant hash function ℋ : {0, 1}* → {0, 1}ⁿ and a session-specific nonce TS are introduced. Thus, an attacker finds it computationally infeasible to find ℋ(r∥TS∥𝒟₁∥𝒟₂) = ℋ(r′∥TS′∥𝒟₁∥𝒟₂) for a given (r, TS) such that values r′ ≠ r and TS′ ≠ TS. The resultant AKE protocol after incorporating the above measures is depicted in Fig. 2. The session key r remains secure even if an adversary gains access to the output of the PReF functions f₁ or f₂ for the input x. This is because the adversary is unable to derive r from A and y₁ or y₂, as the ephemeral secret k_1,2 remains unknown to them. Additionally, using k_1,2 offers the benefit of allowing x to be reused across multiple authentications. The adversary cannot deduce r + s from two sessions that using same x but different r and s.

Remark. Our protocol differs from the one proposed by Chatterjee et al. (refer to Figure 6) by utilizing a session-specific secret k_1,2 between the devices 𝒟₁ and 𝒟₂, thereby eliminating the need for the elliptic curve Diffie-Hellman protocol. Specifically, we assume that k_1,2 is a pre-shared short-term secret stored in the devices during deployment. When a session is initiated between 𝒟₁ and 𝒟₂, this secret k_1,2 is used to establish the session key. Afterward, this short-term secret is updated using a collision-resistant hash function H, as depicted in Figure 2. This ensures that k_1,2 acts as an ephemeral secret specific to each session.

2.1

Security Analysis

In this section, we show that our protocol is forward secure according to the standard AKE models, namely Canetti-Krawczyk model [2] and extended Canetti-Krawczyk model [1].

AKE Model for PReF Network. The model assumes that all devices 𝒟₁, …, 𝒟_T and the adversary 𝒜 run as Probabilistic Polynomial Time (PPT) algorithms. The adversary 𝒜 is capable of initiating multiple instances of the protocol between any pair of devices (𝒟_i, 𝒟_j), with each instance identified as a session. Every session is attributed by a unique nonce or session identifier TS, preventing the adversary from reusing the same nonce to start multiple sessions. During the experiment, 𝒜 can issue the following oracle queries:

Key Reveal (TS): This query outputs the session key and nonce TS

Output Reveal $(x \in X_{i, j}^{'})$ \left( {x \in {\cal X}_{i,j}^\prime } \right): The output of the functions embedded in 𝒟_i or 𝒟_j is revealed through this query. Whenever an adversary issues this query with input x, the respective devices that reveals the corresponding long-term secret y are said to be corrupt. Note that this query is analogous to the long-term key reveal query defined in the eCk model [1].

Ephemeral Key Reveal (TS): This query outputs ephemeral key of the session identified by TS.

Test (TS): This query is made only once during the entire experiment. Whenever this query is issued, the challenger chooses a bit b ∈ {0, 1} and reveals either the session key of the session with TS or a uniformly random key.

The adversary uses the above queries to establish a second session with the same key as the targeted session. The adversary is permitted to issue the test query only on a fresh session that meets the following conditions:

𝒜 does not issue Key Reveal query for the test session.
Whenever 𝒜 issues ephemeral key reveal query, then it is not allowed to issue output reveal query for the corresponding pair of devices.
Whenever 𝒜 issues output reveal query for the devices, then it is not allowed to issue ephemeral key reveal query for the same pair of devices.

After issuing a test query on the fresh session, the adversary's goal is to distinguish the session key from a random key. Consequently, the adversary wins the experiment only when it distinguishes the session key from a random key with a non-negligible probability.

Theorem.

The protocol in Figure 2 is a forward secure AKE protocol provided: (a) the pair of functions (f_i, f_j) embedded in the respective devices 𝒟_i and 𝒟_j that is associated with a (T, ε, ε′, δ)–PReF network are pseudorandom by Definition A.1, (b) r is chosen uniformly at random and (c) ℋ is modelled as a random oracle.

Proof.

We first show that the functions f_i and f_j are pseudorandom. Then we argue the security of the our protocol assuming the pseudorandomness of the functions f_i and f_j.

Pseudorandomness. Let 𝒞 represents a PPT algorithm embedded with the function f_i. 𝒞 selects b ∈ {0, 1} at random and computes y_i = E(r) + y_i, + k, for a PReF input $x \in X_{i, j}^{'}$ x \in {\cal X}_{i,j}^\prime and a random r ∈ {0, 1}ⁿ. Whenever b is 0, it sets y_i = f_i(x) and k = k_1,2. Otherwise, it sets y_i = s and k = k′ where s and k′ are chosen at random from {0, 1}ⁿ.

Let ε(λ) be a non-negligible function and 𝒟 be the PPT distinguisher having non-negligible advantage of distinguishing the output E(r) + f_i (x) + k _1,2 from E(r) + s + k′. That is, for all r ∈ {0, 1}ⁿ and s ∈ {0, 1}ⁿ, the advantage of 𝒟 is $| \Pr [D (E (r) + f_{i} (x) + k_{1, 2}) = 1] - \Pr [D (E (r) + s + k^{'}) = 1] | = ε (λ) .$ \left| {\Pr \left[ {{\cal D}\left( {E(r) + {f_i}(x) + {k_{1,2}}} \right) = 1} \right] - \Pr \left[ {{\cal D}\left( {E(r) + s + {k^\prime }} \right) = 1} \right]} \right| = \varepsilon (\lambda ).

Now we show that there exist a PPT algorithm 𝒜 against the pseudorandomness of the function f_i that uses 𝒟 to win the pseudorandom experiment against the challenger as follows:

Whenever an input 1^λ is received from the challenger, the adversary 𝒜 submits x ∈ 𝒳′_i,j
Upon receiving the response x from 𝒜, the challenger selects b ∈ {0, 1} and assigns y_i = f_i(x) and k = k_1,2 if b = 0. Otherwise it sets y_i = s and k = k′ for a random s and k′ chosen from {0, 1}ⁿ.
After receiving y_i from the challenger, 𝒜 simulates the algorithm 𝒞 to distinguisher 𝒟. Finally 𝒜 sets the output b′ = 0 if 𝒟 outputs 0. Otherwise b′ is set to 1.

Clearly the adversary 𝒜 wins the challenger with a non-negligible advantage ε(λ) as the distinguisher 𝒟 wins the challenge with the advantage ε(λ) which is a contradiction to the definition of Pseudorandomnes of f_i. Thus any distinguisher against 𝒞 can distinguish E(r) + f_i(x) + k_1,2 from E(r) + s + k′ only with negligible advantage.

AKE Proof. Assume that there exists a PPT adversary 𝒜 against our AKE protocol in Figure 2. In the AKE experiment, the aim of an adversary is to distinguish between the session key of the test session and a random key.

Consider an event E₁ where an adversary tries to establish a second session with the same session key computed in the target session and then wins the experiment by issuing a session key reveal query to the second session. We now analyze the probability of event E₁ occurring. According to the AKE experiment definition, the adversary is not allowed to use the same nonce to initiate multiple sessions TS, although they can choose the same input x for both sessions. Let the session key for the target session be r and for the second session be m. The only way the adversary can replace m with r is by determining the unknowns k_1,2 and y_i from A and making the checksum B = ℋ(r∥TS∥𝒟₁∥𝒟₂∥x) valid. However, this is negligible under the assumption that the hash function ℋ is collision-resistant.

Recall that a test query is issued against a fresh session where the adversary is allowed to issue either the ephemeral key reveal query or the output reveal query. Now define an event E₂ where an adversary tries to distinguish the target session key from a random key after obtaining secret information used in the target session through the following queries:

Case 1. The adversary 𝒜 issues only the ephemeral key reveal query for the session it targets. The adversary obtains the random value k_1,2 used in the session. The adversary having k_1,2 and x has to compute r from A which is sent public. 𝒜 cannot distinguish E(r) + f_i(x) + k_1,2 from E(r) + s + k_1,2 for a random s as the PReF functions are pseudorandom. On the other hand, 𝒜 cannot recover r from B = ℋ(r∥TS∥𝒟₁∥𝒟₂∥x) since ℋ is modelled as a random oracle and r is chosen uniformly at random. From the above arguments, it is clear that 𝒜 can forge the session only with negligible probability even if the ephemeral key is revealed.
Case 2. Now consider the case where an adversary 𝒜 issues the output reveal query (x) on the target session to obtain f_i(x). Then the adversary is not allowed by definition to use the same x for a new session. The adversary is unable find the session key r from A and f_i(x) without knowing k_1,2. Thus the adversary is successful in forging the session key of the target session only with negligible probability. In particular, it is clear that the above argument holds when the adversary tries to compute session keys of the completed session. In the case of completed sessions, the adversary could not retrieve k_1,2 of the particular session as they are updated at the end of each session and hence the session key r. With this, we claim that our AKE protocol is forward secure.

2.2

A comparative Analysis with the Existing (PUF based) AKE Protocols

This section compares our protocol with existing (PUF based) AKE protocols in terms of computational cost and forward secrecy property. In particular, the computation cost is calculated by referring the work of Shahidinejad and Abawajy [13] where the authors reported the execution time of algorithms listed in Table 1 and Table 2 in both the Intel and ARM processors.

2.2.1

Comparison With AKE protocols

The major goal of our protocol design is to completely avoid public key based cryptographic computations and to depend only on the existence of PReFs and collision resistant hash functions. To achieve this our protocol described in Section 2 uses a session-specific secret k_1,2 which is stored in the devices during deployment. When the first session is initiated between 𝒟₁ and 𝒟₂, the value k_1,2 is used to establish the first session key. In the subsequent sessions, the value k_1,2 gets updated as depicted in Figure 1. This methodology is proposed not only to avoid public key computations but also to ensure that k_1,2 acts as an ephemeral secret specific to each session. During deployment, secret key erasure techniques may be implemented to destruct/zeroizing the secret values [22] to make them inaccessible and avoid the attack of [7]. Our protocol thus avoids storage of long-term secret values when compared with the existing secure storage based AKE protocols [14, 15, 19, 23]. Thus it is evident from Table 1 that our protocol in Figure 2 is more efficient when compared with the other AKE protocols. Note that our PReF based AKE protocol achieves forward secrecy using four hash computations whereas the protocol proposed by Dousti etal. [18] requiring six hash computations lacks forward secrecy.

2.2.2

Comparison With PUF Based AKE protocols

Many PUF based AKE protocols are proposed in the literature [24–30] for resource constrained environments as they are extremely light weight and unpredictable. However the use of PUFs introduces the need to securely store the secret values and to engage in expensive computations [27, 31]. In particular, a root-of-trust is established in protocols [24–26, 29] by a trusted third party that handles secure storage of the data involved and/or aids the light weight devices to accomplish authentication during the protocol run. On the other hand, protocols that eliminate the need of trusted third party either requires expensive elliptic curve based computations [26, 28] or lacks stronger security such as forward secrecy [27]. In a recent article, Boyapally et al. [30] introduced the concept of Harmonizing PUFs (H PUF) and proposed a AKE protocol based on H PUF to achieve efficiency in terms of communication overhead, computation cost and security that depend only on the H PUF and Hash functions as in Table 2. Our PReF based protocol achieves stronger security under the assumption on PReF and Hash functions with minimal computational and communication cost.

3

PReF based AKE for Dynamic Networks

This section proposes a forward secure PReF based AKE protocol for a dynamic PReF network. The approach is similar to the one proposed in [9] where a designated set of honest devices (referred as auxiliary devices) are employed (a) to introduce new devices to the network and (b) to assist the existing devices that could not communicate with the other devices in the network due to the compromise of PReF to re-join the network. The dynamic network consists of two types of devices: (1) primary devices that take part in the key exchange protocol for establishing secure communication with other devices and (2) auxiliary devices that are honest-but-curious and does not take part in the key exchange process with primary devices. Auxiliary devices are solely responsible for assisting new (or primary) devices in joining or rejoining the network.

Protocol Description: Let T and S be the number of primary and auxiliary devices respectively in the network. The major goal of the auxiliary device is to enable the devices (without pre-established PReF pairs with any of the devices in the network) to establish a session key between the primary devices. For a a family of functions ℱ = {f_i : 𝒳 → 𝒴)}, where 𝒳 = {0,1 }^m and 𝒴 = {0, 1}ⁿ are arbitrary sets. Let f_i, i = 1 … T + S be a (T + S, ε,ε′, δ) – ReF graph represented by the functions (f₁, f₂, … f_T+S) ∈ ℱ is constructed where each f_i is embodied to the corresponding devices D_i, i = 1, … T + S.

As illustrated in Figure 3, 𝒟₀ is the auxiliary device that enables D₂ (without the unique set 𝒳_1,2) to establish a session key with the primary device D₁ by communicating with D₁ using the related input set 𝒳_0,1 and the preshared secret k_0,1. Note that the session key derived between D₁ and D₂ is known to the auxillary device D₀ which is assumed to be honest in our protocol description. Our protocol enables the addition of new devices with the computation of: (1) two error correction, two exclusive OR and four hash operations for each of the primary devices and (2) two error correction and five hash computations for the auxiliary device. The following theorem shows that our protocol is weak perfect forward secure.

Theorem.

The protocol in Figure 3 is a forward secure AKE protocol provided: (a) the pair of functions (f_i, f_j) embedded in the respective devices 𝒟_i and 𝒟_j that is associated with a (T, ε, ε′, δ)–PReF network are pseudorandom by Definition A.1, (b)r is chosen uniformly at random and (c) ℋ is modelled as a random oracle. In addition, the auxiliary device 𝒟₀ is assumed to be honest and knows the session key established between the primary and new device.

Proof.

The following AKE proof is given assuming the pseudorandomness of the functions f_i and f_j as shown in Theorem 2.1.

AKE Proof. Assume that there exists a PPT adversary 𝒜 against our AKE protocol in Figure 3. In the AKE experiment, the aim of an adversary is to distinguish between the session key of the test session and a random key.

Consider an event E₁ where an adversary tries to establish a second session with the same session key computed in the target session and then wins the experiment by issuing a session key reveal query to the second session. We now analyze the probability of event E₁ occurring. According to the AKE experiment definition, the adversary is not allowed to use the same nonce to initiate multiple sessions TS, although they can choose the same input x for both sessions. Let the session key for the target session be r and for the second session be m. The only way the adversary can replace m with r is by determining the unknowns k_1,2 and y_i from A and making the checksum B = ℋ(r∥TS∥𝒟₁∥𝒟₂∥x) valid. However, this is negligible under the assumption that the hash function ℋ is collision-resistant.

Recall that a test query is issued against a fresh session where the adversary is allowed to issue either the ephemeral key reveal query or the output reveal query. Now define an event E₂ where an adversary tries to distinguish the target session key from a random key after obtaining secret information used in the target session through the following queries:

Case 1. The adversary 𝒜 issues only the ephemeral key reveal query for the session it targets. The adversary obtains the value k_0,1 and k_0,2 used in the session. The adversary having k_0,1, k_0,2, x₁ and x₂ has to compute r₁ and r₂ from $A_{1}^{0, 1}$ A_1^{0,1} or $A_{2}^{0, 2}$ A_2^{0,2} and $A_{1}^{0, 2}$ A_1^{0,2} or $A_{2}^{0, 1}$ A_2^{0,1} respectively which are sent public. 𝒜 cannot distinguish $E (r_{1}) + y_{1}^{0, 1} + k_{0, 1}$ E\left( {{r_1}} \right) + y_1^{0,1} + {k_{0,1}} from E(r₁) + s + k_0,1 for a random s as the PReF functions are pseudorandom. On the other hand, 𝒜 cannot recover r₁ from $B_{1}^{0, 1} = ℋ (r_{1} ‖ {TS}_{1} ‖ D_{0} ‖ D_{1} ‖ x_{1})$ B_1^{0,1} = {\cal H}\left( {{r_1}\left\| {{\rm{T}}{{\rm{S}}_1}} \right\|{{\cal D}_0}\left\| {{{\cal D}_1}} \right\|{x_1}} \right) since ℋ is modelled as a random oracle and r₁ is chosen uniformly at random. The similar arguement holds for recovery of r₂. Thus, it is clear that 𝒜 can forge the session only with negligible probability even if the ephemeral key is revealed.
Case 2. Now consider the case where an adversary 𝒜 issues the output reveal query (x_j,)j = 1 … 4 on the target session to obtain f_i(x_j), i = 1, 2 and j = 1 … 4. Then the adversary is not allowed by definition to use the same x_j, j = 1 … 4 for a new session. The adversary is unable to find the keys r₁ and r₂ from $A_{1}^{0, 1}$ A_1^{0,1} or $A_{2}^{0, 2}$ A_2^{0,2} and $A_{1}^{0, 2}$ A_1^{0,2} or $A_{2}^{0, 1}$ A_2^{0,1} respectively and f_i(x_j) without knowing k_0,1 and k_0,2. Thus the adversary is successful in forging the session key of the target session only with negligible probability. In particular, it is clear that the above argument holds when the adversary tries to compute session keys of the completed session. In the case of completed sessions, the adversary could not retrieve k_0,1 and k_0,2 of the particular session as they are updated at the end of each session and hence the session key SK. With this, we claim that our AKE protocol desribed in Figure 3 is weak perfect forward secure.

4

Conclusion

Cryptophasia is a phenomenon which enables twins to communicate in a language that only they can understand. Chatterjee et al. investigated how to achieve “Cryptophasia in Hardware" so that a device pair can securely communicate with each other over an insecure/open network. Chatterjee et al. stated, “what if the participating devices are far too resource-constrained to either support the heavy computational costs of such a key exchange protocol or the secure storage requirements to store the resulting secret key? In particular, constraints with respect to computational resources make it dificult to deploy standard public-key techniques such as public-key encryption and or digital signatures to achieve secure and authenticated communication." In this work, we showed that it is feasible to obtain forward-secure AKE protocol without assuming trusted party and public-key crypto computations for the static network. Our forward secure AKE protocol for the static network is built using PReFs, error-correction codes and collision resistant hash functions and is shown to be secure under the widely-accepted security model for AKE protocols. In case of dynamic network, we could achieve it by assuming that the auxiliary devices are trusted and hence designing a PReF based AKE protocol without the assumption of trusted auxiliary devices and random oracles is left for future work.

A Physically Related Functions and its Realisation in Hardware

This section intends to describe the main difference between PReFs and PUFs as the former requires additional assumptions to be realised in hardware. The main objective of PReF is to set randomised functionalities in hardware [8] similar to strong PUF. Contrary to the design of PUF where the similarity in responses of a PUF pair for an entire input space is expected to be unpredictable/uncorrelated, PReF is defined to exhibit its usage on correlated responses for specific values in the input space. This in turn, makes PReFs a predominant function to design efficient AKE protocols as PUF-based AKE protocols need additional assumptions such as the existence of secure channels and/or a trusted third party. On the other hand, it is more challenging to design PReFs compared to PUFs as they rely on :(a) internal devices knowledge to generate related input/output pairs during the setup phase and (b) avoiding the exposure of related input/output pairs to an adversary only having black-box access to the devices [9].

A.1 Notations and Definitions

Denote the security parameter by λ ∈ ℕ. The following definitions are reproduced from [9].

Ideal PReF pairs. Let f_A and f_B be the pair of functions with input and output space 𝒳 and 𝒴 respectively. We call f_A and f_B be the related function pair whenever the output behaviour of f_A and f_B are identical for a specific input from 𝒳. Those inputs form a subset 𝒳_A,B ⊆ 𝒳. Note that the output behaviours of f_A and f_B are uncorrelated for inputs outside of the subset 𝒳_A,B. More formally, it should be difficult for a computationally bounded adversary to correctly guess the output of f_B(x) and f_A(x) for a given input x ⊈ 𝒳_A,B with a probability much better than the random guess.

To realise PReF pairs in the real world using hardware characteristics, the outputs of PReFs pairs are allowed to be non-identical but related via a distance function as in the following definition.

Related Function (ReF). For a family of functions ℱ = {f_i : 𝒳 → 𝒴} and arbitrary sets 𝒳 and 𝒴, assume that there is a well-defined distance function dist: 𝒴 × 𝒴 → ℕ over a pair of elements in 𝒴. Then, each pair (f, f_j) ∈ ℱ × ℱ is defined as (ε, δ) – related for constants ε ∈ (0,1] and δ ∈ ℕ, whenever there exists a set of inputs 𝒳_{i, j} ⊆ 𝒳 that satisfies the following conditions:

|𝒳_i,j| ≥ ε|𝒳|
For any input x ∈ 𝒳_{i, j}, dist[f_i, f_j] ≤ δ.

Reconciliation. The major goal of an AKE protocol is to enable the parties to establish a common secret. In order to design AKE using ReFs, reconciliation to a common secret from the respective parties outputs (evaluated on the same input) has to be achieved. That is, for each ReF pair (f_i, f_j) with related input x and an appropriate δ, there must exist an error correcting code scheme such that: $d i s t [f_{i} (x), f_{j} (x)] \leq δ \Leftrightarrow Decode (f_{i} (x)) = Decode (f_{j} (x))$ {\mathop{\rm dist}\nolimits} \left[ {{f_i}(x),{f_j}(x)} \right] \le \delta \Leftrightarrow {\mathop{\rm Decode}\nolimits} \left( {{{\rm{f}}_{\rm{i}}}({\rm{x}})} \right) = {\mathop{\rm Decode}\nolimits} \left( {{{\rm{f}}_{\rm{j}}}({\rm{x}})} \right)

It is evident that such a reconciliation can be achieved easily using well established information-theoretic techniques such as error-correcting codes (ECC) [11].

Error-Correction Code (ECC). [9] Let (E, D) be the encoding and decoding algorithms of an (n, k,δ) linear error correction code. Then, $D (E (a) + e) = a; E (a) + E (b) = E (a + b)$ D(E(a) + e) = a;\quad E(a) + E(b) = E(a + b) where a, bE(a), E(b) ∈ {0, 1}^k and Hamming weight(e) ≤ δ.

Pseudo-randomness of ReF. Let f_i ∈ ℱ, 0 ≤ i ≤ n be the functions that are (ε, δ) related on the respective input sets 𝒳_i ⊆ 𝒳, 1 ≤ i ≤ n. Let 𝒜 be a probabilistic polynomial time (PPT) algorithm with oracle access to f_i, 0 ≤ i ≤ n. For an input x ∈ 𝒳 and b ∈ {0, 1}, define the event E_𝒜,x,b(λ) : $E_{A, x, b} (λ) : A^{f_{0} (.), f_{1} (.), \dots, f_{n} (.)} (1^{λ}, x, y_{b}) = b$ {{\rm{E}}_{{\cal A},x,b}}(\lambda ):{{\cal A}^{{f_0}(.),{f_1}(.), \ldots ,{f_n}(.)}}\left( {{1^\lambda },x,{y_b}} \right) = b where y_b satisfies the following:

dist(y_b, f₀(x)) ≤ δ whenever b = 0
uniformly random from 𝒴 whenever b = 1

and 𝒜 is not allowed to issue a query of the form f₀(x) and f_i(x), 1 ≤ i ≤ n for x ∈ 𝒳_i. The function f₀ is pseudo-random whenever any input x ∈ 𝒳 satisfies the above conditions. Then, for any such PPT algorithm 𝒜,

| \Pr [E_{A, x, 0} (λ)] - \Pr [E_{A, x, 1} (λ)] | \leq negl (λ) .

\left| {\Pr \left[ {{{\rm{E}}_{{\cal A},x,0}}(\lambda )} \right] - \Pr \left[ {{{\rm{E}}_{{\cal A},x,1}}(\lambda )} \right]} \right| \le {\mathop{\rm negl}\nolimits} (\lambda ).

In the following definition, a ReF graph is defined as a collection of ReF where each ReF pair related over a unique set of inputs satisfies the property of reconciliation and pseudo-randomness.

ReF Graph. Assume ℱ = {f_i: 𝒳 → 𝒴} to be a family of functions for the arbitrary sets 𝒳 and 𝒴. Then, a set of T functions f₁, …, f_T ∈ ℱ represents a (T, ε, ε′, δ) – ReF graph for ε′ ∈ (0, ε] whenever the following holds for each i, j ∈ [T]:

(f_i, f_j) is (ε,δ) related
f_i is pseudorandom
a unique subset of inputs 𝒳′_i,j exists with size at least ε′|𝒳| for f_i and f_j.

Let D be a hardware device manufactured to physically realise the same input-output behaviour of the boolean function f. Then D is referred as reliable embodiment of function f.

Reliable Embodiment. D is a reliable physical embodiment of a function f: 𝒳 → 𝒴 if: $\Pr [D (x) \neq f (x)] \leq neg ∣ (λ)$ \Pr [{\bf{D}}(x) \ne f(x)] \le {\mathop{\rm neg}\nolimits} \mid (\lambda ) for all x ∈ 𝒳 and the probability is defined on multiple calls to the device D.

Physically Related Function(PReF). A device pair (D_i, D_j) represent an (ε, δ) – physically related function, if it reliably embodies an (ε,δ) pair (f_i, f_j).

PReF Network. A set of devices D₁, …, D_T represent a (T, ε, ε′, δ) – PReF network whenever every device D_i reliably embodies a function f_i in a way that the corresponding collection of functions f₁, …, f_T ∈ ℱ in turn represent a (T, ε, ε′,δ) – ReF graph.

A.2 Hardware Realisation of PReFs

Note that PReFs are fundamentally similar to PUFs except for the assumption on the existence of related input set to arrive at a common output. Thus their realisation in hardware also rely on the natural device specific variations to enable unpredictability on the input/output behaviour of the device even for an adversary possessing the complete knowledge of circuit implementation. Thus a natural constraint in the hardware realisation of PReFs is to identify related input set. As the definition A.1 allows the outputs of PReF pairs to be non identical but related to each other through a distance function, the related input subset can be obtained from any arbitrary random boolean functions. Chatterjee et al. proposed machine learning based methodology to obtain related inputs for a given hardware circuit realised with a pair of boolean functions in [9].

B PReF Based Key Exchange Protocol

Chatterjee et al. introduced a basic two party based key exchange protocol meant to establish secure communication by avoiding the use of traditional cryptographic assumptions.

System model for Static PReF Network. Let ℱ = {f_i: 𝒳 → 𝒴} be a family of functions, where 𝒳 = {0, 1}^m and 𝒴 = {0, 1}ⁿ are arbitrary sets. Let Alice and Bob be two parties that physically implement f₁ and f₂ using their respective hardware devices D₁ and D₂. Assume that there exist a trusted party (e.g., a manufacturer) which is semi-honest and does the following before the deployment of devices D_i, i = 1, …, T in the static PReF network with the corresponding functions f_i, i = 1, …, T : (a) A (T, ε,ε′, δ) – ReF graph represented by the functions (f₁, f₂, …, f_T) ∈ ℱ is constructed where each f_i is embodied to the corresponding device D_i, i = 1, …, T. (b) It also publishes the related input set 𝒳_{i, j} for the corresponding devices D_i and D_j on a public loud/ledger. The parties D₁ and D₂ communicate on an input x from a publicly available related input set 𝒳_1,2 and compute the output y using their respective PReFs f₁ and f₂. Note that an adversary with f₀ cannot predict the value y even if it shares PReF pairs 𝒳_1,0 and 𝒳_2,0 as $X_{1, 2} \cap X_{1, 0} = X_{1, 2} \cap X_{2, 0} = ϕ .$ {{\cal X}_{1,2}} \cap {{\cal X}_{1,0}} = {{\cal X}_{1,2}} \cap {{\cal X}_{2,0}} = \phi .

Chatterjee et al.'s Basic Key Exchange from PReFs. The basic key exchange protocol using PReF in Figure 4 is executed to establish a session key between two parties D₁ and D₂ where the party D₁ initiates the session as follows: D₁ selects x at random from the input set 𝒳_1,2 and then computes y₁ from x using f₁. Then D₁ computes A using y₁ and random r and sends (A,x) to D₂. Upon receiving (A,x), D₂ first finds y₂ as f₂(x) and then obtains r using A and y₂. Finally the session key is set as r. Note that the protocol makes use of only physically related function (existence of PUF) and linear Error correcting codes as per Definition A.1 to establish the session key between two parties in one round of communication. The protocol does not require secure storage contrary to the requirement of the scheme proposed in [32] that: (1) uses fuzzy extractors for correcting the noisy response and then match it with the response stored in a server and (2) is vulnerable to attacks as described in [12]. To avoid the possibility of such security vulnerabilities, the protocol in Figure 4 uses BCH-based error correction to reconcile the outputs of PReF from both the devices and then engage in fixation of session key. However the protocol in Figure 4 is secure only against passive adversaries.

Upgraded AKE. To achieve security against replay, impersonation and integrity attacks, the basic protocol in Figure 4 is proposed as depicted in Figure 5 by incorporating a collision-resistant hash function ℋ : {0, 1 }* → {0, 1}ⁿ. Note that it is computationally infeasible to sample TS′ ≠ TS and r ≠ r′ such that ℋ(r∥TS∥𝒟₁∥𝒟₂) = ℋ(r′∥TS′∥𝒟₁∥𝒟₂). Thus with the minimal addition to the basic PReF protocol, the upgraded protocol achieves the security guarantees of [33–35].

Chatterjee et al. [9] pointed out that the upgraded protocol depicted in Figure 5 does not achieve forward secrecy as x values are sent in clear. The adversary having black box access to the PReF oracle f_o that provides the output y = f_o(x) whenever x is given, will learn the session key of the particular session using A. Also, the protocol restricts usage of x more than once as the adversary learns sum of two session keys r + s whenever the same x is used in two sessions with different random values r and s.

Forward Secure AKE. In order to achieve forward secrecy, Chatterjee et al. [9] proposed to incorporate elliptic curve Diffie–Hellman based protocol to compute session keys using the ephemeral values α and β. The protocol is illustrated in Figure 6.

A Novel Forward-Secure Key Establishment Protocol from Physically Related Functions

Full Article

Paradigm

My account