ABSTRACT
The encryption scheme based on Forward Key Rotation is such a scheme that only the authorized person is allowed access to the designated files and the previous versions. In this study, we present a Forward Key Rotation storage scheme based on discrete logarithm and prove its security under random oracle model. Moreover, we propose another improved Forward Key storage scheme from pairing on elliptic curves. Compared to the scheme presented by Kallahalla et al. our scheme uses relatively short keys to provide equivalent security. In addition, the re-generated keys can be verified to ensure that the keys are valid in the improved scheme.
PDF Abstract XML References Citation
How to cite this article
DOI: 10.3923/jas.2008.1967.1971
URL: https://scialert.net/abstract/?doi=jas.2008.1967.1971
INTRODUCTION
As more information becomes available in digital format, enormous quantities of data are created. With the increasing requirement to both temporarily and permanently retain information, the secure storage technique is attracting much attention. In a data storage system, the storage medium for preserving the information is an important target to a malicious attacker. Once the attacker breaks the system, he can gain unauthorized information, disclose some valuable secrets or prevent the access of legitimate users. In order to avoid these risks, the researchers have proposed many potential systems for securing stored information, such as NASD (Gobioff et al., 1999, 1997), PASIS (Ganger et al., 2001; Wylie et al., 2000), CFS (Blaze, 1993), SNAD (Freeman and Miller, 2000; Miller et al., 2001) and PLUTUS (Kallahalla et al., 2003) and so on. Moreover, all these researches come into being a field of computer research. Currently, the major target of a secure storage system is ensuring information confidentiality, integrity and availability without substantially degrading performance.
Kallahalla et al. (2003) present a secure storage scheme, PLUTUS, in 2003. The primary goal of the scheme is to provide file owners with direct control over authorizing access to their files as well as scalable key management. Key revocation is a major problem in secure storage system. Due to the proliferation of keys and the use of file groups, the key revocation is very complicated. Since several files in the file system are encrypted with the same key, key revocation will result in mass re-encryption.
However, Kallahalla et al. (2003) designed a key rotation scheme to alleviate the negative effects. The key rotation scheme can make the updated secret key relate to the previous versions. For the user of PLUTUS, when he is allowed access to a certain re-encrypted files using given file-group key, then he can generate previous versions from the given key. In other words, any valid user can re-generate the matching key for a given file if he has the latest file-group key. Therefore, we call the key rotate scheme designed by Kallahalla Forward Key Rotate (FKR) scheme.
The security of the FKR presented by Kallahalla et al. (2003) is based on the RSA. However, limited by the prime generation technique, producing a pair of suitable keys used in RSA scheme is not an easy thing. Moreover, until now there is no way to show the strength of the RSA is equivalent to that of decomposing a large number. Currently, RSA based schemes use relatively long keys compared to the security they provide. In this aspect, a scheme based on elliptic curves provides much shorter keys. As the requirement of practice, it is necessary to design other KFR storage scheme related to different intractable problems.
In this study, we first present a FKR storage scheme based on discrete logarithm and discuss its security. Subsequently, we present an improved FKR storage scheme from pairings on elliptic curves. Compared to the mechanism presented by Kallahalla et al. (2003) the improved scheme provides relatively short keys to perform the same function. Moreover, the user can verify the validity of the re-generated keys via bilinear pairings.
KALLAHALLA et al. FORWARD KEY ROTATION SCHEME
Kallahalla et al. (2003) proposed a Forward Key Rotation scheme used in PLUTUS system in 2003. In this section, we will briefly review their FKR scheme. Suppose that there exists a secure RSA encrypt scheme as defined in Rivest et al. (1978). Let U0 be a user who will establish a FKR scheme, e0 be the public key of U0 and d0 be the matching private key.
• | User U0 chooses k0εZ*q uniformly at random and computes |
• | When user Ui≠o wants to access the FKR scheme, the user U0 gives Ui≠o the latest key . Hence, Ui≠o has ability to compute and get any kz≤l. |
The security of the scheme is based on RSA. Kallahalla et al. (2003) simplify the key management of PLUTUS using this FKR scheme.
PRELIMINARIES
Complexity assumptions: We assume that a prime p is chosen at random such that p-1 has a large prime factor q. Let g be an element of order q. Define the following problems.
• | Computation diffie-hellman (CDH): Given ga, gb for unknowns a, b εZ*q, compute gabεZ*q. |
• | Decision diffie-hellman (DDH): Given ga, gb, gc for unknowns a, b, c εZ*q, decide whether gab = gc. |
• | K-exponent assumption (k-E): Given for unknown x, compute (Zhang et al., 2004). |
Bilinear maps: Let G1 be a cyclic multiplicative group generated by g, whose order is a prime q and G2 be a cyclic multiplicative group of the same order q. Assume that the discrete logarithm in both G1 and G2 is intractable. A bilinear pairing is a map: G1xG1→G2 and satisfies the following properties:
• | Bilinear: e(ga, pb) = e(g, p)ab. For all g, p ε G1 and a, b ε Zq, the equation holds. |
• | Non-degenerate: There exists p ε G1, if e(g, p) = 1, then g = 0. |
• | Computable: For g, p ε G1, there is an efficient algorithm to compute e(g, p). |
Typically, the map e will be derived either from the modified Weil pairing (Boneh et al., 2001; Boneh and Franklin, 2003) or the tate pairing (Paulo et al., 2002) on an elliptic curve over a finite field. Pairings and other parameters should be selected in proactive for efficiency and security. In group G1, the CDH and K-E assumptions defined are intractable. However, the DDH assumption is tractable.
General scheme: A FKR storage scheme consists of four algorithms.
• | Initialize: Given the security parameter l, the algorithm outputs the system parameters. |
• | Key generation (i): Input the number i, output i-th secret key Ki used to encrypt i-th files. |
• | Encrypt (Ki+1, Ki, Filei): Input two secret keys (Ki+1, Ki) and a file Filei. The algorithm encrypts Filei using (Ki+1, Ki) and outputs the corresponding ciphertext EFi. |
• | Decrypt (Ki+1, Ki, Ki): Input the ciphertext EFi and the secret keys (Ki+1, Ki). The algorithm decrypts the ciphertext using the secret key (Ki+1, Ki) and outputs the corresponding plaintext Filei. |
Security notions: We define adaptively chosen ciphertext security of a FKR storage scheme. Security is defined using the following game between an Attacker and Challenger.
• | Setup: The Challenger initializes the system. The Challenger gives the Attacker the resulting system parameters. |
• | Query phase 1: The Attacker adaptively issues encrypt queries q1, q2, ..., qm and decryption queries q1, q2, ..., qm, respectively. The Challenger simulates Encrypt and Decrypt, respectively and responds with matching answers. |
• | Challenge:Once the Attacker decides that Query phase 1 is over it outputs two equal length files (File0, File1) to the Challenger. The Challenger picks a random bit λε{0, 1} and encrypts the message Fileλ. It gives ciphertext C to the Attacker. |
• | Query phase 2: The Attacker continues to adaptively issue encryption and decryption queries. The Challenger responds as in the phase 1. These queries may be asked adaptively as in Query phase 1. Note that the decrypt query qj = C is not permitted, where 0≤j≤n. |
• | Guess: Finally, the Attacker outputs a guess λ'ε{0, 1} for λ and wins the game if λ' = λ. |
The storage scheme is secure against chosen ciphertext attack, if the Attacker has a negligible advantage ε = |Pr(λ = λ')-1/2| to win the game.
FORWARD KEY ROTATION STORAGE SCHEME
In this part of study, we will design a FKR storage scheme related to discrete logarithm. We suppose that Server who has a series of files {File1, File2, ..., Filen} will establish the FKR storage scheme and a user Alice asks to access it. Let p be a large prime and 〈g〉 be a cyclic multiplicative group generated by g, whose order is a prime q such that q|(p-1). There exists a pair of security algorithms (E, D), where the algorithm E is a secure encryption algorithm based on discrete logarithm and D is the matching decryption algorithm.
Step 1: Server chooses a random number r ∈ Z*q and computes as a secret key.
Step 2: Server generates the encrypted files , where a || b denotes the concatenate of a and b. Thereafter, server publishes all encrypted files.
When Alice asks to access to the FKR storage scheme at the point j, Server sends the secret key Kj+1 to Alice. Since Alice can obtain any encrypted files, she can compute
and get Kj and Filej. Similarly, Alice can obtain Kj-1 and Filej-1 via Kj and EFj-1.
However, by the K-E assumption defined already, Alice cant produce the secret key Kj+2 using Kj and Kj+1. In other words, Alice doesnt have ability to decrypt EFj+1 even though she has secret key Ki≤j+1.
SECURITY
The security of the scheme is partly based on the algorithms (E, D). Thereby, we assume that these two algorithms are secure. Given , one cant deduce by the K-E assumption mentioned already. It means that if Server gives an access point at j, one cant access to the files Filek, where k>j.
Then we will give the following theorem to show the security of the proposed storage scheme.
Theorem: We assume that an attacker Eve who can, with success probability ε, break the FKR storage scheme within a time τ by asking Encrypt and Decrypt oracles at most qE and qD queries respectively, then there exists a challenger Alice who running in a time τ' can solve the DDH problem with success probability ε', where
where, tED is the time for performing an encryption or decryption algorithm.
Proof: We assume that Eve is an attacker who has the ability to break the storage scheme. Then there exists a challenger Alice who can solve the DDH problem by running Eve as a subroutine. The system chooses a random bit bε{0, 1} and a random number rεZ*q. The challenger Alice is given . If b = 1, the system sets , otherwise, chooses a random number TεZ*p.
The attacker Eve is allowed to issue Encrypt, Decrypt and Challenge queries. The challenger Alice will simulate the corresponding oracles to output the answers.
Query phase 1: The attacker Eve is allowed to issue following queries.
Encrypt queries: Eve chooses a random number jε[l, k] and takes the file Filej and then issues query on (j, Filej).
• | If j ≠ i, Alice computes and outputs EFj as the answer, where and . |
• | If j = i, Alice outputs error messages and halts. |
Decrypt queries: Eve chooses a random number jε[l, k] and takes the ciphertext EFj and then issues query on (j, EFj).
• | If j ≠ i, Alice computes and outputs Kj and Filej as the answer, where and . |
• | If j = i, Alice outputs error message and halts. |
Since above simulation is perfect, the attacker Eve cant distinguish the simulated result from the actual results. The above queries can be asked several times. When Eve decides this phase is over, he issues challenge query.
Challenge query: Eve outputs two equal length files File0 and File1 to Alice. Upon receiving the two files, Alice chooses a random bit λε{0, 1} and computes
where, Thereafter, Alice sends EFj to Eve as the answer.
Note that the Challenge query is allowed only once.
Query phase 2: The attacker Eve continues to adaptively issue encryption and decryption queries. The challenger Alice will respond as in the phase 1. However, decryption query qj = EFi is not permitted. We assume that Eve issues at most qE encrypt queries and qD decrypt queries.
Guess: After receiving the answer from Alice, Eve outputs his guess λ'. If λ' = λ, Alice decides b = 1, otherwise b = 0.
Since Eve has ability to break the scheme with non-negligible probability ε, i.e., outputs λ' = λ with probability ε, then the challenger Alice can solve DDH with the same probability.
IMPROVED SCALABLE FKR STORAGE SCHEME
In practice some devices only have limited capability, so we should design a scheme which can provide shorter keys. Thereby, an improved FKR storage scheme from pairing on elliptic curve is presented part of research. In this scheme the re-generated keys can be verified via bilinear pairings. Thus also provide a measure for a user to verify the validity of the plaintext.
Let G1 and G2 be two groups that support a bilinear map. There exists a pair of security algorithms (E, D), where the algorithm E is a secure encryption algorithm based on elliptic curves and D is the matching decryption algorithm.
Step 1: Server chooses a random number rεZ*q and computes .
Step 2: Server generates the encrypted files . Thereafter, server publishes all encrypted files.
When Alice asks to access to the FKR storage scheme at the point j, server sends the secret key Kj+1 to Alice. Since Alice can obtain any encrypted files, she can compute
and get Kj and Filej. Similarly, Alice can obtain Kj-1 and Filej-1 via Kj and EFj-1.
Step 3: After computing Kj and Kj-1, Alice performs the following step to verify the validity of the re-generated keys.
If above equation is true, the re-generated keys are valid. Otherwise, Alice outputs error messages.
CONCLUSIONS
Secure storage is a crucial problem in the Internet. Motivated by Kallahalla forward key rotation and the requirement of the short key schemes, we present two FKR storage scheme. One is based on discrete logarithm and another is from bilinear pairing on elliptic curve. The latter storage scheme is suitable for implementation in many scenarios, especially those where the storage capability of the users is limited.
REFERENCES
- Blaze, M., 1993. A cryptographic file system for Unix. Proceedings of the 1st ACM Conference on Communications and Computing Security, November 3-5, 1993, Virginia, USA., pp: 9-16.
Direct Link - Boneh, D. and M. Franklin, 2003. Identity-based encryption from the Weil pairing. SIAM. J. Comput., 32: 586-615.
Direct Link - Freeman, W. and E. Miller, 2000. Design for a decentralized security system for network-attached storage. Proceedings of the 17th Symposium on Mass Storage Systems and Technologies, October 31-31, 2000, Computer Soc. Los. Alamitos, CA., USA., pp: 361-373.
Direct Link - Ganger, G.R., P.K. Khosla, M. Bakkaloglu, M.W. Bigrigg and G.R. Goodson et al., 2001. Survivable storage systems. DARPA Inform. Survivability Conf. Exposit., 2: 184-195.
Direct Link - Kallahalla, M., E. Riedel, R. Swaminathan, Q. Wang and K. Fu, 2003. Plutus: Scalable secure file sharing on untrusted storage. Proceedings of the 2nd Conference on File and Storage Technologies, March 31-April 2, 2003, San Francisco, CA., pp: 29-42.
Direct Link - Miller, E.L., D.D.E. Long, W. Freeman and B. Reed, 2001. Strong security for distributed file systems. Proceedings of the 20th International Performance, Computing and Communications Conference, April 4-6, 2001, Phoenix, AZ., USA., pp: 34-40.
CrossRef - Rivest, R.L., A. Shamir and L. Adleman, 1978. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM., 21: 120-126.
CrossRefDirect Link - Wylie, J.J., M.W. Bigrigg, J.D. Strunk, G.R. Ganger, H. Kiliccote and P.K. Khosla, 2000. Survivable information storage systems. IEEE Comput., 33: 61-68.
Direct Link