Linear Consistency Test (LCT) in cryptanalysis of irregularly clocked LFSRs in the presence of noise

Abstract

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.