Linear Consistency Test (LCT) in cryptanalysis of irregularly clocked LFSRs in the presence of noise
Master thesis
Permanent lenke
http://hdl.handle.net/11250/143998Utgivelsesdato
2011Metadata
Vis full innførselSamlinger
Sammendrag
ENGELSK: Keystream generators using irregular clocking are frequently used to generate the keystream in
a stream cipher. These generators are typically composed of two Linear Feedback Shift Registers
(LFSRs), where the clocking of the second LFSR is controlled by the output sequence from the
first LFSR.
Various attacks exist to cryptanalyse such generators. Among the more popular are correlation
attacks and algebraic attacks. When only the ciphertext is known, the usual approach is to use
correlation methods. These attacks are accomplished in two stages. First, the initial state of the
clocked LFSR is found, then the clock control sequence is reconstructed. Algebraic attacks, on the
other hand, have only been applied in the known-plaintext scenario to cryptanalyse irregularly
clocked generators.
The Linear Consistency Test (LCT) is an algebraic key recovery attack which uses some guessed
bits from the internal state of the generator to set up a set of equations used to determine
whether the initial guess was correct or not. In this thesis, an extension of the LCT attack is
implemented that successfully reconstructs the clock control sequence in the ciphertext only scenario.
Experiments show that this attack can handle low to moderate levels of noise, and it is
estimated to perform better than correlation attacks on irregularly clocked generators. NORSK: Nøkkelstrømgeneratorer med uregelmessig klokking blir ofte brukt for å generere nøkkelstrømmen
i et flytchiffer. Disse generatorene er typisk bygd opp av to lineært tilbakekoblede skiftregistre
(LFSRer) hvor klokkingen av det andre LFSRet kontrolleres av utdatasekvensen fra det
første LFSRet.
Forskjellige typer angrep eksisterer for å knekke slike generatorer. Korrelasjonsangrep og algebraiske
angrep er metoder som er mye brukt. Når bare chifferteksten er kjent, er det vanlig
å bruke korrelasjonsangrep. Disse angrepene utføres i to trinn. Først blir starttilstanden til det
klokkede LFSRet funnet, deretter rekonstrueres klokkekontrollsekvensen. Algebraiske angrep derimot,
er bare blitt brukt i kjent klartekstscenariet i kryptoanalyse av uregelmessig klokkede generatorer.
Lineær Konsistenstest (LKT) er et algebraisk nøkkelgjenfinningsangrep som bruker kjente bit
fra den indre tilstanden til en generator til å sette opp et ligningssett som brukes for å bestemme
om den gjettede starttilstanden var riktig eller ikke. I denne oppgaven implementeres en utvidelse
av LKT-angrepet som lykkes i å rekonstruere klokkekontrollsekvensen i bare-chiffertekstscenariet.
Eksperimenter viser at dette angrepet kan håndtere lave til moderate støynivåer, og det
er estimert til å ha bedre ytelse enn korrelasjonsangrep på uregelmessig klokkede generatorer.