Practical RSA-PAKE for Low-Power Device in Imbalanced Wireless Networks

Abstract

For enhancing the security of ubiquitous communication, we have to consider three keywords: mobility, wireless, and low computing capability. In this paper, we study one of suitable security protocols for the ubiquitous communication environment. We discuss RSA-based password-authenticated key exchange (RSA-PAKE) protocols for imbalanced wireless networks where a party uses a low-power device to communicate with another party equipped with a powerful computing device. For imbalanced wireless network applications, it is important to reduce the cost of communication for a low-power device even though the cost for powerful devices is increasing. The most power-consuming operation in RSA-PAKE protocols is the reliability test of unauthorized RSA public keys. Hence, it is important to design an efficient reliability test method to construct an efficient RSA-PAKE protocol. In this paper, we propose a new reliability test technique and design a provably secure RSA-PAKE protocol using the technique. Our protocol is suitable for securing the communications conducted over imbalanced wireless networks since the operations computed by one communicating party are efficient enough to be implemented on most low-power devices such as mobile phones and PDAs. The cost of a low-power device is reduced by 84.25% compared with CEKEP, the most efficient RSA-PAKE protocol. We prove the security of our protocol under a firmly formalized security model.

1. Introduction

For enhancing the security of ubiquitous communication, we have to consider three keywords: mobility, wireless, and low computing capability. In this paper, we study one of suitable security protocols for the ubiquitous communication environment. We discuss RSA-based password-authenticated key exchange (RSA-PAKE) protocols for imbalanced wireless networks where a party uses a low-power device to communicate with another party equipped with a powerful computing device.

For securing the communications conducted over wireless network, password-authenticated key exchange (PAKE) protocols are needed since two parties can establish a session key without storing any sensitive information in mobile devices. Note that we have an interest in imbalanced wireless networks where two communicating parties have different computational capabilities. Generally, mobile devices have low capabilities. Hence, for imbalanced wireless networks, it is important to reduce the cost of communications for a low-power device even though the cost for a powerful device is increased. For PAKE protocols that have been designed based on the Diffie-Hellman key exchange protocol (DH-PAKE protocol), each communicating party should compute at least two exponentiations with 160-bit exponents (for 80-bit security). Hence, it seems hard to design a DH-PAKE protocol for imbalanced wireless network applications where a party uses a low-power mobile device for communications. For PAKE protocols that have been designed based on the RSA function (RSA-PAKE protocol), one of the two parties can establish a session key by performing a small number of encryptions. Hence, RSA-based PAKE protocols seem to be suitable for imbalanced wireless networks since the cost of the RSA function is imbalanced in the sense that the encryption operation is very efficient while decryption is not. For example, if we use 3 as the public exponent for the RSA function, the encryption operation requires 2 multiplications while the decryption requires one exponentiation with a full-size (1024-bit) exponent.

For RSA-PAKE protocols, the existence of the public-key infrastructure (PKI) is not assumed, and thus a set of unauthorized public key pairs $(n,e)$ is used without any authorized certificate. Therefore, we have to verify the reliability of the unauthorized RSA keys. Due to the additional cost for verifying the reliability of the keys, it is not easy to design an efficient RSA-PAKE protocol. Note that the most power-consuming operation in RSA-PAKE protocols is the reliability test of unauthorized RSA public keys. Hence, it is important to design an efficient reliability test method to improve the performance of an RSA-PAKE protocol. Until now, several researchers have tried to design efficient RSA-PAKE protocols [1–8]. However, they are not sufficiently efficient enough to be implemented on most of low-power devices. Hence, it will be valuable to design a new RSA-PAKE protocol which provides a more efficient key exchange for low-power devices than existing RSA-PAKE protocols.

The goal of this paper is to design a new RSA-PAKE protocol which is suitable for securing the communications conducted over imbalanced wireless networks. To design an efficient RSA-PAKE, we provide very simple and efficient conditions for testing the reliability of a set of RSA parameters. In our protocol, a low-power device can establish a session key by choosing a 52-bit prime and performing one exponentiation with the prime exponent. According to our experimental results, the cost of a client is reduced by 84.25% compared with the CEKEP, which is the most efficient RSA-PAKE protocol until now. Our protocol can be implemented more efficiently by generating the prime before a key exchange protocol is initiated. In this case, the cost of a client can be reduced by 88.46%. We prove the security of our protocol in the random oracle model under a firmly formalized security model.

2. Preliminary

In this section, we briefly review formal security models for RSA-PAKE protocols and some mathematical backgrounds.

2.1. Security Model

Let A and B be two communicating parties, and let $\mathcal{D}$ be the password space. We assume that A and B share a password $pw\in \mathcal{D}$ . Let E be an active adversary who attacks the key exchange between A and B by controlling their messages. The adversary may capture transmitted messages and verify guessed passwords using the collected information until he/she finds the correct password. This type of attack is called an offline password guessing attack. The security goal of a password-authenticated key exchange protocol is to provide password-enabled key exchange which is secure against offline password guessing attacks mounted by the active adversary E. In this paper, we review the main points of well-formalized security models introduced by Bellare et al. [9]. (Refer to [9] for details.)

Adversarial Model. When a protocol is executed, each party behaves as specified in the protocol. For given queries, each instance returns its outputs. Let ${\Pi }_A^i$ be the ith instance of A. Note that each instance may be used only once. Each instance has a session key $sk$ , a session id $sid$ , and a partner id $pid$ . In general, the session id of ${\Pi }_A^i$ is the ordered concatenation of all messages sent and received by ${\Pi }_A^i$ . An adversary can make queries to any instance. When the instance returns its output to the adversary, the internal state of the instance is also updated. E can make the following queries for any instance.

• (i) 

$\text{Send}(A,i,m)$ . E sends a message m to the instance ${\Pi }_A^i$ . Then, ${\Pi }_A^i$ executes as specified by the protocol and returns its response to E. If the instance accepts given m as a valid message, the acceptance of the message, the session id $sid$ , and the partner id $pid$ will be made visible to E. If the message is not accepted as a valid one, the instance terminates the oracle call, and the termination is also made visible to the adversary.

(ii) 

$\text{Execute}(A,i,B,j)$ . By this oracle call, E obtains a transcript of an honest execution between two instances ${\Pi }_A^i$ and ${\Pi }_B^j$ , where ${\Pi }_A^i$ and ${\Pi }_B^j$ are unused instances such that $A\ne B$ .

(iii) 

$\text{Reveal}(A,i)$ . By this oracle call, $s{k}_A^i$ is given to the adversary E, where $s{k}_A^i$ is the session key of ${\Pi }_A^i$ .

(iv) 

$\text{Test}(A,i)$ . The instance ${\Pi }_A^i$ generates a random bit b. If $b=1$ , real session key of the instance is given to E. If $b=0$ , a random value is given to E as a session key. This query is allowed only once.

In the random oracle model, cryptographic hash functions are treated as random oracles. Hence, the adversary can make queries for random oracles. The queries for random oracles are treated as follows.

• (v) 

$\text{Oracle}(m)$ . E obtains a random value for the message m by this oracle call. When the oracle models a hash function, the answer returned by the oracle is the hashed value of m.

Partnering, Freshness, and Correctness. We say that two instances ${\Pi }_A^i$ and ${\Pi }_B^j$ are partnered if they satisfy the following conditions:

• (1)

${\Pi }_A^i$ and ${\Pi }_B^j$ have accepted given messages;

(2)

${\Pi }_A^i$ and ${\Pi }_B^j$ have the same session id $sid$ ;

(3)

the partner id of ${\Pi }_A^i$ is B and vice versa.

An instance ${\Pi }_A^i$ is called fresh if the instance has accepted given messages and E does not ask   $\text{Reveal}$ oracle queries for ${\Pi }_A^i$ or its partner instance ${\Pi }_B^j$ . The correctness requires that two instances should have the same session key if they are partnered and they have accepted.

Definitions of Security. Let $\mathcal{P}$ be a password-based protocol and let $\mathcal{A}$ be an adversary who tries to break the security of the protocol $\mathcal{P}$ . Let Succ be the event that $\mathcal{A}$ asks a Test query on a fresh instance ${\Pi }_A^i$ and correctly guesses the bit b which was selected during the Test query. Then, the advantage of $\mathcal{A}$ is defined as   $\text{Adv}(\mathcal{A},\mathcal{P})=2\text{Pr}[\text{Succ}]-1$ . Note that all probabilistic polynomial time adversaries can always test the validity of a guessed password by performing an online dictionary attack. Hence, the protocol $\mathcal{P}$ is considered to be secure if an online dictionary attack is the best way to break the security of $\mathcal{P}$ . Note that an online attack can be mounted by making a Send oracle query. Based on the above observation, the security of an RSA-PAKE protocol can be defined as follows.

Definition 1.

Let $\left|\mathcal{D}\right|$ be the size of the password space $\mathcal{D}$ and let $q_S$ be the number of Send queries. Then, an RSA-PAKE protocol $\mathcal{P}$ is secure if the following holds:

$$\begin{array}{cc}& {\mathsf{A}\mathsf{d}\mathsf{v}}_{\mathcal{P},\mathcal{D}}^{\mathsf{P}\mathsf{A}\mathsf{K}\mathsf{E}}=\underset{\mathcal{A}\in \mathcal{A}\mathcal{D}\mathcal{V}}{\max }\left\{\mathsf{A}\mathsf{d}\mathsf{v}\left(\mathcal{A},\mathcal{P}\right)\right\}\le \frac{q_S}{\left|\mathcal{D}\right|}+ϵ,\end{array}$$

(1)

where $\mathcal{A}\mathcal{D}\mathcal{V}$ is the set of all probabilistic polynomial time adversaries and ϵ is a negligible value.

2.2. Mathematical Background

We recall a well-known theorem, the prime number theorem [10], and use it for obtaining two theorems, Theorems 2 and 3, that are used to demonstrate the security of our protocol.

Recall that the prime number theorem tells us that the number of primes smaller than a positive integer x is approximately $\pi (x)\approx x/\ln x$ for a large x.

Theorem 2.

Let e be an ${\mathcal{l}}_e$ -bit prime chosen uniformly at random. Then, the probability that someone correctly guesses the prime is about $2{\mathcal{l}}_e/2^{{\mathcal{l}}_e}$ .

Theorem 3.

Let e be a randomly chosen ${\mathcal{l}}_e$ -bit pseudoprime which is not a prime with the probability $1/2^{{\mathcal{l}}_p}$ . Then, the probability that someone chooses an ${\mathcal{l}}_n$ -bit integer n such that $e\hspace{0.17em}|\hspace{0.17em}\mathrm{\hspace{0.17em}\hspace{0.17em}}\varphi (n)$ is bounded by $2{\mathcal{l}}_n/2^{{\mathcal{l}}_e}+1/2^{{\mathcal{l}}_p}$ .

It is easy to prove the above theorems, and thus we omit (Omitted proofs will be provided in the full-version of this paper.) them due to lack of space.

3. Our RSA-PAKE Protocol

In this section, we propose an efficient RSA-PAKE protocol which is suitable for imbalanced wireless networks. We assume that two communicating parties A and B share a common password $pw$ for establishing a session key. Let ${\mathcal{P}}_{{\mathcal{l}}_e}$ be the set of all ${\mathcal{l}}_e$ -bit pseudoprimes that are not prime with probability $1/2^{{\mathcal{l}}_p}\approx 1/2\left|\mathcal{D}\right|$ . The size of the prime is determined such that ${\mathcal{l}}_e\ge {\log }_2{\mathcal{l}}_n+{\log }_2\left|\mathcal{D}\right|+2$ . We use four hash functions $H:\{\mathrm{0,1}{\}}^{*}\to {\mathbb{Z}}_n$ and $H_i:\{\mathrm{0,1}{\}}^{*}\to \{\mathrm{0,1}{\}}^{{\mathcal{l}}_h}$ for $i=\mathrm{1,2},3$ . Then, our RSA-PAKE protocol runs as follows.

Step 1.

A chooses an ${\mathcal{l}}_n$ -bit RSA modulus n and a random $r_A\in \{\mathrm{0,1}{\}}^{{\mathcal{l}}_r}$ and sends them to B.

Step 2.

If n is not an ${\mathcal{l}}_n$ -bit odd number, B terminates the protocol. Otherwise, he/she chooses an ${\mathcal{l}}_e$ -bit prime e and a random $r_B\in \{\mathrm{0,1}{\}}^{{\mathcal{l}}_r}$ and computes   $\alpha =H(pw||\text{info})$ , where  $\text{info}=i{d}_A\left|\right|i{d}_B\left|\right|r_A\left|\right|r_B\left|\right|n\left|\right|e$ . If $\text{gcd}(\alpha ,n)\ne 1$ , B chooses a random $z\in {\mathbb{Z}}_n^{*}$ . Otherwise, he/she computes $z=\alpha ·r^e\mathrm{mod}n$ for randomly chosen $r\in {\mathbb{Z}}_n^{*}$ . B gives $(i{d}_B,i{d}_A,e,r_B,z)$ to A.

Step 3.

If e is not an ${\mathcal{l}}_e$ -bit prime, A terminates the protocol execution. A computes   $\alpha =H(pw||\text{info})$ and tests if two conditions $\text{gcd}(\alpha ,n)=1$ and $\text{gcd}(e,\varphi (n))=1$ hold. If one of the conditions does not hold, A chooses a random $\widehat{r}\in {\mathbb{Z}}_n^{*}$ . Otherwise, he/she computes $\widehat{r}=(z·{\alpha }^{-1}{)}^d\mathrm{mod}n$ , where $d=e^{-1}\mathrm{mod}\varphi (n)$ . Then, A computes   $\beta =H_1(\widehat{r}||\text{info})$ and sends it to B.

Step 4.

If the condition   $\beta =H_1(r||\text{info})$ does not hold, B terminates the protocol. Otherwise, B sends   $\gamma =H_2(r||\text{info})$ to A. B computes   $s{k}_B=H_3(r||\text{info})$ and uses it as a session key.

Step 5.

If   $\gamma \ne H_2(\widehat{r}||\text{info})$ , A terminates the protocol; otherwise, he/she computes   $s{k}_A=H_3(\widehat{r}||\text{info})$ and uses it as a session key.

Remark 4.

Note that, in our protocol, we use a pseudoprime which is not prime with probability $1/2^{{\mathcal{l}}_p}$ . Therefore, the number of iterations of the Miller-Rabin primary test is determined so that a pseudoprime is indeed a prime with probability $1-1/2^{{\mathcal{l}}_p}$ .

4. Security Analysis

In this section, we prove the security of our protocol according to the security model described in Section 2.1. Similar to the work by Zhang [7], we define a series of hybrid experiments where the first experiment describes the real adversary attack and each experiment is gradually modified so that the adversary has negligible advantage in the last experiment. We denote these hybrid experiments by  ${\text{Exp}}_i$ for $i\in \{0,\dots ,4\}$ . Let  $\text{Adv}(\mathcal{A},i)$ be the advantage of $\mathcal{A}$ in  ${\text{Exp}}_i$ .

Experiment  ${\text{Exp}}_0$ . The first experiment coincides with the real adversary attack. Therefore, all transmitting messages are computed according to the description of the proposed protocol. Since we prove the security of our protocol in the random oracle model, four hash functions are treated as random oracles and we maintain a list of input-output pairs for each random oracle.

Note that we have   ${\mathsf{A}\text{d}\mathsf{v}}_{\mathsf{R}\mathsf{S}\mathsf{A}\text{-}\mathsf{P}\mathsf{A}\mathsf{K}\mathsf{E},\mathcal{D}}^{\mathsf{P}\mathsf{A}\mathsf{K}\mathsf{E}}(\mathcal{A})=\text{Adv}(\mathcal{A},0)$ for an adversary $\mathcal{A}$ since the first experiment describes the real adversary attack.

Experiment  ${\text{Exp}}_1$ . In this experiment, we modify the Execute oracle. When the   $\text{Execute}$ oracle is called for two instances ${\Pi }_A^i$ and ${\Pi }_B^j$ , the session keys $s{k}_A^i$ and $s{k}_B^j$ are replaced by an ${\mathcal{l}}_h$ -bit random string rather than an output of the random oracle $H_3$ .

In Lemma 5, we will show that the increment of the advantage of $\mathcal{A}$ that resulted from the modification of the Execute oracle is bounded by a negligible value. Throughout this paper,  $\text{Ad}{\text{v}}_{\text{RSA}}$ denotes the maximum advantage of adversaries who solve the RSA problem.

Lemma 5.

For any polynomial time adversary $\mathcal{A}$ who asks at most $q_{\text{E}}$ times of Execute queries and $q_H$ times of hash queries, one has the following relation:

$$\begin{array}{cc}& \left|\mathsf{A}\mathsf{d}\mathsf{v}\left(\mathcal{A},0\right)-\mathsf{A}\mathsf{d}\mathsf{v}\left(\mathcal{A},1\right)\right|\le q_E{\mathsf{A}\mathsf{d}\mathsf{v}}_{\mathsf{R}\mathsf{S}\mathsf{A}}+\frac{q_E{q}_H}{\varphi \left(n\right)}.\end{array}$$

(2)

Proof.

We omit (Omitted proofs will be provided in the full-version of this paper.) the proof of Lemma 5, due to lack of space.

The remainder of our security proof is to show that the Send oracle gives negligible advantage to the adversary. We can classify Send oracle into five types as follows.

• (i) 

${\text{Send}}_0(A,i)$ . The instance ${\Pi }_A^i$ generates a random $r_A$ and an RSA modulus n and returns $r_A$ and n.

(ii) 

${\text{Send}}_1(B,j,i{d}_A,r_A,n)$ . If n is not an ${\mathcal{l}}_n$ -bit odd number, the protocol is terminated. Otherwise, ${\Pi }_B^j$ chooses an ${\mathcal{l}}_e$ -bit prime e and a random $r_B\in \{\mathrm{0,1}{\}}^{{\mathcal{l}}_r}$ , queries the hash oracle H on   $pw\left|\right|\text{info}$ where $\text{info}=i{d}_A\left|\right|i{d}_B\left|\right|r_A\left|\right|r_B\left|\right|n\left|\right|e$ , and receives the reply α from the oracle. If $\text{gcd}(\alpha ,n)\ne 1$ , ${\Pi }_B^j$ chooses a random $z\in {\mathbb{Z}}_n^{*}$ . Otherwise, it computes $z=\alpha ·r^e\mathrm{mod}n$ for randomly chosen $r\in {\mathbb{Z}}_n^{*}$ . The instance ${\Pi }_B^j$ returns $(e,r_B,z)$ .

(iii) 

${\text{Send}}_2(A,i,r_B,z,e)$ . If e is not an ${\mathcal{l}}_e$ -bit prime, the protocol execution is terminated. Otherwise, ${\Pi }_A^i$ queries H on   $pw\left|\right|\text{info}$ , receives the answer α from the oracle H, computes   $\alpha =H(pw||\text{info})$ , and tests if $\text{gcd}(\alpha ,n)=1$ and $\text{gcd}(e,\varphi (n))=1$ . If one of the conditions does not hold, ${\Pi }_A^i$ chooses a random $\widehat{r}\in {\mathbb{Z}}_n^{*}$ ; otherwise, it computes $\widehat{r}=(z·{\alpha }^{-1}{)}^d\mathrm{mod}n$ . Then, ${\Pi }_A^i$ queries the hash oracle $H_1$ on    $\widehat{r}\left|\right|\text{info}$ and returns the reply β received from $H_1$ .

(iv) 

${\text{Send}}_3(B,j,\beta )$ . If the answer returned by $H_1$ on    $r\left|\right|\text{info}$ is not β, ${\Pi }_B^j$ rejects the protocol; otherwise, it queries the hash oracles $H_2$ and $H_3$ on   $r\left|\right|\text{info}$ and receives the replies γ and $sk$ from $H_2$ and $H_3$ , respectively. Then, ${\Pi }_B^j$ accepts $sk$ as a session key and returns γ.

 (v)

${\text{Send}}_4(A,i,\gamma )$ . If the answer returned by $H_2$ on $\widehat{r}\left|\right|\text{info}$ is not γ, ${\Pi }_A^i$ rejects the protocol; otherwise, ${\Pi }_A^i$ accepts the answer returned by the oracle $H_3$ on   $\widehat{r}\left|\right|\text{info}$ as a session key.

A message is called oracle generated if it was returned by an instance; otherwise, the message is called adversary generated. If a message was returned by ${\Pi }_A^i$ , it is called ${\Pi }_A^i$ -oracle-generated message.

Experiment  ${\text{Exp}}_2$ . In this experiment, we modify the following if an instance ${\Pi }_B^j$ receives a ${\Pi }_A^i$ -oracle-generated message $(r_A,n)$ in a Send oracle call.

• (i)

If both ${\Pi }_A^i$ and ${\Pi }_B^j$ accept, we choose a random ${\mathcal{l}}_h$ -bit value and give it to two instances as a session key.

(ii)

If ${\Pi }_A^i$ does not accept but ${\Pi }_B^j$ accepts, we choose a random ${\mathcal{l}}_h$ -bit value and give it to ${\Pi }_B^j$ as a session key. In this case, no session key is defined for ${\Pi }_A^i$ .

Lemma 6.

For any polynomial time adversary $\mathcal{A}$ who asks at most $q_S$   Send queries, one has

$$\begin{array}{cc}& \left|\mathsf{A}\mathsf{d}\mathsf{v}\left(\mathcal{A},1\right)-\mathsf{A}\mathsf{d}\mathsf{v}\left(\mathcal{A},2\right)\right|\le q_S{\mathsf{A}\mathsf{d}\mathsf{v}}_{\mathsf{R}\mathsf{S}\mathsf{A}}+\frac{q_S{q}_H}{\varphi \left(n\right)}.\end{array}$$

(3)

Proof.

Let $n=pq$ be an RSA modulus where p and q are distinct primes. Note that since the modulus n is chosen by the instance ${\Pi }_A^i$ (not by the adversary $\mathcal{A}$ ),

$$\begin{array}{cc}& \mathsf{P}\mathsf{r}\left[\text{gcd}\left(\alpha ,n\right)\ne 1\right]=\frac{n-\varphi \left(n\right)}{n}=\frac{p+q-1}{n}\approx \frac{1}{2^{{\mathcal{l}}_n/2}}\end{array}$$

(4)

for randomly chosen $\alpha \in {\mathbb{Z}}_n^{*}$ . Hence, we can assume that $\text{gcd}(\alpha ,n)=1$ for randomly chosen $\alpha \in {\mathbb{Z}}_n^{*}$ .

Assume that ${\Pi }_B^j$ receives a ${\Pi }_A^i$ -oracle-generated message $(r_A,n)$ in a Send oracle call and returns $(e,r_B,z)$ where e is ${\mathcal{l}}_e$ -bit prime, $r_B\in \{\mathrm{0,1}{\}}^{{\mathcal{l}}_r}$ , and $z=\alpha ·r^e\mathrm{mod}n$ for random $r\in {\mathbb{Z}}_n^{*}$ and $\alpha \in {\mathbb{Z}}_n^{*}$ . Note that α is the answer returned by the random oracle H on $pw\left|\right|i{d}_A\left|\right|i{d}_B\left|\right|r_A\left|\right|r_B\left|\right|n\left|\right|e$ , since $\text{gcd}(\alpha ,n)=1$ holds with probability $1\approx 1-2^{-{\mathcal{l}}_n/2}$ . Note that, as proved in Lemma 5, we can show that the probability that $\mathcal{A}$ recovers the random value r is  ${\text{P}}_r\le \text{Ad}{\text{v}}_{\text{RSA}}+q_H/\varphi (n)$ . Since $\mathcal{A}$ cannot generate valid β and γ without the knowledge of r, two instances ${\Pi }_A^i$ and ${\Pi }_B^j$ accept the protocol execution only if the instances ${\Pi }_A^i$ and ${\Pi }_B^j$ receive ${\Pi }_B^j$ -oracle-generated message β and ${\Pi }_A^i$ -oracle-generated message γ, respectively. Hence, $\mathcal{A}$ can distinguish   ${\text{Exp}}_1$ and  ${\text{Exp}}_2$ only if the adversary can test to see whether or not a session key is the answer returned by the random oracle $H_3$ on $r\left|\right|i{d}_A\left|\right|i{d}_B\left|\right|r_A\left|\right|r_B\left|\right|n\left|\right|e$ . Without the knowledge of r, the session key seems to be a random value in $\mathcal{A}$ 's point of view, and thus $\mathcal{A}$ cannot distinguish between two experiments. As a result, we have $\left|\text{Adv}(\mathcal{A},1)-\text{Adv}(\mathcal{A},2)\right|=q_S{\text{P}}_r\le q_S\text{Ad}{\text{v}}_{\text{RSA}}+$   $q_S{q}_H/\varphi (n)$ , since $\mathcal{A}$ asks at most $q_S$ times of Send queries.

Experiment  ${\text{Exp}}_3$ . In this experiment, we consider the case where an instance ${\Pi }_A^i$ receives a ${\Pi }_B^j$ -oracle-generated message $(e,r_B,z)$ in a   ${\text{Send}}_2$ oracle call, while the instance ${\Pi }_B^j$ received a ${\Pi }_A^i$ -oracle-generated message $(r_A,n)$ in  a   ${\text{Send}}_1$ oracle call. If ${\Pi }_A^i$ and ${\Pi }_B^j$ accept the protocol execution and their session keys are not replaced by a random value in the experiment   ${\text{Exp}}_2$ , we give a random ${\mathcal{l}}_h$ -bit value to them as a session key.

Lemma 7.

For any polynomial time adversary $\mathcal{A}$ who asks at most $q_S$   Send queries, one has $\text{Adv}(\mathcal{A},2)=\text{Adv}(\mathcal{A},3)$ .

Proof.

It is clear that the advantage of $\mathcal{A}$ in   ${\text{Exp}}_3$ is identical with its advantage in  ${\text{Exp}}_2$ since the only way to distinguish two experiments is recovering the random value as discussed in Lemma 6.

Experiment  ${\text{Exp}}_4$ . In this experiment, we consider the case where an instance ${\Pi }_A^i$ (or ${\Pi }_B^j$ ) receives an adversary-generated message in a  ${\text{Send}}_2$ (or  ${\text{Send}}_1$ ) oracle call. If ${\Pi }_A^i$ (or ${\Pi }_B^j$ ) accepts the protocol execution, we stop the experiment and the adversary is said to have succeeded. Note that the modification of the experiment certainly improves the adversary's advantage.

Lemma 8.

For any polynomial time adversary $\mathcal{A}$ , one has the following relation:   $\text{Adv}(\mathcal{A},3)\le \text{Adv}(\mathcal{A},4)$ .

Proof.

Note that, in   ${\text{Exp}}_4$ , the adversary $\mathcal{A}$ can obtain more information than in   ${\text{Exp}}_3$ . Hence, it is obvious that   $\text{Adv}(\mathcal{A},4)$ is greater than   $\text{Adv}(\mathcal{A},3)$ .

It remains to show that the adversary's advantage in the last experiment is negligible.

Lemma 9.

For any polynomial time adversary $\mathcal{A}$ who asks at most   $q_S\hspace{0.17em}\hspace{0.17em}\text{Send}$ queries and $q_H$ random oracle queries, one has    $\text{Adv}(\mathcal{A},4)\le q_S/\left|\mathcal{D}\right|+q_S\text{Ad}{\text{v}}_{\text{RSA}}+q_S{q}_H/\varphi (n)+q_S/2^{{\mathcal{l}}_h}$ .

Proof.

We omit (Omitted proofs will be provided in the full-version of this paper.) the proof of Lemma 9, due to lack of space.

By combining Lemmas 5, 6, 7, 8, and 9, we obtain Theorem 10.

Theorem 10.

Let $\mathcal{A}$ be a probabilistic polynomial time algorithm which asks at most $q_E$   Execute queries, $q_S$   Send queries, and $q_H$   Oracle queries for hash functions. Let $\left|\mathcal{D}\right|$ be the size of password space $\mathcal{D}$ . Then, one has

$$\begin{array}{cc}& {\mathsf{A}\mathsf{d}\mathsf{v}}_{\mathsf{R}\mathsf{S}\mathsf{A}\text{-}\mathsf{P}\mathsf{A}\mathsf{K}\mathsf{E},\mathcal{D}}^{\mathsf{P}\mathsf{A}\mathsf{K}\mathsf{E}}\left(\mathcal{A}\right)\le \frac{q_S}{\left|\mathcal{D}\right|}+q_1{\mathsf{A}\mathsf{d}\mathsf{v}}_{\mathsf{R}\mathsf{S}\mathsf{A}}+\frac{q_2}{\varphi \left(n\right)}+\frac{q_S}{2^{{\mathcal{l}}_h}},\end{array}$$

(5)

where $q_1=q_E+3q_S$ and $q_2=(q_E+3q_S)q_H$ .

Proof.

Note that, by Lemma 8, it is easy to see that   $\text{Adv}(\mathcal{A},0)\le {\sum }_{i=0}^2‍|\text{Adv}(\mathcal{A},i)-\text{Adv}(\mathcal{A},i+1)|+\text{Adv}(\mathcal{A},4)$ . By Lemmas 5, 6, 7, and 9, we have

$$\begin{array}{cc}& \mathsf{A}\mathsf{d}\mathsf{v}(\mathcal{A},0)\le \frac{q_S}{\left|\mathcal{D}\right|}+q_1{\mathsf{A}\mathsf{d}\mathsf{v}}_{\mathsf{R}\mathsf{S}\mathsf{A}}+\frac{q_2}{\varphi \left(n\right)}+\frac{q_S}{2^{{\mathcal{l}}_h}},\end{array}$$

(6)

where $q_1=q_E+3q_S$ and $q_2=(q_E+3q_S)q_H$ . Since      ${\mathsf{A}\mathsf{d}\mathsf{v}}_{\mathsf{R}\mathsf{S}\mathsf{A}\text{-}\mathsf{P}\mathsf{A}\mathsf{K}\mathsf{E},\mathcal{D}}^{\mathsf{P}\mathsf{A}\mathsf{K}\mathsf{E}}(\mathcal{A})=\text{Adv}(\mathcal{A},0)$ , we complete the proof of Theorem 10.

Note that Theorem 10 tells us that the proposed RSA-PAKE protocol is secure in terms of the security models described in Section 2.1 if the RSA problem is intractable.

5. Performance

In this section, we compare the proposed protocol with existing RSA-PAKE protocols, except the EPAKE protocol since the insecurity of that protocol has been discovered [11]. Let  ${\text{C}}_{\text{Exp}}^a$ be the cost of an exponentiation under a 1024-bit modulo with an a-bit exponent, let ${\text{C}}_{\text{MGen}}^a$ be the cost of generating an a-bit RSA modulus,  let ${\text{C}}_{\text{PGen}}^a$ be the cost of generating an a-bit prime, and let  ${\text{C}}_{\text{PVer}}^a$ be the cost of verification of an a-bit prime. Note that $\alpha {\text{C}}_{\text{Exp}}^a={\text{C}}_{\text{Exp}}^{\alpha a}$ . For comparison, we set ${\mathcal{l}}_n=1024$ , ${\mathcal{l}}_r={\mathcal{l}}_h=160$ , ${\mathcal{l}}_{e_1}=1025$ , ${\mathcal{l}}_{e_2}=96$ , and ${\mathcal{l}}_e=52$ . For determining the number of Miller-Rabin primary tests, we refer to [12]. Our protocol uses a 52-bit pseudoprime e which is indeed prime with probability $1-1/2^{{\mathcal{l}}_p}(=1-2^{-41})$ , and so it suffices to perform the primary tests 37 times according to the formula given in [12].

We performed experiments under Windows XP Professional with a 3.4 GHz Pentium 4 processor. As seen in Table 1, our protocol provides very efficient key exchange compared with other RSA-PAKE protocols in terms of the computational complexity. The computational complexity of the party is reduced by 84.25% compared to the CEKEP protocol. Moreover, the proposed protocol can be implemented more efficiently by generating a prime before a key exchange protocol is initiated. The PEKEP is the most efficient RSA-PAKE protocol in terms of communication overhead. The size of the communicating message of our scheme is almost the same as that of the PEKEP and shorter than other protocols, and thus our protocol is also efficient in terms of the communication overhead.

Table 1

Performance comparison.

(a) Computational cost of client (low-power device holder).
	Parameters		Encryption		Execution time
	Operation	Time	Operation	Time	Total	Precomp.
SNAPI [3]	${\mathsf{C}}_{\mathsf{P}\mathsf{V}\mathsf{e}\mathsf{r}}^{1025}$	156.89 ms	${\mathsf{C}}_{\mathsf{E}\mathsf{x}\mathsf{p}}^{1025}$	49.06 ms	205.95 ms	205.95 ms
PEKEP [7]	—	0 ms	${646\mathsf{C}}_{\mathsf{E}\mathsf{x}\mathsf{p}}^{\left|e\right|}$ ( $e=3$ )	188.31 ms	188.31 ms	188.31 ms
CEKEP [7]	—	0 ms	${50\mathsf{C}}_{\mathsf{E}\mathsf{x}\mathsf{p}}^{\left|e\right|}$ ( $e=3$ )	29.2 ms	29.2 ms	29.2 ms
Ours	${\mathsf{C}}_{\mathsf{P}\mathsf{G}\mathsf{e}\mathsf{n}}^{52}$	1.23 ms	${\mathsf{C}}_{\mathsf{E}\mathsf{x}\mathsf{p}}^{52}$	3.37 ms	4.6 ms	3.37 ms

(b) Computational cost of server (powerful computing equipment holder).
	Parameters		Encryption		Execution time
	Operation	Time	Operation	Time	Total	Precomp.
SNAPI [3]	${\mathsf{C}}_{\mathsf{M}\mathsf{G}\mathsf{e}\mathsf{n}}^{1024}$	760.58 ms	${\mathsf{C}}_{\mathsf{E}\mathsf{x}\mathsf{p}}^{1024}$	48.78 ms	809.36 ms	48.78 ms
PEKEP [7]	${\mathsf{C}}_{\mathsf{M}\mathsf{G}\mathsf{e}\mathsf{n}}^{1024}$	760.58 ms	${2\mathsf{C}}_{\mathsf{E}\mathsf{x}\mathsf{p}}^{1024}$	97.56 ms	858.14 ms	97.56 ms
CEKEP [7]	${\mathsf{C}}_{\mathsf{M}\mathsf{G}\mathsf{e}\mathsf{n}}^{1024}$	760.58 ms	${3\mathsf{C}}_{\mathsf{E}\mathsf{x}\mathsf{p}}^{1024}$	146.34 ms	906.92 ms	146.34 ms
Ours	${\mathsf{C}}_{\mathsf{M}\mathsf{G}\mathsf{e}\mathsf{n}}^{1024}+{\mathsf{C}}_{\mathsf{P}\mathsf{V}\mathsf{e}\mathsf{r}}^{52}$	761.13 ms	${\mathsf{C}}_{\mathsf{E}\mathsf{x}\mathsf{p}}^{1024}$	48.78 ms	809.91 ms	49.33 ms

(c) Communication overhead
	Transmitting messages		Rounds
	Components	Length
SNAPI [3]	$2{\mathcal{l}}_n+{\mathcal{l}}_{e_1}+2{\mathcal{l}}_r+2{\mathcal{l}}_h$	3713 bits	4
PEKEP [7]	$2{\mathcal{l}}_n+2{\mathcal{l}}_r+2{\mathcal{l}}_h$	2688 bits	4
CEKEP [7]	$3{\mathcal{l}}_n+4{\mathcal{l}}_r+2{\mathcal{l}}_h$	4032 bits	6
Ours	$2{\mathcal{l}}_n+{\mathcal{l}}_e+2{\mathcal{l}}_r+2{\mathcal{l}}_h$	2740 bits	4

6. Conclusion

In this paper, we proposed an efficient RSA-PAKE protocol which is suitable for securing the communications conducted over imbalanced wireless networks and proved the security of our protocol in the random oracle model. Compared with other RSA-PAKE protocols, our protocol provides very efficient key exchange. In our protocol, the cost of a low-power device holder can be reduced by 84.25% compared with the CEKEP. Moreover, our protocol can be implemented more efficiently by pregenerating a prime before a key exchange protocol is initiated.