Lavineffekt

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 5 augusti 2021; kontroller kräver 2 redigeringar .

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] .

Kriterier

För att kontrollera en bra lavineffekt i en viss algoritm används flera kriterier [4] :

Lavinkriterium

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] .

Strikt lavinkriterium

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] .

Definition

En boolesk funktion , där  är en vektor av variabler, uppfyller SLC om, när en av ingångsbitarna ändras, ändras utmatningsbiten med sannolikhet exakt .

Exempel

Ett 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.

Bit Independence Criterium

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.

Definition

En 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.

Garanterad ordning lavineffekt

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] .

Förvirring och diffusion

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] .

Lavineffekt i populära algoritmer

Lavineffekt i DES

Räknar beroende utdatabitar

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 DES
Runda
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ång

Fö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

Lavineffekt i AES

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.

Lavineffekttest i AES

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

Lavineffekt i GOST 28147-89

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-89
Runda
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-89

Fö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] .

Exempel

Exempel på hashfunktioner

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'

Exempel på chiffer

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'

Ett exempel på en dålig lavineffekt

Caesar-chifferet implementerar inte lavineffekten:

E(k = 3, "aaaaaaaaaaaaaaaa") = 'dddddddddddddddd' E(k = 3, "a c aaaaaaaaaaaaaa") = 'dfdddddddddddddd'

Anteckningar

  1. Horst Feistel, "Kryptografi och datorsekretess." Scientific American , vol. 228, nr. 5, 1973. (JPEG-skannade bilder) Arkiverad 6 juni 2019 på Wayback Machine
  2. Richard A. Mollin, "Codes: the guide to secrecy from ancient to modern times", Chapman & Hall/CRC, 2005, s. 142. (Visad på Google Books) Arkiverad 2 januari 2015 på Wayback Machine
  3. 1 2 William Stallings, "Kryptografi och nätverkssäkerhet: principer och praxis", Prentice Hall, 1999, s. 80. (Visa på Google Books) Arkiverad 2 januari 2015 på Wayback Machine
  4. 1 2 3 Isl VERGILI, Melek D. YUCEL. VOL.9 // Avalanche and Bit Independence Properties för ensembler av slumpmässigt valda n X n S-boxar . - Turk J Elec Engin, 2001. - S. 137. Arkiverad kopia (otillgänglig länk) . Hämtad 9 november 2009. Arkiverad från originalet 12 mars 2005. 
  5. 1 2 Thomas W. Cusick, Pantelimon Stanica, Pantelimon Stănică. Kryptografiska booleska funktioner och applikationer . - Academic Press, 2009. - S. 25.
  6. Réjane Forré, "The Strict Avalanche Criterion: Spectral Properties of Boolean Functions and an Extended Definition", Proceedings on Advances in cryptology, Springer-Verlag New York, Inc., 1990, s. 450. (PDF-länk) Arkiverad den 19 maj 2003 på Wayback Machine .
  7. Federal Agency for Education Siberian State Aerospace University uppkallad efter akademikern M.F. Reshetnev. AKTUELL INFORMATIONSTEKNIK SÄKERHETSFRÅGOR (länk till PDF) Arkiverad 5 maj 2021 på Wayback Machine
  8. Shannon C. , Company A. T. a. T. Communication Theory of Secrecy Systems  (engelska) // Bell Syst. Tech. J. - Short Hills, NJ, etc : 1949. - Vol. 28, Iss. 4. - P. 656-715. — ISSN 0005-8580 ; 2376-7154 - doi:10.1002/J.1538-7305.1949.TB00928.X
  9. Sourav Mukhopadhyay. Kapitel 2 // Kryptografi och nätverkssäkerhet . — Indien: Institutionen för matematik Indian Institute of Technology Kharagpur. - S. 20. Arkiverad kopia (otillgänglig länk) . Hämtad 4 november 2012. Arkiverad från originalet 20 november 2016. 
  10. Amish Kumar, Mrs. Namita Tiwari. Vol. 1 // EFFEKTIVT GENOMFÖRANDE OCH LADEN EFFEKT AV AES . - Institutionen för CSE MANIT-Bhopal: IJSPTM, augusti 2012. - S. 34.
  11. C. Charnes, O'Connor, J. Pieprzyk, R. Safavi-Naini, Y. Zheng. Ytterligare kommentarer Sovjetisk krypteringsalgoritm . — 1 juni 1994. - S. 1-8.  (inte tillgänglig länk)
  12. AKTUELLA PROBLEM MED INFORMATIONSTEKNOLOGISK SÄKERHET. Samling av material från III International Scientific and Practical Conference Krasnoyarsk 2009. (Länk till PDF) Arkivexemplar av 5 maj 2021 på Wayback Machine
  13. "a" = 0110 00 0 1, "c" = 0110 00 1 1