计算机科学技术学报 ›› 2018,Vol. 33 ›› Issue (6): 1261-1277.doi: 10.1007/s11390-018-1886-4

所属专题: Theory and Algorithms

• • 上一篇    下一篇

推广的可调Even-Mansour密码及其应用

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
  • 收稿日期:2017-06-16 修回日期:2018-09-13 出版日期:2018-11-15 发布日期:2018-11-15
  • 通讯作者: Hong-Gang Hu,E-mail:hghu2005@ustc.edu.cn E-mail:hghu2005@ustc.edu.cn
  • 作者简介: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.
  • 基金资助:
    This work was supported by the National Natural Science Foundation of China under Grant Nos. 61522210 and 61632013.

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.

这篇文章描述了一个推广的可调分组密码HPH,它是基于一个公共的随机置换P和一个带有密钥和调柄策略的泛哈希函数H。令K是一个随机选择的密钥,(t1,t2)是一个有效调柄,x是一个明文,则生成的密文可表示为y=HPH_K((t1,t2),x)。文章使用H-coefficients技术证明了HPH是一个安全的强可调伪随机置换。然后,聚焦HPH在多密钥、相关密钥攻击下的安全性,证明了HPH既实现了多密钥强可调伪随机置换安全又实现了相关密钥强可调伪随机置换安全。最后,将HPH拓展到更广泛的应用环境中。它可以直接应用在认证和认证加密工作模式中。应用到PMAC1方案和OPP方案,提出了改善的认证模式HPMAC和新的认证加密模式OPH,并证明了新提出的方案都实现了多密钥安全和相关密钥安全。

关键词: 可调分组密码, H-coefficients技术, 认证, 认证加密, 可证明安全

Abstract: 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. 一种抗SCPA和DOS攻击的高安全性的固件升级方案[J]. 计算机科学技术学报, 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. 针对CDMA蜂窝网络认证协议的侧信道分析[J]. 计算机科学技术学报, 2019, 34(5): 1079-1095.
[3] Yong-Qiang Lv, Qiang Zhou, Yi-Ci Cai, Gang Qu. 可信芯片:问题与挑战[J]. , 2014, 29(5): 918-928.
[4] 龚征, Pieter Hartel, Svetla Nikova, 唐韶华, 朱博. TuLP:一类面向医疗传感器网络的轻量级消息认证码[J]. , 2014, 29(1): 53-68.
[5] Jing Xu and Wen-Tao Zhu. 移动网络匿名认证协议的一般性构造[J]. , 2013, 28(4): 732-742.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 刘明业; 洪恩宇;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] 陈世华;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] 高庆狮; 张祥; 杨树范; 陈树清;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] 陈肇雄; 高庆狮;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] 黄河燕;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] 闵应骅; 韩智德;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] 唐同诰; 招兆铿;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] 闵应骅;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] 朱鸿;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] 李明慧;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn
总访问量: