Cryptanalysis of an E0-like Combiner with Memory |
| |
Authors: | Yi Lu Serge Vaudenay |
| |
Affiliation: | (1) School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore, 637616;(2) EPFL, CH-1015 Lausanne, Switzerland |
| |
Abstract: | 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. |
| |
Keywords: | Stream cipher Combiner Bluetooth E0 Correlation |
本文献已被 SpringerLink 等数据库收录! |
|