The use of k-best paths algorithms in clock control sequence reconstruction
Master thesis
Permanent lenke
http://hdl.handle.net/11250/143870Utgivelsesdato
2006Metadata
Vis full innførselSamlinger
Sammendrag
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.