Abstract
In the last one and a half decade there has been a lot of activity toward development of cryptographic techniques for disk encryption. It has been almost canonized that an encryption scheme suitable for the application of disk encryption must be length preserving, i.e., it rules out the use of schemes such as authenticated encryption where an authentication tag is also produced as a part of the ciphertext resulting in ciphertexts being longer than the corresponding plaintexts. The notion of a tweakable enciphering scheme (TES) has been formalized as the appropriate primitive for disk encryption, and it has been argued that they provide the maximum security possible for a tagless scheme. On the other hand, TESs are less efficient than some existing authenticated encryption schemes. Also TES cannot provide true authentication as they do not have authentication tags. In this paper, we analyze the possibility of the use of encryption schemes where length expansion is produced for the purpose of disk encryption. On the negative side, we argue that nonce-based authenticated encryption schemes are not appropriate for this application. On the positive side, we demonstrate that deterministic authenticated encryption (DAE) schemes may have more advantages than disadvantages compared to a TES when used for disk encryption. Finally, we propose a new deterministic authenticated encryption scheme called BCTR which is suitable for this purpose. We provide the full specification of BCTR, prove its security and also report an efficient implementation in reconfigurable hardware. Our experiments suggests that BCTR performs significantly better than existing TESs and existing DAE schemes.
Similar content being viewed by others
Notes
TESs do provide implicit authentication in the sense that if a single bit of a valid ciphertext is changed then it gets decrypted to a random plaintext which can be detected by a high-level application which would use the plaintext.
References
Bellare, M., Namprempre, C.: Authenticated encryption: relations among notions and analysis of the generic composition paradigm. J. Cryptol. 21(4), 469–491 (2008)
Bernstein, D.J.: Polynomial Evaluation and Message Authentication (2007). http://cr.yp.to/papers.html#pema
Bulens, P., Standaert, F.-X., Quisquater, J.-J., Pellegrin, P., Rouvroy, G.: Implementation of the AES-128 on Virtex-5 FPGAs. In: Vaudenay, S. (ed.) AFRICACRYPT, vol 5023 of Lecture Notes in Computer Science, pp. 16–26. Springer, Berlin (2008)
CAESAR. Competition for Authenticated Encryption: Security, Applicability, and Robustness. http://competitions.cr.yp.to/caesar.html
Chakraborty, D., Hernandez-Jimenez, V., Sarkar, P.: Another look at XCB. Cryptogr. Commun. 7(4), 439–468 (2015)
Chakraborty, D., Mancillas-López, C.: Double ciphertext mode: a proposal for secure backup. Int. J. Appl. Cryptogr. 2(3), 271–287 (2012)
Chakraborty, D., Mancillas-López, C., Rodríguez-Henríquez, F., Sarkar, P.: Efficient hardware implementations of BRW polynomials and tweakable enciphering schemes. IEEE Trans. Comput. 62(2), 279–294 (2013)
Chakraborty, D., Mancillas-López, C., Sarkar, P.: STES: A stream cipher based low cost scheme for securing stored data. IEEE Trans. Comput. 64(9), 2691–2707 (2015)
Chakraborty, D., Sarkar, P.: A New Mode of Encryption Providing a Tweakable Strong Pseudo-Random Permutation. In: Robshaw, M.J.B. (ed.) Fast Software Encryption 2006, vol 4047 of Lecture Notes in Computer Science, pp. 293–309. Springer, Berlin (2006)
Chakraborty, D., Sarkar, P.: HCH: a new tweakable enciphering scheme using the hash-counter-hash approach. IEEE Trans. Inf. Theory 54(4), 1683–1699 (2008)
Chakraborty, D., Sarkar, P.: On modes of operations of a block cipher for authentication and authenticated encryption. IACR Cryptol. ePrint Arch. 2014, 627 (2014)
Chicoine, P., Hassner, M., Noblitt, M., Silvus, G., Weber, B., Grochowski, E.: Hard disk drive long data sector white paper. The International Disk Drive Equipments and Materials Association (2007). http://www.idema.org/wp-content/plugins/download-monitor/download.php?id=1222
Ferguson, N.: AES-CBC + Elephant Diffuser: A Disk Encryption Algorithm for Windows Vista. Microsoft white paper (2006). http://download.microsoft.com/download/0/2/3/0238acaf-d3bf-4a6d-b3d6-0a0be4bbb36e/BitLockerCipher200608
Halevi, S.: EME\(^{{*}}\): Extending EME to handle arbitrary-length messages with associated data. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT, vol 3348 of Lecture Notes in Computer Science, pp. 315–327. Springer, Berlin (2004)
Halevi, S.: Invertible universal hashing and the TET encryption mode. In: Menezes, A. (ed.) CRYPTO, vol 4622 of Lecture Notes in Computer Science, pp. 412–429. Springer, Berlin (2007)
Halevi, S., Rogaway, P.: A tweakable enciphering mode. In: Boneh, D. (ed.) CRYPTO, vol 2729 of Lecture Notes in Computer Science, pp. 482–499. Springer, Berlin (2003)
Halevi, S., Rogaway, P.: A parallelizable enciphering mode. In: Okamoto, T. (ed.) CT-RSA, vol 2964 of Lecture Notes in Computer Science, pp. 292–304. Springer, Berlin (2004)
IEEE Std 1619-2007: Standard for Cryptographic Protection of Data on Block-Oriented Storage Devices. IEEE Computer Society (2008). Available at: http://standards.ieee.org/findstds/standard/1619-2007.html
IEEE Std 1619.2-2010: IEEE Standard for Wide-block Encryption for Shared Storage Media. IEEE Computer Society, March 2011. http://standards.ieee.org/findstds/standard/1619.2-2010.html
Iwata, T., Yasuda, K.: BTM: A single-key, inverse-cipher-free mode for deterministic authenticated encryption. In: Jacobson Jr. M.J., Rijmen, V., Safavi-Naini, R. (eds.) Selected Areas in Cryptography, vol 5867 of Lecture Notes in Computer Science, pp. 313–330. Springer, Berlin (2009)
Iwata, T., Yasuda, K.: HBS: A single-key mode of operation for deterministic authenticated encryption. In: Dunkelman, O. (ed.) FSE, vol 5665 of Lecture Notes in Computer Science, pp. 394–415. Springer, Berlin (2009)
Krovetz, T., Rogaway, P.: The software performance of authenticated-encryption modes. In: Joux, A. (ed.) Fast Software Encryption—18th International Workshop, FSE 2011, Lyngby, Denmark, February 13–16, 2011, Revised Selected Papers, vol 6733 of Lecture Notes in Computer Science, pp. 306–327. Springer, Berlin (2011)
Liskov, M., Minematsu, K.: Comments on XTS-AES. Comments On The Proposal To Approve XTS-AES (2008)
Liskov, M., Rivest, R.L., Wagner, D.: Tweakable block ciphers. In: Yung, M. (ed.)Proceedings of the Advances in Cryptology—CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2002, vol 2442 of Lecture Notes in Computer Science, pp. 31–46. Springer, Berlin (2002)
Mancillas-López, C., Chakraborty, D., Rodríguez-Henríquez, F.: Reconfigurable hardware implementations of tweakable enciphering schemes. IEEE Trans. Comput. 59(11), 1547–1561 (2010)
McGrew, D.A., Fluhrer, S.R.: The Extended Codebook (XCB) Mode of Operation. Cryptology ePrint Archive, Report 2004/278 (2004). http://eprint.iacr.org/
McGrew, D.A., Fluhrer, S.R.: The security of the extended codebook (XCB) mode of operation. In: Adams, C.M., Miri, A., Wiener, M.J., (eds.) Selected Areas in Cryptography, vol 4876 of Lecture Notes in Computer Science, pp. 311–327. Springer, Berlin (2007)
Rogaway, P.: Efficient instantiations of tweakable blockciphers and refinements to modes ocb and pmac. In: Lee, P.J. (ed.) ASIACRYPT, vol 3329 of Lecture Notes in Computer Science, pp. 16–31. Springer, Berlin (2004)
Rogaway, P., Bellare, M., Black, J.: OCB: a block-cipher mode of operation for efficient authenticated encryption. ACM Trans. Inf. Syst. Secur. 6(3), 365–403 (2003)
Rogaway, P., Shrimpton, T.: A provable-security treatment of the key-wrap problem. In: Vaudenay, S. (ed.) EUROCRYPT, vol 4004 of Lecture Notes in Computer Science, pp. 373–390. Springer, Berlin (2006)
Sarkar, P.: Improving upon the TET mode of operation. In: Nam, K.-H., Rhee, G. (eds.) ICISC, vol 4817 of Lecture Notes in Computer Science, pp. 180–192. Springer, Berlin (2007)
Sarkar, P.: Efficient tweakable enciphering schemes from (block-wise) universal hash functions. IEEE Trans. Inf. Theory 55(10), 4749–4760 (2009)
Sarkar, P.: Tweakable enciphering schemes using only the encryption function of a block cipher. Inf. Process. Lett. 111(19), 945–955 (2011)
Sarkar, P.: Modes of operations for encryption and authentication using stream ciphers supporting an initialisation vector. Cryptogr. Commun. 6(3), 189–231 (2014)
S. Technology: Comments on XTS-AES. Comments On The Proposal To Approve XTS-AES (2008)
Vasic, B., Despotovic, M., Senk, V.: Recording physics and organization of data on a disk. In: Kurtas, E.M., Vasic, B. (eds.) Coding and Signal Processing for Magnetic Recording Systems, pp. 1–9. CRC Press, Boston (2004)
Wang, P., Feng, D., Wu, W.: HCTR: A variable-input-length enciphering mode. In: Feng, D., Lin, D., Yung, M. (eds.) CISC, vol 3822 of Lecture Notes in Computer Science, pp. 175–188. Springer, Berlin (2005)
Acknowledgements
The authors thank the reviewers for their comments and suggestions.
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
1.1 Proof of Theorem 1
First we state some useful properties of BRW polynomials without proof. For the proofs, the interested reader is referred to [2, 32].
Property 1
If \(m\ge 3\) and \(t\le m < 2t-1\) then \(\mathsf{BRW}_h(X_1,\ldots ,X_m)\) is a monic polynomial of degree \(2t-1\).
Property 2
Let \(X=(X_1,X_2,\ldots ,X_m),X^{\prime }=(X^{\prime }_1,X^{\prime }_2,\ldots ,X^{\prime }_m)\in [{ GF}(2^n)]^m\) such that \(X\ne X^{\prime }\). Let \(Y = \mathsf{BRW}_h(X_1,X_2,\ldots ,X_m)\) and \(Y^{\prime } = \mathsf{BRW}_h(X^{\prime }_1,X^{\prime }_2,\ldots ,X^{\prime }_m)\). Then for every fixed \(a \in { GF}(2^n)\)
The probability is taken over the random choice of h.
For proving Theorem 1, we also use the following lemma.
Lemma 1
Let \(X=(X_1,X_2,\ldots ,X_m),X^{\prime }=(X^{\prime }_1,X^{\prime }_2,\ldots ,X^{\prime }_m)\in [{ GF}(2^n)]^m\) such that \(X\ne X^{\prime }\). Let \(Y = h\mathsf{BRW}_h(X_1,X_2,\ldots ,X_m)\) and \(Y^{\prime } = h\mathsf{BRW}_h(X^{\prime }_1,X^{\prime }_2,\ldots ,X^{\prime }_m)\). Then for every fixed \(\delta \in { GF}(2^n)\)
The probability is taken over the random choice of h.
The proof easily follows from Property 2 of the BRW polynomials [32].
Proof of Theorem 1
To prove the security of BCTR\([\varPi ]\), we replace the block cipher E in the construction of Fig. 1 by a permutation \(\pi \) chosen uniformly at random from \(\varPi = \mathrm {Perm}(n)\). We call the encryption function of BCTR\([\varPi ]\) as \({{\mathbf {E}}}_{h,\pi }\), where \(h\mathop {\leftarrow }\limits ^{\$}\{0,1\}^n\) is the key for the BRW polynomial. We prove the privacy bound first. We consider the game playing technique. We briefly discuss the games below:
-
1.
Game G0: In G0 (shown in Fig. 4), the block cipher is replaced by the random permutation \(\pi \). The permutation \(\pi \) is constructed on the fly keeping record of the domain and range sets as done in the subroutine Ch-\(\pi \) in Fig. 4. Thus, G0 provide the proper encryption oracle to \(\mathcal {A}\). Thus, we have:
$$\begin{aligned} \Pr \left[ \mathcal {A}^{{{\mathbf {E}}}_{h,\pi }(.,.)}\Rightarrow 1\right] = \Pr [\mathcal {A}^{\text{ G0 }}\Rightarrow 1]. \end{aligned}$$(6) -
2.
Game G1: Fig. 4 with the boxed entries removed represents the game G1. In G1, it is not guaranteed that Ch-\(\pi \) behaves like a permutation, but the games G0 and G1 are identical until the bad flag is set. Thus, we have
$$\begin{aligned} \Pr [\mathcal {A}^{\text{ G0 }}\Rightarrow 1] - \Pr [\mathcal {A}^{\text{ G1 }}\Rightarrow 1] \le \Pr [\mathcal {A}^{\text{ G1 }} \text{ sets } \text{ bad }]. \end{aligned}$$(7)Note that in G1 the adversary gets random strings as output irrespective of his queries. Hence,
$$\begin{aligned} \Pr [\mathcal {A}^{\text{ G1 }}\Rightarrow 1] = \Pr [\mathcal {A}^{\$(.,.)}\Rightarrow 1]. \end{aligned}$$(8) -
3.
Game G2: In Game G2 (shown in Fig. 5), we do not use the subroutine Ch-\(\pi \) any more but return random strings immediately after the \(\mathcal {A}\) asks a query. Later we keep track of the elements that would have got in the domain and range sets of the permutation \(\pi \) in multisets \(\mathcal{S}\) and \(\mathcal{R}\). We set the bad flag when there is a collision in either \(\mathcal{S}\) or \(\mathcal{R}\). For the adversary, the games G1 and G2 are identical. So,
$$\begin{aligned} \Pr [\mathcal {A}^{{G1}} \Rightarrow 1] = \Pr [\mathcal {A}^{{G2}} \Rightarrow 1], \end{aligned}$$(9)and
$$\begin{aligned} \Pr [\mathcal {A}^{{G1}} \text{ sets } \text{ bad }] = \Pr [\mathcal {A}^{{G2}} \text{ sets } \text{ bad }]. \end{aligned}$$(10)
Hence, using Eqs. (6), (7), (8), (9) and (10), we have
According to the definition of the privacy advantage of \(\mathcal {A}\), we have
Now we need to bound \(\Pr [\mathcal {A}^{{G2}} \text{ sets } \text{ bad }]\). Assuming that \(\mathcal{A}\) makes a total of q queries, the elements in the multisets \(\mathcal{S}\) and \(\mathcal{R}\) after the interaction of \(\mathcal{A}\) with G2 terminates would be
Let \(\mathsf{COLLD}\) be the event that there is a collision in \(\mathcal{S}\) and \(\mathsf{COLLR}\) be the event that there is a collision in \(\mathcal{R}\). Using the facts that \(\gamma ^s = h\mathsf{BRW}_h(P_1^s||P_2^s||\ldots ||P_m^s||T^s)\) and \(\tau ^s, C_i^s\) are uniform random elements of \(\{0,1\}^n\), we have the following:
-
1.
For \(1\le s, s'\le q\) and \(s \ne s', \Pr [\gamma ^s = \gamma ^{s'}] \le 2(m+1)/2^n\) (see Lemma 1).
-
2.
For \(1\le s, s'\le q, 1\le i,i'\le m\), and \(s \ne s', \Pr [\tau ^{s} \oplus {\mathsf{bin}}_n(i)= \tau ^{s'} \oplus {\mathsf{bin}}_n(i')] \le 1/2^n\), as \(\tau ^s, \tau ^{s'}\) are uniform random elements in \(\{0,1\}^n\).
-
3.
For \(1\le s\le q, 1\le i,i'\le m\), and \(i \ne i', \Pr [\tau ^{s} \oplus {\mathsf{bin}}_n(i)= \tau ^{s} \oplus {\mathsf{bin}}_n(i')] =0\).
-
4.
For \(1\le s\le q, 1\le i \le m, \Pr [\gamma ^s = \tau ^s \oplus {\mathsf{bin}}_n(i)] = 2(m+1)/2^n\). To see this, note that \(\gamma ^s \oplus \tau ^s \oplus {\mathsf{bin}}_n(i)\) is a nonzero polynomial on h of degree at most \(2(m+1)\) [32].
-
5.
For \(1\le s, s'\le q\) and \(s \ne s', \Pr [\tau ^s = \tau ^{s'}] =1/2^n\).
-
6.
For \(1\le s\le q, 1\le i, i'\le m\), and \(i \ne i', \Pr [C_i^s \oplus P_i^s =C_{i'}^s \oplus P_{i'}^s] = 1/2^n\).
-
7.
For \(1\le s\le q, 1\le i\le m, \Pr [\tau ^s = C_i^s \oplus P_i^s] = 1/2^n\), as \(\tau ^s\) and \(C_i^s\) are uniform random elements in \(\{0,1\}^n\).
Using the above observations, and the union bound we conclude,
and
Thus, we have
This completes the proof of the privacy bound.
Proving the authentication bound: To prove the authenticity bound, we assume that \(\mathcal {A}\) makes a total of q queries including the forgery. The first \(q-1\) queries are \((T^1;P^1),(T^2;P^2),\ldots , (T^{q-1};P^{q-1})\).
Finally \(\mathcal {A}\) attempts a forgery \((T^q;C^q||\tau ^q)\).
We describe how the queries of \(\mathcal{A}\) are responded. As in the previous proof, we assume the BCTR construction to be instantiated with \(\pi \) selected randomly from \(\text{ Perm }(n)\). We start with two empty multisets \(\mathsf{Dom}\) and \(\mathsf{Ran}\). In response to the \(s^{th}\) query \((T^s,P^s)\)(\(1\le s \le q-1\)) the following steps are executed:
-
1.
A uniform random string \(C^s||\tau ^s\) of \((m+1)n\) bits is returned to \(\mathcal{A}\).
-
2.
\(\gamma ^s = h\mathsf{BRW}_h(P^s1,P^s_2,\ldots ,P^s_m,T^s_m)\) is inserted in \(\mathsf{Dom}\) and \(\tau ^s\) is inserted in \(\mathsf{Ran}\).
-
3.
For \(1\le i \le m, \tau ^s \oplus \mathsf{bin}_n(i)\) is inserted in \(\mathsf{Dom}\) and \((P^s_i \oplus C^s_i)\) is inserted into \(\mathsf{Ran}\).
Note that this simulation is perfect if there is no collision in the multisets \(\mathsf{Dom}\) and \(\mathsf{Rng}\).
For the final forgery query \(C^q||\tau ^q\), let \(C^q = C^q_1|| C^q_2||\cdots ||C^q_m\), and \(P_i^q = C_i^q \oplus \pi (\tau ^q \oplus \mathsf{bin}_n(i)\), for \(1\le i \le m\). Let \(\gamma ^q = h\mathsf{BRW}_h(P_1^q,P_2^q,\ldots ,P_m^q)\). The adversary is successful in its forgery if \(\pi (\gamma ^q) = \tau ^q\). If \(\gamma ^q\) is distinct from all the elements in \(\mathsf{Dom}\) and \(\tau ^q\) is also distinct from all elements in \(\mathsf{Rng}\), then \(\Pr [\pi (\gamma ^q) = \tau ^q] = 1/2^n\). If \(\gamma ^q\) is distinct from all elements in \(\mathsf{Dom}\) and \(\tau ^q\) is in \(\mathsf{Rng}\), then \(\Pr [\pi (\gamma ^q) = \tau ^q] = 0\).
Let \(\mathsf{COLL}\) be the event that there is a collision in the set \(\mathsf{Dom} \cup \{ \gamma ^q\}\) or \(\mathsf{Rng}\), then we have
It is easy to verify that \(\Pr [\mathsf{COL}] \le \Pr [\mathsf{COLLD}] + \Pr [\mathsf{COLLR}]\), where \(\mathsf{COLLD}\) and \(\mathsf{COLLR}\) are defined in the proof for privacy. Thus, using Eqs. (14), (15), we have
as desired.\(\square \)
Rights and permissions
About this article
Cite this article
Chakraborty, D., López, C.M. & Sarkar, P. Disk encryption: do we need to preserve length?. J Cryptogr Eng 8, 49–69 (2018). https://doi.org/10.1007/s13389-016-0147-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13389-016-0147-0