Lavineffekt
Lavineffekten ("jordskredseffekten") är en egenskap hos algoritmer för blockchiffer och kryptografiska hashfunktioner. Den är ofta önskvärd inom kryptografi. Effekten innebär att en stor del av resultatet måste förändras även när ingången förändras endast lite. I bra blockchiffer innebär detta: En liten förändring av nyckeln eller klartexten bör orsaka en kraftig förändring av chiffertexten.
Detta innebär att små förändringar kan spridas snabbt när algoritmen använder iterationer. Varje bit i resultatet är alltså beroende av varje bit i indata.
Termen lavinverkan användes först av Horst Feistel (Feistel 1973). Senare identifierades begreppet med Shannons förvirringsegenskap.
Om en blockkryptering eller en kryptografisk hashfunktion inte uppfyller lavinverkan i betydande grad har den dålig randomisering. En kryptoanalytiker kan alltså göra prognoser om inmatningen om han eller hon bara får utmatningen. Detta kan vara tillräckligt för att helt eller delvis knäcka algoritmen.
Det är ett av de viktigaste målen när man skapar en stark chiffer eller en kryptografisk hashfunktion. De försöker bygga in en bra lavinverkan i den. Matematiskt sett används fjärilseffekten. Det är därför som de flesta blockchiffer är produktchiffer. Det är också därför som hashfunktioner har stora datablock.
Hashfunktionen SHA1 har en bra lavinverkan. När en enda bit ändras blir hashsumman helt annorlunda.
Namn
Namnet har sitt ursprung i jordskred. En liten sten kan falla ner och tillsammans med lite snö skapa ett destruktivt jordskred. Stenen var liten, men kunde orsaka mycket förstörelse. Det är samma sak som vad denna effekt gör. En liten förändring av insatsen (stenen) bör förändra resultatet (landskapet).
Strikt kriterium för laviner
Det strikta lavinkriteriet (SAC; ett "starkt jordskredskriterium") är en egenskap hos boolska funktioner. Det är av betydelse för kryptografi. Det är uppfyllt om alla utgångsbitar förändras med en sannolikhet på 50 procent om en enda ingångsbit förändras.
SAC byggde på begreppen evolutionskompletthet och lavin. Det introducerades av Webster och Tavares 1985. Numera är det ett krav för varje modernt kryptografiskt system. Det uppfylldes t.ex. av alla finalister i AES-tävlingen.
Kriterium för bitoberoende
Kriteriet Bit independence criterion (BIC; ett kriterium som är oberoende av biten) är ett kriterium. Det lyder: När en enskild ingångsbit ändras (inverteras) ska två utgångsbitar ändras oberoende av varandra. Detta gäller för alla bitar.
Den skulle t.ex. inte vara nöjd om den ena utgångsbiten endast ändras när den andra utgångsbiten också ändras. De kanske ändras bara för att inmatningsbiten ändras. I annat fall skulle utgångsbitarna vara beroende av varandra.
Relaterade sidor
- Förvirring och spridning
Frågor och svar
Fråga: Vad är lavinverkan?
S: Lavineffekten (även känd som "jordskredseffekten") är en egenskap hos blockchiffer och algoritmer för kryptografiska hashfunktioner som säger att en liten förändring av nyckeln eller klartexten bör leda till en kraftig förändring av chiffertexten.
F: Vem använde först termen "lavinverkan"?
S: Termen lavinverkan användes för första gången av Horst Feistel 1973.
F: Hur förhåller sig detta till Shannons förvirringsegenskap?
S: Begreppet lavinverkan identifierades genom Shannons egenskap av förvirring, som anger att om ett blockchiffer eller en kryptografisk hashfunktion inte uppfyller denna grad i betydande grad, så har den dålig randomisering och kan delvis eller helt brytas (knäckas).
F: Vilka är några designmål när man skapar starka chiffer?
S: När människor skapar starka chiffer försöker de bygga in en bra lavinverkan i dem med hjälp av matematiska principer som fjärilseffekten. Detta är anledningen till att de flesta blockchiffer är produktchiffer och till att hashfunktioner har stora datablock.
F: Vad händer om en algoritm inte uppfyller lavineffekten?
S: Om en algoritm inte uppfyller avalancheeffekten i betydande grad har den dålig randomisering och kan delvis eller helt brytas (knäckas) av kryptoanalytiker som kan göra prognoser om inmatningen baserat på endast en given utmatning.
F: Varför använder de flesta blockchiffrar produktchiffrar?
S: De flesta blockchiffer använder produktchiffer eftersom de hjälper till att bygga in bra avalanceeffekter i dem med hjälp av matematiska principer som fjärilseffekten.
F: Varför har hashfunktioner stora datablock?
S: Hashfunktioner har stora datablock eftersom de hjälper till att bygga upp goda avalanceeffekter med hjälp av matematiska principer, t.ex. fjärilseffekten.
