CLOCK CONTROL SEQUENCE RECONSTRUCTION IN THE GENERALIZED SHRINKING GENERATOR
Slobodan Petrović · 2007
NORSK: "Shrinking" generatoren er en populær representant for pseudotilfeldige sekvens generatorer (PTSG) som anvender såkalt uregelmessig klokking. Det karakteristiske ved denne familien av PTSG er at de har en eller flere lineært tilbakekoblede skift registre(LTSR) hvis klokking blir kontrollert av sekvensen til en av subgeneratorene. Denne sekvensen kalles klokke-kontroll sekvensen. I denne rapporten presenterer vi en algoritme som rekonstruerer klokke-kontroll sekvensen til en generalisert "shrinking" generator med tilstedeværelse av støy. "Shrinking" generatoren blir først redusert til en step1-stepE generator (en annen klasse av PTSG med uregelmessig klokking), hvor E avhenger av den maksimale lengden på etterfølgende nuller i ut-sekvevnsen til den klokkende delen av generatoren. Deretter utføres det et retningsstyrt søk for optimale og suboptimale stier i "edit-distance" matrisen som samsvarer med generatoren. Det tillatte vekt-avviket fra det optimale bestemmes av støy-nivået i den statistiske modellen av generatoren. Innvirkningen som utilstrekkelig estimering av lengden på ut-sekvensen fra den klokkede LTSR uten uregelmessig klokking har på nivået tilsvarende støy, diskuteres. Forsøksresultane som presenteres viser at totalt antall klokke-kontroll sekvens kandidater øker moderat etter hvert som den nødvendige klokke-kontroll sekvens lengden øker. Fordelen med dette angrepet i forhold til andre angrep rapportert i litteraturen, er at dette angrepet er effektivt selv om støy-nivået er relativt høyt og at løsningen garantert vil bli funnet.