The use of k-best paths algorithms in clock control sequence reconstruction

Abstract

NORSK: Nøkkelstraumgeneratorar som er baserte på klokkekontrollerte lineært tilbakekopla skiftregister blir ofte brukte i fytchiffer-system. Kryptoanalyse av slike generatorar kan delast inn i to etappar: Den første etappen finn kandidatar til starttilstanden (initial state) til skiftregisteret, og den andre etappen rekonstruerer klokkekontrollsekvensen. Ein kan finna kandidatar til denne starttilstanden ved å rekna ut editeringsdistansen (edit distance) mellom talsekvensen som blir produsert av kvar mogleg starttilstand, og den observerte chifferteksten, og behalda dei kandidatane som gjev ein distanse under ein viss verdi som er bestemt på førehand. Utrekninga av editeringsdistansen skjer rekursivt, ved å fylla ei matrise med partielle editeringsdistansar. Klokkekontrollsekvensen kan då rekonstruerast ved å finna stigar tilbake gjennom denne matrisa. I eit kjent-klartekst-angrep vil ein optimal stig, som det finst effektive metodar for å finna, gje den korrekte klokkekontrollsekvensen. Derimot, når klarteksten ikkje er kjent, vert han oppfatta som støy i kryptoanalyseprosessen, og denne støyen gjer det naudsynt å vurdera suboptimale stigar gjennom matrisa, i tillegg til dei optimale stigane. Denne oppgåva brukar ein k-best-paths-algoritme til å finna dei k kortaste stigane i matrisa, i håp om at ein av dei representerer den korrekte klokkekontrollsekvensen. Gjennom eksperimentelle resultat vert det vist at angrepet fungerer, og at det finn løysinga raskare enn eit liknande angrep, basert på eit depth-first search, når det ikkje er noko støy. Derimot så ser det ut til at depth-first-search-angrepet gjennomsnittleg er betre når støynivået aukar.

ENGELSK: Keystream generators based on clock-controlled linear feedback shift registers are often used in stream cipher systems. Cryptanalysis of such generators can be divided into two stages: In the first stage the initial state of the LFSR is found; the second stage reconstructs the clock control sequence. A set of candidate initial states for the LFSR can be found by computing the edit distance between the sequences produced by every possible initial state and the observed ciphertex, keeping the candidates that give distances below a given threshold. The edit distance is computed recursively, and a matrix of partial edit distances is filed out during these computations. Clock control sequence reconstruction can be done by finding paths back through the edit distance matrix. In the known plaintext scenario an optimal path, which can be found very efficiently, would give the correct clock control sequence. However, when the plaintext is not known, it behaves like noise in the cryptanalytic process, and this noise makes it necessary to also consider suboptimal paths through the matrices. This thesis uses a k-best paths algorithm to extract the k shortest paths from the matrix, in order to find the path that represents the correct clock control sequence. It is shown, through experimental results, that the attack is successful, and that it performs better than a similar depth-first search attack when there is no noise. However, in the presence of noise, the depth-first search performs slightly better than the k-best paths attack, on average.