Journal of Computer Science and Technology ›› 2018, Vol. 33 ›› Issue (6): 1261-1277.doi: 10.1007/s11390-018-1886-4

Special Issue: Theory and Algorithms

• Regular Paper • Previous Articles     Next Articles

Generalized Tweakable Even-Mansour Cipher and Its Applications

Ping Zhang, Hong-Gang Hu*   

  1. Key Laboratory of Electromagnetic Space Information, Chinese Academy of Sciences, Hefei 230027, China School of Information Science and Technology, University of Science and Technology of China, Hefei 230027, China
  • Received:2017-06-16 Revised:2018-09-13 Online:2018-11-15 Published:2018-11-15
  • Contact: Hong-Gang Hu,E-mail:hghu2005@ustc.edu.cn E-mail:hghu2005@ustc.edu.cn
  • About author:Ping Zhang received his Ph.D. degree in information and communication engineering from the University of Science and Technology of China, Hefei, in June 2018. His major research interests include pseudorandom number generators, block ciphers, and authenticated encryption modes.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China under Grant Nos. 61522210 and 61632013.

This paper describes a generalized tweakable blockcipher HPH (Hash-Permutation-Hash), which is based on a public random permutation P and a family of almost-XOR-universal hash functions H={HK}KK as a tweak and key schedule, and defined as y=HP HK((t1, t2), x)=P (xHK(t1)) ⊕ HK(t2), where K is a key randomly chosen from a key space K, (t1, t2) is a tweak chosen from a valid tweak space T, x is a plaintext, and y is a ciphertext. We prove that HPH is a secure strong tweakable pseudorandom permutation (STPRP) by using H-coefficients technique. Then we focus on the security of HPH against multi-key and related-key attacks. We prove that HPH achieves both multi-key STPRP security and related-key STPRP security. HPH can be extended to wide applications. It can be directly applied to authentication and authenticated encryption modes. We apply HPH to PMAC1 and OPP, provide an improved authentication mode HPMAC and a new authenticated encryption mode OPH, and prove that the two modes achieve single-key security, multi-key security, and related-key security.

Key words: tweakable blockcipher; H-coefficients technique; authentication; authenticated encryption; provable security;

[1] Halevi S, Rogaway P. A tweakable enciphering mode. In Lecture Notes in Computer Science 2729, Boneh D (ed.), Springer-Verlag, 2003, pp.482-499.
[2] Liskov M, Rivest R L, Wagner D. Tweakable block ciphers. In Lecture Notes in Computer Science 2442, Yung M (ed.), Springer-Verlag, 2002, pp.31-46.
[3] Halevi S, Rogaway P. A parallelizable enciphering mode. In Lecture Notes in Computer Science 2964, Okamoto T (ed.), Springer-Verlag, 2004, pp.292-304.
[4] Rogaway P, Zhang H. Online ciphers from tweakable blockciphers. In Lecture Notes in Computer Science 6558, Kiayias A (ed.), Springer-Verlag, 2011, pp.237-249.
[5] Rogaway P. Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC. In Lecture Notes in Computer Science 3329, Lee P J (ed.), Springer-Verlag, 2004, pp.16-31.
[6] Landecker W, Shrimpton T, Terashima R S. Tweakable blockciphers with beyond birthday-bound security. In Lecture Notes in Computer Science 7417, Safavi-Naini R, Canetti R (eds.), Springer-Verlag, 2012, pp.14-30.
[7] Krovetz T, Rogaway P. The software performance of authenticated-encryption modes. In Lecture Notes in Computer Science 6733, Joux A (ed.), Springer-Verlag, 2011, pp.306-327.
[8] Andreeva E, Bogdanov A, Luykx A, Mennink B, Tischhauser E, Yasuda K. Parallelizable and authenticated online ciphers. In Lecture Notes in Computer Science 8269, Sako K, Sarkar P (eds.), Springer-Verlag, 2013, pp.424-443.
[9] Granger R, Jovanovic P, Mennink B, Neves S. Improved masking for tweakable blockciphers with applications to authenticated encryption. In Lecture Notes in Computer Science 9665, Fischlin M, Coron J S (eds.), Springer-Verlag, 2016, pp.263-293.
[10] Bossuet L, Datta N, Mancillas-López C, Nandi M. ELmD:A pipelineable authenticated encryption and its hardware implementation. IEEE Trans. Computers, 2016, 65(11):3318-3331.
[11] Chakraborty D, Sarkar P. On modes of operations of a block cipher for authentication and authenticated encryption. Cryptography and Communications, 2016, 8(4):455-511.
[12] Peyrin T, Seurin Y. Counter-in-Tweak:Authenticated encryption modes for tweakable block ciphers. In Lecture Notes in Computer Science 9814, Robshaw M, Katz J (eds.), Springer-Verlag, 2016, pp.33-63.
[13] Wang L, Guo J, Zhang G, Zhao J, Gu D. How to build fully secure tweakable blockciphers from classical blockciphers. In Lecture Notes in Computer Science 10031, Cheon J, Takagi T (eds.), Springer-Verlag, 2016, pp.455-483.
[14] Cogliati B, Lampe R, Seurin Y. Tweaking Even-Mansour ciphers. In Lecture Notes in Computer Science 9215, Gennaro R, Robshaw M (eds.), Springer-Verlag, 2015, pp.189-208.
[15] Cogliati B, Seurin Y. Beyond-birthday-bound security for tweakable Even-Mansour ciphers with linear tweak and key mixing. In Lecture Notes in Computer Science 9453, Iwata T, Cheon H (eds.), Springer-Verlag, 2015, pp.134-158.
[16] Mennink B. XPX:Generalized tweakable Even-Mansour with improved security guarantees. In Lecture Notes in Computer Science 9814, Robshaw M, Katz J (eds.), Springer-Verlag, 2016, pp.64-94.
[17] Reyhanitabar R, Vaudenay S, Vizár D. Misuse-resistant variants of the OMD authenticated encryption mode. In Lecture Notes in Computer Science 8782, Chow S S M, Liu J K, Hui L C K, Yiu S (eds.), Springer-Verlag, 2014, pp.55-70.
[18] Reyhanitabar R, Vaudenay S, Vizár D. Boosting OMD for almost free authentication of associated data. In Lecture Notes in Computer Science 9054, Leander G (ed.), Springer-Verlag, 2015, pp.411-427.
[19] Mouha N, Luykx A. Multi-key security:The Even-Mansour construction revisited. In Lecture Notes in Computer Science 9215, Gennaro R, Robshaw M (eds.), Springer-Verlag, 2015, pp.209-223.
[20] Reyhanitabar R, Vaudenay S, Vizár D. Authenticated encryption with variable stretch. In Lecture Notes in Computer Science 10031, Cheon J, Takagi T (eds.), SpringerVerlag, 2016, pp.396-425.
[21] Chatterjee S, Menezes A, Sarkar P. Another look at tightness. In Lecture Notes in Computer Science 10031, Miri A, Vaudenay S (eds.), Springer-Verlag, 2011, pp.293-319.
[22] Mantin I, Shamir A. A practical attack on broadcast RC4. In Lecture Notes in Computer Science 10031, Matsui M (ed.), Springer-Verlag, 2001, pp.152-164.
[23] Fouque P, Joux A, Mavromati C. Multi-user collisions:Applications to discrete logarithm, Even-Mansour and PRINCE. In Lecture Notes in Computer Science 8873, Sarkar P, Iwata T (eds.), Springer-Verlag, 2014, pp.420-438.
[24] Bellare M, Bernstein D J, Tessaro S. Hash-function based PRFs:AMAC and its multi-user security. In Lecture Notes in Computer Science 9665, Fischlin M, Coron J S (eds.), Springer-Verlag, 2016, pp.566-595.
[25] Bellare M, Tackmann B. The multi-user security of authenticated encryption:AES-GCM in TLS 1.3. In Lecture Notes in Computer Science 9665, Robshaw M, Katz J (eds.), Springer-Verlag, 2016, pp.247-276.
[26] Hoang V T, Tessaro S. Key-alternating ciphers and keylength extension:Exact bounds and multi-user security. In Lecture Notes in Computer Science 9814, Robshaw M, Katz J (eds.), Springer-Verlag, 2016, pp.3-32.
[27] Guo Z, Wu W, Liu R, Zhang L. Multi-key analysis of tweakable Even-Mansour with applications to minalpher and OPP. IACR Transactions on Symmetric Cryptology, 2016, 2016(2):288-306.
[28] Biham E. New types of cryptoanalytic attacks using related keys (extended abstract). In Lecture Notes in Computer Science 765, Helleseth T (ed.), Springer-Verlag, 1993, pp.398-409.
[29] Biham E. New types of cryptanalytic attacks using related keys. Journal of Cryptology, 1994, 7(4):229-246.
[30] Bellare M, Kohno T. A theoretical treatment of relatedkey attacks:RKA-PRPs, RKA-PRFs, and applications. In Lecture Notes in Computer Science 2656, Biham E (ed.), Springer-Verlag, 2003, pp.491-506.
[31] Biryukov A, Khovratovich D. Related-key cryptanalysis of the full AES-192 and AES-256. In Lecture Notes in Computer Science 5912, Matsui M (ed.), Springer-Verlag, 2009, pp.1-18.
[32] Sun S, Hu L, Wang P, Qiao K, Ma X, Song L. Automatic security evaluation and (related-key) differential characteristic search:Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. In Lecture Notes in Computer Science 8873, Sarkar P, Iwata T (eds.), Springer-Verlag, 2014, pp.158-178.
[33] Chen J, Miyaji A. A new practical key recovery attack on the stream cipher RC4 under related-key model. In Lecture Notes in Computer Science 6584, Lai X, Yung M, Lin D (eds.), Springer-Verlag, 2010, pp.62-76.
[34] Cogliati B, Seurin Y. On the provable security of the iterated Even-Mansour cipher against related-key and chosenkey attacks. In Lecture Notes in Computer Science 9056, Oswald E, Fischlin M (eds.), Springer-Verlag, 2015, pp.584-613.
[35] Wang P, Li Y, Zhang L, Zheng K. Related-key almost universal hash functions:Definitions, constructions and applications. In Lecture Notes in Computer Science 9783, Peyrin T (ed.), Springer-Verlag, 2016, pp.514-532.
[36] Peyrin T, Sasaki Y, Wang L. Generic related-key attacks for HMAC. In Lecture Notes in Computer Science 7658, Wang X, Sako K (eds.), Springer-Verlag, 2012, pp.580-597.
[37] Bhattacharyya R, Roy A. Secure message authentication against related-key attack. In Lecture Notes in Computer Science 8424, Moriai S (ed.), Springer-Verlag, 2013, pp.305-324.
[38] Dobraunig C, Eichlseder M, Mendel F. Related-key forgeries for Prost-OTR. In Lecture Notes in Computer Science 9054, Leander G (ed.), Springer-Verlag, 2015, pp.282-296.
[39] Patarin J. The "Coefficients H" technique. In Lecture Notes in Computer Science 5381, Avanzi R M, Keliher L, Sica F (eds.), Springer-Verlag, 2008, pp.328-345.
[40] Kurosawa K. Power of a public random permutation and its application to authenticated encryption. IEEE Transactions on Information Theory, 2010, 5(10):5366-5374.
[41] Chen S, Steinberger J P. Tight security bounds for keyalternating ciphers. In Lecture Notes in Computer Science 8441, Nguyen P Q, Oswald E (eds.), Springer-Verlag, 2014, pp.327-350.
[42] Cogliati B, Seurin Y. EWCDM:An efficient, beyondbirthday secure, nonce-misuse resistant MAC. In Lecture Notes in Computer Science 9814, Robshaw M, Katz J (eds.), Springer-Verlag, 2016, pp.121-149.
[43] Datta N, Nandi M. ELmE:A misuse resistant parallel authenticated encryption. In Lecture Notes in Computer Science 8544, Susilo W, Mu Y (eds.), Springer-Verlag, 2014, pp.306-321.
[44] Daemen J, Lamberger M, Pramstaller N, Rijmen V, Vercauteren F. Computational aspects of the expected differential probability of 4-round AES and AES-like ciphers. Computing, 2009, 85(1):85-104.
[45] Rogaway P, Bellare M, Black J. OCB:A block-cipher mode of operation for efficient authenticated encryption. ACM Transactions on Information and System Security, 2003, 6(3):365-403.
[46] Sasaki Y, Yasuda K. A new mode of operation for incremental authenticated encryption with associated data. In Lecture Notes in Computer Science 9566, Dunkelman O, Keliher L (eds.), Springer-Verlag, 2016, pp.397-416.
[47] Sarkar P. Modes of operations for encryption and authentication using stream ciphers supporting an initialisation vector. Cryptography and Communications, 2014, 6(3):189-231.
[1] Yan-Hong Fan, Mei-Qin Wang, Yan-Bin Li, Kai Hu, Mu-Zhou Li. A Secure IoT Firmware Update Scheme Against SCPA and DoS Attacks [J]. Journal of Computer Science and Technology, 2021, 36(2): 419-433.
[2] Chi Zhang, Jun-Rong Liu, Da-Wu Gu, Wei-Jia Wang, Xiang-Jun Lu, Zheng Guo, Hai-Ning Lu. Side-Channel Analysis for the Authentication Protocols of CDMA Cellular Networks [J]. Journal of Computer Science and Technology, 2019, 34(5): 1079-1095.
[3] Linke Guo, Chi Zhang, Yuguang Fang, Phone Lin. A Privacy-Preserving Attribute-Based Reputation System in Online Social Networks [J]. , 2015, 30(3): 578-597.
[4] Yong-Qiang Lv, Qiang Zhou, Yi-Ci Cai, Gang Qu. Trusted Integrated Circuits: the Problem and Challenges [J]. , 2014, 29(5): 918-928.
[5] Zheng Gong, Pieter Hartel, Svetla Nikova, Shao-Hua Tang, and Bo Zhu. TuLP:A Family of Lightweight Message Authentication Codes for Body Sensor Networks [J]. , 2014, 29(1): 53-68.
[6] Jing Xu and Wen-Tao Zhu. A Generic Framework for Anonymous Authentication in Mobile Networks [J]. , 2013, 28(4): 732-742.
[7] Xi-Yang Liu (刘西洋), Member, CCF, ACM, Hai-Chang Gao (高海昌), Member, IEEE Li-Ming Wang (王黎明), and Xiu-Ling Chang (常秀玲). An Enhanced Drawing Reproduction Graphical Password Strategy [J]. , 2011, 26(6): 988-999.
[8] Yong Xi, Ke-Wei Sha, Wei-Song Shi, Loren Schwiebert, and Tao Zhang. Probabilistic Adaptive Anonymous Authentication in Vehicular Networks [J]. , 2008, 23(6 ): 916-928 .
[9] Rafiullah Chamlawi, Asifullah Khan, and Adnan Idris. Wavelet Based Image Authentication and Recovery [J]. , 2007, 22(6): 795-804 .
[10] Yong-Dong Zhang, Sheng Tang, and Jin-Tao Li. Secure and Incidental Distortion Tolerant Digital Signature for Image Authentication [J]. , 2007, 22(4): 618-625 .
[11] Sin-Kyu Kim, Jae-Woo Choi, Dae-Hun Nyang, Gene-Beck Hahn, and Joo-Seok Song. Smart Proactive Caching Scheme for Fast Authenticated Handoff in Wireless LAN [J]. , 2007, 22(3): 476-480 .
[12] Kai-Le Su, Qing-Liang Chen, Abdul Sattar, Wei-Ya Yue, Guan-Feng Lv, and Xi-Zhong Zheng. Verification of Authentication Protocols for Epistemic Goals via SAT Compilation [J]. , 2006, 21(6): 932-943 .
[13] Weisong Shi , Sharun Santhosh, and Hanping Lufei. Secure Application-Aware Service Differentiation in Public Area Wireless Networks [J]. , 2005, 20(5): 676-688 .
[14] David Zhang[1], Guang-Ming Lu[2], Adams Wai-Kin Kong[1,3], and Michael Wong[1]. Online Palmprint Identification System for Civil Applications [J]. , 2005, 20(1): 0-0.
[15] Qing-Hua Zheng, David L. Pepyne, and Qing Wang. New Approach to WLAN Security with Synchronized Pseudo Random [J]. , 2004, 19(6): 0-0.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved