【作者】 李学远；

【导师】 王新梅；

【作者基本信息】 西安电子科技大学 ， 通信与信息系统， 2009， 博士

【摘要】 本文对基于分组密码的消息认证码进行了研究,包括消息认证码的安全性分析,消息认证码算法的改进,安全性证明的改进以得到一个更好的上界等,主要成果有:(1)OMAC1``算法是OMAC的一个改进算法,旨在消除OMAC中最后两个密钥之间的简单代数关系,提高OMAC抵抗密钥恢复攻击和伪造攻击的能力。但有关研究表明,即使在底层分组密码是一个伪随机置换的假设下,也不能证明OMAC1``的安全性。能构造一个满足一定条件的伪随机置换,使得利用该伪随机置换的OMAC1``不再安全,攻击者仅需一次询问便能得到成功的伪造。因此,OMAC1``并没有真正提高OMAC的安全性,OMAC1``的安全性较OMAC弱。因为OMAC1``的密钥之间存在常数异或的关系,当底层分组密码满足在一定相关密钥攻击下是一个RKA-PRP的更高安全性假设,证明了OMAC1``是一个伪随机函数。(2)尽管目前一些分组密码在已知的相关密钥攻击下仍然是安全的,但和伪随机置换的假设相比,分组密码在一定相关密钥攻击下是一个RKA-PRP的假设要求过高。事实上,几乎所有基于分组密码的消息认证码的安全性都是建立在底层分组密码是一个伪随机置换的假设上。将两个密钥之间的固定差分设为全0,并在CBC链中引入一个加密的常数,改进了OMAC1``算法。改进的OMAC1``能在底层分组密码是一个伪随机置换的假设下,证明是一个伪随机函数。并分析了改进方法的合理性。(3)基于有向无环图DAG结构的消息认证码利用满足伪随机函数保持性的一系列带权图。它包含了许多广泛使用的消息认证码,比如XCBC,TMAC,OMAC,以及PMAC等。改进了基于DAG的消息认证码的安全性证明,得到一个新的上界O ( qσ2 n),其中,q是攻击者询问的次数,σ是所有询问所包含的分组总数。(4)PMAC是一种可并行运算的消息认证码。消息的所有分组在分组密码加密前先要进行掩盖,以防止利用明文特征进行攻击。但这个过程也泄露了可以利用的信息。利用这些边信息,得到一种新的PMAC的攻击方法,该方法在长消息的应用环境很实用。(5)证明了OPMAC是一个伪随机函数,原OPMAC仅证明了其具有不可伪造性。对一个消息认证码来说,伪随机函数是一个比不可伪造性更强的安全性定义。OPMAC不仅仅具有不可伪造性,还是一个伪随机函数。而且,所得到的新上界是用所有询问所包含的分组总数表示的形式,不再是用最长消息长度表示的形式。当询问消息的长度严重失衡时,这是一个更好的界。(6)在一些安全协议中,经常需要同时认证一组数据。但普通消息认证码的输入仅为单个的字符串,因此,有必要设计一种输入可为字符串向量的消息认证码。文中得到两种不同的输入可为字符串向量的消息认证码的构造方法。第一个基于合成的通用哈希函数,先用一个并行的通用哈希函数处理字符串向量,所得结果输入另一个通用哈希函数,然后用分组密码加密得到认证标记。并在底层分组密码是一个伪随机置换的假设下,证明了它是一个伪随机函数。但它需要三个密钥。第二种构造方法利用分组密码,模拟PMAC的结构,得到的输入可为字符串向量的消息认证码具有双层可并行运算的结构。它仅需一个密钥。最后,证明了它的安全性。更多还原

【Abstract】 Message authentication codes based on the block cipher are researched, including the security analysis of some message authentication codes, the improvement of some message authentication codes, improving the security analysis of message authentication codes in order to obtain better upper bounds etc. We obtain the main results as follows:(1) OMAC1`` is an improvement of OMAC for avoiding the simple algebraic relationship between the last two keys and enhancing the resistance of OMAC to the key recovery attack and forgery attack. But some research result shows that OMAC1`` is not provable secure even if the underlying block cipher is a pseudorandom permutation. A pseudorandom permutation with some property can be constructed and if this pseudorandom permutation is used in OMAC1``, then OMAC1`` is completely insecure and simple forgery attacks can be obtained by using only one oracle query. So, the security of OMAC is not really improved by OMAC1``. OMAC1`` is less secure than the original OMAC. As the use of keys related by some fixed xor difference in the OMAC1``, under the stronger assumption that the underlying block cipher is a RKA-PRP against a certain class of related key attacks, OMAC1`` is proved to be a pseudorandom function.(2) Although existing block ciphers are still secure against known related key attacks, the assumption of RKA-PRP against a certain class of related key attacks on the block cipher is still stronger than the standard pseudorandom permutation assumption. Actually, almost all block cipher based message authentication codes proved their securities under the assumption of the underlying block cipher as a pseudorandom permutation. By setting the fixed xor difference of the keys to all zeros and using the encryption of some constant in the CBC computation, OMAC1`` is improved. The improved OMAC1`` can be proved to be secure under the standard pseudorandom permutation assumption. Also, the rationality of the modification is analyzed.(3) A message authentication code based on the DAG construction uses a sequence of colored graphs that are PRF-preserving. It includes many known constructions like XCBC, TMAC, OMAC, PMAC etc. An improved security analysis of the message authentication code using DAG construction is presented. The newly obtained bound is O ( qσ2 n), where an adversary can make at most q queries with at mostσmany blocks.(4) PMAC is a parallelizable message authentication code. The message blocks are masked before they are encrypted by the block cipher in order to avoid the attacks using the properties of the messages. But some useful information is issued in this process. Using this side channel, a new attack is proposed against PMAC. It is very practical in the setting where long messages are authenticated.(5) Originally, OPMAC is only proved to be unforgeable. Now, it is proved that OPMAC is also a pseudorandom function. For a message authentication code, PRF is a stronger security definition than unforgeability. So, OPMAC is not only unforgeable, but also it is a pseudorandom function. Furthermore, the new bound is expressed in terms of the total blocks in all the queries of an adversary, while the previous bound is expressed in terms of the maximum length of each query. This new bound is better than the original bound, if the lengths of queries are heavily unbalanced.(6) In some security protocols, there is usually a need to authenticate a group of data. But ordinary message authentication codes only take a single string as input, so it is necessary to design a message authentication code accepting a vector of strings as input. We present two constructions for vector-input message authentication codes. The first one makes use of the composition of universal hash families. First, the vector of strings is processed by a parallel universal hash function, the result is put into another universal hash function, and then it is encrypted. Under the assumption that the underlying block cipher is a pseudorandom permutation, its security is proved. But it needs three keys. The second construction uses only block ciphers. It simulates the structure of PMAC, the resultant vector-input message authentication code is two-level parallelizable. It needs only one key. At last, its security is proved.更多还原