Lavineeffekt
Lavineeffekten ("jordskredseffekten") er en egenskab ved algoritmer til blokchifre og kryptografiske hashfunktioner. Den er ofte ønsket i kryptografi. Effekten siger, at en stor del af output skal ændres, selv når input kun ændres en smule. I gode blokchiffrer betyder dette: En lille ændring i nøglen eller i klarteksten skal medføre en kraftig ændring i cifferteksten.
Det betyder, at små ændringer kan spredes hurtigt, når algoritmen anvender iterationer. Hver bit i output afhænger således af hver bit i input.
Udtrykket lavineeffekt blev først brugt af Horst Feistel (Feistel 1973). Senere blev begrebet identificeret med Shannons egenskab af forvirring.
Hvis en block cipher- eller kryptografisk hash-funktion ikke opfylder lavineeffekten i væsentlig grad, har den en dårlig randomisering. En kryptoanalytiker kan således foretage forudsigelser om input, hvis han kun får output. Dette kan være tilstrækkeligt til helt eller delvist at bryde (knække) algoritmen.
Det er en af de primære designmålsætninger, når man skaber en stærk kryptering eller en kryptografisk hashfunktion. De forsøger at bygge en god lavineeffekt i den. Matematisk set bruger dette sommerfugleeffekten. Det er derfor, at de fleste blokchiffrer er produktchiffrer. Det er også derfor, at hash-funktioner har store datablokke.
SHA1-hashfunktionen har en god lavineeffekt. Når en enkelt bit ændres, bliver hashsummen helt anderledes.
Navn
Navnet har sin oprindelse i jordskred. En lille sten kan falde ned, gå sammen med noget sne og skabe et ødelæggende jordskred. Stenen var lille, men kunne forårsage mange ødelæggelser. Det er det samme som det, denne virkning gør. En lille ændring i input (stenen) skal ændre output (landskabet).
Strengt lavinekriterium
Det strenge lavinekriterium (SAC; et "stærkt jordskredskriterium") er en egenskab ved boolske funktioner. Det er af betydning for kryptografi. Det er opfyldt, hvis alle outputbits ændres med en sandsynlighed på 50 %, hvis en enkelt inputbit ændres.
SAC blev bygget på begreberne evolutionskomplethed og lavine. Det blev introduceret af Webster og Tavares i 1985. I dag er det et krav til ethvert moderne kryptografisk system. Det blev f.eks. opfyldt af alle finalisterne i AES-konkurrencen.
Kriterium for bituafhængighed
Bit-uafhængighedskriteriet (BIC; et kriterium, der er uafhængigt af bit) er et kriterium. Det lyder således: Når en enkelt indgangsbit ændres (inverteres), skal to udgangsbits ændres uafhængigt af hinanden. Dette gælder for alle bits.
Det ville f.eks. ikke være tilfredsstillende, hvis den ene udgangsbit kun ændres, når den anden udgangsbit også ændres. De ændrer sig måske kun, fordi input-bitten ændres. I modsat fald ville outputbitsne afhænge af hinanden.
Relaterede sider
- Forvirring og spredning
Spørgsmål og svar
Spørgsmål: Hvad er lavinteffekten?
A: Lavineeffekten (også kendt som "jordskredseffekten") er en egenskab ved blokchifre og algoritmer med kryptografiske hashfunktioner, som siger, at en lille ændring i nøglen eller klarteksten bør medføre en kraftig ændring i cifferteksten.
Spørgsmål: Hvem brugte først udtrykket "lavineeffekt"?
A: Udtrykket lavineeffekt blev første gang brugt af Horst Feistel i 1973.
Spørgsmål: Hvordan hænger det sammen med Shannons egenskab om forvirring?
A: Begrebet lavineeffekt blev identificeret ved Shannons egenskab af forvirring, som fastslår, at hvis en blokchiffer eller kryptografisk hashfunktion ikke opfylder denne grad i væsentlig grad, så har den dårlig randomisering og kan delvist eller helt brydes (knækkes).
Spørgsmål: Hvad er nogle af designmålene, når man skaber stærke krypteringssystemer?
A: Når folk skaber stærke krypteringskoder, forsøger de at bygge en god lavineeffekt ind i dem ved hjælp af matematiske principper som f.eks. sommerfugleeffekten. Dette er grunden til, at de fleste blokchiffrer er produktchiffrer, og at hash-funktioner har store datablokke.
Spørgsmål: Hvad sker der, hvis en algoritme ikke opfylder lavinteffekten?
Svar: Hvis en algoritme ikke opfylder lavineeffekten i væsentlig grad, er den dårligt randomiseret og kan helt eller delvist knækkes (crackes) af kryptoanalytikere, der kan forudsige input på grundlag af et givet output.
Spørgsmål: Hvorfor bruger de fleste blokchifre produktchifre?
Svar: De fleste blokchifre anvender produktchifre, fordi de hjælper med at bygge gode avalanceeffekter ind i dem ved hjælp af matematiske principper som f.eks. sommerfugleeffekten.
Spørgsmål: Hvorfor har hash-funktioner store datablokke?
Svar: Hash-funktioner har store datablokke, fordi det hjælper med at opbygge gode avalanceeffekter ved hjælp af matematiske principper som f.eks. sommerfugleeffekten.
