宋海欣，范修斌，武传坤，冯登国

（1．中国科学院 软件研究所信息安全国家重点实验室，北京 100190；

2．中国科学院 研究生院，北京 100049）

1 引言

在 2009年欧洲密码年会上，Dinur和 Shamir提出了立方攻击（cube attack）[1]的密码分析方法并对流密码算法Trivium[2]进行了分析，立方攻击是一种新型的代数攻击方法，旨在寻找密码算法固有的低次方程以恢复密钥[3～7]或进行区分攻击[8～10]。

一般来讲，密码算法模型如图1所示。对分组密码来讲，密码算法可看作mbit明文与nbit密钥的函数，经过轮函数的迭代过程，产生密文。对流密码来讲，密码算法可看作mbit初始向量IV与nbit密钥的函数，流密码算法设计一般分为初始化过程和密钥流产生过程，很多流密码算法，如Trivium[2]、Grain v1[11]、Mickey[12]、F-FCSR-H[13]等，其初始化过程均采用低次函数迭代一定拍数，使密钥和初始向量达到一定程度的混乱与扩散。无论是流密码算法还是分组密码算法，一般开始随着迭代拍数的增加，密码算法的代数次数和代数标准型(ANF)项数会戏剧性地增加，迭代一定拍数后，密码算法的代数次数和代数标准型项数会达到一个相对稳定且不可预测的状态。

图1 密码算法模型

本文就一般随机布尔函数及布尔函数的代数次数或代数标准型项数受限情况下，从理论上分析了立方攻击的成功概率，设 f (v1,v2, … ,vm,k1, k2,… ,kn)为m个公开变量 ( v1,v2,… ,vm)及n个密钥变量(k1, k2,… ,kn)的布尔函数，证明了以下结论：1）针对一般随机布尔函数进行讨论，立方攻击的成功概论，设随机布尔函数的代数次数至多为s，若代数次数s与极大项(maxterm)[1]的代数次数l满足关系s - l = 1时，立方攻击的成功概率为1；……