带记忆组合生成器的代数攻击

文章描述了代数攻击的一般原理和可攻击的流密码类型,针对带记忆非线性组合流密码的代数攻击,基于Courtios等人的工作,给出了一种新的寻找可用于代数攻击的低阶多元方程的方法。     

KeeLoq密码Courtois攻击方法的分析和修正

KeeLoq密码是由Willem Smit设计的分组密码算法,广泛应用于汽车的无线门锁装置。Courtois等人在2007年提出了破译KeeLoq的4种滑动-代数攻击方法,其中第4种滑动-代数攻击方法的计算复杂性最小。本文证明了Courtois的第4种滑动-代数攻击方法的攻击原理是错误的,因而无法实现对KeeLoq的破译。此外,本文还对该方法进行了修正,提出了改进的攻击方法,利用232个已知明文能够以O(248) 次加密的计算复杂性求出KeeLoq密码的密钥,成功率为1。对于KeeLoq密码26％的密钥,其连续64圈圈函数形成的复合函数至少具有两个不动点,此时改进的攻击方法的计算复杂性还可降至O(248) 次加密。     

基于汉明重的LED代数旁路攻击研究

对CHES 2011会议提出的LED轻型分组密码抗代数旁路攻击能力进行了评估。给出了密码算法代数旁路攻击模型及LED密码代数方程表示方法;利用示波器采集微控制器ATMEGA324P上的LED实现功耗泄露,选取功耗特征较为明显的部分泄露点,基于 Pearson 相关系数方法推断加密中间状态汉明重;分别基于可满足性问题、伪布尔优化问题、线性编程问题给出了LED密码和汉明重泄露的3种代数方程表示方法;使用CryptoMinisat和SCIP 2种解析器对建立的代数方程求解恢复密钥,在已知明文、未知明密文、容错等场景下进行了大量的攻击实验。结果表明,LED易遭受代数旁路攻击,一条功耗曲线的1轮汉明重泄露分析即可恢复64 bit完整密钥。     

eSTREAM和流密码分析现状

eSTREAM是继NESSIE之后欧洲启动的一个规模更大,为期4年的信息安全项目。文中通过介绍eSTREAM计划中的流密码征集情况和评测体系,并对征集到的34个侯选流密码算法进行了初步的安全分析总结。介绍了流密码两种典型的攻击类型：代数攻击、相关攻击,目的为引出流密码安全的定义。最后,对流密码发展现状和前景做了较详尽的总结和展望。     

流密码典型分析方法及实例

流密码的设计与分析在现代密码学中占有重要地位。简要介绍了流密码分析的基本原理和模型,主要包括：折中攻击、猜测和决定攻击、相关攻击、最佳仿射攻击、代数攻击和边信道攻击。然后基于Mathematica平台,使用简易密钥流发生器为测试对象,对其中的折中攻击、猜测和决定攻击及相关攻击进行了仿真实现。通过实验,揭示了流密码算法的一个重要设计原则：避免内部状态演变的线性性以及输出序列统计性质的偏向性。最后对流密码分析方法给予了总结和展望。     

PRESENT密码代数故障攻击

提出了一种新的PRESENT密码故障分析方法——代数故障攻击。将代数攻击和故障攻击相结合,首先利用代数攻击方法建立密码算法等效布尔代数方程组;然后通过故障攻击手段获取错误密文信息,并将故障差分和密文差分转化为额外的布尔代数方程组;最后使用CryptoMiniSAT解析器求解方程组恢复密钥。结果表明:在PRESENT-80的第29轮注入宽度为4的故障,故障位置和值未知时,2次故障注入可在50s内恢复64bit后期白化密钥,将PRESENT-80密钥搜索空间降低为216,经1min暴力破解恢复完整主密钥;和现有PRESENT故障攻击相比,该攻击所需样本量是最小的;此外该代数故障分析方法也可为其他分组密码故障分析提供一定思路。     

PRESENT代数故障攻击的改进与评估

提出了一种基于代数分析的PRESENT故障攻击改进方法,将代数分析用于密码和故障方程构建,通过逆向构建加密方程来加快求解速度;提出了一种故障注入后的密钥剩余熵评估方法,可评估不同故障模型下的PRESENT抗故障攻击安全性;最后对智能卡上的8位智能卡上的PRESENT实现进行了时钟毛刺故障注入,最好情况下1次故障注入即可恢复主密钥,这是PRESENT故障攻击在数据复杂度上的最好结果。     

立方攻击成功率分析

在一般随机布尔函数及布尔函数的代数次数或代数标准型项数受限情况下,从理论上分析了立方攻击的成功概率,对立方攻击密码分析方法提供了理论支持。理论结果与对流密码算法Trivium及Grain v1的实验结果是相吻合的。     

扩展的代数侧信道攻击及其应用

Renauld等人提出的代数侧信道攻击是将代数攻击和侧信道攻击结合起来的一种对分组密码的攻击方法.目前的研究主要针对算法的8-bit实现平台,对于更大的如64-bit实现平台,未见文献讨论.为此,本文提出一种扩展的代数侧信道攻击,直接将侧信道信息表示为密钥的显式函数.相比于通常的代数侧信道攻击,所需泄露信息更少.作为应用,给出了对LBlock轻量级分组密码的扩展的代数侧信道攻击,结果如下:对于64-bit平台实现的LBlock,假设其1-3轮输出的Hamming重量可以准确获得,则利用35个已知明文,便可建立关于LBlock 80-bit主密钥的非线性方程组;在普通的PC机上,利用Magma数学软件v2.12-16求Groebner基,1分钟内可以求得80-bit主密钥.这是对LBlock的首个代数侧信道攻击,同时说明Renauld等人给出的对代数侧信道攻击的其中一个防范方法:"将实现方法从8-bit平台转移到更大的设备"是不够的.     

超椭圆曲线离散对数的Weil Descent代数攻击的分析

本文首先介绍了Galbraith的Weil Descent代数攻击方法，然后对定义在GF（q^n)上的形如y^2 xy=f(x)的HCDLP能否用Weil Descent代数方法攻击作了详细讨论，作为例子，研究了GF（4）和GF（8）上的这类曲线。得到结论：（1）Weil Descent代数攻击法只能适用于极少部分这类超椭圆曲线；（2）当亏格或基域增大时，Weil Descent方法攻击成功的概率趋向于0。所以说Weil Descent代数攻击法对建立在GF（2^n)上的这类超椭圆曲线密码体制并没有太大的威胁。     

Some results on the algebraic immunity of Boolean functions

From the motivation of algebraic attacks on stream and block ciphers,the concept of algebraic immunity(AI) of a Boolean function was introduced and studied extensively.High algebraic immunity is a necessary condition for resisting algebraic attacks.In this paper,we give some lower bounds on the algebraic immunity of Boolean functions.The results are applied to give lower bounds on the AI of symmetric Boolean functions and rotation symmetric Boolean functions.Some balanced rotation symmetric Boolean functions with their AI near the maximum possible value「n/2」are constructed.     

一类布尔函数零化子的代数次数

序列密码代数攻击的成效取决于所使用的非线性布尔函数零化子的代数次数,但如何构造一个给定函数的低次数零化子仍是一个难题.本文对张文英等人提出的关于一类布尔函数存在n-k次零化子的结论给出了新的证明,弥补了原文证明不严密的缺陷.     

基于单变量多项式表示的具有最大代数免疫度奇变元函数构造

To protect against algebraic attacks, a high algebraic immunity is now an important criterion for Boolean functions used in stream ciphers. In this paper, a new method based on a univariate polynomial representation of Boolean functions is proposed. The proposed method is used to construct Boolean functions with an odd number of variables and with maximum algebraic immunity. We also discuss the nonlinearity of the constructed functions. Moreover, a lower bound is determined for the number of Boolean functions with maximum algebraic immunity.     

Vectorial Boolean functions and induced algebraic equations

A general mathematical framework behind algebraic cryptanalytic attacks is developed. The framework relates to finding algebraic equations induced by vectorial Boolean functions and, in particular, equations of low algebraic degree. The equations may involve only a subset of input variables and may or may not be conditioned on the values of output variables. In addition, the equations may have a constrained form interesting for the so-called fast algebraic attacks. A possible divide-and-conquer effect is pointed out and the notion of algebraic immunity order, naturally extending the notion of correlation immunity order, is defined. An application of general results to stream ciphers known as combiners with or without memory, with possibly multiple outputs, is studied in particular detail and the concept of divide-and-conquer algebraic attacks is introduced. Special properties of combiners with finite input memory, such as nonlinear filter generators, are also established. It is also pointed out that Groumlbner basis algorithms may be used for finding low-degree induced algebraic equations     

Attacks on Block Ciphers of Low Algebraic Degree

In this paper an attack on block ciphers is introduced, the interpolation attack. This method is useful for attacking ciphers that use simple algebraic functions (in particular quadratic functions) as S-boxes. Also, attacks based on higher-order differentials are introduced. They are special and important cases of the interpolation attacks. The attacks are applied to several block ciphers, the six-round prototype cipher by Nyberg and Knudsen, which is provably secure against ordinary differential cryptanalysis, a modified version of the block cipher SHARK, and a block cipher suggested by Kiefer. Received April 1999 and revised October 2000 Online publication 9 April 2001     

信息反馈流密码体制

传统流密码体制的安全性已越来越严重地受到各种攻击的威胁,对此人们在尽各种努力寻找新型的安全体制。本文发展了早期人们考虑到的信息反馈流密码体制,分析了它们的安全性并指出这种新型流密码的实用价值。初步分析表明,信息反馈流密码体制具有较高的安全性。     

密码学中布尔函数的零化子

布尔函数的零化子与代数攻击息息相关,但是如何构造一个给定函数的低次零化子仍然是一个悬而未决的问题.本文对此问题进行了研究,研究结果表明,如果布尔函数的零点集有一个k维子空间,那么,函数就会有代数次数为n-k的零化子.然而如何找到函数的具有最低代数次数的零化子仍然是一个亟待解决的难题.     

LFCSR:基于FCSR的新密码学部件

为了有效抵抗M Hell与T Johansson对基于带进位反馈移位寄存器（Feedback with carry shift Register,FCSR）的流密码的实时攻击,本文给出了一个使用密码学部件（FCSR）的新方法.在该方法中,只需要将FCSR的有效进位单元的内容与线性反馈移位寄存器（Linear Fedback Shift Regsiters,LFSR）的对应比特进行异或,随后即可执行原FCSR的运算.以新方法得到的组合部件的状态转移函数依然是二次的,因而对代数攻击和相关攻击有天然的免疫性,尤其重要的是理论分析与实验结果表明新的组合部件的所有进位单元的输出序列是独立的,无偏的,具有良好的统计特性,因而可以有效的阻止M Hell与T Johansson对基于FCSR的流密码的实时攻击以及其它类似攻击.