Correlation properties of a general binary combiner with memory

Correlation properties of a general binary combiner with an arbitrary number M of memory bits are derived and novel design criteria proposed. For any positive integer m, the sum of the squares of the correlation coefficients between all nonzero linear functions of m successive output bits and all linear functions of the corresponding m successive inputs is shown to be dependent upon a particular combiner, unlike the memoryless combiners. The minimum and maximum values of the correlation sum as well as the necessary and sufficient conditions for them to be achieved are determined. It turns out that the security of combiners with memory can be considerably improved if M is not small.An efficient linear sequential circuit approximation (LSCA) method is developed for obtaining output and input linear functions with comparatively large correlation coefficients which is feasible for large M and works for any practical scheme. The method consists in deriving and solving a linear sequential circuit with additional nonbalanced inputs that is based on linear approximations of the output and the component next-state functions. The corresponding correlation attack on combiners with linear feedback shift registers is analyzed and it is shown that every such combiner with or without memory is essentially zero-order correlation immune.A preliminary version of this paper was presented at Eurocrypt '92 and was published in the proceedings. This research was supported in part by the Science Fund of Serbia, Grant #0403, through the Institute of Mathematics, Serbian Academy of Arts and Sciences.     

一类基于时变逻辑的序列发生器

基于带记忆组合逻辑的序列发生器虽然抗传统的相关攻击,但易受线性时序电路逼近攻击.结合表更新的思想,本文给出了一类基于时变逻辑的序列发生器模型,并分析了输入输出间的相关性等密码学性质.许多密码体制都可归于此种模型,该模型对设计序列发生器有借鉴意义.     

前馈网络的信息泄漏与收集

提出了一种攻击单、多输出前馈网络的新方法，该方法的基本思想是利用最大谱原则，充分收集输入信息的线性组合和输出信息的线性组合的相关性，由输出序列构造出与输入序列具有更大相关件的序列，从而达到提高相关分析成功率的目的。文中最后给出了具体的应用实例。     

前馈流密码的相关分析

提出了分析前馈流密码的一种相关攻击方法，此方法的基本思想是利用系统的多路输入信息和输出信息所具有的相关性，由输出序列构造出输入序列具有更大相关性的序列，进而达到有效地求解输入序列的目的。作为这种方法的应用，给出了一个具体的分析实例。     

On identification of certain nonlinear systems (Corresp.)

In the fields of communication and control there sometimes arises the problem of determining the characteristics of a time-invariant system from discrete records of its input and output during a limited interval of time, where the output data are contaminated with random noise. When this system is linear, we can use the convolution sum to obtain a characterization of the output as a linear combination of past inputs. Hill and McMurtry [4] showed that if we choose a Legendre binary noise sequence as input to a linear system, then the least squares approximation to the characterizing coefficients is expressible in a computationally feasible form, even when a large number of coefficients is involved. In this correspondence we characterize a nonlinear system by a generalization of the convolution sum and show that if we choose Golomb's maximal linear recurring binary-noise sequence [2] as input, then the least squares approximation to the characterizing coefficients is expressible in a computationally feasible form. Thus, the maximal linear recurring sequence occupies the same role in investigating certain nonlinear systems that the Legendre sequence occupies in investigating linear systems.     

Edit Probability Correlation Attacks on Stop / Go Clocked Keystream Generators

Abstract. Divide-and-conquer correlation attacks on the alternating step generator, the bilateral stop/ go generator, and the alleged A5 generator are proposed. They are based on appropriately defined edit probabilities incorporating the stop/ go clocking in these generators. Recursive algorithms for the efficient computation of the edit probabilities are derived. It is shown how the edit probabilities can be used to mount statistically optimal correlation attacks on the corresponding subsets of stop/ go clocked shift registers. By using a statistical hypothesis testing method for estimating the underlying false alarm probability, it is argued that the minimum output sequence length required to be known for a successful attack is linear in the total length of the targeted shift registers. This is illustrated by experimental attacks on the alternating step generator and the bilateral stop/ go generator composed of relatively short shift registers.     

具有1比特记忆的组合器的相关性

探讨了具有1比特记忆的组合器的输出序列和输入序列的相关性以及记忆对相关性的影响。     

Conditional correlation attack on combiners with memory

A connection between linear codes and the correlation attack conditioned on the output of binary combiners with memory is established. Using a sort of random coding argument, it is shown that an average combiner with memory is potentially vulnerable to such an attack only if the number of outputs is equal to or greater than the number of inputs. The required computational complexity in the former case is exponentially greater than in the latter case     

混沌序列与一类基于移位寄存器的非线性序列的性能比较

混沌序列与一类基于移位寄存器的非线性序列非线性前馈逻辑(Non-Linear Feed-ForwardLogic,NLFFL)序列都具有非线性、宽带类噪声、大的码族、长的周期且容易产生的特性,通过对它们在产生方式、相关性能、多址性能以及抗相关攻击能力等方面进行分析和仿真研究,说明混沌序列与该类非线性序列在性能上总体相当,但对于短周期序列(N1023),混沌序列的抗相关攻击、抗干扰能力更强,因此更具有实用价值。     

基于回溯法的逆推攻击

该文针对基于乘法电路的前馈序列密码模型的分析问题,在Golic逆推攻击算法的基础上,利用回溯法及前馈函数的输入输出相关性,提出了基于回溯法的逆推攻击算法。在解决了回溯法平均计算复杂性的基础上,给出了基于回溯法的逆推攻击算法的平均计算复杂性。新的逆推攻击算法在存储复杂性和平均计算复杂性方面均优于Golic算法。     

Fast correlation attacks on certain stream ciphers

Suppose that the output of a running key generator employed in a stream cipher is correlated to a linear feedback shift register sequence (LFSR sequence) a with correlation probabilityp>0.5. Then two new correlation attacks (Algorithms A and B) are presented to determine the initial digits of a, provided that the numbert of feedback taps is small (t<10 ifp0.75). The computational complexity of Algorithm A is of orderO(2^ck), wherek denotes the length of the LFSR andc<1 depends on the input parameters of the attack, and Algorithm B is polynomial (in fact, even linear) in the lengthk of the LFSR. These algorithms are much faster than an exhaustive search over all phases of the LFSR, and are demonstrated to be successful against shift registers of considerable lengthk (typically,k=1000). On the other hand, for correlation probabilitiesp0.75 the attacks are proven to be infeasible against long LFSRs if they have a greater number of taps (roughlyk100 andt10).This work was supported in part by GRETAG Ltd., Regensdorf, Switzerland.     

Maximum Correlation Analysis of Nonlinear Combining Functions in Stream Ciphers

The maximum correlation of a Boolean function to all Boolean functions of a subset of its input variables is investigated. A relationship is derived between the maximum correlation and the mutual information between the output of a balanced Boolean function and a subset of its random input variables. For bent functions (which are never balanced), both the mutual information and the maximum correlation are bounded and shown to be small in a strong sense. Received 14 February 1996 and revised 15 January 2000 Online publication 19 May 2000     

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

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

Correlation properties of combiners with memory in stream ciphers

For pseudo-random generators where one or several LFSRs are combined by a memoryless function, it is known that the output sequences are correlated to certain LFSR-sequences whose correlation coefficients c _t satisfy the equation _i c ₂ ⁱ = 1. In this paper it is proved that a corresponding result also holds for generators whose LFSRs are connected to a combiner with memory.If correlation probabilities are conditioned on side information, e.g., on known output digits, it is shown that new or stronger correlations may occur. This is exemplified for the summation cipher with only two LFSRs where such correlations can be exploited in a known plaintext attack. A cryptanalytic algorithm is given which is shown to be successful for LFSRs of considerable length and with arbitrary feedback connection.A preliminary version of this paper was presented at Eurocrypt '90, May 21–24, Århus, Denmark, and has appeared in the proceedings, pp. 204–213.     

A robust O(N log n) algorithm for optimal decoding of first-orderΣ-Δ sequences

An exact recursive formula is derived to describe the structure of an ideal first-order Σ-Δ output sequence as a function of its input. Specifically, it is shown that every Σ-Δ sequence generated by the constant input x∈[0, 1] can be decomposed into a shorter E-A subsequence whose input x'∈[0, 1) may be used to recover that of the original Σ-Δ sequence. This formula is applied to develop an O(N log N) algorithm for decoding an N-length sequence. Without knowledge of the modulator's initial state, it exhibits an average improvement, over all initial states, of 4.2 dB in output signal-to-noise ratio (SNR) compared with a near-optimal linear finite impulse response (FIR) filter. The regularity of the ideal first-order Σ-Δ structure with constant inputs permits the algorithm to be extended to bandlimited and noise-corrupted data. A simple error correction procedure is demonstrated, and it is shown that the recursive algorithm can outperform FIR filters on sequences of length N<64 having input SNRs as low as 30 dB     

Embedding probabilities for the Alternating Step Generator

The edit distance correlation attack on the well- known alternating step generator for stream cipher applications was proposed by Golic and Menicocci. The attack can be successful only if the probability of the zero edit distance, the so-called embedding probability, conditioned on a given segment of the output sequence, decreases with the segment length, and if the decrease is exponential, then the required segment length is linear in the total length of the two linear feedback shift registers involved. The exponential decrease for the maximal value of the embedding probability, regarded as a function of the output segment, was estimated experimentally by Golic and Menicocci. In this paper, by using the connection with the interleaving and decimation operations, the embedding probability is analyzed theoretically. Exponentially small upper bounds on the maximal embedding probability are thus derived. An exact expression for the minimal embedding probability is also determined     

序列密码的复合攻击法

该文针对序列密码,提出了复合攻击的思想,并用相关攻击和求逆攻击复合对前馈网络进行了 分析,理论和实验结果给出了复合攻击法的计算复杂度,并与常用的攻出法进行了比较。     

基于相关攻击的A5/1算法识别

利用相关攻击获得畸变的A5/1序列,再用统计工具对其进行处理可以得出A5/1统计特征,从而找到正确区分A5/1算法输出和伪随机序列的方法。实验验证该方法能有效地将A5/1算法输出和伪随机序列区分开来。     

一种新的GF（q）上的广义自缩生成器

设计了一种新的GF(q)上的广义自缩生成器,该生成器的主要特点在于输出方式不同于原生成器。研究表明生成的大序列族有良好的互相关性、均衡性,并且给出了最小周期的下界。同时也指出该序列有丰富的群结构和线性空间结构。