Lavineffekt är ett begrepp inom kryptografi som vanligtvis används för att blockera chiffer och kryptografiska hashfunktioner . En viktig kryptografisk egenskap för kryptering, vilket innebär att ändring av värdet på ett litet antal bitar i inmatningstexten eller i nyckeln leder till en "lavin" förändring av värdena för utdatabitarna i chiffertexten. Med andra ord är det beroendet av alla utbitar på varje ingångsbit.
Begreppet "lavineffekt" introducerades först av Feistel i en artikel Cryptography and Computer Privacy , publicerad i Scientific American i maj 1973 [1] , även om begreppet användes så tidigt som Shannon .
I algoritmer med flera pass uppnås vanligtvis lavineffekten på grund av att en förändring i en ingångsbit vid varje pass leder till förändringar i flera utbitar [2] .
Om den kryptografiska algoritmen inte har tillräcklig lavineffekt kan kryptoanalytikern göra en gissning om ingångsinformationen baserat på utdatainformationen. Att uppnå en lavineffekt är således ett viktigt mål i utvecklingen av en kryptografisk algoritm [3] .
För att kontrollera en bra lavineffekt i en viss algoritm används flera kriterier [4] :
En kryptografisk algoritm uppfyller lavinkriteriet om en förändring i en bit av inmatningssekvensen i genomsnitt ändrar hälften av utbitarna.
Formellt kan en funktion definieras enligt följande:
En funktion uppfyller lavinkriteriet om en ändring i en ingångsbit orsakar en genomsnittlig ändring i hälften av utgångsbitarna [4] .
Definitionen av Severe Avalanche Criterion (SLC) gavs först av C. Tavares och A. Webster i deras S-box- forskning och designarbete .
En boolesk funktion kan ses som en del av en S-box-struktur. Designen av S-boxar baserade på booleska funktioner som uppfyller SLK har studerats av Adams och C. Tavares, Kwangio Kim . Sedan 1990 har SLC studerats i samband med booleska funktioner [5] .
DefinitionEn boolesk funktion , där är en vektor av variabler, uppfyller SLC om, när en av ingångsbitarna ändras, ändras utmatningsbiten med sannolikhet exakt .
ExempelEtt exempel på en boolesk funktion av tre variabler som uppfyller SLC [5] :
Inmatningsbitar | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
---|---|---|---|---|---|---|---|---|
utgångsbit | ett | ett | ett | 0 | 0 | ett | ett | ett |
En kryptografisk algoritm sägs uppfylla det strikta lavinkriteriet [6] om, när en bit av ingångssekvensen ändras, varje bit i utmatningssekvensen ändras med en sannolikhet på en sekund.
C. Tavares och A. Webster definierade i sitt arbete med studien och beskrivningen av S-boxar ett annat kriterium för en boolesk funktion , kallat bitoberoendekriteriet , enligt vilket, när en ingångsbit ändras, eventuellt två utdatabitar ändras oberoende av varandra från vän.
DefinitionEn funktion uppfyller bitoberoendekriteriet om, för någon , där , vändning av en bit vid ingången orsakar bitändringar och , och dessa ändringar är oberoende. För att mäta oberoendet av två utgångsbitar, införs en korrelationskoefficient mellan den -: e och -e komponenterna i utgångsvektorn för den modifierade utgångsvektorn, som kallas lavinvektorn och betecknas som .
.Bitoberoendeparametern för funktionen hittas som:
.Denna parameter visar hur väl funktionen uppfyller bitoberoendekriteriet . Det tar värden i intervallet , och i bästa fall är det lika med 0 och vi kan prata om oberoende, i värsta fall 1 när det finns beroende [4] .
En kryptografisk algoritm sägs uppfylla bitoberoendekriteriet om, när någon ingångsbit ändras, två utmatningsbitar ändras oberoende av varandra.
Det finns också en garanterad lavineffekt .
Garanterat lavinkriterium ( GAC ) av ordning är uppfyllt om en ändring av en bit vid ingången till substitutionsnoden ändrar åtminstone utbitarna vid utgången. Implementeringen av GAC- ordningen i intervallet från 2 till 5 för substitutionsnoderna ger alla chiffer en mycket hög lavineffekt på grund av spridningen av förändringar i bitar när data passerar genom krypteringsrundorna i Feistel-schemat [7] .
Shannon introducerade begreppen förvirring och diffusion som metoder som komplicerar statistisk kryptoanalys . Enligt Shannon:
Diffusion är en metod där redundans i indatastatistiken "distribueras" genom hela utdatastrukturen. Samtidigt krävs stora mängder utdata för statistisk analys, strukturen på källtexten är dold. Implementerat med P-boxar , med andra ord måste varje bit av klartexten påverka varje bit av chiffertexten. Att sprida en okrypterad bit över ett stort antal krypterade bitar skymmer den statistiska strukturen för klartexten. Att avgöra hur chiffertextens statistiska egenskaper beror på klartextens statistiska egenskaper borde inte vara lätt.
Förvirring är en metod där beroendet av nyckeln och utdata görs så komplext som möjligt, i synnerhet icke-linjärt. I det här fallet blir det svårare att dra slutsatser om nyckeln från utdata, såväl som om originaldata, om en del av nyckeln är känd. Implementerad med S-block .
Lavineffekten är en konsekvens av god förvirring och diffusion [8] .
I DES har lavineffekten karaktären av en strikt lavineffekt och manifesterar sig redan i den fjärde eller femte omgången [3] , uppskattad för varje operation (förutsatt att i början av omgången har påverkan av en initialt vald bit spridits till bitarna på höger sida och till vänster):
Efter expansion:
Om man antar slumpmässiga träffar i 8 S-boxar, enligt allokeringsproblemet , kommer bitarna att falla in i: S-boxar.
Ett av NSA :s krav för S-boxar var att förändring av varje bit av ingången skulle ändra 2 bitar av utdata. Vi kommer att anta att varje S-box-ingångsbit påverkar alla fyra utgångsbitarna. Kommer att bli beroende: bitar.
Efter bitvis tillägg av vänster och höger del :
Influenstabell för 1 bit vänster sida i DESRunda | ||||
---|---|---|---|---|
Förlängning |
S-block |
|||
0 | ett | 0 | 0 | 0 |
ett | 0 | 0 | 0 | (0, 1) 1 |
2 | ett | 1 → 1,5 | 1,5 → 5,5 | (5,5, 0) → 5,5 |
3 | 5.5 | 5,5 → 8,3 | 8,2 → 20,5 | (20,5, 1) → 20,9 |
fyra | 20.9 | 20,9 → 31,3 | 31,3 → 32 | (32, 20,9) → 32 |
5 | 32 | 32 | 32 | 32 |
För att uppnå maximal lavineffekt måste du noggrant välja expansionen, S-boxarna, samt permutation i funktionen .
Tabell över hur många bitar som ändras per omgångFöljande tabell visar antalet utdatabitar som ändrats i varje omgång, förutsatt att en bit av källtexten och en bit av nyckeln ändrats. [9]
Inmatningstextändringar | Viktiga ändringar | ||
---|---|---|---|
Runda | Antalet ändrade bitar |
Runda | Antalet ändrade bitar |
0 | ett | 0 | 0 |
ett | 6 | ett | 2 |
2 | 21 | 2 | fjorton |
3 | 35 | 3 | 28 |
fyra | 39 | fyra | 32 |
5 | 34 | 5 | trettio |
6 | 32 | 6 | 32 |
7 | 31 | 7 | 35 |
åtta | 29 | åtta | 34 |
9 | 42 | 9 | 40 |
tio | 44 | tio | 38 |
elva | 32 | elva | 31 |
12 | trettio | 12 | 33 |
13 | trettio | 13 | 28 |
fjorton | 26 | fjorton | 26 |
femton | 29 | femton | 34 |
16 | 34 | 16 | 35 |
I AES ser lavineffekten ut enligt följande: i den första omgången sprider åtgärden MixColumns() ändringar i en byte till alla 4 byte i kolumnen, varefter, i den andra omgången, tillämpas ShiftRows() och MixColumns() operationer sprider förändringar till hela tabellen. Därmed uppnås fullständig diffusion redan i andra omgången. Förvirring skapas av SubBytes()-operationen.
Tabellen visar de numeriska värdena för lavineffekten för S-boxar i AES. I det första fallet ändras byte "11" (i hexadecimal notation) till "10", i det andra fallet ändras byte "11" till "12", i det tredje - "00" till "10". Följaktligen beräknades lavineffektkoefficienten för varje fall. Från dessa data kan vi tydligt se att den krypterade utgående texten inte alls är enkel, med en ganska enkel ingångstext [10] . Och lavineffektens koefficient är nära 0,5, vilket betyder att lavinkriteriet är väl uppfyllt.
Mata in text | Chiffertext [ specificera ] | Lavineffekt |
---|---|---|
11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 | 79 F8 CC 24 01 82 DD 7F 2D 89 F7 E7 78 B7 EE 30 | 0,4375(56) |
11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 10 | 9D 4C 1D B4 6A 93 27 B5 20 64 37 D1 3D 9D 2A | |
11 22 33 66 55 44 55 44 77 88 99 66 44 45 36 12 | 4A A9 16 11 E2 8A 9F 67 35 30 1F 80 16 C5 B7 CD | 0,5153(66) |
11 22 33 66 55 44 55 44 77 88 99 66 44 45 36 11 | D7 00 43 2D 51 78 F7 65 50 03 03 75 B1 E4 2D A0 | |
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 | C6 A1 3B 37 87 8F 5B 82 6F 4F 81 62 A1 C8 79 | 0,4453(57) |
10 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 | 0D 19 33 06 27 42 FE 01 9C FE 06 E1 A8 1A A0 01 |
Lavineffekten på ingången tillhandahålls av (4 gånger 4) S-boxar och en cyklisk förskjutning till vänster av
Tabell över påverkansutbredning av 1 bit av vänster sida i GOST 28147-89Runda | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
ett | 2 | 3 | fyra | 5 | 6 | 7 | åtta | ett | 2 | 3 | fyra | 5 | 6 | 7 | åtta | |
0 | ett | |||||||||||||||
ett | ett | |||||||||||||||
2 | ett | 3 | ett | |||||||||||||
fyra | 3 | fyra | ett | ett | fyra | ett | 3 | ett | 3 | fyra | ||||||
5 | fyra | ett | 3 | ett | 3 | fyra | 3 | fyra | fyra | fyra | fyra | fyra | ett | |||
6 | 3 | fyra | fyra | fyra | fyra | fyra | ett | fyra | fyra | fyra | fyra | fyra | 3 | 3 | fyra | |
7 | fyra | fyra | fyra | fyra | fyra | 3 | 3 | fyra | fyra | fyra | fyra | fyra | fyra | fyra | fyra | fyra |
åtta | fyra | fyra | fyra | fyra | fyra | fyra | fyra | fyra | fyra | fyra | fyra | fyra | fyra | fyra | fyra | fyra |
Tabellen visar att i varje omgång ökar antalet oberoende bitar med i genomsnitt 4 gånger som ett resultat av skiftningen och nedgången av utsignalen från föregående omgångs S-box till 2 S-boxar i nästa omgång. Fördelningen av beroende bitar i grupper om 4 bitar på vänster och höger sida visas utan hänsyn till addition med den runda nyckeln. Det antas att varje bit vid S-boxens ingång påverkar alla bitar av utsignalen. Antalet omgångar för att uppnå full lavineffekt utan att ta hänsyn till tillägget med nyckeln är 8. Experimentell verifiering för S-boxar som används av Ryska federationens centralbank visar att 8 omgångar krävs .
Värdet av lavineffekten i GOST 28147-89För kryptografisk styrka är nyckelkraven för bitkonverteringsoperationer i en krypteringsrunda icke-linjäritet, det vill säga oförmågan att välja en linjär funktion som approximerar denna konvertering väl, och en lavineffekt - att uppfylla dessa krav gör det svårt att utföra linjärt och differentiell kryptoanalys av chifferet. Om vi från dessa positioner betraktar transformationsoperationerna i krypteringsrundan enligt GOST 28147-89 , så är det lätt att se till att kryptografisk styrka endast tillhandahålls av additionsoperationer med en nyckel och utför bitsubstitution i tabellen, eftersom operationerna av bitvis skift och modulo 2 summering är linjära och har ingen lavineffekt. Av detta kan vi dra slutsatsen att den avgörande faktorn för tillförlitligheten av kryptering i enlighet med GOST 28147-89 är en korrekt vald nyckelinformation (nyckel- och substitutionstabell). När det gäller datakryptering med en nollnyckel och en trivial substitutionstabell, vars alla noder innehåller siffror från 0 till 15 i stigande ordning, är det ganska enkelt att hitta klartexten från en känd chiffertext med både linjär och differentiell kryptoanalys.
Som visas i [11] kan operationen att lägga till data med en undernyckel inte ge en tillräcklig lavineffekt, eftersom när man ändrar en bit vid ingången av denna procedur, ändras endast en bit vid utgången med en sannolikhet på 0,5, de återstående bitarna förändras med en mycket mindre sannolikhet. Detta tyder på att för att säkerställa krypteringens kryptografiska styrka är det inte tillräckligt att säkerställa tillräcklig nyckelkvalitet - det är också nödvändigt att använda starka ersättningstabeller med hög olinjäritet och lavineffekt [12] .
Exemplen visar hur hashen ändras när en bit i inmatningssekvensen ändras.
SHA-1 :
SHA-1(0110 0001 0110 00 0 1 0110 0001 0110 00 0 1) = '70c881d4a26984ddce795f6f71817c9cf4480e79' SHA-1(0110 0001 0110 00 1 1 0110 0001 0110 00 0 1) = 'c6fdc1a445881de1f33e09cf00420a57b493b96d' SHA-1(0110 0001 0110 00 0 1 0110 0001 0110 00 1 1) = '00b25f15212ed225d3389b5f75369c82084b3a76'MD5 :
MD5(0110 0001 0110 00 0 1 0110 0001 0110 00 0 1) = '74b87337454200d4d33f80c4663dc5e5' MD5(0110 0001 0110 00 1 1 0110 0001 0110 00 0 1) = 'ca7de9e17429612452a717a44c36e688' MD5(0110 0001 0110 00 0 1 0110 0001 0110 00 1 1) = '3963a2ba65ac8eb1c6e2140460031925'Exemplen visar hur det krypterade meddelandet ändras när en bit [13] i inmatningssekvensen eller i nyckeln ändras.
AES :
AES(nyckel = "aaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaa") = '5188c6474b228cbdd242e9125ebe1d53' AES(nyckel = "aaaaaaaaaaaaaaaa", "aa c aaaaaaaaaaaaaa") = 'f7e5c1118f5cb86198e37ff7a29974bc' AES(nyckel = "aa c aaaaaaaaaaaaa", "aaaaaaaaaaaaaaaa") = '2c50b5cac9c755d67aa61b87c26248eb' AES(nyckel = "aa c aaaaaaaaaaaaa", "aa c aaaaaaaaaaaaa") = '87c09128de852b990b3dfbd65c7d9094'RC4 :
RC4(nyckel = "aaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaa") = '71ddf97f23b8e42a4f0ccc463d7da4aa' RC4(nyckel = "aaaaaaaaaaaaaaaa", "aa c aaaaaaaaaaaaaa") = '3d0feab630a32d1d0654c5481bd9ddd9' RC4(nyckel = "aa c aaaaaaaaaaaaa", "aaaaaaaaaaaaaaaa") = '476266d77453695b6cee682f23b0c51d' RC4(nyckel = "aa c aaaaaaaaaaaaa", "aa c aaaaaaaaaaaaa") = '3139d4506185d48e9b9e3dbbd4b57ec2'Caesar-chifferet implementerar inte lavineffekten:
E(k = 3, "aaaaaaaaaaaaaaaa") = 'dddddddddddddddd' E(k = 3, "a c aaaaaaaaaaaaaa") = 'dfdddddddddddddd'Symmetriska kryptosystem | |
---|---|
Streama chiffer | |
Feistel nätverk | |
SP nätverk | |
Övrig |
Public key kryptosystem | |||||||||
---|---|---|---|---|---|---|---|---|---|
Algoritmer |
| ||||||||
Teori |
| ||||||||
Standarder |
| ||||||||
Ämnen |
|
Hash-funktioner | |
---|---|
generell mening | |
Kryptografisk | |
Nyckelgenereringsfunktioner | |
Kontrollnummer ( jämförelse ) | |
Hashes |
|