Synchronization Fault Cryptanalysis for Breaking A5/1
  
  Marcin Gomulkiewicz,  Miroslaw Kutylowski,  Heinrich Theodor Vierhaus   
                             Pawel Wlaz

A5/1 pseudo-random bit generator, known from GSM  networks,  potentially
might  be  used  for  other  purposes,  such  as  secret  hiding  during
cryptographic  hardware  testing,  stream  encryption  in  piconets  and
others.  The  main  advantages  of  A5/1 are low cost and a fixed output
ratio.

We show that a hardware implementation of A5/1 and similar constructions
must  be quite careful. It faces a danger of a new kind of attack, which
significantly reduces possible keyspace, allowing full recovery  of  the
contents  of  the  internal registers of A5/1. We use ``fault analysis''
strategy: we disturb the A5/1 encrypting device (namely, clocking of the
LFSR registers) so it produces an incorrect keystream, and through error
analysis we deduce the state of the  internal  registers.  If  a  secret
material  is  used  to  initialize the generator, like for GSM, this may
enable to recover this secret. The attack is based on unique  properties
of  the  clocking  scheme  used  by  A5/1,  which  is the basic security
component of this construction.

The  computations  that have to be performed in our attack are about 100
times faster than in the cases of the previous fault-less  cryptanalysis
methods.