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)³)     

Cryptanalysis of self-shrinking generator

A simple cryptanalysis of the self-shrinking generator with very short keystream for the case of unknown connection polynomial is provided. The expected complexity of this cryptanalysis is 2/sup 1.5L/ when the length of the LFSR of the generator is L.     

钟控密钥流生成器及其密码性能

提出了一种新的钟控密钥流生成器,由3个移位寄存器组成：两个被钟控的线性反馈移位寄存器A和B,一个提供钟控信息的非线性反馈移位寄存器C。设A、B和C的长度分别为l1、l2和l3。移位寄存器A和B的钟控信息由从移位寄存器C选取的两个比特串提供,移位的次数分别是两个比特串的汉明重量。研究了该生成器的周期、线性复杂度和k错线性复杂度,分析了这种密钥流生成器的安全性。     

On the linear complexity of nonlinearly filtered PN-sequences

Binary sequences of period 2/sup n/-1 generated by a linear feedback shift register (LFSR) whose stages are filtered by a nonlinear function, f, are studied. New iterative formulas are derived for the calculation of the linear complexity of the output sequences. It is shown that these tools provide an efficient mechanism for controlling the linear complexity of the nonlinearly filtered maximal-length sequences.     

A fast algorithm for determining the minimal polynomial where of a sequence with period 2p/sup n/ over GF (q)

A fast algorithm is presented for determining the linear complexity and the minimal polynomial of a sequence with period 2p/sup n/ over GF (q), where p and q are odd prime, and q is a primitive root (mod p/sup 2/). The algorithm uses the fact that in this case the factorization of x/sup 2p(n)/-1 is especially simple.     

Low-complexity finite field multiplier using irreducible trinomials

A low-complexity array multiplier for GF(2/sup m/) fields with an irreducible trinomial X/sup m/+X/sup n/+1 is presented. The space complexity of the proposed multiplier is reduced from order O(m/sup 2/) to O(m) compared with the Lee's array multiplier. The time complexity of the proposed multiplier is about half that of Lee's array multiplier.     

Linear complexity of a type of clock-controlled sequence

A new type of cascaded clock-controlled system is proposed. There are r+1 linear feedback shift registers (LFSRs) of length n in the system if the degree of cascade connection is r. It is proved that for an rth degree cascade the output sequences have linear complexity n Sigma /sub i=0//sup r/ (2/sup n/-1)/sup i/, period (2/sup n/-1)/sup r+1/ and good statistical properties. Such a model can generate key stream sequences of stream ciphers in computer applications.<>     

Simple MAP decoding of first-order Reed-Muller and Hamming codes

A maximum a posteriori (MAP) probability decoder of a block code minimizes the probability of error for each transmitted symbol separately. The standard way of implementing MAP decoding of a linear code is the Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm, which is based on a trellis representation of the code. The complexity of the BCJR algorithm for the first-order Reed-Muller (RM-1) codes and Hamming codes is proportional to n/sup 2/, where n is the code's length. In this correspondence, we present new MAP decoding algorithms for binary and nonbinary RM-1 and Hamming codes. The proposed algorithms have complexities proportional to q/sup 2/n log/sub q/n, where q is the alphabet size. In particular, for the binary codes this yields complexity of order n log n.     

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.     

基于E0算法的猜测决定攻击

对短距离无线蓝牙技术中使用的E0序列密码算法进行了猜测决定攻击,攻击中利用线性逼近的方法做出了一个巧妙的攻击假设,降低了攻击所需的猜测量,并且通过一个检验方程降低了候选状态的数量,攻击的计算复杂度为O(276),需要约988bit密钥流,属于短密钥流攻击.相对于长密钥流攻击,短密钥流攻击所需的密钥流不超过2745bit,对E0的安全性更具威胁.与目前已有的针对E0的短密钥流攻击相比,所提出猜测决定的攻击结果是最好的.     

A new non-orthogonal space-time code with low decoding complexity

A full diversity block space-time code over two transmit antennas and two symbol periods is introduced. In this method, each code is equal to the addition of two matrices; A/sup m/ and DA/sup n/, where A and D are the two constant matrices and m and n are the two data symbols. A is selected such that the set A/sup m/, 0 /spl les/ m /spl les/ 2/sup b/ - 1 is closed under the matrix multiplication. This structure allows a simple maximum likelihood (ML) decoding method, and at the same time, simplifies the optimization of the coding advantage. Simulations show that the performance of the new code is very close to that of the Damen code (M. O. Damen et al., 2002) which is the best known block space-time code in terms of the coding advantage. Moreover, the decoding complexity of the proposed method is significantly lower than that of the Damen code.     

Efficient adaptive algorithms and minimax bounds for zero-delay lossy source coding

Zero-delay lossy source coding schemes are considered for both individual sequences and random sources. Performance is measured by the distortion redundancy, which is defined as the difference between the normalized cumulative mean squared distortion of the scheme and the normalized cumulative distortion of the best scalar quantizer of the same rate that is matched to the entire sequence to be encoded. By improving and generalizing a scheme of Linder and Lugosi, Weissman and Merhav showed the existence of a randomized scheme that, for any bounded individual sequence of length n, achieves a distortion redundancy O(n/sup -1/3/logn). However, both schemes have prohibitive complexity (both space and time), which makes practical implementation infeasible. In this paper, we present an algorithm that computes Weissman and Merhav's scheme efficiently. In particular, we introduce an algorithm with encoding complexity O(n/sup 4/3/) and distortion redundancy O(n/sup -1/3/logn). The complexity can be made linear in the sequence length n at the price of increasing the distortion redundancy to O(n/sup -1/4//spl radic/logn). We also consider the problem of minimax distortion redundancy in zero-delay lossy coding of random sources. By introducing a simplistic scheme and proving a lower bound, we show that for the class of bounded memoryless sources, the minimax expected distortion redundancy is upper and lower bounded by constant multiples of n/sup -1/2/.     

Linear models for a time-variant permutation generator

A keystream generator, known as RC4, consisting of a permutation table that slowly varies in time under the control of itself, is analyzed by the linear model approach. The objective is to find linear relations among the keystream bits that hold with probability different from one half by using the linear sequential circuit approximation method. To estimate the corresponding correlation coefficients, some interesting correlation properties of random Boolean functions are derived. It is thus shown that the second binary derivative of the least significant hit output sequence is correlated to 1 with the correlation coefficient close to 15·2^-3n where n is the variable word size of RC4. The output sequence length required for the linear statistical weakness detection is then around 64ⁿ/225. The result can be used to distinguish RC4 from other keystream generators and to determine the unknown parameter n, as well as for the plaintext uncertainty reduction if n is small     

Key function of normal basis multipliers in GR(2/sup n/)

A new definition of the key function in GF(2/sup n/) is given. Based on this definition, a method to speed up software implementations of the normal basis multiplication is presented. It is also shown that the normal basis with maximum complexity can be used to design low complexity multipliers. In particular, it is shown that the circuit complexity of a type I optimal normal basis multiplier can be further reduced.     

Computing the error linear complexity spectrum of a binary sequence of period 2/sup n/

Binary sequences with high linear complexity are of interest in cryptography. The linear complexity should remain high even when a small number of changes are made to the sequence. The error linear complexity spectrum of a sequence reveals how the linear complexity of the sequence varies as an increasing number of the bits of the sequence are changed. We present an algorithm which computes the error linear complexity for binary sequences of period /spl lscr/=2/sup n/ using O(/spl lscr/(log/spl lscr/)/sup 2/) bit operations. The algorithm generalizes both the Games-Chan (1983) and Stamp-Martin (1993) algorithms, which compute the linear complexity and the k-error linear complexity of a binary sequence of period /spl lscr/=2/sup n/, respectively. We also discuss an application of an extension of our algorithm to decoding a class of linear subcodes of Reed-Muller codes.     

An Efficient State Recovery Attack on the X-FCSR Family of Stream Ciphers

We describe a state recovery attack on the X-FCSR family of stream ciphers. In this attack we analyse each block of output keystream and try to solve for the state. The solver will succeed when a number of state conditions are satisfied. For X-FCSR-256, our best attack has a computational complexity of only 2^4.7 table lookups per block of keystream, with an expected 2^44.3 such blocks before the attack is successful. The precomputational storage requirement is 2³³. For X-FCSR-128, the computational complexity of our best attack is 2^16.3 table lookups per block of keystream, where we expect 2^55.2 output blocks before the attack comes through. The precomputational storage requirement for X-FCSR-128 is 2⁶⁷.     

Floorplanning using a tree representation: a summary

We present an ordered tree (O-tree) structure to represent nonslicing floorplans. The O-tree uses only n (2+[lg n]) bits for a floorplan of n rectangular blocks. We define an admissible placement as a compacted placement in both x and y directions. For each admissible placement, we can find an O-tree representation. We show that the number of possible O-tree combinations is O(n!2/sup 2n-2//n/sup 1.5/). This is very concise compared to a sequence pair representation that has O((n!)/sup 2/) combinations. The approximate ratio of sequence pair and O-tree combinations is O(n/sup 2/(n/4e)/sup n/). The complexity of an O-tree is even smaller than a binary tree structure for a slicing floorplan that has O(n!2/sup 5n-3//n/sup 1.5/) combinations. Given an O-tree, it takes only linear time to construct the placement and its constraint graph. We have developed a deterministic floorplanning algorithm utilizing the structure of O-tree. Empirical results on MCNC (www.mcnc.org) benchmarks show promising performance with average 16% improvement in wire length and 1% less dead space over the previous central processing unit (CPU) intensive cluster refinement method.     

Efficient VLSI digital logarithmic codecs

N bit digital words can be logarithmically encoded and compressed to a word length of (log/sub 2/n+m-1) bit maintaining a relative accuracy of m bit over (n-m) octaves of signal level. A bit-serial VLSI coder is reported, which requires little more than a log/sub 2/n counter and an output register and it has a latency of one wordlength. The bit-parallel coder can be built with less than n/sup 2/ transistors and has less than n/4 gate delays. The decoder has similar properties and it expands the logarithm to an antilogarithm with n bit of dynamic range. Using these codecs, digital multiplication, division, powers and roots are reduced to additions, subtractions and shifts, respectively.<>     

Sphere-packing bounds for convolutional codes

We introduce general sphere-packing bounds for convolutional codes. These improve upon the Heller (1968) bound for high-rate convolutional codes. For example, based on the Heller bound, McEliece (1998) suggested that for a rate (n - 1)/n convolutional code of free distance 5 with /spl nu/ memory elements in its minimal encoder it holds that n /spl les/ 2/sup (/spl nu/+1)/2/. A simple corollary of our bounds shows that in this case, n < 2/sup /spl nu//2/, an improvement by a factor of /spl radic/2. The bound can be further strengthened. Note that the resulting bounds are also highly useful for codes of limited bit-oriented trellis complexity. Moreover, the results can be used in a constructive way in the sense that they can be used to facilitate efficient computer search for codes.     

Fast correlation attacks on Bluetooth combiner

I. Introduction BluetoothTM is a standard for wireless short-range connectivity specified by the BluetoothTMspecial interest group in Ref.[1]. The specificationdefines a stream cipher algorithm E0 to be used forpoint-to-point encryption within the Bluetooth net-work. The main component of the Bluetooth streamcipher algorithm is the keystream generator (Blue-tooth combiner) which is derived from the well-known summation generator with four input LinearFeedback Shift Registers (LFSRs). A…