Forskydningsangreb

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 6. maj 2018; checks kræver 9 redigeringer .

Shift attack ( eng.  slide attack ) - kryptografisk angreb , som i det generelle tilfælde er et angreb baseret på udvalgt klartekst , som tillader kryptering af blok-multi-runde ciphers, uanset antallet af brugte runder. Foreslået af Alex Biryukov og David Wagner i 1999 [1] .

Oprettelseshistorie

Ideen om at skabe et forskydningsangreb kom først op med Edna Grossman og Brian Tuckerman i 1977. Den tilsvarende rapport blev offentliggjort [2] sammen med IBM . Grossman og Tuckerman var i stand til at vise muligheden for et angreb på en temmelig svag New Data Seal (NDS) chiffer . Angrebet udnytter det faktum, at chifferen i hver runde kun blander den samme nøgle ved at bruge den samme tabel i hver runde. Brugen af ​​klartekster omgår dette og giver os mulighed for at betragte det som den tidligste version af skifteangrebet.

I 1990 blev differentiel kryptoanalyse foreslået , hvilket demonstrerede sårbarheden af ​​multi-round DES-lignende kryptosystemer [3] . En måde at sikre deres kryptografiske styrke på var at øge antallet af brugte runder, hvilket øgede angrebets beregningsmæssige kompleksitet i forhold til deres antal. Brugen af ​​denne forbedring til mange krypteringsalgoritmer var især baseret på den empiriske vurdering, at enhver, selv ret svag cipher, kan gøres kryptografisk stærke ved at gentage krypteringsoperationerne mange gange:

Med undtagelse af kun nogle få degenererede tilfælde kan algoritmen gøres vilkårligt sikker ved at øge antallet af runder.

Originaltekst  (engelsk)[ Visskjule] Med undtagelse af nogle få degenererede tilfælde kan en algoritme gøres vilkårligt sikker ved at tilføje flere runder. — B. Preneel, V. Rijmen, A. Bosselears: Principper og ydeevne for kryptografiske algoritmer [4]

For eksempel havde nogle cifre, der blev foreslået som kandidater til AES-konkurrencen i 1997, et ret stort antal runder: RC6(20), MARS(32), SERPENT(32), CAST(48) [1] .

I 1999 blev der dog publiceret en artikel af Alex Biryukov og David Wagner, der beskrev et forskydningsangreb, som modbeviste denne antagelse. Et træk ved dette angreb var, at det ikke afhang af antallet af chifferrunder; dens succes krævede kun identiteten af ​​runderne og muligheden for krypteringsanalyse af krypteringsfunktionen i en separat runde. Artiklen beskrev også anvendelsen af ​​dette angreb på TREYFER -chifferet og forenklede versioner af DES -chifferne (2K-DES) og BLOWFISH [1] .

I 2000 blev der udgivet en anden artikel, som demonstrerede forbedrede versioner af skiftangrebet - "Sliding with a twist" og "Complementation slide", hvilket gør det muligt at udvide det til cifre, hvis runder har små forskelle. Så ved hjælp af disse forbedringer blev nogle modifikationer af DES -chifferet knækket , såvel som en forenklet 20-rund version af krypteringsstandarden GOST 28147-89 [5] [6] .

Generel beskrivelse

I det enkleste tilfælde [7] anvendes et shift-angreb på krypteringsalgoritmer, som er flere gentagelser af en krypteringsfunktion , hvis input ved hver runde er chifferteksten (resultatet af kryptering i den foregående runde) og en rundnøgle , hvilket er det samme for alle runder. De vigtigste krav til en vellykket implementering af dette angreb er [7] :

  1. Identitet af runder (hvilket er garanteret ved at bruge den samme funktion og den samme tast på hver runde)
  2. Evnen til nemt at finde nøglen , kende teksten ved input og teksten ved output af en runde

Algoritmen for det enkleste angreb

Trin 1. Lad os tage noget almindelig tekst ved inputtet og den tilsvarende chiffertekst ved udgangen af ​​krypteringsalgoritmen. Trin 2. Tag en anden almindelig tekst og dens tilsvarende chiffertekst , så parret er forskelligt fra det allerede valgte par . Trin 3. Antag at er relateret til relationen = , og er relateret til relationen , dvs. og er resultaterne af en-runde kryptering og hhv. Lad os kalde sådan et par for et "glidende par" (glidende par) [1] . Ved at bruge påstanden om, at krypteringsnøglen let kan beregnes, ved at kende teksten ved input og teksten ved output af en runde, beregner vi nøglen ved den første runde af kryptering ved relationen , og nøglen ved den sidste runde af kryptering af relationen . Trin 4. Lad os tjekke ligheden . Fordi ved betingelse er alle runde nøgler de samme, så skal denne lighed være opfyldt, ellers er antagelsen i trin 3 forkert, og det er nødvendigt at vende tilbage til trin 2, og ekskludere det testede par fra listen over mulige kandidater. Opfyldelsen af ​​lighed indikerer, at nøglen potentielt er den ønskede runde nøgle. Trin 5. For at kontrollere den fundne nøgle for falske positiver, bør du erstatte den i krypteringsalgoritmen og kontrollere den korrekte funktion på flere forskellige kendte par af "plaintext - ciphertext ". På trods af at det er muligt for den forkerte nøgle at bestå denne test, er sandsynligheden for dette ved gode cifre ekstremt lille [7] , hvilket betyder, at den verificerede nøgle med stor sandsynlighed er den ønskede runde nøgle. I tilfælde af vellykket verifikation erklærer vi således, at nøglen skal søges, ellers vender vi tilbage til trin 2, og ekskluderer det verificerede par og nøglen fra listen over mulige kandidater.

Bemærkninger om algoritmen

Skift angrebsændringer

I tilfælde af moderne blokcifre er de runde nøgler normalt ikke de samme. Dette fører til det faktum, at den algoritme, der bruges i konstruktionen af ​​det enkleste angreb, generelt er uanvendelig for sådanne cifre og kræver nogle tilføjelser.

Udtalelse af problemet

Lad der være en krypteringsalgoritme nr. 1, bestående af blokke, sådan at nøglen bruges i th runde (vi vil antage, at det samlede antal nøgler , nøglen bliver nødvendig senere), og lad os vælge et par af nøgler. "plaintext - chiffertekst" . Ved udgangen af ​​første runde får vi teksten , hvor er krypteringsfunktionen.

Ydermere involverer shift-angrebet kryptering af teksten med en ny blokchiffer nr. 2, bestående af blokke fra til . Lad os betegne chifferteksten ved udgangen af ​​den -th blok som . Det er let at se, at i dette tilfælde, ved udgangen af ​​den i-te blok, vil vi få den tekst, der allerede findes ovenfor , hvilket betyder, at teksten og chifferteksten er relateret af relationen .

Således har vi fået et par , der opfylder relationerne og , som ikke er andet end et generelt skiftepar. I overensstemmelse hermed vil disse relationer i det enkleste tilfælde have formen og .

Hvis vi antager, at noget tekst er relateret til forholdet , bør vi få chifferteksten ved udgangen af ​​krypteringsalgoritme #2 med teksten ved indgangen, for at bekræfte eller afkræfte den ved hjælp af nøgletal . I tilfælde af et trivielt nøgleskema er krypteringsalgoritmerne nr. 1 og nr. 2 identiske, hvilket betyder , at den kan opnås ved at kryptere teksten med en allerede eksisterende blokchiffer. Ellers er krypteringsalgoritmer nr. 1 og nr. 2 forskellige, og kryptanalytikeren er ikke i stand til at konstruere algoritme nr. 2, hvilket betyder, at chifferteksten ikke kan opnås.

Tilfældet med et Feistel-netværk med to-runder selv-lighed

Komplementeringsdias [ 5 ]  _

Som nævnt i bemærkningerne til angrebsalgoritmen, kan tilfældet med krypteringsanalyse af chiffer med p-runde selv-lighed nemt reduceres til det enkleste tilfælde af et shift-angreb ved at kombinere flere runder til én, hvilket svarer til at skifte chifferblokke vha. runder. I tilfælde af et Feistel-netværk med skiftevis skiftende runde taster og , dvs. med to-runders selvlighed kan denne tilgang øge kompleksiteten af ​​kryptoanalyse og dermed gøre skiftangrebet ineffektivt. I stedet blev det som hidtil foreslået kun at skifte med én omgang i stedet for to, men samtidig ændre lidt på kravene til skifteparret.

I beskrivelsen af ​​problemet betragtet ovenfor, blev det angivet, at for at søge efter et skiftpar, i det generelle tilfælde, er det nødvendigt at kunne arbejde med to -blokcifre - den oprindelige, bestående af blokke fra til , og den nye, bestående af blokke fra til . Komplementeringsdias giver dig mulighed for kun at arbejde med den originale blokchiffer.

Selvom følgende ræsonnement vil blive demonstreret ved hjælp af en 4-rund chiffer, kan den udvides til et hvilket som helst antal runder. Lad os først se på, hvordan klarteksten ændrer sig i forskellige runder af kryptering. Lad os repræsentere klarteksten som , hvor og er henholdsvis venstre og højre del af teksten.

Rundt tal Venstre side Højre del
en
2
3
fire

Lad os betegne teksten ved udgangen af ​​runde 1 og chifferteksten . Bemærk nu, at for at finde chifferteksten ved udgangen af ​​en 4-rund blokchiffer med et nøgleskema , er det nok at tilføje forskellen til højre side af hver runde af den originale chiffer og derefter kryptere teksten med resulterende chiffer (fig. 2, højre diagram). For at gøre dette, vil vi levere teksten til input af den oprindelige chiffer . Lad os betegne chifferteksten som . Lad os overveje, hvordan teksten ændres i forskellige runder af kryptering.

Rundt tal Venstre side Højre del
en
2
3

fire

Heraf kan det ses, at den indførte forskel er bevaret ved hver runde, hvilket betyder, at chifferteksterne og hænger sammen med relationerne: og , og parrene "plaintext - chiffertekst" og af relationerne og .

Hvis teksterne er forbundet med et forhold , siger de, at teksterne og har en forskydningsforskel ( engelsk slide difference ) .  

Således opnås følgende ligninger for forskydningsparret:


Som før, i tilfælde af -bit-tekster, kræves klartekster for at finde skiftparret . Forskydningsparret skal nu opfylde ligningen (se fig. 2). I tilfælde af at finde et potentielt skiftpar, tillader den anden ligning at finde en kandidat , og hvis funktionen er tilstrækkelig sårbar over for kryptoanalyse, så giver disse ligninger os mulighed for at finde de potentielle ønskede nøgler og . Derefter er det kun tilbage at kontrollere for falske positiver.

Sliding with a twist  [ 5 ]

Kravet angivet i problemformuleringen for at kunne arbejde med den oprindelige ciffer #1, bestående af blokke fra til , og den nye ciffer #2, bestående af blokke fra fra til , kan nemt transformeres ved hjælp af den såkaldte shift- og roter tilgang.

Hvis vi udelukker den sidste permutation af venstre og højre del af teksten og vender om rækkefølgen af ​​nøglerne, så vil dekryptering i Feistel-netværket ske på nøjagtig samme måde som kryptering [1] . Skift-og-rotér tilgangen bruger denne egenskab, nemlig den foreslår at bruge dekrypteringsalgoritmen som chiffer #2 (se fig. 3).

Denne tilgang har ingen grundlæggende forskelle fra den enkleste algoritme. Som i det simpleste tilfælde er kravene til skifteparret , hvor . Således får vi ligningerne:


og en tilstand, der gør det nemmere at finde skiftpar:

Som sædvanlig, i tilfælde af -bit-tekster, er der behov for klartekster for at finde skift-parret . Hvis den findes, giver funktionens sårbarhed dig mulighed for at finde nøglen fra ligningerne .

Antallet af påkrævede tekster på dette trin kan reduceres til . For at gøre dette, krypterer vi forskellige tekster i formularen , og dekrypterer forskellige tekster af formularen , hvor og er faste og opfylder betingelsen . Da vi nu i virkeligheden arbejder med - bit-tekster, er der ifølge fødselsdagsparadokset blandt disse "klartekst-cifertekst"-par stor sandsynlighed for et skiftpar.

Nøglen kan findes ved at anvende metoden beskrevet for det generelle tilfælde af blokcifre med p-runde-selvlighed, nemlig ved at kombinere hver efterfølgende to runder til én - således reducerer vi problemet til det enkleste tilfælde. Selvom størrelsen af ​​den runde nøgle fordobles, vil dette ikke komplicere krypteringsanalysen, da nøglen , som er halvdelen af ​​den nye runde nøgle, allerede er kendt, og vi skal kun finde den anden halvdel, der er lige stor som runden. indtast det oprindelige problem.

Andre ændringer

En separat modifikation kan betragtes som den samtidige brug af de to fremgangsmåder beskrevet ovenfor - Komplementeringsslide og Sliding with a twist, som gør det muligt at udvide skiftangrebet til cifre med 4-runders selvlighed [5] .

Problemet med krypteringsanalyse af cifre med ulige runder adskiller sig fra alle de tilfælde, der er behandlet indtil videre, i hvis løsning ingen af ​​de overvejede angrebsmodifikationer kan bruges. For så vidt angår sådanne cifre, blev der foreslået et genjustering af diasangreb [ 8 ]  , demonstreret på eksemplet med ændringer af DES -chifferet , især eksemplet med den fulde 16-runde version af DES

Sliding-linear attack ( engelsk  slide-linear attack ) [9] er et eksempel på implementeringen af ​​et skiftangreb ved hjælp af principperne for lineær kryptoanalyse . Arbejdet med dette angreb blev vist på chifferen 4K-DES.

Der er også forbedringer for at fremskynde implementeringen af ​​allerede eksisterende modifikationer af forskydningsangrebet. Især en af ​​disse forbedringer, beskrevet i arbejdet af Eli Biham, Orr Dunkelman, Nathan Keller: Improved Slide Attacks [10] , gør det muligt at finde skiftpar meget hurtigere ved hjælp af en cyklisk chifferstruktur og tilsvarende nøglepermutationer. Driften af ​​denne modifikation blev vist på eksemplet med forskellige varianter af GOST 28147-89 (GOST) chiffer.

Krypteringsalgoritmer sårbare over for skiftende angreb og dets modifikationer

Beskrevet i de originale artikler: [1] [5]

Beskrevet i andre kilder

Skift-angreb af klassen af ​​hash-funktioner [13]

Ud over deres oprindelige formål - at angribe blokcifre, har principperne for shift-angrebet også fundet anvendelse inden for hashfunktionskryptanalyse. I lighed med tilfældet med blokcifre, hvor et skiftangreb er blevet brugt til at finde nøgleskemaet, har det vist sig at være potentielt anvendeligt til at finde den hemmelige nøgle, der bruges til at generere og validere hashen af ​​den transmitterede meddelelse. Især blev denne tilgang demonstreret på eksemplet med generering af simuleret indsættelse (MAC) .

Skiftangrebet viste sig også at være nyttigt, ikke kun i tilfælde af kryptografiske hash-funktioner, der tager værdien af ​​en hemmelig nøgle som en parameter, men også i tilfælde af hash-funktioner, der kun producerer en hash baseret på en besked. En analyse af sådanne funktioner baseret på et skiftangreb gør det muligt med en høj grad af sandsynlighed at identificere nogle skiftegenskaber og som et resultat visse mønstre i driften af ​​hashing-algoritmer.

Hash-funktioner sårbare over for shift-angreb: [13]

Måder at øge kryptografisk modstand mod ændringer af skiftangreb [7] [16]

Da nøgleskemaets sårbarheder bruges under skiftangrebet, er en af ​​foranstaltningerne at komplicere det. Det er især nødvendigt at undgå cykliske gentagelser i nøgleskemaet, hvis det er muligt, eller i det mindste bruge en tilstrækkelig lang gentagelsesperiode. I tilfælde af et lille antal taster, i stedet for en simpel periodisk gentagelse, bør en tilfældig rækkefølge af deres rækkefølge anvendes.

Ud over svagheden i nøgleskemaet udnytter skiftangrebet også de samme runder. En måde at undgå dette på er at bruge nogle forskellige runde konstanter som parameter for krypteringsfunktionen på separate runder - dette giver dig mulighed for at gøre forskelle i driften af ​​individuelle krypteringsblokke uden at komplicere krypteringsalgoritmen som helhed væsentligt.

Effektiviteten af ​​et skifteangreb kan også reduceres betydeligt ved at øge den kryptografiske styrke af den runde krypteringsfunktion. Så dens modstand mod angreb baseret på klartekster vil gøre det meget sværere at finde den runde nøgle selv i nærvær af et skiftpar.

Noter

  1. 1 2 3 4 5 6 7 Alex Biryukov, David Wagner. Slide-angreb  //  Hurtig softwarekryptering. 6th International Workshop, FSE'99 Rom, Italien, 24.-26. marts, 1999 Proceedings. - Springer Berlin Heidelberg, 1999. - S. 245-259 . - ISBN 978-3-540-66226-6 .  (utilgængeligt link)
  2. EK Grossman, Thomas J. Watson IBM Research Center Research Division, B. Tuckerman. Analyse af en Feistel-lignende chiffer svækket ved at have ingen roterende nøgle . - IBM Thomas J. Watson Research Division, 1977. - 33 s.
  3. Eli Biham, Adi Shamir. Differentiel krypteringsanalyse af DES-lignende kryptosystemer  //  Fremskridt i kryptologi-CRYPT0' 90 Proceedings. - Springer Berlin Heidelberg, 1990. - S. 2-21 . — ISBN 978-3-540-54508-8 .  (utilgængeligt link)
  4. B. Preneel, V. Rijmen, A. Bosselears. Principper og ydeevne for kryptografiske algoritmer  //  Dr. Dobbs Journal. - Miller Freeman, 1998. - Vol. 23 , nr. 12 . - S. 126-131 .
  5. 1 2 3 4 5 6 Alex Biryukov, David Wagner. Advanced Slide Attacks  (engelsk)  // Advances in Cryptology - EUROCRYPT 2000. International konference om teori og anvendelse af kryptografiske teknikker Brugge, Belgien, 14.-18. maj 2000 Proceedings. - Springer Berlin Heidelberg, 2000. - S. 589-606 . — ISBN 978-3-540-67517-4 .  (utilgængeligt link)
  6. 1 2 Panasenko S.P. Shift-angreb // Krypteringsalgoritmer. Særlig opslagsbog - St. Petersborg. : BHV-SPb , 2009. - S. 40-42. — 576 s. — ISBN 978-5-9775-0319-8
  7. 1 2 3 4 5 Chalermpong Worawannotai, Isabelle Stanton. En vejledning om diasangreb  . Arkiveret fra originalen den 29. november 2014.
  8. Raphael C.-W. Phan. Advanced Slide Attacks Revisited: Realigning Slide on DES  //  Progress in Cryptology – Mycrypt 2005. Første internationale konference om kryptologi i Malaysia, Kuala Lumpur, Malaysia, 28.-30. september 2005. Proceedings. - Springer Berlin Heidelberg, 2005. - S. 263-276 . — ISBN 978-3-540-28938-8 . Arkiveret fra originalen den 12. juni 2018.
  9. 1 2 Soichi Furuya. Slide-angreb med en kendt almindelig tekst-krypteringsanalyse  (engelsk)  // Informationssikkerhed og kryptologi - ICISC 2001. 4. internationale konference Seoul, Korea, 6.-7. december 2001 Proceedings. - Springer Berlin Heidelberg, 2002. - S. 214-225 . - ISBN 978-3-540-43319-4 . Arkiveret fra originalen den 9. juni 2018.
  10. Eli Biham, Orr Dunkelman, Nathan Keller. Forbedrede diasangreb  //  Hurtig softwarekryptering. 14th International Workshop, FSE 2007, Luxembourg, Luxembourg, 26.-28. marts 2007, Revised Selected Papers. - Springer Berlin Heidelberg, 2007. - S. 153-166 . — ISBN 978-3-540-74617-1 .  (utilgængeligt link)
  11. Selçuk Kavut, Melek D. Yücel. Slide Attack on Spectr-H64  //  Progress in Cryptology - INDOCRYPT 2002. Tredje internationale konference om kryptologi i Indien Hyderabad, Indien, 16.-18. december 2002 Proceedings. - Springer Berlin Heidelberg, 2002. - S. 34-47 . - ISBN 978-3-540-00263-5 . Arkiveret fra originalen den 11. juni 2018.
  12. Nicolas T. Courtois, Gregory V. Bard, David Wagner. Algebraiske og slideangreb på KeeLoq  //  Hurtig softwarekryptering. 15th International Workshop, FSE 2008, Lausanne, Schweiz, 10.-13. februar 2008, Revised Selected Papers. - Springer Berlin Heidelberg, 2008. - S. 97-115 . — ISBN 978-3-540-71038-7 . Arkiveret fra originalen den 30. oktober 2018.
  13. 1 2 Michael Gorski, Stefan Lucks, Thomas Peyrin. Slide-angreb på en klasse af hash-funktioner  //  Fremskridt inden for kryptologi - ASIACRYPT 2008. 14. internationale konference om teori og anvendelse af kryptologi og informationssikkerhed, Melbourne, Australien, 7.-11. december 2008. Proceedings. - Springer Berlin Heidelberg, 2008. - S. 143-160 . - ISBN 978-3-540-89254-0 .  (utilgængeligt link)
  14. Yu Sasaki, Lei Wang, Kazuo Ohta, Noboru Kunihiro. Password Recovery on Challenge and Response: Impossible Differential Attack on Hash Function  //  Fremskridt i kryptologi – AFRICACRYPT 2008. Første internationale konference om kryptologi i Afrika, Casablanca, Marokko, 11.-14. juni 2008. Proceedings. - Springer Berlin Heidelberg, 2008. - S. 290-307 . — ISBN 978-3-540-68159-5 . Arkiveret fra originalen den 6. juni 2018.
  15. 1 2 Markku-Juhani O. Saarinen. Krypteringsanalyse af blokchiffere baseret på SHA-1 og MD5  //  Hurtig softwarekryptering. 10th International Workshop, FSE 2003, Lund, Sverige, 24.-26. februar 2003. Reviderede papirer. - Springer Berlin Heidelberg, 2003. - S. 36-44 . — ISBN 978-3-540-20449-7 .  (utilgængeligt link)
  16. Francois-Xavier Standaert, Gilles Piret, Jean-Jacques Quisquater. Krypteringsanalyse af blokcifre: En undersøgelse  //  UCL Crypto Group Technical Report Series. - 2003. Arkiveret 10. februar 2014.