A new linear consistency test attack on noised irregularly clocked linear feedback shift registers

Abstract

Linear Consistency Test (LCT) is a widely used algebraic attack against pseudorandom generator schemes. A system of linear equations depending on a guessed part of the key is assigned to the analyzed generator and checked for consistency. If the guessed part of the key is not the right one, the system will be inconsistent with high probability. In the presence of noise, additional measures are necessary for this attack to be successful. They must reduce the influence of intercepted output bits complemented by noise. In this paper, a technique is described that tries to guess which bit(s) of the intercepted output sequence are complemented by noise and remove all the equations from the linear system assigned to the generator that depend on those bits. The technique is demonstrated on cryptanalysis of a Binary Rate Multiplier (BRM). The experiments on this generator show that such an attack is feasible if the noise level is up to moderate.