Reconstruction of clock sequences in irregularly clocked pseudorandom sequence generators

Abstract

Flytchiffer som benytter irregulært klokkede Linear Feedback Shift Registre (LFSR) som kombineres i en ikke-lineær boolsk funksjon er mye brukt siden disse produserer sekvenser med veldig lange perioder, høy lineær kompleksitet og gode statistiske egenskaper.

Det er derimot kjent at slike chiffer kan knekkes ved bruk av det såkalte “Generalised correlation”-angrepet [Golic et al. 1991]. Motstand mot slike angrep avhenger av karakteristikken til den boolske funksjonen som kombinerer registrene. I tillegg, hvis de kombinerte registrene er lange (over 30 bit), er det vanskelig å gjennomføre angrepet siden det avhenger av å kalkulere “constrained edit distance” for hver testede initielle verdi til det klokkende registeret og tidskompleksiteten til denne kalkulasjonen er kvadratisk i forhold til lengden av den analyserte sekvensen.

I stedet for a kalkulere “edit distance” er det mulig å søke etter den næreste forekomsten av den analyserte chiffertekstsekvensen i sekvensen generert av registeret som angripes. Dette er mulig ved å gjennomføre et “constrained approximate”-søk etter chiffertekstsekvensen som vist i [Petrovic 2018].

Det neste og siste steget i kryptoanalysen på et slikt system er å rekonstruere klokkesekvensen og den initielle verdien til det klokkende registeret. I det klassiske “dynamic programming”-baserte angrepet blir dette gjort ved å gå tilbake gjennom matrisen med “partial constrained edit distances”.

I denne masteroppgaven blir mulighetene for å rekonstruere klokkesekvensen til det klokkende registeret når man benytter bit-parallelismen til moderne CPUer undersøkt. Et nytt angrep som benytter CPUens multi-threading og bit-parallelisme til å gjennomføre approximate search i kombinasjon med et “brute force”-angrep blir presentert. Flere eksperimenter som har til hensikt å finne de optimale parametrene til approximate search fasen blir også gjennomført.

Stream ciphers implementing irregularly clocked Linear Feedback Shift Registers (LFSRs), whose outputs are combined in a non-linear boolean function, are popular since they produce output sequences with extremely long periods, high linear complexities and excellent statistics.

However, it is known that such schemes can be broken by means of the so-called generalised correlation attack [Golic et al. 1991]. Resistance to such an attack depends on the characteristics of the combining boolean function. In addition, if the clocked LFSR is relatively long (over 30 bits), it is difficult to execute the attack since it involves computation of the constrained edit distance for every tested initial state of the clocked LFSR and the time complexity of this calculation is quadratic in the length of the intercepted output sequence of the generator.

Instead of computing constrained edit distance, it is possible to find the best embedding of the intercepted ciphertext sequence of the generator in the output sequence of the attacked LFSR for every initial state of that LFSR. This is possible to achieve by performing a constrained approximate search for the intercepted sequence as shown in [Petrovic 2018].

The next and final step in the cryptographic attack on such ciphers is the reconstruction of the clock control sequence and the initial state of the clocking LFSR. In the case of the classical, dynamic programming-based approach, this is done by backtracking through the matrix of partial constrained edit distances.

In this thesis, the possibilities of clock sequence reconstruction in the bit-parallel approximate search scenario is investigated and a novel attack combining the use of multi-threaded bit-parallel approximate search and a brute-force attack is developed and presented. Several experiments are also conducted in an attempt to find arbitrary optimal input parameters in the approximate search phase of the attack. %Experiments in order to determine the optimal input parameters, which are very important in order to improve the efficiency of the attack, are also carried out and the results presented.