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

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

蓝牙组合生成器相关系数的计算方法

蓝牙组合生成器是蓝牙协议中使用的密钥流生成算法,它是一个带4 bit记忆的非线性组合生成器,其输入和输出之间相关系数的表示和计算是一个困难的问题,而这是对这种生成器进行相关性分析和相关攻击的基础.该文对一般的带记忆组合生成器给出了相关系数和条件相关系数的计算公式,该公式易于实现快速计算.基于此公式计算了蓝牙组合生成器的各种相关系数,并列出了部分结果.     

对比特搜索生成器的猜测确定攻击

针对具有低重量反馈多项式的比特搜索生成器(BSG),利用猜测确定攻击的思想提出了一种快速密钥恢复攻击。该算法基于BSG序列的差分构造特点,首先由截获的密钥流恢复出候选差分序列,然后用反馈多项式对候选差分序列进行校验,以此减少需要求解的L维线性方程系统的数量,从而大大减少了算法所需的复杂度。理论分析和仿真结果表明,对于反馈多项式的重量小于10的BSG,该算法明显优于现有的攻击方法。特别地当反馈多项式的重量为3时,该算法能够将最好的攻击结果O(L320.5L)降低到O(L20.5L)。     

对一种基于logistic映射的分组加密机制的分析和改进

对一种改进的混沌分组密码机制分析后发现其本质上是流密码系统,并且密钥流与明文无关.通过选择明文攻击,在很小的计算代价下获得了密钥流.给出了选择明文攻击的算法,并通过实验进行了验证.为克服原加密算法的缺陷,采用密文反馈的形式使密钥流与明文相关.     

针对流密码HC-256’的区分攻击

流密码HC-256’是eSTREAM计划候选密码HC-256的改进算法,至今未见关于HC-256’的安全性分析结果。该文提出了一种针对HC-256’的线性区分攻击,利用不同的非线性函数代替内部状态更新函数来寻找偶数位置上密钥流生成序列的弱点,通过线性逼近HC-256’的内部状态构造区分器。分析结果表明,需要约2 281bit,就能以0.9545的区分优势对密钥流进行区分。同时,该攻击为解决Sekar等人在2009年IWSEC会议上提出的问题进行了有益的探索。     

MIBS-80的13轮不可能差分分析

该文首次对13轮MIBS-80算法进行了不可能差分分析。首先基于MIBS-80中S盒的不可能差分筛选明文对,其次通过第1轮轮密钥与第2轮轮密钥、第1轮轮密钥与第13轮轮密钥之间的制约关系进一步筛选明文对。该文的攻击排除掉的明文对数量是已有的不可能差分攻击排除掉的明文对数量的218.2倍,因而同时降低了攻击的存储复杂度和时间复杂度。此外,该文多次利用查表的方法求出攻击中涉及的密钥,进一步降低了攻击所需的时间复杂度和存储复杂度。最后,该文利用独立的80 bit轮密钥来恢复主密钥,确保得到正确密钥。该文的攻击需要260.1个选择明文,269.5次13轮加密,存储量为271.2个64 bit,该结果优于已有的不可能差分攻击。     

CIKS-128分组算法的相关密钥-差分攻击

分析研究了CIKS-128分组密码算法在相关密钥-差分攻击下的安全性.利用DDP结构和非线性函数的差分信息泄漏规律构造了一条高概率相关密钥-差分特征,并给出攻击算法,恢复出了192bit密钥;在此基础上,对剩余64bit密钥进行穷举攻击,恢复出了算法的全部256bit密钥.攻击所需的计算复杂度为2⁷⁷次CIKS-128算法加密,数据复杂度为2⁷⁷个相关密钥-选择明文,存储复杂度为2^25.4字节存储空间.分析结果表明,CIKS-128算法在相关密钥-差分攻击条件下是不安全的.     

密码算法旁路立方攻击改进与应用

立方攻击的预处理阶段复杂度随输出比特代数次数的增长呈指数级增长,寻找有效立方集合的难度也随之增加。该文对立方攻击中预处理阶段的算法做了改进,在立方集合搜索时,由随机搜索变为带目标的搜索,设计了一个新的目标搜索优化算法,优化了预处理阶段的计算复杂度,进而使离线阶段时间复杂度显著降低。将改进的立方攻击结合旁路方法应用在MIBS分组密码算法上,从旁路攻击的角度分析MIBS的算法特点,在第3轮选择了泄露位置,建立关于初始密钥和输出比特的超定的线性方程组,可以直接恢复33 bit密钥,利用二次检测恢复6 bit密钥。所需选择明文量221.64,时间复杂度225。该结果较现有结果有较大改进,恢复的密钥数增多,在线阶段的时间复杂度降低。     

八维广义同步系统在伪随机数发生器中的应用

该文提出一类4维离散系统。利用系统平衡点处 Jacobi 矩阵的特征值来分析系统在平衡点处的稳定性,建立了一个判别这类系统为周期或混沌的定理。依据该定理构造了一个新的4维离散系统。该系统具有正的Lyapunov指数,数值模拟显示该系统的动力学行为具有混沌特性。结合该系统和系统广义同步定理构造了一个8维广义同步混沌系统。利用该系统构造了一个16 bit混沌伪随机数发生器 (CPRNG),其密钥空间大于21245。利用FIPS 140-2 检测/广义FIPS 140-2检测判别标准分别检测由CPRNG, Narendra RBG, RC4 PRNG和ZUC PRNG生成的1000个长度为20000 bit的密钥流的随机性。检测结果表明,分别有100%/99%, 100%/82.9%, 99.9%/ 98.8%和100%/97.9%密钥流通过FIPS 140-2检测/广义FIPS 140-2 检测标准。数值仿真显示不同密钥流之间有平均50.004%不同码。结果说明设计的伪随机数发生器有好的随机性,可以抵抗穷尽攻击。该文提出的CPRNG为密码安全的研究与发展提供了新的工具。     

LBlock 码的不可能差分密码性能分析

该文分析研究了LBlock分组密码算法的不可能差分性质.基于LBlock算法的轮函数结构和部分密钥分别猜测技术,给出了21轮和22轮的LBlock算法的不可能差分分析方法.攻击21轮LBlock算法所需的数据量约为262,计算量约为262次21轮加密;攻击22轮LBlock算法所需的数据量约为262.5,计算量约为263.5次22轮加密.与已有的结果相比较,分析所需的计算量均有明显的降低,是目前不可能差分分析攻击LBlock的最好结果.     

Faster attack on certain stream ciphers

A number of keystream generators can be attacked by guessing the contents of one shift register and then checking to see whether this guess is consistent with the observed keystream. Where the target register is n bits long, this gives an attack of complexity 2/sup n-0(1)/. A further optimisation is presented which appears to reduce the complexity to about 2/sup n/2/ in many cases of practical interest.<>     

A New Attack on the Filter Generator

The filter generator is an important building block in many stream ciphers. The generator consists of a linear feedback shift register of length n that generates an m-sequence of period 2ⁿ-1 filtered through a Boolean function of degree d that combines bits from the shift register and creates an output bit z_t at any time t. The previous best attacks aimed at reconstructing the initial state from an observed keystream, have essentially reduced the problem to solving a nonlinear system of D=Sigma_i=1 ^d(n/i) equations in n unknowns using techniques based on linear algebra. This attack needs about D bits of keystream and the system can be solved in complexity O(D^omega), where omega can be taken to be Strassen's reduction exponent omega=log₂(7)ap2.807. This paper describes a new algorithm that recovers the initial state of most filter generators after observing O(D) keystream bits with complexity O((D-n)/2)apO(D), after a pre-computation with complexity O(D(log₂D)³)     

Collision analysis of the GMR-2 cipher used in the satellite phone

A collision property analysis of the GMR-2 cipher used in the satellite phone was presented.By using the F-component as a bridge,the link between the difference of the key byte and the collision of the output ofFas well as the link between the collision of the output of F and the collision of keystream byte were analyzed,which finally revealed the relationship between the difference of the original key byte and the keystream collision.The theoretical analysis showed that for a random frame number,a special chosen key pair could lead to a keystream collision with a high probability,when the key pair has only one byte difference in which the most significant 4 bit of the difference was equal to the last significant 4 bit.The experimental result shows that the keystream collision probability is 2^?8.248,which is far higher than the ideal collision probability 2^?120.This proves once again,that there exists serious potential security hazards in the GMR-2 cipher.     

A Linear Distinguishing Attack on Scream

A linear distinguishing attack on the stream cipher Scream is proposed. When the keystream is of length 2⁹⁸ words, the distinguisher has a detectable advantage. When the keystream length is around 2¹²⁰ the advantage is very close to 1. This shows certain weaknesses of Scream. In the process, the paper introduces new general ideas on how to improve the performance of linear distinguishing attacks on stream ciphers.     

On the Existence of Secure Keystream Generators

Designers of stream ciphers have generally used ad hoc methods to build systems that are secure against known attacks. There is often a sense that this is the best that can be done, that any system will eventually fall to a practical attack. In this paper we show that there are families of keystream generators that resist all possible attacks of a very general type in which a small number of known bits of a keystream are used to synthesize a generator of the keystream (called a synthesizing algorithm). Such attacks are exemplified by the Berlekamp—Massey attack. We first formalize the notions of a family of finite keystream generators and of a synthesizing algorithm. We then show that for any function h(n) that is in \cal O (2 ^n/d ) for every d>0 , there is a family \cal B of periodic sequences such that any efficient synthesizing algorithm outputs a generator of size h(log (\mathop \rm per \nolimits(B))) given the required number of bits of a sequence B∈ \cal B of large enough period. This result is tight in the sense that it fails for any faster growing function h(n) . We also consider several variations on this scenario. Received July 1996 and revised April 2000 Online publication 27 November, 2000     

Shorter bit sequence is enough to break stream cipher LILI-128

LILI-128 is the stream cipher proposed as a candidate cipher for the New European Schemes for Signatures, Integrity, and Encryption (NESSIE) Project. Some methods of breaking it more efficiently than an exhaustive search for its secret key have been found already. The authors propose a new method, which uses shorter bit sequence to break LILI-128 successfully. An attack that can be made with less data can be a more practical threat. With only 2/sup 7/ bits of keystream, this method can break LILI-128 successfully. The efficiency of our attack depends on the memory size. For example, with 2/sup 99.1/ computations, our attack breaks LILI-128, if 2/sup 28.6/-bit memory is available.     

Cryptanalysis of an E0-like Combiner with Memory

In this paper, we study an E0-like combiner with memory as the keystream generator. First, we formulate a systematic and simple method to compute correlations of the FSM output sequences (up to certain bits). An upper bound of the correlations is given, which is useful to the designer. Second, we show how to build either a uni-bias-based or multi-bias-based distinguisher to distinguish the keystream produced by the combiner from a truly random sequence, once correlations are found. The data complexity of both distinguishers is carefully analyzed for performance comparison. We show that the multi-bias-based distinguisher outperforms the uni-bias-based distinguisher only when the patterns of the largest biases are linearly dependent. The keystream distinguisher is then upgraded for use in the key-recovery attack. The latter actually reduces to the well-known Maximum Likelihood Decoding (MLD) problem given the keystream long enough. We devise an algorithm based on Fast Walsh Transform (FWT) to solve the MLD problem for any linear code with dimension L and length n within time O(n+L⋅2 ^L ). Meanwhile, we summarize a design criterion for our E0-like combiner with memory to resist the proposed attacks.     

(Non-)Random Sequences from (Non-)Random Permutations—Analysis of RC4 Stream Cipher

RC4 has been the most popular stream cipher in the history of symmetric key cryptography. Its internal state contains a permutation over all possible bytes from 0 to 255, and it attempts to generate a pseudo-random sequence of bytes (called keystream) by extracting elements of this permutation. Over the last twenty years, numerous cryptanalytic results on RC4 stream cipher have been published, many of which are based on non-random (biased) events involving the secret key, the state variables, and the keystream of the cipher. Though biases based on the secret key are common in RC4 literature, none of the existing ones depends on the length of the secret key. In the first part of this paper, we investigate the effect of RC4 keylength on its keystream, and report significant biases involving the length of the secret key. In the process, we prove the two known empirical biases that were experimentally reported and used in recent attacks against WEP and WPA by Sepehrdad, Vaudenay and Vuagnoux in EUROCRYPT 2011. After our current work, there remains no bias in the literature of WEP and WPA attacks without a proof. In the second part of the paper, we present theoretical proofs of some significant initial-round empirical biases observed by Sepehrdad, Vaudenay and Vuagnoux in SAC 2010. In the third part, we present the derivation of the complete probability distribution of the first byte of RC4 keystream, a problem left open for a decade since the observation by Mironov in CRYPTO 2002. Further, the existence of positive biases towards zero for all the initial bytes 3 to 255 is proved and exploited towards a generalized broadcast attack on RC4. We also investigate for long-term non-randomness in the keystream, and prove a new long-term bias of RC4.     

Protecting poorly chosen secrets from guessing attacks

In a security system that allows people to choose their own passwords, people tend to choose passwords that can be easily guessed. This weakness exists in practically all widely used systems. Instead of forcing users to choose secrets that are likely to be difficult for them to remember, solutions that maintain user convenience and a high level of security at the same time are proposed. The basic idea is to ensure that data available to the attacker is sufficiently unpredictable to prevent an offline verification of whether a guess is successful or not. Common forms of guessing attacks are examined, examples of cryptographic protocols that are immune to such attacks are developed, and a systematic way to examine protocols to detect vulnerabilities to such attacks is suggested