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 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.     

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.<>     

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.     

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     

A Dichotomy for Local Small-Bias Generators

We consider pseudorandom generators in which each output bit depends on a constant number of input bits. Such generators have appealingly simple structure: They can be described by a sparse input–output dependency graph \(G\) and a small predicate \(P\) that is applied at each output. Following the works of Cryan and Miltersen (MFCS’01) and by Mossel et al (STOC’03), we ask: which graphs and predicates yield “small-bias” generators (that fool linear distinguishers)? We identify an explicit class of degenerate predicates and prove the following. For most graphs, all non-degenerate predicates yield small-bias generators, \(f:\{0,1\}^n \rightarrow \{0,1\}^m\), with output length \(m = n^{1 + \epsilon }\) for some constant \(\epsilon > 0\). Conversely, we show that for most graphs, degenerate predicates are not secure against linear distinguishers, even when the output length is linear \(m=n+\Omega (n)\). Taken together, these results expose a dichotomy: Every predicate is either very hard or very easy, in the sense that it either yields a small-bias generator for almost all graphs or fails to do so for almost all graphs. As a secondary contribution, we attempt to support the view that small-bias is a good measure of pseudorandomness for local functions with large stretch. We do so by demonstrating that resilience to linear distinguishers implies resilience to a larger class of attacks.     

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

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

How to Protect DES Against Exhaustive Key Search (an Analysis of DESX)

The block cipher \DESX is defined by \DESX _k.k1.k2 (x) = k2\xor \DES _k (k1\xor x) , where \xor denotes bitwise exclusive-or. This construction was first suggested by Rivest as a computationally cheap way to protect \DES against exhaustive key-search attacks. This paper proves, in a formal model, that the DESX construction is sound. We show that, when F is an idealized block cipher, \FX _k.k1.k2 (x)=k2\xor F _k (k1\xor x) is substantially more resistant to key search than is F . In fact, our analysis says that \FX has an effective key length of at least κ + n - 1 - \lg m bits, where κ is the key length of F , n is the block length, and m bounds the number of \langle x, \FX _K (x)\rangle pairs the adversary can obtain. Received July 1997 and revised July 2000 Online publication 27 November, 2000     

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

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

Vesta-2M流密码的密码分析

分析了俄国商用密码Vesta-2M流密码的安全性。流密码Vesta-2M的密钥流发生器的初始密钥规模为O(2^536)。本文指出文献[1]中攻击方法的错误，并提出一种已知明文攻击方法，所需明文量很小(约几百比特)，计算复杂度的上界为O(2^372)。     

Bit commitment using pseudorandomness

We show how a pseudorandom generator can provide a bit-commitment protocol. We also analyze the number of bits communicated when parties commit to many bits simultaneously, and show that the assumption of the existence of pseudorandom generators suffices to assure amortized O(1) bits of communication per bit commitment.Part of this work was done while the author was at the University of California at Berkeley. This research was supported by NSF Grant CCR 88-13632.     

High Quality Uniform Random Number Generation Using LUT Optimised State-transition Matrices

This paper presents a family of uniform random number generators designed for efficient implementation in Lookup table (LUT) based FPGA architectures. A generator with a period of 2 ^k  − 1 can be implemented using k flip-flops and k LUTs, and provides k random output bits each cycle. Each generator is based on a binary linear recurrence, with a state-transition matrix designed to make best use of all available LUT inputs in a given FPGA architecture, and to ensure that the critical path between all registers is a single LUT. This class of generator provides a higher sample rate per area than LFSR and Combined Tausworthe generators, and operates at similar or higher clock-rates. The statistical quality of the generators increases with k, and can be used to pass all common empirical tests such as Diehard, Crush and the NIST cryptographic test suite. Theoretical properties such as global equidistribution can also be calculated, and best and average case statistics shown. Due to the large number of random bits generated per cycle these generators can be used as a basis for generators with even higher statistical quality, and an example involving combination through addition is demonstrated.

Source codes as random number generators

A random number generator generates fair coin flips by processing deterministically an arbitrary source of nonideal randomness. An optimal random number generator generates asymptotically fair coin flips from a stationary ergodic source at a rate of bits per source symbol equal to the entropy rate of the source. Since optimal noiseless data compression codes produce incompressible outputs, it is natural to investigate their capabilities as optimal random number generators. We show under general conditions that optimal variable-length source codes asymptotically achieve optimal variable-length random bit generation in a rather strong sense. In particular, we show in what sense the Lempel-Ziv (1978) algorithm can be considered an optimal universal random bit generator from arbitrary stationary ergodic random sources with unknown distributions     

有限域上超椭圆曲线离散对数问题的错误攻击

In this paper, we present two explicit inva-lid-curve attacks on the genus 2 hyperelliptic curve o-ver a finite field. First, we propose two explicit attack models by injecting a one-bit fault in a given divisor. Then, we discuss the construction of an invalid curve based on the faulted divisor. Our attacks are based on the fact that the Hyperelliptic Curve Scalar Multiplica-tion (HECSM) algorithm does not utilize the curve parameters and We consider three hyperelliptic curves as the attack targets. For curve with security level 186 (in bits), our attack method can get the weakest inva-lid curve with security level 42 (in bits); there are 93 invalid curves with security level less than 50. We al-so estimate the theoretical probability of getting a weak hyperelliptic curve whose cardinality is a smooth integer. Finally, we show that the complexity of the fault attack is subexponential if the attacker can freely inject a fault in the input divisor. Cryptosystems based on the genus 2 hyperelliptic curves cannot work against our attack algorithm in practice.     

Inferring sequences produced by a linear congruential generator missing low-order bits

An efficient algorithm is given for inferring sequences produced by linear congruential pseudorandom number generators when some of the low-order bits of the numbers produced are unavailable. These generators have the formX _n=aX _n–1+b (modm). We assume that the constantsa,b, andm are unknown, and thatt=O(log logm) of the low-order bits are not used.This work was supported by an Educational Opportunity Fellowship and by DARPA Grant No. N00039-82-C-0235.     

The Insecurity of the Digital Signature Algorithm with Partially Known Nonces

We present a polynomial-time algorithm that provably recovers the signer's secret DSA key when a few consecutive bits of the random nonces k (used at each signature generation) are known for a number of DSA signatures at most linear in log q (q denoting as usual the small prime of DSA), under a reasonable assumption on the hash function used in DSA. For most significant or least significant bits, the number of required bits is about log ^1/2 q , but can be decreased to log log q with a running time q ^{O(1/log log q )} subexponential in log q , and even further to two in polynomial time if one assumes access to ideal lattice basis reduction, namely an oracle for the lattice closest vector problem for the infinity norm. For arbitrary consecutive bits, the attack requires twice as many bits. All previously known results were only heuristic, including those of Howgrave-Graham and Smart who recently introduced that topic. Our attack is based on a connection with the hidden number problem (HNP) introduced at Crypto '96 by Boneh and Venkatesan in order to study the bit-security of the Diffie—Hellman key exchange. The HNP consists, given a prime number q , of recovering a number α ∈ F _q such that for many known random t ∈ F _q a certain approximation of t α is known. To handle the DSA case, we extend Boneh and Venkatesan's results on the HNP to the case where t has not necessarily perfectly uniform distribution, and establish uniformity statements on the DSA signatures, using exponential sum techniques. The efficiency of our attack has been validated experimentally, and illustrates once again the fact that one should be very cautious with the pseudo-random generation of the nonce within DSA.     

Differential Fault Attack on the Stream Cipher LIZARD

In this paper, we try to give a security evaluation of LIZARD stream cipher in regard to fault attacks, which, to the best of our knowledge, is the first fault analysis on LIZARD. We design a differential engine of LIZARD to track the differential trail of the keystreams. It is shown that the distributions of the keystream differences are heavily biased. Utilizing this characteristic, we propose an improved method to identify the fault location for LIZARD whose success probability approaches 1. Then we use the fault-free keystream and faulty keystreams to generate system of equations in internal state variables and solve it by SAT solver. The result shows that with 100 keystream bits, only 6 different faults are needed to recover the internal state. Finally, the comparison between LIZARD and Grain v1 shows that LIZARD is more resistable than Grain v1 in regard to fault attacks.     

Attacks on Fast Double Block Length Hash Functions

The security of hash functions based on a block cipher with a block length of m bits and a key length of k bits, where , is considered. New attacks are presented on a large class of iterated hash functions with a 2m -bit hash result which processes in each iteration two message blocks using two encryptions. In particular, the attacks break three proposed schemes: Parallel-DM, the PBGV hash function, and the LOKI DBH mode. Received 1 March 1996 and revised 16 December 1996     

On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators

   Abstract. Assuming the intractability of factoring, we show that the output of the exponentiation modulo a composite function f _N,g (x)=g ^x mod N (where N=P⋅ Q ) is pseudorandom, even when its input is restricted to being half the size (i.e. x<

Algebraic nonlinearity and its applications to cryptography

The algebraic nonlinearity of an n-bit boolean function is defined as the degree of the polynomial f(X) Z ₂[x ₁, x ₂,..., x _n] that represents f. We prove that the average degree of an ANF polynomial for an n-bit function is n+o(1). Further, for a balanced n-bit function, any subfunction obtained by holding less than n-[log n]- 1 bits constant is also expected to be nonaffine. A function is partially linear if f(X) has some indeterminates that only occur in terms bounded by degree 1. Boolean functions which can be mapped to partially linear functions via a linear transformation are said to have a linear structure, and are a potentially weak class of functions for cryptography. We prove that the number of n-bit functions that have a linear structure is asymptotic .The author is presently employed by the Distributed System Technology Center, Brisbane, Australia.Project sponsored in part by NSERC operating Grant OGP0121648, and the National Security Agency under Grant Number MDA904-91-H-0012. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation hereon.