Cryptanalysis of Irregularly Clocked LFSR: using approximate RBP search on FPGA

Abstract

Kryptoanalyse av et kryptosystem som benytter en Binary Rate Multiplier (BRM), 0/1 klokking, som nøkkelgenerator resulterer i at Siegenthaler's klassiske korrelasjonsangrep[4] ikke kan benyttes. Dette pga. at kryptoteksten og udesimerte bit-sekvensen genert av det irregulært klokkede Linear Feedback Shift-Register (LFSR) er av forskjellige lengede. Istedetfor ved å benytte det generaliserte korrelasjonsangrepet utviklet av Golic og Mihaljevic[2] kan Levenshtein-distansen mellom sekvensen bli benyttet til korrelering.

I denne masteroppgaven utforsker vi muligheten for å implementere et ubegrenset Approximate Row-wise Bit-Parallel (ARBP) søk, med shift-AND algoritmen utviklet av Wu and Manber[5], for å finne Levenshtein-distansen mellom kryptoteksten og den udesimerte bit-sekvensen generert av et irregulært klokket LFSR, for så og benytte det til korrelasjon. Oppgavens funn viser at FPGA utfører jobben bedre enn en CPU, siden den operer med en konstant gjennomsnittstid, estimert av Ttot = Rops × 4f . Hvor Rops er antall verdier som må oppdateres iløpet av et komplett søk, og f er FPGA-designets klokkefrekvens.

CPU-ens gjennomsnitstid er vist å ha en lineær stigningskurve, basert på lengden av søkeordet som er gitt av en periodisk økning av faktoren ⌈M/w⌉, hvor M er søkeordets lengde og w er CPU-ens register-størrelse.

Alt i alt, tiden påkrevd for å prossesere et kryptosystem med reelle verdier ved bruk av Field-Programmable Gate Array (FPGA) krever store mengder ressurser. Et feedback polynomial av størrelse L=32 med M=1024 og klokkefrekvens f=2.39GHz krever 43 dager for å fullføres, mens M=4096 krever 695 dager for å fullføres. Selv om dette er lang tid, krever det kun 700 FPGA-er for å redusere søketiden til under et døgn, hvor kostnaden kun er innkjøp av FPGA-er. Hvilket gjør det mulig å søke større polynomer, gitt at man har ressurser nok.

Cryptanalysis on a cipher system the utilising 0/1 clocking Binary Rate Multiplier (BRM) as the keystream generator renders Siegenthaler’s classical correlation attack[4] unusable since the output sequence and the undecimated bit sequence generated by the irregularly clocked Linear Feedback Shift-Register (LFSR) are of different lengths. Instead, by utilising the generalised correlation attack developed by Golic and Mihaljevic[2] the Levenshtein distance between the two sequences can be utilised as the basis for correlation.

In this thesis, we explore the application of implementing an unconstrained Approximate Row-wise Bit-Parallel (ARBP) search, using Wu and Manber’s shift-AND algorithm[5], to obtain the Levenshtein distance between the ciphertext and the undecimated bit sequence of the irregularly clocked LFSR as the correlation metric. Our findings shows that the FPGA will perform better than a Central Processing Unit (CPU) implementation, as it operates with constant mean execution time, estimated by Ttot = Rops × 4f . Where Rops represents the number of search state values which must be updated throughout the search, and f is the FPGA designs clock rate.

The CPUs processing time is shown to be of linear growth, based on the length of the search word as given by its periodic increase by a factor of ⌈M/w⌉, where M is the search word length, and w is the size of the CPUs machine word.

However, overall the time required for processing a real-world cipher system using Field-Programmable Gate Array (FPGA) requires a large amount of resources. Even a feedback polynomial of L = 32, with M = 1024 and a clock rate of f = 2.39GHz will require 43 days to complete, while M = 4096 would require 695 days to complete. Even so, given 700 FPGAs running simultaneously a search can be completed within a day at the cost of the additional FPGAs needed, making it possible given enough resources are available.