Security Issues of ID-Based on/offline Signcryption Revisited

Ⅰ. Introduction

An ID-based on/offline signcryption (OOSE) is one of the well-developed cryptography primitives that securely merges three cryptographic features; an ID-based cryptography, a signcryption cryptography, and an on/offline function. First, ID-based cryptography, initially proposed by Shamir^[1], aims to use a simple identifier (ID) or an email address to encrypt messages rather than relying on the existing public keys that always need tiresome validation procedure to verify digital certificates. Second, a signcryption (for short, SE) is literally a combination of signature and encrypton primitives, firstly suggested by Zheng^[2], has now become a indispensable primitive that guarantees both confidentiality and authentication. Lastly, an idea of the offline and online function is to separate one signcryption phase into two phases; offline signcryption and online signcryption. Its purpose is that, through an offline phase, it can save computational costs by pretreating high-cost parts of the whole computations beforehand.

Therefore, an ID-based offline and online signcryption (for short, OOSE) is an enhanced primitive not only solves the issues of managing the certificates, but also efficiently provides confidentiality and authentication properties simultaneously with two separated phases. The study on OOSE had been actively explored for the two decades, but now it seems to have become inactive because many provably secure and efficient schemes have been already presented and their securities are analyzed too enough.

From the viewpoint of OOSE, it is so natural process that original senders who have already produced offline signcryption (for short, OffSE) in an offline phase to subsequently produce online sigcryptions (for short, OnSE) in the online phase. Our motivation, however, starts from breaking this assumption. Instead, we assume that OffSE and OnSE are functionally and physically separated and their working process may not be performed in one specific device at once. That is, after a sender A performs OffSE phase, their outputs [TeX:] $$c_f$$ are securely managed in the memory space. Then, after a long period of time, the same sender A who brings [TeX:] $$c_f$$ (e.g. through USB) may do OnSE through other remote devices. At this point, a new access issue, “Is it right for anyone who just brings [TeX:] $$c_f$$ to freely access OnSE phase without being required anything?” , can be raised. To enhance security, each phase must be independent and not affect the security of the other phase under the corruption of each phase.

We observe that, up to now, most schemes do not consider such malicious scenario. In the paper, thus, we firstly raise an access issue that anyone who holds [TeX:] $$c_f$$ from OffSE can produce a valid online signature without any permission of senders. Furthermore, reversely, anyone who can access final OnSE phases can produce OffSE or OnSE freely. In this paper, we present these offline and online attacks in OOSE and analyzed them through relevant OOSE results. Next, we explain the existing OOSE with security definitions. At last, our observations and its analysis based on new attacks are newly presented.

Ⅱ. OOSE Process and Definitions

2.1 On/offline signcryption process

An ID-based OOSE consists of six phases. We suppose that a sender [TeX:] $$ID_s$$ sends signcryption for m to a receiver [TeX:] $$ID_r.$$

· Setup : It generates public parameters such as multiplicative cyclic group, generator, description of hash, and pairing operation e. It also generates a master key msk and a public key [TeX:] $$P_{p u b} .$$

· Extract : On inputs msk, ID, it generates a secret key d for an identifier ID

· Offline Signcrypt (OffSE) : It produces an offline ciphertext [TeX:] $$c_f$$ on inputs of a sender’s secret key [TeX:] $$d_s$$ and [TeX:] $$ID_s.$$ It is an intermediate ciphertext that is later delivered to an online signcryption.

· Online Signcrypt (OnSE) : It generates a final signcrypt [TeX:] $$c_n$$ on inputs of [TeX:] $$c_f$$ and [TeX:] $$ID_r.$$

· DeSigncrypt : On inputs [TeX:] $$c_n, ID_s, ID_r,$$ it decrypts [TeX:] $$c_n$$ with the receiver’s secret key [TeX:] $$d_r$$ and outputs message m and signature σ . If [TeX:] $$c_n$$ is not valid, it outputs a message of invalid

· Verification : It verifies signature σ for m using the sender’s [TeX:] $$ID_s$$ and public values, and then outputs its result (valid or invalid).

Originally, in the field of OOSE, OffSE takes the message m and the receiver’s [TeX:] $$ID_r$$ as inputs and outputs intermediate [TeX:] $$c_f$$. Then OnSE takes [TeX:] $$c_f$$ and produces [TeX:] $$c_n$$ as a final signcrypt. Recently, however, a new idea, which the message m and IDr are later given to OnSE (not to OffSE), has been suggested. This approach enables the sender to more flexibly prepare OffSE operations without the information of receiver’s [TeX:] $$ID_r$$ and message m. That is, senders can prepare as many OffSE outputs as possible in offline phases, which the sender can use for any ID and messages. This procedure is definitely more convenient than existing approach that OffSE requires them all in advance.

As compared in Fig 1, the left side (a) shows the previous approach that OffSE takes ID and m while the right side (b) shows the new approach that OnSE takes ID and m. One best advantage of approach (b), the sender can merge any offline signcrypts [TeX:] $$c_{fi}$$, [TeX:] $$1 \leq i \leq k$$ with any identifier, message IDi , mi and conveniently make a final signcrypt [TeX:] $$c_{oi}, 1 \leq i \leq k.$$

Fig. 1.

Comparison of two OOSE paradigms

2.2 OOSE security definition

OOSE guarantees two formal security properties; message confidentiality and unforgeability, as follows. Confidentiality. An ID-based OOSE is secure against chosen ciphertext attack if no PPT adversary [TeX:] $$\mathscr{A}$$ gain advantage with non-negligible probability through the following experimental game in which a challenger C allows an adversary [TeX:] $$\mathscr{A}$$ to ask queries defined below and measure its advantage on unforgeability and confidentiality.

· By running Setup phase, [TeX:] $$\mathscr{C}$$ first obtains msk and then provides [TeX:] $$\mathscr{A}$$ with pubic parameters. [TeX:] $$\mathscr{C}$$ allows for [TeX:] $$\mathscr{A}$$ to ask the following queries. The queries can be adaptively made depending on the results of previous queries.

- Extract : For any ID, [TeX:] $$\mathscr{A}$$ can ask Extract query then obtain a secret key d for ID.

- Signcrypt : For [TeX:] $$ID_s, ID_r,$$ and m, [TeX:] $$\mathscr{A}$$ can ask Signcrypt query then obtain signcryption ciphertext [TeX:] $$c_n$$.

- DeSigncrypt : For [TeX:] $$c_n, ID_s, ID_r, \mathscr{A}$$ can ask DeSigncrypt query then obtain a message m and its signature σ, if [TeX:] $$c_n$$ is a valid signcryption. Otherwise, [TeX:] $$\mathscr{A}$$ obtains an invalid notification.

· After queries, [TeX:] $$\mathscr{A}$$ comes up with two target messages [TeX:] $$m_0, m_1,$$ two target identities [TeX:] $$ID_s, ID_r, \text{ to } \mathscr{C}$$.

· Then [TeX:] $$\mathscr{C}$$ selects a random bit [TeX:] $$b \in\{0,1\}$$ and makes a target ciphertext [TeX:] $$c_b^*$$ for [TeX:] $$m_b, I D_s, I D_r.$$

· Finally, [TeX:] $$\mathscr{A}$$ guesses the bit b′ for b. If b′ = b then we define [TeX:] $$\mathscr{A}$$ wins the game. [TeX:] $$\mathscr{A}$$'s advantage to win is defined as

· Query restriction : To avoid the cases that [TeX:] $$\mathscr{A}$$ win easily, [TeX:] $$\mathscr{A}$$ is neither able to ask DeSigncrypt query for [TeX:] $$c_n^*, I D_s, I D_r$$ nor Extract query for [TeX:] $$I D_r.$$

Unforgeability. An ID-based OOSE is existentially unforgeable against chosen message attack if no PPT adversary [TeX:] $$\mathscr{A}$$ gain advantage with non-negligible probability through the following game.

· As in Definition 1, [TeX:] $$\mathscr{C}$$ obtains msk from running Setup phase. And, [TeX:] $$\mathscr{C}$$ provides [TeX:] $$\mathscr{A}$$ with pubic parameters.

· [TeX:] $$\mathscr{C}$$ allows for [TeX:] $$\mathscr{A}$$ to adaptively ask the queries as defined in Definition 1.

· After queries, [TeX:] $$\mathscr{A}$$ finally outputs [TeX:] $$c_n^* \text { for } I D_s, I D_r .$$ If DeSigncrypt for [TeX:] $$c_n^*, I D_s, I D_r$$ is a valid then we define that [TeX:] $$\mathscr{A}$$ wins the game. [TeX:] $$\mathscr{A}$$'s advantage is the probability of winning the game.

· Query restriction : To avoid the trivial cases, [TeX:] $$\mathscr{A}$$ is neither able to ask DeSigncrypt query that produces m, σ nor Extract query for [TeX:] $$I D_s.$$

Ⅲ. Observations of the Existing Schemes

3.1 Structural difference

Basically, OOSE (either type (a) or (b) in Fig. 1) is different with the original SE in a way that OOSE is designed to separate a signcryption step into two (on/ off) phases, due to this, it certainly requires long-term memory space to connect the two phases. In other words, for the later computation in OnSE, the outputs of the first OffSE must be stored in a secure memory space. Despite their difference, one notable thing is that many OOSE schemes so far follow the security model of the existing ID-based SE schemes. In OOSE, one can easily observe that the number of types of behaviors for [TeX:] $$\mathscr{A}$$ can be more variant than the previous SE. Referring to OOSE definitions, nonetheless, the experiment permits a Signcrypt query, despite being OOSE with on/offline phases. During two phases, for instance, [TeX:] $$\mathscr{A}$$ can ask either OffSE or OnSE separately, not just one Signcrypt query in SE. Also, [TeX:] $$\mathscr{A}$$ may corrupt memory space to gain much advantage in the game. In Fig 2, two new types of attacks are illustrated with these single phase attacks.

Fig. 2.

Online and Offline attacks

3.2 New attacks

Based on the observations above, our new attacks assume that OffSE and OnSE are physically disparate, thus, there arises an access issue between OffSE and OnSE. That is, if a sender [TeX:] $$\mathscr{A}$$ can access OffSE then is it right to permit A to get an access to OnSE as a matter of course? In the existing OOSE, it is assumed that A, which has access to OffSE and memory, can naturally do perform OnSE. To be more specific, OffSE requires sender’s secret key while OnSE just needs random values (internally generated or obtained from memory) without requiring any secret long-term values. If we suppose an adversary [TeX:] $$\mathscr{A}$$ who corrupts [TeX:] $$c_f$$ of OffSE and secret values in the memory space, then, using them, [TeX:] $$\mathscr{A}$$ can produce a final signcryption [TeX:] $$c_n$$ of OnSE. As illustrated in Fig 2, we simply define this type of attack as an offline attack (for short, [TeX:] $$\Delta_{\text {off } \rightarrow \text { on }}$$ in Table 1). Reversely, [TeX:] $$\mathscr{A}$$ can use the existing [TeX:] $$c_n \text{ and } c_f$$ in the memory spaces to produce a secret d used for OffSE. It makes it possible for [TeX:] $$\mathscr{A}$$ to forge every next [TeX:] $$c_f, c_n.$$ We define this type of attack as an online attack (for short, [TeX:] $$\Delta \text {on } \rightarrow \text { off }$$ in Table 1).

3.3 Analysis of the schemes and discussions

3.3.1 Analysis

One remarkable result analyzed in Table 1 is that most OOSE schemes do not guarantee the security against the offline attack. The reason is not from any security fault but it is from the existing OOSE definition, such that only their OffSEs requires secrets for an input. For instance, as in the algorithms (Table 1), SHMS scheme^[3], the secret d is used for making S in OffSE while OnSE simply perform basic operations for signcryption using [TeX:] $$c_f$$ values. Thus, any adversary can easily produce any further valid signcryptions without any consent if once [TeX:] $$c_f$$ is corrupted.

Interestingly, one result NRKAKY^[9] has been presented to use a secret d as an input for OnSE, thus, [TeX:] $$\mathscr{A}$$ without knowing d should not mount the offline attack using [TeX:] $$c_f$$. On the other side, however, in the scheme, once the adversary [TeX:] $$\mathscr{A}$$ (can be an insider or outsider) obtains an arbitrary output of OnSE and its corresponding [TeX:] $$c_f$$ in the memory, then [TeX:] $$\mathscr{A}$$ can produce new [TeX:] $$c_f, c_n$$ values, as follows.

· Let’s suppose [TeX:] $$\mathscr{A}$$ obtains [TeX:] $$c_f$$ (U, W, y, k), and its corresponding [TeX:] $$c_n$$ (h, V, C), for a receiver [TeX:] $$I D_r.$$

· Then [TeX:] $$\mathscr{A}$$ simply computes [TeX:] $$(V-W) \cdot h^{-1}$$ to get d.

· [TeX:] $$\mathscr{A}$$ with d can do follow every steps from OffSE to OnSE then make new [TeX:] $$c_f, c_n$$ for a new message m.

The above reverse scenario relies on the fact that two situations (OnSE and memory) are perfectly stolen by [TeX:] $$\mathscr{A}$$, which has not been considered in the existing schemes, up to date either. As in Table 1, we have analyzed relevant schemes regarding the offline and online attacks. To the best of our knowledge, there exists no scheme considering two attacks, which implies both [TeX:] $$\Delta_{\text {on } \rightarrow \text { off }}$$ and [TeX:] $$\Delta_{\text {off } \rightarrow \text { on }}$$ are N.

Table 1.

Analysis of relevant protocols

3.3.2 Observations

· Most OOSE schemes have been designed for OffSE to require a secret key. One clear observation is that most schemes of OffSEs only tackle the secret key (not with both phases). That is, at the first OffSE, it produces authentic data [TeX:] $$c_f$$ with the secret value, in which a digital signature is applied, then at the second OnSE, [TeX:] $$c_f$$ is simply merged to make signcryptions with the message m and ID, which only require lightweight operations such as multiplication and addition without making any other random values. This unbalance computation process, in a sense, is certainly an efficient design of OOSE. However, we observe that, regarding most OOSE schemes, if once [TeX:] $$c_f$$ is corrupted, then all security is not guaranteed, as summarized in Table 1.

· Although both phases have its own private keys, the scheme can be insecure against on/offline attacks. The simple way to handle these attacks is to design OnSE to take a sender’s secret as OffSE does. However, unfortunately, it is never a simple work to securely add sender’s secrets into each phases.

For instance, let’s see the LKAT algorithm^[7] in the table. The scheme takes a secret d in OffSE to make S′ while OnSE does perform simple operations using cf values without any secret. According to our claims, due to d in OffSE, no adversary is supposed to perform OffSE at all. However, an adversary is able to obtain [TeX:] $$\alpha^{-1} \text { from } c_f.$$ This implies that the adversary can capture any past OffSE message S from [TeX:] $$c_f$$ and easily compute d.

The same applies to another scheme SMS^[4]. The scheme also requires secrets d and x that are used for each step OffSE and OnSE, respectively to guarantee unforgeability. Although both phases take each secret value, its issue comes from [TeX:] $$y^{\prime} \text { in } c_f,$$ which is used as a symmetric key to make c. Under the corruption of [TeX:] $$c_f$$, any adversary can recover m, which breaks confidentiality.

This analysis reminds us of the fact that each phase can be insecure even though they are designed with secret value at each step. If OffSE produced the related secret value from output [TeX:] $$c_f$$, then any adversary with [TeX:] $$c_f$$ may compute the secret value, which breaks unforgeability and confidentiality of signcryptions. Therefore, how to securely make each secret values and [TeX:] $$c_f$$ must be a careful consideration considered for constructing a secure OOSE.

· Only one scheme SMS^[4] is designed with two separate secrets, but it already inherits other security vulnerabilities. What we claim here is that, when we design OOSE, the scheme can guarantee much security if their two phases (offline and online) were designed with independent secret values to make its output, which definitely does not affect the security of the other phase, even if each phase corruption happens. Our observation is that there has been one such scheme SMS^[4], as analyzed in Table 1. Although SMS^[4] does not take into accounts of these attacks in their security model, the scheme SMS were wisely designed with separate private keys in their on/offline phases.

However, other security concern in SMS has been found by Selvi et al.^[4] They have shown that an adversary can produce a valid signcryption for a message m, a sender [TeX:] $$ID_A$$, and a receiver [TeX:] $$ID_C$$ through using a valid signcryption for m, a sender [TeX:] $$ID_A$$, and a receiver [TeX:] $$ID_B$$. Please note that this is not the security breach from on/offline attacks discussed here, but under their security model. To the best of our knowledge, there exists no scheme that is secure against on/offline attacks in recent provably secure schemes.

3.3.3 Other cryptographic primitives

It is worthwhile to see the case of on/offline encryption (for instance, LZ^[5] in Table 1) where two phases are not interested in taking their secret inputs since it is a public encryption that must be performed only with public values. Hence, on/offline public encryption does not relate to our security issues.

Another case of on/offline signature (LHHW^[10] in Table 1), however, does have concerns with our security issues, since the scheme is a digital signature, and a secret d is used to make S in OffSE. In other words, in OnSE phase, only [TeX:] $$c_f$$ values are required without any secret value. When we say on/offline phases are secure, normally each phase corruption should not affect other phase’s security (forgery). As described in Table 1, when an adversary corrupts [TeX:] $$c_f$$ from memory, anyone can perform OnSE, which denotes that an adversary can produce any valid signature. Our result shows that [TeX:] $$\Delta_{\text {off } \leftarrow \text { on }}$$ is possible in LHHW while its reverse [TeX:] $$\Delta_{\text {off } \leftarrow \text { on }}$$ is impossible due to the secret value d.

3.4 Discussion on Countermeasures

Our new assumption here is that an adversary [TeX:] $$\mathscr{A}$$ is allowed to obtain [TeX:] $$c_f$$ from memory corruptions. This assumption more empowers the behaviors of the adversary, making the security model much stronger at the same time. For example, queries for corruptions of memory to get cf must be required in the model in addition to existing Extract query to obtain the secret key.

One generic solution is to apply other existing secure cryptographic primitives (a secure digital signature (Sign), a public key encryption (PE), a symmetric key encryption (SE)) into OOSE. Let’s suppose a sender [TeX:] $$I D_A$$ and a receiver [TeX:] $$I D_B.$$

· OffSE : A secure PE with [TeX:] $$I D_A$$'s public key can be used for encryption of K where K is a symmetric key for SE. Since the PE with [TeX:] $$I D_A$$'s public key can be decrypted with [TeX:] $$I D_A$$'s private key, this is exactly a self encryption that only [TeX:] $$I D_A$$ can decrypt at OnSE. We define the ciphertext of PE as a, then, using Sign, we make a signature δ for a. δ and a are stored to memory for later use.

· OnSE : The sender [TeX:] $$I D_A$$ verifies δ, if it is valid then decrypts a by its own private key and recover K. The sender encrypts a message m with K and makes a ciphertext b. Lastly, b is also signed using Sign then delivered to [TeX:] $$I D_B$$ with b.

This generic approach is similar with PGP protocol for email security, but different in the sense of self encryption from OffSE to OnSE. That is, for message confidentiality, our OffSE phase allows a sender to encrypt symmetric key K with own public key, which the sender later decrypts them in OnSE. Due to the double usage of signatures, it shows low efficiency compared with the existing protocols. An on/offline secure design of OOSE for gaining efficiency remains future work, including the method to design a secure [TeX:] $$c_f$$ in a security model such that it should not affect confidentiality and unforgeability, even though [TeX:] $$c_f$$ is corrupted.

Ⅳ. Concluding Remarks

Basically our observations are based on the fact that most OnSE in OOSE do not need the sender’s secret as an input while OffSE in OOSE needs the sender’s secret. As a result, the risky points arise when OffSE phase is completed, because its output secrets cf are managed in a long-term memory (not RAM, but flash memory or ROM) for later computations. What we are concerned about is that these long-term memory may become vulnerable by memory leaks or corruptions in any IoT situations. Therefore, we first present the novel offline/online attacks from those vulnerability and analyzed them in Table 1.