Security Analysis of an Enhanced Certificateless Signcryption in the Standard Model

Abstract

Quite recently, Luo and Wan putted forward a new certificateless signcryption (CLSC) scheme with low computation cost in the standard model. They stated that their newly proposed scheme achieves the unforgeability against adaptive chosen message attack (i.e, unforgeability) and indistinguishability against adaptive chosen ciphertext attack (i.e., confidentiality). However, we find that the scheme cannot reach the claimed security feature. Specifically, in this paper, we will demonstrate that in Luo and Wan’s CLSC scheme, the plaintext can be easily recovered from the ciphertext by ordinary attacker and malicious-but-passive KGC. In addition, we identify that this scheme even cannot resist forgery attack of a malicious KGC.

1 Introduction

Unforgeability and confidentiality are two fundamental security requirements in many real-world cryptographic applications. The former can be realized by adopting signature and the latter can be achieved using encryption. When both requirements are needed, a conventional method is using the sign-then-encrypt. The drawback of this approach is low efficiency. Therefore, this method is not suitable for computationally restricted environments or low-bandwidth communication networks. To overcome the weakness mentioned above, in Crypto’97, Zheng proposed a new public key cryptography primitive called signcryption (SC) in [1] for offering message confidentiality and unforgeability simultaneously. It aims to have lower communication overhead and computational cost than the conventional method.

The first concrete SC scheme was given by Zheng [1], which is based on the traditional public key infrastructure (PKI). After this pioneering work, many traditional PKI-based and identity (ID)-based SC schemes [2,3,4,5] have been constructed. In traditional PKI, SC scheme requires certificate to bind user’s public key, which bring the problem of certificate management. Through adopting user’s identity as its public key, ID-based SC scheme addresses this problem. In ID-based SC scheme, both sender’s signing key and receiver’s decrypting key are supplied by a Private Key Generator (PKG). Therefore, it will yields security issue: key escrow. Barbosa and Farshim [6] first proposed a certificateless signcryption (CLSC) to solve the problems of key escrow and certificate management. In CLSC, user’s key consists of two parts: one is his public/secret key pair created by the user himself; the other is partial private key issued by a Key Generation Certer (KGC). The cryptographic operations of CLSC, such as signature and decryption, are able to be executed only if an executor knows not only the partial private key but also the secret key. In addition, compared with the PKI-based scheme, an important advantage of certificateless (CL) scheme is that CL scheme does not require certificate. In CLSC, the encryption process and verification process only require the public key of the receiver and public key of the sender, respectively.

Motivated by above attractive features, following the seminal work of Barbosa and Farshim in [6], many researchers have devoted themselves to the design of secure and practical CLSC schemes. However, the security of most of the previous CLSC schemes is just proven using the idealized random oracle (RO). The first CLSC scheme without RO model was proposed by Liu et al. [7]. Later, several CLSC schemes were proposed [8,9,10] in the standard model. Considering that most of SC schemes in the standard model have some weaknesses in terms of temporary information security or computation cost, Luo and Wan [11] proposed a new CLSC scheme in the standard model to overcome the aforementioned weaknesses. They claimed that their newly proposed scheme achieves not only message unforgeability, but also message confidentiality.

However, we find that their scheme is not as secure as they claimed. We will show that both the ordinary attacker and malicious-but-passive KGC in fact can break the confidentiality of their scheme. Moreover, even an honest-but-curious KGC can also break the unforgeability of the scheme.

2 Reviewing Luo and Wan’s Scheme

In this section, we briefly review of the CLSC scheme of Luo and Wan, which consists of five algorithms as follows:

Setup

Let G₁, G₂ be cyclic groups with prime order p and g be generator of G₁. $e:G_{1} \times G_{1} \to G_{2}$ is defined as a bilinear map. $H:\{ 0,1\}^{*} \to \{ 0,1\}^{{B_{m} }}$ is a collision resistant hash function. This algorithm randomly selects two elements $u^{\prime},m^{\prime} \in G_{1}$, and two vectors $\vec{u} = (u_{i} )_{{B_{u} }} ,\vec{m} = (m_{j} )_{{B_{m} }}$ of length B_u and B_m, respectively. In addition, it also selects $\alpha \in Z_{p}^{*}$ at random as the master secret key and sets $P_{pub} = g^{\alpha }$. The public parameter is set to be $params = \{ G_{1} ,G_{2} ,e,p,g,P_{pub} ,u^{\prime},m^{\prime},\vec{u},\vec{m},H\}$.

UKG

The user with identity $u \in \{ 0,1\}^{{B_{u} }}$ selects random number x_u from $Z_{p}^{*}$ and sets his secret key and public key pair $(x_{u} ,PK_{u} )$, where $PK_{u} = g^{{x_{u} }}$.

PPKE

Let U denote the set $\{ i|u_{i} = 1,1 \le i \le B_{u} \}$, where u_i is the ith bit of identity $u \in \{ 0,1\}^{{B_{u} }}$. For user with identity u, this algorithm computes $d_{u} = (u^{\prime}\prod\nolimits_{i \in U} {u_{i} } )^{\alpha }$ as user u’s partial private key.

Signcrypt

When sender A with identity u_A attempts to securely send a message M to the receiver B with identity u_B and public key PK_B, he selects a random number $k \in Z_{p}^{*}$. Then A uses his partial private key and secret key $(d_{A} ,x_{A} )$ to compute the signcryption information $\sigma = (R,S,T)$ of M as follows:

$$R = M \cdot PK_{B}^{{x_{A} }} \cdot e\left( {d_{A} \cdot PK_{B}^{k} ,{\kern 1pt} u^{{\prime }} \prod\limits_{i \in U_{B}} {u_{i} } } \right),\quad S = g^{k} ,\quad T = d_{A} \cdot \left( {m^{{\prime }} \prod\limits_{{j \in \bar{M}}} {m_{j} } } \right)^{{k + x_{A} }}$$

(1)

where $\bar{M} \subset \{ 1,2, \ldots ,B_{m} \}$ denotes the set $\{ j|m_{j} = 1,1 \le j \le B_{m} \}$, m_j is the jth bit of the hash value $m = H(R,S,u_{A} ,u_{B} ,PK_{A} ,PK_{B} )$.

Unsigncrypt

Receiver B computes $m = H(R,S,u_{A} ,u_{B} ,PK_{A} ,PK_{B} )$ and verifies whether the equation below holds

$$e(T,g) = e\left( {P_{pub} ,u^{\prime}\prod\limits_{{i \in U_{A} }} {u_{i} } } \right) \cdot e\left( {S,m^{\prime}\prod\limits_{{j \in \bar{M}}} {m_{j} } } \right) \cdot e\left( {PK_{A} ,m^{\prime}\prod\limits_{{j \in \bar{M}}} {m_{j} } } \right)$$

(2)

If it does not hold, B returns “⊥”; otherwise, B decrypts the ciphertext:

$$M = R/\left( {PK_{A}^{{x_{B} }} \cdot e\left( {d_{B} ,u^{\prime}\prod\limits_{{i \in U_{A} }} {u_{i} } } \right) \cdot e\left( {S^{{x_{B} }} ,u^{\prime}\prod\limits_{{i \in U_{A} }} {u_{i} } } \right)} \right)$$

(3)

3 Security Analysis of Luo and Wan’s Scheme

In [11], the authors claimed that their CLSC scheme can provide both message unforgeability and message confidentiality requirements against two types of the attackers: ordinary attacker ${\mathcal{A}}_{I}$ and malicious-but-passive KGC ${\mathcal{A}}_{II}$. The former can replace the user public key PK_u; however, it cannot access to the target user partial private key d_u. While the latter has the ability to generate the system parameter maliciously, but it can neither perform public key replacement nor access the target user secret key x_u. In this section, we present several concrete attacks to demonstrate that if there exist both ordinary attacker ${\mathcal{A}}_{I}$ and malicious-but-passive KGC attacker ${\mathcal{A}}_{II}$, the CLSC scheme does not satisfy the essential security requirements of CLSC, i.e., confidentiality and unforgeability.

For convenience, we let $F_{1} (u)$ denote $u^{\prime}\prod\nolimits_{i \in U} {u_{i} }$, where $u \in \{ 0,1\}^{{B_{u} }}$,$U = \{ i|u_{i} = 1,1 \le i \le B_{u} \}$, and let $F_{2} (m)$ denote $m^{\prime}\prod\nolimits_{{j \in \bar{M}}} {m_{j} }$, where $m \in \{ 0,1\}^{{B_{m} }}$,$\bar{M} = \{ j|m_{j} = 1,1 \le j \le B_{m} \}$, i.e.,

$$F_{1} (u) = u^{{\prime }} \prod\limits_{i \in U} {u_{i} } ,\quad F_{2} (m) = m^{{\prime }} \prod\limits_{{j \in \bar{M}}} {m_{j} } .$$

3.1 Analysis of Unforgeability

In this subsection, we reveal that a malicious-but-passive KGC as an attacker has the ability to break the unforgeability of Luo and Wan’s CLSC scheme. We also show that it is even possible for an honest-but-curious KGC (who honestly runs Setup algorithm) to mount forgery attack.

3.1.1 Malicious-But-Passive KGC Forgery Attack

A dishonest KGC ${\mathcal{A}}_{II}$ can impersonate a sender u_A to forge his signcryption information of arbitrarily chosen message by maliciously generating system parameters. Concretely, ${\mathcal{A}}_{II}$ executes the following three steps.

• Step 1 In the Setup procedure, implant a trapdoor in the following way:

  • 1. Randomly choose $x^{\prime},x_{i},y^{\prime},y_{j} \in Z_{p}^{*}$ and dishonestly create $u^{{\prime }} = g^{{x^{\prime}}} ,u_{i} = g^{{x_{i} }},m^{{\prime }} = g^{{y^{\prime}}} ,m_{j} = g^{{y_{j} }}$ for $1 \le i \le B_{u},1 \le j \le B_{m}$.

  • 2. Produce other system parameters along with master secret key according to Setup algorithm. Thus, we have $F_{1} (u) = u^{\prime}\prod\nolimits_{i \in U} {u_{i} } = g^{{x^{\prime} + \sum\limits_{i \in U} {x_{i} } }}$ for user identity u.

• Step 2 Obtain $PK_{B}^{{x_{A} }}$ in the following way:

  • 1. Choose an arbitrary message M, submit $(M,u_{A} ,u_{B} )$ for a Signcrypt query and obtain the signcryption (R, S, T) as a response.

  • 2. Using $PK_{B}^{{x_{A} }} = R/\left( {M \cdot e\left( {d_{A} ,F_{1} (u_{B} )} \right) \cdot e\left( {S^{{x^{\prime} + \sum\limits_{{i \in U_{B} }} {x_{i} } }} ,PK_{B} } \right)} \right)$ retrieve $PK_{B}^{{x_{A} }}$.

• Step 3 Use $PK_{B}^{{x_{A} }}$ and forge a signcryption in the following way.

  • 1. Choose an arbitrary message $M^{*}$;

  • 2. Calculate the signcryption $\sigma^{*} = (R^{*} ,S^{*} ,T^{*} )$ of message $M^{*}$ as:

    $$R^{*} = M^{*} \cdot PK_{B}^{{x_{A} }} \cdot e(d_{A} \cdot PK_{B}^{k} ,F_{1} (u_{B} )),\quad S^{*} = g^{k} ,\quad T^{*} = d_{A} (F_{2} (m^{*} ))^{k} \cdot (PK_{A} )^{{y^{\prime} + \sum\limits_{{i \in \bar{ M} }} {y_{j} } }}$$

    where k is randomly chosen from $Z_{p}^{*}$.

It is obvious that the forged $\sigma^{*}$ is a valid signcryption information $\sigma^{*} = \left( {R^{*} ,S^{*} ,T^{*} } \right)$ on the message $M^{*}$ and ${\mathcal{A}}_{II}$ does not compromise any user secret key. It means that the KGC is able to forge a signcryption information for any message.

3.1.2 Honest-But-Curious KGC Forgery Attack

An honest-but-curious KGC ${\mathcal{A}}_{II}$ can create a valid signcryption information on arbitrarily chosen message. Concretely, ${\mathcal{A}}_{II}$ executes the following two steps.

• Step 1 Obtain the value $PK_{A}^{{x_{B} }} e(PK_{A}^{{ - x_{B} }} ,F_{1} (u_{B} ))$ in the following way:

  • 1. Given the master secret key α and the system parameter params which are the output of the setup algorithm of Luo and Wan’s scheme.

  • 2. Randomly choose a message $M \in \{ 0,1\}^{*}$ and generate the triple-tuple $c^{\prime} = (R^{\prime},S^{\prime},T^{\prime})$ as follows:

    $$R^{{\prime }} = M \cdot e(d_{A} \cdot PK_{B}^{{k^{\prime}}} ,F_{1} (u_{B} )),\quad S^{{\prime }} = g^{{k^{\prime}}} (PK_{A} )^{ - 1} ,\quad T^{{\prime }} = d_{A} (F_{2} (m^{{\prime }} ))^{{k^{\prime}}}$$

    where k′ is a random value chosen $Z_{p}^{*}$, and $m^{\prime} = H(R^{\prime},S^{\prime},u_{A} ,u_{B} ,PK_{A} ,PK_{B} )$. It be easily verified that $e(T^{\prime},g) = e(P_{pub} ,F_{1} (u_{A} )) \cdot e(S^{\prime},F_{2} (m^{\prime})) \cdot e(PK_{A} ,F_{2} (m^{\prime}))$ holds. Therefore, this forged triple $c^{\prime} = (R^{\prime},S^{\prime},T^{\prime})$ is a valid ciphertext under the sender u_A’s public key PK_A and receiver u_B’s public key PK_B.

  • 3. Submit $(c^{\prime},u_{A} ,u_{B} )$ for a Unsigncrypt query where u_A and u_B act as the sender’s identity and receiver’s identity, respectively. Then obtain an answer M″. Since this forged signcryption $c^{\prime} = (R^{\prime},S^{\prime},T^{\prime})$ can pass through Eq. (2), the result $M^{\prime\prime}$ of Unsigncrypt query is not ‘‘⊥’’. It means that M″ is the plaintext of ciphertext c′. According to the decryption Eq. (3), M″ is computed as follows

    $$M^{\prime\prime} = R^{\prime}/\left( {PK_{A}^{{x_{B} }} e(d_{B} ,F_{1} (u_{A} ))e(S^{\prime{x_{B} }} ,F_{1} (u_{B} )} \right)$$

    (4)

    Combining Eq. (2) and Eq. (4), we have

    $$\begin{aligned} M^{{\prime \prime }} & = M \cdot e(d_{A} \cdot PK_{B}^{{k^{\prime}}} ,F_{1} (u_{B} ))/\left( {PK_{A}^{{x_{B} }} e(d_{B} ,F_{1} (u_{A} ))e(\left( {g^{{k^{\prime}}} (PK_{A} )^{ - 1} } \right)^{{x_{B} }} ,F_{1} (u_{B} ))} \right) \\ & = M \cdot e(d_{A} \cdot (g^{{k^{\prime}}} )^{{x_{B} }} ,F_{1} (u_{B} ))/\left( {PK_{A}^{{x_{B} }} \cdot e(d_{A} \cdot (g^{{k^{\prime}}} )^{{x_{B} }} \cdot (PK_{A} )^{{ - x_{B} }} ,F_{1} (u_{B} ))} \right) \\ & = M/\left( {PK_{A}^{{x_{B} }} e(PK_{A}^{{ - x_{B} }} ,F_{1} (u_{B} ))} \right) \\ \end{aligned}$$

  • 4. From $M^{\prime\prime} = M/PK_{A}^{{x_{B} }} e(PK_{A}^{{ - x_{B} }} ,F_{1} (u_{B} ))$, derive $PK_{A}^{{x_{B} }} e(PK_{A}^{{ - x_{B} }} ,F_{1} (u_{B} ))$ by computing $PK_{A}^{{x_{B} }} e(PK_{A}^{{ - x_{B} }} ,F_{1} (u_{B} )) = M/M^{\prime\prime}$.

• Step 2 With $PK_{A}^{{x_{B} }} e(PK_{A}^{{ - x_{B} }} ,F_{1} (u_{B} ))$ and sender’s partial private key d_A, forge a signcryption as follows.

  • 1. Choose an arbitrary message $M^{*}$;

  • 2. Calculate the signcryption $\sigma^{*} = (R^{*} ,S^{*} ,T^{*} )$ of message $M^{*}$ as:

    $$R^{*} = M^{*} \cdot W \cdot e(d_{A} \cdot PK_{B}^{k} ,F_{1} (u_{B} )),\quad S^{*} = g^{k} PK_{A}^{ - 1} ,\quad T^{*} = d_{A} (F_{2} (m^{*} ))^{k}$$

    where k is randomly chosen from $Z_{p}^{*} ,W = PK_{A}^{{x_{B} }} e(PK_{A}^{{ - x_{B} }} ,F_{1} (u_{B} )),m^{*} = H(R^{*} ,S^{*} ,u_{A} ,u_{B} ,PK_{A} ,PK_{B} )$.

This $\sigma^{*} = (R^{*} ,S^{*} ,T^{*} )$ is a valid signcryption for the $M^{*}$ because the verification Eq. (2) holds

$$\begin{aligned} e(T^{*} ,g) & = e\left( {d_{A} (F_{2} (m^{*} ))^{k} ,g} \right) \\ & = e\left( {d_{A} ,g} \right)e\left( {g^{k} ,F_{2} (m^{*} )} \right) \\ & = e\left( {F_{1} (u_{A} ),P_{pub} } \right)e\left( {(g^{k} PK_{A}^{ - 1} ) \cdot PK_{A} ,F_{2} (m^{*} )} \right) \\ & = e(P_{pub} ,F_{1} (u_{A} ))e(S^{*} ,F_{2} (m^{*} ))e(PK_{A} ,F_{2} (m^{*} )) \\ \end{aligned}$$

and the unsigncrypt result is

$$\begin{aligned} & R^{*} /(PK_{A}^{{x_{B} }} \cdot e(d_{B} ,F_{1} (u_{A} )) \cdot e(S^{*{x_{B} }} ,F_{1} (u_{B} ))) \\ & \quad = M^{*} \cdot PK_{A}^{{x_{B} }} e(PK_{A}^{{ - x_{B} }} ,F_{1} (u_{B} )) \cdot e(d_{A} \cdot PK_{B}^{k} ,F_{1} (u_{B} ))/(PK_{A}^{{x_{B} }} \cdot e(d_{B} ,F_{1} (u_{A} )) \cdot e((g^{k} PK_{A}^{ - 1} )^{{x_{B} }} ,F_{1} (u_{B} ))) \\ & \quad = M^{*} \cdot e(d_{A} \cdot PK_{B}^{k} ,F_{1} (u_{B} ))/(e(d_{A} ,F_{1} (u_{B} )) \cdot e(PK_{B}^{k} ,F_{1} (u_{B} ))) \\ & \quad = M^{*} \\ \end{aligned}$$

It indicates that an honest-but-curious KGC is also able to forge a signcryption information for any message. Thus, the scheme in [11] fails to offer the message unforgeability against KGC.

3.2 Analysis of Confidentiality

Through presenting two attacks, we reveal that both ordinary attacker and malicious-but-passive KGC have the ability to recover message from any ciphertext.

3.2.1 Ordinary Attacker Confidentiality Attack

An ordinary attacker ${\mathcal{A}}_{I}$ is able to derive the value $e(d_{A} ,F_{1} (u_{B} ))$ by replacing receiver’s public key, and hence can decrypt any ciphertext signcrypted under the replaced public key of the receiver. Concretely, ${\mathcal{A}}_{I}$ executes the following two steps.

• Step 1 Obtain the value $e(d_{A} ,F_{1} (u_{B} ))$ in the following way:

  • 1. Choose $x^{\prime}_{B}$ from $Z_{p}^{*}$, compute and set $PK^{\prime}_{B} = g^{{x^{\prime}_{B} }}$ as the user u_B’s new public key.

  • 2. Randomly choose a message M, submit $(M,u_{A} ,u_{B} )$ for a Signcrypt query, and obtains a signcryption information $\sigma = (R,S,T)$. Note that R satisfies Eq. (1), i.e., $R = M \cdot PK_{A}^{{x^{\prime}_{B} }} \cdot e(d_{A} S^{{x^{\prime}_{B} }} ,F_{1} (u_{B} ))$.

  • 3. With σ and $x^{\prime}_{B}$, extract the value $e(d_{A} ,F_{1} (u_{B} ))$ by computing

    $$e(d_{A} ,F_{1} (u_{B} )){ = }R/\left( {M \cdot PK_{A}^{{x^{\prime}_{B} }} \cdot e(S^{{x^{\prime}_{B} }} ,F_{1} (u_{B} ))} \right)$$

• Step 2 Decrypt ciphertext in the following way:

  • 1. Assume $\sigma^{*} = (R^{*} ,S^{*} ,T^{*} )$ is a valid ciphertext generated on the message $M^{*}$ with the replaced public key $PK^{\prime}_{B}$ of the receiver u_B.

  • 2. Using the obtained $e(d_{A} ,F_{1} (u_{B} ))$ and u_B’s secret key $x^{\prime}_{B}$ chosen by ${\mathcal{A}}_{I}$, recover the message $M^{*} = R^{*} /(e(d_{A} ,F_{1} (u_{B} )) \cdot PK_{A}^{{x^{\prime}_{B} }} \cdot e((S^{*} )^{{x^{\prime}_{B} }} ,F_{1} (u_{B} )))$ from the ciphertext $\sigma^{*}$.

It is obvious that the $M^{*}$ is a correct result and ${\mathcal{A}}_{I}$ does not compromise the receiver u_B partial private key. Therefore, the CLSC scheme cannot provide message confidentiality against ordinary attacker.

3.2.2 Malicious-But-Passive KGC Confidentiality Attack

A dishonest KGC ${\mathcal{A}}_{II}$ can decrypt any ciphertext signcrypted. Concretely, ${\mathcal{A}}_{II}$ executes the following three steps.

• Step 1 In the Setup procedure, implant a trapdoor in the following way:

  • 1. Randomly choose $x^{\prime},x_{i} \in Z_{p}^{*}$ and dishonestly create $u^{{\prime }} = g^{{x^{\prime}}} ,u_{i} = g^{{x_{i} }}$ for $1 \le i \le B_{u}$.

  • 2. Produce other system parameters along with master secret key according to Setup algorithm. Thus, we have $F_{1} (u) = g^{{x^{\prime} + \sum\limits_{i \in U} {x_{i} } }}$ for user identity u.

• Step 2 Obtain $PK_{B}^{{x_{A} }}$ in the following way:

  • 1. Choose an arbitrary message M, submit $(M,u_{A} ,u_{B} )$ for a Signcrypt query and obtain the signcryption (R, S, T) as a response.

  • 2. Using $PK_{B}^{{x_{A} }} = R/\left( {M \cdot e(d_{A} ,F_{1}(u_B ) )\cdot e(S^{{x^{\prime} + \sum\limits_{{i \in U_{B} }} {x_{i} } }} ,PK_{B} )} \right)$ retrieve $PK_{B}^{{x_{A} }}$.

• Step 3 Use $PK_{B}^{{x_{A} }}$ and decrypt ciphertext $\sigma^{*} = (R^{*} ,S^{*} ,T^{*} )$ in the following way.

  $$M^{*} = R^{*} /\left( {PK_{A}^{{x_{B} }} \cdot e(d_{A} ,F_{1} (u_{B} )) \cdot e(S^{*} ,(PK_{B} )^{{x^{\prime} + \sum\limits_{{i \in U_{b} }} {x_{i} } }} )} \right).$$

  It is obvious that the $M^{*}$ is a correct result and ${\mathcal{A}}_{II}$ does not compromise any user secret key. Thus, the CLSC scheme in [11] cannot provide message confidentiality against malicious-but-passive KGC.

4 Conclusions

Recently, Luo and Wan proposed a new CLSC scheme to improve security and performance, and claimed that their scheme is secure under ordinary user attacks and malicious-but-passive KGC attacks without random oracles. In this paper, we analyze both the unforgeability and the confidentiality of the scheme. Through the above analysis, we demonstrated that in Luo and Wan’s CLSC scheme, an attacker (KGC or user) can recover message from arbitrary ciphertext and an attacker (KGC) can forge a valid ciphertext for any message. These results indicate that their scheme does not satisfy the unforgeability and confidentiality, i.e., it fails to achieve the basic security goal for a CLSC scheme.