对Raviyoyla v1的实际伪造攻击  

A Single Query Forgery Attack on Raviyoyla v1

作　　者：姚远[1,2] 张斌[1] 吴文玲[1] 

机构地区：[1]中国科学院软件研究所可信计算与信息保障实验室,北京100190 [2]中国科学院大学,北京100190

出　　处：《计算机学报》2016年第3期478-491,共14页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(2013CB338002)资助~~

摘　　要：随着移动互联网的兴起和大数据时代的来临,人们迫切需要安全高效的认证密码算法.2013年,在NIST的赞助下,Bernstein等人发起了名为CAESAR的认证密码竞选.对竞选算法的安全性评估已成为当前对称密码学研究领域的热点问题.Raviyoyla v1是提交到CAESAR第1轮竞选的候选算法之一.它是建立在eStream计划的候选算法MAG v2的基础上的流密码算法,并采用带密钥的杂凑函数进行认证.虽然设计者声称Raviyoyla v1具有128比特的完整性,但是该文成功地构造了一种针对Raviyoyla v1的实际伪造攻击,从而说明该算法是极不安全的.具体地,通过在明文消息中引入特殊形式的差分,攻击者能够使算法的内部状态在输出认证标签时没有差分.而且,这种差分并不局限于某些具体值,从而可以利用同一个消息得到多个伪造.理论分析表明,该形式的差分有超过0.307 143的概率使得内部状态发生碰撞.因此,平均而言只需要大约3次实验即可成功地进行伪造.特别地,若将差分限定到一些特殊值上,成功概率非常接近于1.单机实验结果显示,攻击者能够在几秒钟之内成功地进行伪造.尽管设计者针对上述攻击提出了一种可能的改进方案,但文章的进一步分析表明改进并不是本质的,修改后的算法仍然不能抵抗基于差分的伪造攻击.针对设计者提出的各种可能的修正,该文都给出了实际可行的攻击.实验证实,这些攻击具有很高的成功概率且在单机上只需花费几秒钟的时间.文章最后列举了所有可能情形下的伪造示例.据我们所知,公开文献中尚无对Raviyoyla v1及其改进版的认证部分的分析,因此该文对CAESAR竞选有重要意义.Raviyoyla vl is an authenticated encryption algorithm submitted for the first round of the CAESAR competition, which is a grand occasion launched in 2013 with the support of NIST to identify efficient, flexible and secure authenticated encryption primitives. Raviyoyla v1 is composed by an additive stream cipher motivated by the eStream candidate MAG v2 and a keyed hash function. While the designer declares 128 bit security for authentication, we propose a method to construct forgeries using a single query in this paper and the complexity is negligible. Indeed, we introduce a differential of a specific form to the public message and try to canceling it before outputting any authenticated tags. Specially, the differential is not restricted to any particular value and thus multiple forgeries may be made through a single query. Our theoretical analysis shows that the probability for a randomly selected differential of our form to be canceled out is at least 0. 307143. Therefore, it is sufficient to have three trials to obtain a forgery. Moreover, the probability can approach one for some specialized values and the attack can be applied successfully within a few seconds based on our experiments on a PC. Furthermore, the revised Raviyoyla vl is vulnerable from our attack as well and we provide several sample forgeries for possible revisions, which are found by negligible time complexity. As far as we know, no cryptanalysis on the authentication part of Raviyoyla vl and its revision has been proposed in public. Therefore, our work is significant for the CAESAR competition.

关 键 词：CAESAR Raviyoyla V1 伪造攻击 差分分析 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]