基于多比特输出点函数混淆器的消息认证码_论文

第３９卷　第１期　计算机工程　２０１３年１月　Ｖｏｌ－３９　ＮＯ．１　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｊａｎｕａｒｙ　２０１３　・安全技术・　文章■号・１０００—ｌ３４２８（２０１３）０１—０１４４—－ｏ５　文献标识码ｌ　Ａ　中圈分类号：ＴＰ３０９・２　基于多比特输出点函数混淆器的消息认证码　龚高翔　，袁征　，李超　（１．西安电子科技大学通信工程学院，西安７１００７１；２．北京电子科技学院，北京１０００７０）　摘要：大多数消息认证码的安全性只依赖于Ｈａｓｈ函数，但部分Ｈａｓｈ函数未被证明是安全的。为此，提出一种基于多比　特输出点函数混淆器的消息认证方案，在此基础上，利用带多比特输出点函数混淆器和带密钥的Ｈａｓｈ函数构造一个新的消　息认证码方案。分析结果表明，该方案的安全性同时依赖于Ｈａｓｈ函数和多比特输出点函数混淆器，可以更好地保证数据传　输的完整性。　关健词：消息认证码；混淆器；虚拟灰盒混淆；带密钥的Ｈａｓｈ函数；对称加密；嵌套ＭＡＣ　Ｍｅｓｓａｇｅ　Ａｕｔｈｅｎｔｉｃａｔｉｏｎ　Ｃｏｄｅ　Ｂａｓｅｄ　０ｎ　Ｐｏｉｎｔ　Ｆｕｎｃｔｉｏｎ　Ｏｂｆｕｓｃａｔｏｒ　ｗｉｔｈ　Ｍｕｌｔｉ．．ｂｉｔ　０ｕｔｐｕｔｓ　ＧｏＮＧ　Ｇａｏ—ｘｉａｎｇ　，ＹＵＡＮ　Ｚｈｅｎｇ‘，ＬＩ　Ｃｈａｏ　（１．Ｓｃｈｏｏｌ　ｏｆＴｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉｄｉａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｌｌ　７１００７１，Ｃｈｉｎａ；　２．Ｂｅｉｊｉｎｇ　Ｅｌｅｃｔｒｏｎｉｃ　Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ　Ｉｎｓｔｉｔｕｔｅ，Ｂｅｉｊｉｎｇ　１　０００７０，Ｃｈｉｎａ）　［Ａｂｓｔｒａｃｔ］Ｓｅｃｕｒｉｔｙ　ｏｆ　ｍｏｓｔ　ｍｅｓｓａｇｅ　ａｕｔｈｅｎｔｉｃａｔｉｏｎ　ｃｏｄｅｓ　ｄｅｐｅｎｄｓ　ｏｎ　Ｈａｓｈ　ｆｕｎｃｔｉｏｎ，ｂｕｔ　ｓｏｍｅ　Ｈａｓｈ　ｆｕｎｃｔｉｏｎｓ　ｈａｖｅ　ｎｏｔ　ｂｅｅｎ　ｐｒｏｖｅｄ　ｓａｆｅ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ａ　ｎｅｗ　ｋｉｎｄ　ｏｆ　ｍｅｓｓａｇｅ　ａｕｔｈｅｎｔｉｃａｔｉｏｎ　ｓｃｈｅｍｅ　ｂａｓｅｄ　ｏｎ　ｐｏｉｎｔ　ｆｕｎｃｔｉｏｎ　ｏｂｆｕｓｃａｔｏｒ　ｗｉｔｈ　ｍｕｌｔｉ—ｂｉｔ　ｏｕｔｐｕｔｓ　ａｎｄ　ａ　Ｍｅｓｓａｇｅ　Ａｕｔｈｅｎｔｉｃａｔｉｏｎ　Ｃｏｄｅ（ＭＡＣ）ｃｏｎｓｔｒｕｃｔｉｏｎ　ｓｃｈｅｍｅ　ｉｎｃｌｕｄｉｎｇ　ａ　ｐｏｉｎｔ　ｕｆｎｃｔｉｏｎ　ｏｂｆｕｓｃａｔｏｒ　ｗｉｔｈ　ｍｕｌｔｉ　ｂｉｔ　ｏｕｔｐｕｔｓ　ａｎｄ　Ｈａｓｈ　ｆｕｎｃｔｉｏｎ　ｗｉｔｈ　ｋｅｙ．Ａｎａｌｙｓｉｓ　ｒｅｓｕｌｔｓ　ｄｅｍｏｎｓｔｒａｔｅ　ｓｅｃｕｒｉｙｔ　ｏｆ　ｔｈｅ　ｓｃｈｅｍｅ　ｄｅｐｅｎｄｓ　ｏｎ　ｔｈｅ　Ｈａｓｈ　ｆｕｎｃｔｉｏｎ　ａｎｄ　ｐｏｉｎｔ　ｆｕｎｃｔｉｏｎ　ｏｂｆｕｓｃａｔｏｒ　ｗｉｔｈ　ｍｕｌｔｉ—ｂｉｔ　ｏｕｔｐｕｔｓ，ＳＯ　ｉｔ　Ｃａｎ　ｂｅｔｔｅｒ　ｇｕａｒａｎｔｅｅ　ｔｈｅ　ｉｎｔｅｇｒｉｔｙ　ｏｆ　ｈｔｅ　ｄａｔａ　ｔｒａｎｓｍｉｓｓｉｏｎ．　［Ｋｅｙ　ｗｏｒｄｓ］Ｍｅｓｓａｇｅ　Ａｕｔｈｅｎｔｉｃａｔｉｏｎ　Ｃｏｄｅ（ＭＡＣ）；ｏｂｆｕｓｃａｔｏｒ；Ｖｉｒｔｕａｌ　Ｇｒｅｙ　Ｂｏｘ（ＶＧＢ）ｏｂｆｕｓｃａｔｉｏｎ；Ｈａｓｈ　ｆｕｎｃｔｉｏｎ　ｗｉｈｔ　ｋｅｙ；　ｓｙｍｍｅｔｒｉｃ　ｅｎｃｒｙｐｔｉｏｎ；ｎｅｓｔｅｄ　ＭＡＣ　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００—３４２８．２０１３．Ｏ１．０３１　１概述　的构造方法，充分利用了Ｈａｓｈ函数的优点。Ｈａｓｈ函　数可把一种任意长度的消息压缩为某一固定长度的　随着网络技术的快速发展，尤其是电子商务的不　消息摘要，还具有抵抗碰撞等性质。　断进步，信息的完整性问题变得越来越重要，特别是　在不安全信道通信的双方，需要有一种方法来保证发　由于混淆的数据难以识别（即不容易认识理解），　送者发送的数据能被接收者验证其真伪，以防止数据　因此本文根据黑盒混淆的一种放松形式一一虚拟灰　在没有授权的情况下被恶意篡改。常用的方法是通过　盒（Ｖｉｒｔｕａｌ　Ｇｒｅｙ　Ｂｏｘ，ＶＧＢ）混淆　Ｊ，通过添加一定的条　构造消息认证码（Ｍｅｓｓａｇｅ　Ａｕｔｈｅｎｔｉｃａｔｉｏｎ　Ｃｏｄｅ，ＭＡＣ）　件，构造一个多比特输出点函数混淆器，使其可以抵　来保证数据的完整性，它是信息安全的基本标准之　抗多种攻击。再将混淆和带密钥的Ｈａｓｈ函数相结合，　　得到一种更加安全的消息认证方法。　一，可以有效地防止数据未经授权就被篡改。构造ＭＡＣ的方法很多，可以归纳为３种类型¨Ｊ：　２虚拟黑盒混淆　基于带密钥的Ｈａｓｈ函数的构造方法，基于分组密码　对于回路Ｃ，一个概率多项式时间Ｏ是一个虚拟　的构造方法，自定义的构造方法。第ｌ类是目前常用　黑盒混淆器，它满足以下３个条件：　基金项目：国家自然科学基金资助项Ｉ￣Ｉ（６１０７０２５０）；北京市自然科学基金资助项Ｉ￣ｌ（４１０２０５５）　作者倚介：龚高翔（１９８６－－），男，硕士研究生，主研方向：密码学；袁征，教授；李超，硕士研究生　收稿日期：２０１２－０３－２０　１｜｝回日期：２０１２－０５－１２　Ｅ－ｍａｉｌ：５５０７１１２１０＠ｑｑ．ｃｏｍ　

第３９卷第１期　龚高翔，袁征，李超：基于多比特输出点函数混淆器的消息认证码　１４５　（１）功能性　对于任意刀∈Ｎ，ｃ∈Ｃｎ，ｏ（ｃ）是一个回路，与Ｃ　计算相同的功能。　（２）多项式减缓　存在一个多项式ｑ，其对任意ｎ∈Ｎ，ｃ∈Ｃｎ，有　ｌＤ（ｃ）ｌ≤ｑ（ＩｃＩ）。　（３）虚拟黑盒　对于任意ＰＰＴ（Ｐｒｏｂａｂｉｌｉｓｔｉｃ　Ｐｏｌｙｎｏｍｉａｌ　Ｔｉｍｅ）敌　手　和多项式Ｐ，存在一个ＰＰＴ模拟器　，对于所有　满足足够大的ｎ∈Ｎ和Ｃ∈　：　Ｐｒ　ＥＡ（０（ｃ））＝１卜Ｐｒ［Ｓｃ（　）＝　如果此混淆器运行在多项式时间内，那这个混淆器０　是有效的。　黑盒混淆中多项式减缓性能展现了混淆后回路　的复杂度，并且其中的虚拟黑盒性能也为混淆后回路　的安全提供了强有力的保障，混淆后的回路就像一个　“黑盒”，从某种意义上说，除了输入输出行为外，　它不泄露关于回路的任何信息。更加确切地说，任何　可以访问一个混淆回路的有效攻击者只能通过一个　只有预言机通道进入方案的有效模拟器进行模拟。由　于黑盒混淆的要求严格，因此对于许多混淆任务都不　能完成，而黑盒混淆的２种放松形式一一最可能混淆　和不可辨别混淆，在无边界模拟器的无限Ｏｒａｃｌｅ访问　下也是不安全的。相对而言，虚拟灰盒混淆的安全性　要比它们高，而且也能完成许多黑盒混淆不能完成的　任务，在一定的条件下，能构造出多比特输出点函数　混淆器。　３多比特输出点函数混淆器　定义多比特输出点函数混淆器　设Ｏ是一个点混淆器，对于具有ｍ－比特输出的　点回路，定义一个概率多项式混淆器０　Ｊ。对于一个　点　∈　和输出Ｙ＝ＹｌＹ２…Ｙｍ∈｛０，１）　，选择一个随　机　∈　－｛ｘ），并定义　＝（ａ０，ａｌ，…，ａｍ）。ａ０＝　，　对于任意ｉ∈［ｍ】，如果Ｙｆ＝１，Ｃｌｉ：　，其他情况下，　＝Ｓ。这个混淆器的输出是：　０　’（　）＝ｃ（Ｄ（　），Ｄ（　），…，ｏ（ｃ￣ｍ））　其中，Ｃ是一个回路。在输入ｚ时，ｃ首先检测ａ０＝ｚ　是否成立，如果不成立，则返回上；如果发现所有其　他坐标都为ｃｔｉ＝ｚ，则输出ＹｌＹ２…　，其中，ＹＪ＝１；　其他情况则输出０　Ｊ。　命题如果０是一个ｆ　＋１）．可组合点混淆器，然　后Ｄｌ驯（已经由定义构造出）是一个对于ｍ－比特点回　路的虚拟黑盒混淆器。此外，对于任意的分解性能　＋１＝，×ｆｍ。＋１）０ｆ　’）是一个虚拟灰盒的，－可组合　的多比特的点回路混淆器。　本文利用此混淆器的优点【４Ｊ，将其与带密钥的　Ｈａｓｈ函数相结合，得到一种新的消息认证码。　４基于多比特输出点函数混淆器的ＭＡＣ　传统方法构造的ＭＡＣ实质上是将消息ｍ和双方　共享的密钥值ｋ作为输入函数，如果将函数值记为　ＭＡ　（ｍ），这个函数值就是一个认证标记，一般用　表示。而基于带密钥的Ｈａｓｈ函数设计ＭＡＣ【Ｊ　的基本　思路是：利用Ｈａｓｈ函数能把较长的消息变换成较短　的消息摘要并且具有抵抗碰撞等良好的性质，通过在　函数中加入密钥，保证消息的完整性，然后对Ｈａｓｈ　函数和密钥做特殊构造后作为消息认证码。　本文将上述设计中的Ｈａｓｈ函数和密钥以及多比　特可组合虚拟灰盒的点混淆器相结合，从而构造出一　个基于多比特输出点函数混淆器的ＭＡＣ。　本文构造ＭＡＣ的思路如下：先把消息利用带密　钥的Ｈａｓｈ函数进行处理，随后产生的结果通过多比　特输出点函数混淆器进行混淆，使结果难以识别，最　后把混淆后的结果再一次通过带密钥的Ｈａｓｈ函数进　行处理。假定（　，　，Ｋ，Ｇ）和（Ｃ，Ｄ　Ｌ，　）是Ｈａｓｈ族，　ｆ　，Ｃ，Ｏ）是混淆器族。这些Ｈａｓｈ族与混淆器族复合　成为（　，Ｄ，Ｍ，ＧｏＯｏＨ），其中，Ｍ＝ＫｘＬ。　构造方法具体如下：　（１）基于密钥的Ｈａｓｈ函数经过特殊的构造可得：　ｂ＝ｇ　（ａ）　其中，ｂ∈　；ａ∈　；ｇ∈Ｇ；ｋ∈Ｋ。　（２）对第（１）步产生的结果ｂ，在多比特输出点函数　混淆器下进行混淆：　Ｃ＝ｏ（ｂ）　其中，ｂ∈Ｂ；Ｃ∈ｃ；Ｏ∈Ｏ。　（３）对上一步结果通过第２个Ｈａｓｈ族处理得：　ｄ＝　（ｃ）　其中，ｄ∈Ｄ；ＣＥ　ｃ；ｈ∈　；，∈Ｌ。　根据以上３步的综合结果为：　ｄ＝（ｇ。０。　）　（口）＝ｈｔ（Ｏ（ｇｋ（　）））　在这个结构中，ａ是任意输入长度的消息；Ｃ、Ｄ　是使ｌＣｌ≥ＩＤｌ的有限集；Ａ是有限或者无限的集合，　如果　是有限的，则有　≥ＪＢＩ；ｋ和，是一定长度的　密钥；ｂ＝ｇ　（ａ）是基于带密钥Ｈａｓｈ函数的一种特殊　构造算法；Ｄ　Ｊ是　一比特输出点函数混淆器。由　第（３）步中得到的认证标记ｄ＝ｈｔ（ｏ（ｇ　（口）））产生一　

计算机工程　２０１３年１月１５日　个二元有效对（口，ｄ）。对于第（１）步和第（３）步中的Ｈａｓｈ　函数，因为各个Ｈａｓｈ函数都具有自身的优点，所以　最好使用２种不同的函数。如果这２个Ｈａｓｈ族和多　比特输出点函数混淆器族是在满足合理的安全要求　的情况下构造的，则可以保证本文构造的ＭＡＣ是安　全的。　下面以ＨＭＡＣ（Ｈａｓｈ　Ｍｅｓｓａｇｅ　Ａｕｔｈｅｎｔｉｃａｔｉｏｎ　Ｃｏｄｅ）为例进行改进，改进思路是在２个Ｈａｓｈ函数族　之间添加一个多比特输出点函数混淆器。以下将对该　构造方法进行描述：　构造方法的表达式如下：　ＭＡＣ＝　ＨＩ（Ｋ　。　）ＩｌＤｌ　Ｈｌ（Ｋ　④　ｄ）ｌｌＭ…　算法的运行过程描述如下：　（１）对　左填充０以产生一个ｂ比特长的　（例如　的长为２５６比特，ｂ＝５１２，则需填充３２个零字节　０ｘ００）。　（２）　与ｉｐａｄ逐一比特异或，以产生ｂ比特长的　分组　。　（３）将　链接到　之后。　（４）对第（３）步产生的数据流做Ｈａｓｈ函数运算。　（５）对第（４）步得到的数据流，利用此混淆器Ｏ进　行混淆。　（６）Ｋ　与ｏｐａｄ逐一比特异或，以产生ｂ比特的分　组　。　（７）将第（５）步得到的混淆值链接在　后。　（８）将Ｈａｓｈ作用于第（７）步产生的数据流并输出最　终的结果。　注意，Ｋ　与ｉｐａｄ逐比特异或和与ｏｐａｄ逐比特异　或的结果是将　中的一半，然后比特取反，但是取反　２次的比特的位置不同。而Ｓｉ和　通过杂凑函数中压　缩函数的处理，相当于以伪随机方式由　产生了２　个密钥。该算法避免了ＭＡＣ的安全性只归结到所使　用的Ｈａｓｈ函数上，也依赖于混淆器的安全性。这样　可以显著增强ＭＡＣ的安全性。　目前通常是在传输消息后，并在此消息后附加关　于此消息通过ＭＡＣ构造的认证标记，一般一方传给　另一方的是（　，　），然后另一方根据这一消息使用　ＭＡＣ算法和共享密钥ｋ计算出的结果来判断消息是　否被篡改。而本文构造ＭＡＣ的方法能够更加可靠地　保证一方发送的数据能被另一方验证其真伪性，方法　如下：首先网络通信的双方之间秘密共享一对密钥　（　，ｆ），在通信时，参加通信的一个实体向参加通信　的另一个实体发送一个消息ａ，并将此消息使用ＭＡＣ　算法和以上秘密共享的一对密钥（　，，）计算出一个　值，这个值就是认证标记ｄ，然后将这个值附加在消　息ａ之后传送给另一个实体。另一个实体在接收到该　消息后使用同样的方法计算出接收消息的认证标记，　并和他接收到的认证标记作比较：如果计算的认证标　记和接收到的认证标记相同，则认为消息ａ在由对方　传送到自己的过程中没有被篡改；如果不同，就认为　消息在传送过程中被修改了。　５安全性分析　对于以上构造出的消息认证方法安全性分析，可　以分成４步：　（１）对最里层带密钥的Ｈａｓｈ函数的安全性分析。　（２）对　．比特输出点函数混淆器０　Ｊ的安全性　分析。　（３）对最外层带密钥的Ｈａｓｈ函数的安全性分析。　（４）对此认证的组合构造方法的安全性分析。　第（１）步和第（３）步都可以归结为对带密钥的Ｈａｓｈ　函数的安全性分析。　５．１带密钥的Ｈａｓｈ函数安全性分析　假设给定一个固定的（未知的）密钥，（　，　，　，Ｇ）　是碰撞稳定的，给定一个固定的（未知的）密钥，作为　ＭＡＣ，ｆＣ，Ｄ，Ｌ，Ｈ）安全的。这一步的安全性主要依　赖于Ｈａｓｈ函数和它经过的特殊构造。　Ｈａｓｈ函数的优点包括：　（１）Ｈａｓｈ函数可以将任意长度的消息压缩为某一　固定长度的消息摘要的函数。　（２）Ｈａｓｈ函数具有抵抗碰撞的良好性质，从而可　以抵抗敌手的伪造攻击。　（３）具有迭代结构的Ｈａｓｈ函数（如ＭＤ５、ＳＨＡ）可　以反复使用压缩函数将长消息映射为短消息，这样也　可以加固经过Ｈａｓｈ函数处理的消息的完整性。　（４）免费性，即Ｈａｓｈ函数不受法律限制，可以免　费使用。　（５）黑盒性，即可以将底层的Ｈａｓｈ函数看成是一　个模块，根据需要随时方便地进行更换。　带密钥的Ｈａｓｈ函数与不带密钥的Ｈａｓｈ函数在保　证数据完整性方面的区别如下：　（１）使用不带密钥的Ｈａｓｈ函数时，消息摘要必须　被安全存放，不能被篡改。　（２）如果由通信双方来确定所使用的Ｈａｓｈ函数，　他们可以在不安全的信道中同时传送消息和认证　标签。　由此可知，在目前的网络通信中，通信双方往往　处于不安全的信道上，基于带密钥的Ｈａｓｈ函数所构　建的ＭＡＣ更实用。而且在软件实现中，这种ＭＡＣ　

第３９卷第１期　龚高翔，袁征，李超：基于多比特输出点函数混淆器的消息认证码　１４７　比使用分组密码构造的ＭＡＣ运行速度快，效率特　别高。　加密特性以及对称加密自身的特征、性能，将３层组　合构造方法的安全性分析转化为２层组合构造方法的　安全性分析。　由于，ｚ－比特输出点函数混淆器Ｄ　Ｊ具有对称加　５．２　－比特输出点西数混淆器安全性分析　这一步的安全性主要依赖于混淆器的安全性，因　此，下面主要从４个方面分析，ｚ－比特输出点函数混淆　器Ｄ　Ｊ的安全性：　密的功能，因此对称加密的加解密使用相同的算法，　（１）由于混淆后的函数难以识别，这给敌手攻击增　加了难度，因此该混淆器可以增强安全性。　（２）虚拟灰盒混淆虽然允许有无限的计算能力，但　对称加密算法具有公开、计算量小、加密速度快、加　密效率高等优点，在此３层构造方法中，此混淆器进　行的操作只是把Ｂ通过混淆器混淆转化为Ｃ：　Ｃ＝ｏ（ｂ），其中，ｂ∈　ｃ∈ｃ；０∈０。在整个结构中　只是把　转化为ｃ，而且对称加密自身具有效率高和　是限制了预言机的访问次数，从而保证了混淆的安　全性。　（３）可组合混淆可以同时对多个回路进行串行作　用，这样可以大大提高在ＭＡＣ构造中的运行速度，　从而为另一实体验证消息的真伪性节约时间，因此，　该混淆器具有快速性。　（４）在文献［４・５］中，多比特输出点函数混淆暗示了　非常强的对称加密，对于密钥依赖消息和随机弱密钥　是安全的。　以上，？－比特输出点函数混淆器　到对称加密　的表示如下：　（ｍ）＝０　Ｊ（　卅）　（ｃ）＝ｃ（七）　其中，Ｃ为一个多比特点回路，以及ｋ属于密钥空间　的一个密钥。　文献［６】给出了关于两者关系的定理：　（１）对于独立消息，存在一个具有　（　１．熵安全的　ＭＢＰＦ（Ｍｕｌｔｉ－ｂｉｔ　Ｐｏｉｎｔ　Ｆｕｎｃｔｉｏｎ）混淆器，其充分必要条　件是对于ｔｚ（ｎ）一弱密钥，存在具有错误密钥检测的语　义安全对称加密方案。　（２）对于独立消息，存在一个具有　（　）．熵安全的　自我可组合的ＭＢＰＦ混淆器，其充分必要条件是对于　（　）－弱密钥，存在ＣＰＡ（Ｃｈｏｓｅｎ　Ｐｌａｉｎ　Ａｔｔａｃｋ）安全加　密方案和具有错误密钥检测性能。　（３）对于独立消息的标准概念，存在具有　（即）－　熵安全的ＭＢＰＦ混淆器，其充分必要条件是存在具有　（　）・弱密钥和错误密钥检测性能的语义安全的　ＫＤＭ（Ｋｅｙ　Ｄｅｐｅｎｄｅｎｔ　Ｍｅｓｓａｇｅ）］Ｊ１］密方案。　文献［６］还将上述定理扩展应用到多比特输出点　函数混淆器中，保证了这类混淆器的安全性。　定理１对于ｍ・比特点回路，０是一个多比特输　出点函数混淆器，则加密方案（Ｅ０，Ｄ０１是（ｍ，ｔ）．多密　钥消息安全的　Ｊ。　５．３　消息认证的组合构造方法安全性分析　下面利用多比特输出点函数混淆器具有的对称　速度快的优点，所以，此混淆器对于整个构造的安全　性影响很小，可以忽略不计。因此，这里只须考虑　２个带密钥的Ｈａｓｈ函数进行嵌套的安全性分析　Ｊ。　忽略此混淆器在整个组合构造中的影响，此组合　构造在本质上是一个嵌套ＭＡＣ，即如果嵌套ＭＡＣ　满足如下２个条件，则嵌套ＭＡＣ是安全的：　（１）给定一个固定的（未知的）密钥（Ｃ，Ｄ，Ｌ，　），其　作为ＭＡＣ是安全的。　（２）给定固定的（未知的）密钥（Ａ，Ｂ，Ｋ，Ｇ），其是碰　撞稳定的。　下面对嵌套ＭＡＣ、外层ＭＡＣ和当密钥保密时对　Ｈａｓｈ族的碰撞３种Ｈａｓｈ族的某些攻击的相对难度进　行比较，由此证明该构造的安全性。　由于概率至少为　，因此嵌套ＭＡＣ最多向嵌套　预言机查询ｑ次后就能输出有效的二元对（　，Ｚ）。设　Ｘ１，　２，…，　为攻击者查询，Ｚ１，ｚ２，…，　为预言机做出　的响应应答。在攻击者执行完查询后，可以得到有效　二元对（Ｘ１，　），（　，ｚ２），…，（　，Ｚｑ）以及可能的有效二　元对（　，Ｚ）。假定现在取出Ｘ１，Ｘ２，…，　和　，向Ｈａｓｈ　预言机做ｑ＋１次查询，从而有：　．ｙ１＝　（Ｘ１）　Ｙ２＝ｇｋ（　）　Ｙｑ＝ｇｋ（Ｘｑ）　Ｙ＝ｇｋ（　）　如果　∈｛Ｙｌ，．ｙ２，…，Ｙｑ｝，例如　＝Ｙｉ，则有一对　，Ｘ，成为碰撞的解。这是一次成功的未知密钥碰撞攻　击。如果　｛Ｙｌ，Ｙ２，…，Ｙｑ｝，则可以输出二元对（Ｊ，，ｚ），　这可能是外层ＭＡＣ的有效对。从ｑ个外层ＭＡＣ查　询中得到ｑ个响应回答，也就是（　１，ｚ　），　（Ｙ２，Ｚ２），…，Ｙｑ，Ｚｑ）可构成一个假冒。假定任何未知密　钥的碰撞攻击最多有　的成功率，而嵌套ＭＡＣ攻击　者至少有￡的成功率，则（　，ｚ）为有效二元对，并且　

１４８　计算机工程　２０１３年１月１５　Ｅｔ　因为　｛Ｙｌ，Ｙ２，…，Ｙｇ｝的概率至少是　一　，任何外层　ＭＡＣ攻击成功的概率最多是￡７，而上述外层ＭＡＣ　攻击成功的概率至少是￡一ｅｌ，所以有ｓ≤ｅｌ＋ｅ２。　［２】Ｂａｒａｋ　Ｂ，Ｇｏｌｄｒｅｉｃｈ　Ｏ，Ｉｍｐａｇｌｉａｚｚｏ　Ｒ，ｅｔ　ａ１．Ｏｎ　ｔｈｅ　（Ｉｍ）ｐｏｓｓｉｂｉｌｉｔｙ　ｏｆ　Ｏｂｆｕｓｃａｔｉｎｇ　Ｐｒｏｇｒａｍ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ＣＲＹＰＴＯ’０１．［Ｓ．１．］：Ｓｐｒｉｎｇｅｒ，２００１：１－１８．　［３］　Ｃａｎｅ￣ｉ　Ｒ，Ｄａｋｄｏｕｋ　Ｒ　Ｒ．Ｏｂｆｕｓｃａｔｉｎｇ　Ｐｏｉｎｔ　Ｆｕｎｃｔｉｏｎｓ　ｗｉｔｈ　Ｍｕｌｔｉｂｉｔ　Ｏｕｔｐｕｔ［Ｃ］／／Ｐｒｏｃ．ｏｆＥＵＲＯＣＲＹＰＴ’０８－［Ｓ．１．］：　Ｓｐｒｉｎｇｅｒ，２００８：４８９－５０８．　定理２对于上述嵌套ＭＡＣ，若　是保密的，假　定随机选择的ｇ　∈Ｇ不存在（ｑ，ｇ＋１）－碰撞攻击，随　机选择的ｈＬ∈Ｈ不存在（　，ｑ）一假冒（其中，￡是保密　的），并且随机选择的（ｇ。　）ｒ　１∈Ｇ。　对于嵌套　…一，　［４　Ｂｉ４］ｔａｎｓｋｙ　Ｎ，Ｃａｎｅ￣ｉ　Ｒ．Ｏｎ　Ｓｔｒｏｎｇ　Ｓｉｍｕｌａｔｉｏｎ　ａｎｄ　Ｃｏｍｐｏｓａｂｌｅ　Ｐｏｉｎｔ　Ｏｂｆｕｓｃａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ｔｈｅ　３０ｔｈ　Ａｎｎｕａｌ　Ｃｒｙｐｔｏｌｏｇｙ　Ｃｏｎｆｅｒｅｎｃｅ．Ｓａｎｔａ　Ｂａｒｂａｒａ，ＵＳＡ：　ＭＡＣ存在（￡，ｇ）一假冒，则Ｅ≤Ｅ１＋￡２。与最里层的　Ｈａｓｈ函数相比，可以保持嵌套Ｈａｓｈ函数的最初性能，　【Ｓ．ｎ．】，２０１０：５２０－５３７．　［５］Ｈａｉｔｎｅｒ　Ｉ，Ｈｏｌｅｎｓｔｅｉｎ　Ｏｎ　ｔｈｅ（Ｉｍ）ｐｏｓｓｉｂｉｌｉｔｙ　ｏｆ　Ｋｅｙ　不会因为嵌套以及混淆器在一起作用而降低Ｈａｓｈ函　数的性能。　带密钥的Ｈａｓｈ函数的构造等同于一个ＭＡＣ的　构造，ＨＭＡＣ、ＵＭＡＣ等嵌套ＭＡＣ构造方法都给出　了安全性证明，具体见文献［９．１０］。　Ｄｅｐｅｎｄｅｎｔ　Ｅｎｃｒｙｐｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ＴＣＣ’０９．［Ｓ．１．］：　Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２００９：２０２－２１９．　［６］　Ｃａｎｅｔｔｉ　Ｒ，Ｋａｌａｉ　Ｙ　Ｔ’Ｖａｒｉａ　Ｍ，ｅｔ　ａ１．Ｏｎ　Ｓｙｍｍｅｔｒｉｃ　Ｅｎｃｒｙｐｔｉｏｎ　ａｎｄ　Ｐｏｉｎｔ　Ｏｂｆｕｓｃａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ＴＣＣ’１０．　Ｈｅｉｄｅｌｂｅｒｇ，Ｇｅｒｍａｎｙ：Ｓｐｒｉｎｇｅｒ，２０１　０．　６结束语　目前构造出的ＭＡＣ其安全性主要依赖于底层的　Ｈａｓｈ函数，而所使用的Ｈａｓｈ函数中有些没有安全性　证明，因此，不能保证ＭＡＣ的安全。为此，本文利　【７］Ｂｉｔａｎｓｋｙ　Ｎ，Ｃａｎｅｔｔｉ　Ｒ．Ｏｎ　Ｓｔｒｏｎｇ　Ｓｉｍｕｌａｔｉｏｎ　ａｎｄ　Ｃｏｍｐｏｓａｂｌｅ　Ｐｏｉｎｔ　Ｏｂｆｕｓｃａｔｉｏｎ［ＥＢ／ＯＬ］．［２０１　１－１０—２０１．　ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ．　用多比特输出点函数混淆器，提出一种构造ＭＡＣ的　新方法。该混淆器不仅可以提高ＭＡＣ的运行速度，　［８］Ｓｔｉｎｓｏｎ　Ｄ　Ｒ．密码学原理与实践［Ｍ］．冯登国，译．北京：　电子工业出版社，２００３．　［９］　Ｂｌａｃｋ　Ｊ，Ｈａｌｅｖｉ　Ｓ，Ｋｒａｗｃｚｙｋ　Ｈ，ｅｔ　ａ１．ＵＭＡＣ：Ｆａｓｔ　ａｎｄ　Ｓｅｃｕｒｅ　Ｍｅｓｓａｇｅ　Ａｕｔｈｅｎｔｉｃａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ＣＲＹＰＴＯ’９９．　Ｈｅｉｄｅｌｂｅｒｇ，Ｇｅｒｍａｎｙ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，１９９９：２１６—２４５．　与基于带密钥的Ｈａｓｈ函数构造的ＭＡＣ相比，还进　一步保证了安全性。　参考文献　［１０】于洪波．杂凑函数以及ＨＭＡＣ／ＮＭＡＣ的安全性分析［Ｄ】．　济南：山东大学，２００７．　编辑张帆　【１］王大印，林东岱，吴文玲．消息认证码研究［Ｊ］．通讯和　计算机，２００５，２（１０）：７６．８０．　（上接第１４３页）　【３】Ｔａｎ　Ｚｕｏｗｅｎ．Ａｎ　Ｅｎｈａｎｃｅｄ　Ｔｈｒｅｅ－ｐａｒｔｙ　Ａｕｔｈｅｎｔｉｃａｔｉｏｎ　Ｋｅｙ　Ｅｘｃｈａｎｇｅ　Ｐｒｏｔｏｃｏｌ　ｆｏｒ　Ｍｏｂｉｌｅ　Ｃｏｍｍｅｒｃｅ　【７】Ｚｈａｏ　Ｊｉａｎｊｉｅ，Ｇｕ　Ｄａｗｕ．Ｐｒｏｖａｂｌｙ　Ｓｅｃｕｒｅ　Ｔｈｒｅｅ—ｐａｒｔｙ　Ｐａｓｓｗｏｒｄ—ｂａｓｅｄ　Ａｕｔｈｅｎｔｉｃａｔｅｄ　Ｋｅｙ　Ｅｘｃｈａｎｇｅ　Ｐｒｏｔｏｃｏｌ［Ｊ］．　Ｅｎｖｉｒｏｎｍｅｎｔｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２０１０，５（５）：　４３６．４４３．　Ｉｎｆｏｒｍ￣ｉｏｎ　Ｓｃｉｅｎｃｅｓ，２０１２，１８４（１）：３１０－３２３．　［８］隋爱芬，杨义先，钮心忻，等．基于椭圆曲线密码的可　Ｓｅｃｕｒｉｔｙ　Ｗｅａｋｎｅｓｓｅｓ　ｏｆ　Ａｕｔｈｅｎｔｉｃａｔｅｄ　Ｋｅｙ　［４］Ｎｏｓｅ　认证密钥协商协议的研究［Ｊ］．北京邮电大学学报，２００４，　２７（３）：２８－３２．　Ａｇｒｅｅｍｅｎｔ　Ｐｒｏｔｏｃｏｌｓ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ　Ｌｅｔｔｅｒｓ，　２０１１，ｌ１１（１４）：６８７—６９６．　【５】Ｔａｎ　Ｚｕｏｗｅｎ．Ａｎ　Ｉｍｐｒｏｖｅｍｅｎｔ　ｏｎ　Ａ　Ｔｈｒｅｅ￣ｐａｒｔｙ　Ａｕｔｈｅｎｔｉｃａｔｉｏｎ　Ｋｅｙ　Ｅｘｃｈａｎｇｅ　Ｐｒｏｔｏｃｏｌ　Ｕｓｉｎｇ　Ｅｌｌｉｐｔｉｃ　［９］Ｃｈａｎｇ　Ｔｉｎｇｙｉ，Ｈｗａｎｇ　Ｍｉｎ－Ｓｈｉａｎｇ，Ｙａｎｇ　Ｗｅｉｐａｎｇ．Ａ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ・－ｅｆｉｃｉｅｎｔ　Ｔｈｆｒｅｅ－・ｐａｒｔｙ　Ｐａｓｓｗｏｒｄ　Ａｕｔｈｅｎｔｉ－－　ｃａｔｅｄ　Ｋｅｙ　Ｅｘｃｈａｎｇｅ　Ｐｒｏｔｏｃｏｌ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅｓ，　２０１１，１８１（１）：２１７－２２６．　Ｃｕｒｖｅ　Ｃｒｙｐｔｏｇｒａｐｈｙ［Ｊ］．　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｎｖｅｒｇｅｎｃｅ　Ｉｎｆｏｒｍ￣ｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ，２０１０，５（４）：１２０—１２１．　［１　０］Ｔａｎ　Ｚｕｏｗｅｎ．Ｅｆｉｃｉｆｅｎｔ　Ｉｄｅｎｔｉｔｙ－ｂａｓｅｄ　Ａｕｔｈｅｎｔｉｃａｔｅｄ　Ｍｕｌｔｉｐｌｅ　Ｋｅｙ　Ｅｘｃｈａｎｇｅ　Ｐｒｏｔｏｃｏｌ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ　ａｎｄ　Ｅｌｅｃｔｒｉｃａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，２０１１，３７（２）：１９１—１９８．　［６］陈建熊，孙乐昌．认证测试对分析重放攻击的缺陷［Ｊ］．　计算机应用研究，２００９，２６（２）：７３９－７４１．　编辑张帆