Cryptanalysis of Irregularly Clocked LFSR: using approximate RBP search on FPGA
Magnus Øverbø · NORA - Norwegian Open Research Archives · 2019
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.