Differentiel kryptoanalyse

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 3. januar 2020; checks kræver 5 redigeringer .

Differentiel kryptoanalyse er en metode til kryptoanalyse af symmetriske blokcifre (og andre kryptografiske primitiver , især hash-funktioner og stream-cifre ).

Differentiel krypteringsanalyse er baseret på undersøgelsen af transformationen af forskellene mellem krypterede værdier i forskellige runder af kryptering . Som en forskel bruges som regel operationen af bitvis summering modulo 2 , selvom der er angreb med beregningen af differencen modulo . Det er et statistisk angreb. Anvendelig til at knække DES , FEAL og nogle andre cifre, som regel udviklet tidligere end begyndelsen af 90'erne. Antallet af runder af moderne ciphers ( AES , Camellia , etc.) blev beregnet under hensyntagen til sikkerhed , herunder differentiel kryptoanalyse. $2^{32}$

Historie

Differentiel kryptoanalyse blev foreslået i 1990 af de israelske eksperter Eli Biham og Adi Shamir for at bryde kryptosystemer som DES. I deres arbejde viste de, at DES-algoritmen viste sig at være ret modstandsdygtig over for denne kryptoanalysemetode, og enhver mindste ændring i strukturen af algoritmen gør den mere sårbar.

I 1994 publicerede IBMs Don Coppersmith en artikel [ 1 ] hvori det blev fastslået, at metoden til differentiel kryptoanalyse var kendt af IBM allerede i 1974, og et af målene med udviklingen af DES var at beskytte mod denne metode. IBM havde sine hemmeligheder. Coppersmith forklarede:

Designet udnyttede visse kryptoanalytiske metoder, især metoden "differentiel kryptoanalyse", som ikke er blevet offentliggjort i den åbne litteratur. Efter diskussioner med NSA blev det besluttet, at afsløring af designprocessen også ville afsløre en metode til differentiel kryptoanalyse, hvis kraft kunne bruges mod mange cifre. Dette vil igen reducere USA's fordel i forhold til andre lande inden for kryptografi.

DES viste sig at være kryptografisk modstandsdygtig over for differentiel kryptoanalyse, i modsætning til nogle andre chiffer. Så for eksempel viste FEAL -chifferet sig at være sårbart . En 4-runders FEAL-4 kan knækkes med så lidt som 8 valgte klartekster , og selv en 31-runders FEAL er sårbar over for angreb.

DES Hacking Scheme

I 1990 fandt Eli Biham og Adi Shamir , ved hjælp af differentiel kryptoanalyse, en måde at bryde DES på, som var mere effektiv end brute force. Ved at arbejde med par af chiffertekster , hvis klartekster har visse forskelle, har videnskabsmænd analyseret udviklingen af disse forskelle, efterhånden som klarteksterne passerer gennem stadierne af DES .

Enkelt runde analyse

Den grundlæggende metode til differentiel kryptoanalyse er det adaptivt valgte klartekstangreb , selvom det har en udvidelse til klartekstangreb . For at udføre angrebet bruges par af klartekster forbundet med en vis forskel. For DES og DES-lignende systemer er det defineret som eksklusive ELLER (XOR) . Ved dekryptering er det kun nødvendigt med værdien af de tilsvarende chiffertekstpar.

Diagrammet viser Feistel-funktionen . Lad og vær et par input, der adskiller sig med . De udgange, der svarer til dem, er kendte og lig med og , forskellen mellem dem er . Permutationen med forlængelse og -blok er derfor også kendt og er også kendt . og er ukendte, men vi ved, at deres forskel er , fordi forskelle c og neutraliseres. De eneste ikke-lineære elementer i kredsløbet er -blokke. For hver -blok kan du gemme en tabel, hvis rækker er forskellene ved input af -blokken, kolonnerne er forskellene ved output, og i skæringspunktet - antallet af par, der har givet input og output forskelle, og et sted at opbevare disse par selv. $x$ $X'$ $\Delta X$ $Y$ $Y'$ $\Delta Y$ $P$ $\Delta A$ $\Delta C$ $B$ $B'$ $\Delta A$ $XOR\ K_{{i}}$ $EN$ $EN'$ $S$ $S$ $S$

Åbning af den runde nøgle er baseret på det faktum, at for en given værdi er ikke alle værdier lige sandsynlige, men kombinationen af og giver os mulighed for at antage værdierne og . For kendt og dette giver os mulighed for at bestemme . Med undtagelse af alle de nødvendige oplysninger for den sidste runde er indeholdt i det sidste par chiffertekster. $\Delta A$ $\Delta C$ $\Delta A$ $\Delta C$ $A\ XOR\ K_{{i}}$ $A'\ XOR\ K_{{i}}$ $EN$ $EN'$ $K_{{i}}$ $\Delta C$

Efter at have bestemt rundnøglen for den sidste cyklus, bliver det muligt delvist at dekryptere chifferteksterne og derefter bruge ovenstående metode til at finde alle rundnøglerne.

Karakteristika

For at bestemme de mulige forskelle mellem de chiffertekster, der modtages i den i-te runde, bruges runde karakteristika .

N-runde-karakteristikken er en tupel , der er sammensat af klartekstforskelle , chiffertekstforskelle og et sæt forskelle i mellemliggende krypteringsresultater for hver tidligere runde. $\Omega \ =\ (\Omega _{{P)),\Omega _({\Lambda )),\Omega _{{T)))$ $\Omega _{{P}}$ $\Omega _{{T}}$ $\Omega _{{\Lambda }}\ =\ (\Lambda _{{1}},\Lambda _{{2}},\ ...\ ,\Lambda _{{n}})$

Karakteristikken tildeles en sandsynlighed svarende til sandsynligheden for, at et tilfældigt par af klartekster med en forskel som følge af kryptering med tilfældige nøgler har runde forskelle og chiffertekstforskelle, der matcher dem, der er angivet i karakteristikken. Et par åbne tekster svarende til karakteristikken kaldes "korrekt" . Par åbne tekster, der ikke svarer til karakteristikken, kaldes "forkerte" . $\Omega _{{P}}$

Lad os tage værdien af forskellen mellem tekster ved udgangen af den næstsidste cyklus, brugt til at bestemme den mulige undernøgle til sidste runde, . I et sådant tilfælde bestemmer det "korrekte" tekstpar den rigtige nøgle, mens det "forkerte" par bestemmer en tilfældig nøgle. $\Delta A=\Omega _{{T}}$

I et angreb bruges flere karakteristika normalt samtidigt. Strukturer bruges almindeligvis til at bevare hukommelsen.

En kvartet er en struktur af fire tekster, som samtidigt indeholder to par tekster for to forskellige karakteristika. Giver dig mulighed for at gemme 1/2 af hukommelsen til almindelig tekst.
Oktet - en struktur på 16 tekster indeholdende 8 par, 4 for hver karakteristik. Giver dig mulighed for at gemme 2/3 af hukommelsen til almindelig tekst.

Signal-til-støj-forhold

For alle nøglemuligheder kan du oprette tællere, og hvis et par foreslår denne mulighed som en gyldig nøgle, vil vi øge den tilsvarende tæller. Den nøgle, der svarer til den største tæller, har stor sandsynlighed for at være korrekt.

For vores beregningsskema vil forholdet mellem antallet af korrekte par S og gennemsnitsværdien af tælleren N blive kaldt signal-til-støj-forholdet og vil blive betegnet med . $S/N$

For at finde den rigtige nøgle og sikre, at de korrekte par er til stede, skal du:

karakteristisk med tilstrækkelig sandsynlighed;
par nok.

Antallet af nødvendige par bestemmes af:

sandsynligheden for karakteristikken;
antallet af nøglebits (de bits, vi ønsker at definere);
niveauet for identifikation af fejlagtige par (par bidrager ikke til tællerne, da de kasseres tidligere).

Lad nøglestørrelsen være k bit, så skal vi bruge tællere. Hvis en: $2^k$

m er antallet af brugte par;
$\alfa$ - den gennemsnitlige tilføjelse til tællerne for et par;
$\beta$ er forholdet mellem par, der bidrager til tællerne i forhold til alle par (inklusive kasserede),

så er gennemsnitsværdien af tælleren N :

N={\frac {m\cdot \alpha \cdot \beta }{2^{{k))))

Hvis er sandsynligheden for karakteristikken, så er antallet af korrekte par S lig med: $s$

S=m\cdot s.

Så er signal-til-støj-forholdet :

S/N={\frac {m\cdot p}{m\cdot \alpha \cdot \beta /2^{{k))))={\frac {2^{{k))\cdot p}{ \alpha \cdot \beta }}.

Bemærk, at for vores designskema afhænger signal-til-støj-forholdet ikke af det samlede antal par. Antallet af nødvendige gyldige par er generelt en funktion af signal-til-støj-forholdet . Det blev eksperimentelt fastslået, at hvis S/N=1-2 , er 20-40 forekomster af korrekte par nødvendige. Hvis forholdet er meget højere, så kan selv 3-4 rigtige par være nok. Endelig, når det er meget lavere, er antallet af nødvendige par enormt.

S/N	Antal par påkrævet
mindre end 1	Veliko
1-2	20-40
mere end 2	3-4

Hack effektivitet

Med en stigning i antallet af runder øges kompleksiteten af kryptoanalyse, men den forbliver mindre end kompleksiteten af udtømmende søgning, når antallet af cyklusser er mindre end 16.

Afhængighed af antallet af runder
Antal runder	Kompleksiteten af angrebet
$fire$	$2^{{4}}$
$6$	$2^{{8}}$
$otte$	$2^{16}$
$9$	$2^{26}$
$ti$	$2^{{35}}$
$elleve$	$2^{{36}}$
$12$	$2^{43}$
$13$	$2^{{44}}$
$fjorten$	$2^{{51}}$
$femten$	$2^{{52}}$
$16$	$2^{{58}}$

Designet af S-bokse påvirker også i væsentlig grad effektiviteten af differentiel kryptoanalyse. DES S-bokse er især optimeret til angrebsmodstand.

Sammenligning med andre metoder

Se Kendte angreb på DES

Differentiel kryptoanalyse og DES-lignende systemer

Mens fuld 16-rund DES oprindeligt blev designet til at være modstandsdygtig over for differentiel kryptoanalyse, viste angrebet sig vellykket mod en bred gruppe af DES-lignende ciphers [2] .

Lucifer , forkortet til otte runder, bryder med mindre end 60 chiffertekster.
FEAL -8 er knækket ved hjælp af mindre end 2000 chiffertekster.
FEAL-4 er cracket ved hjælp af 8 chiffertekster og en almindelig tekst .
FEAL-N og FEAL-NX kan hackes med . $N\leq 31$

Differentiel kryptoanalyse er også anvendelig mod hash-funktioner .

Efter udgivelsen af værker om differentiel kryptoanalyse i begyndelsen af 1990'erne, blev efterfølgende cifre designet til at være modstandsdygtige over for dette angreb.

Ulemper ved metoden

Metoden til differentiel kryptoanalyse er stort set en teoretisk præstation. Dens anvendelse i praksis er begrænset af høje krav til tid og datamængde.

Da differentiel krypteringsanalyse primært er en valgt almindelig tekstangrebsmetode, er det vanskeligt at implementere i praksis. Det kan bruges til at angribe med kendt klartekst, men i tilfælde af en fuld 16-rund DES gør dette det endnu mindre effektivt end et brute-force angreb.

Metoden kræver en stor mængde hukommelse til at gemme kandidatnøgler. Metodens effektivitet afhænger også stærkt af strukturen af den hackede algoritmes S-bokse.

Se også

Noter

↑ Kobbersmed, Don. Data Encryption Standard (DES) og dens styrke mod angreb // IBM Journal of Research and Development : journal. - 1994. - Maj ( bd. 38 , nr. 3 ). — S. 243 . - doi : 10.1147/rd.383.0243 . (kræver abonnement)
↑ Biham E. , Shamir A. Differentiel kryptoanalyse af DES-lignende kryptosystemer . - 1990. - S. 7 .

Litteratur

Bruce Schneier. Anvendt kryptografi. Protokoller, algoritmer, kildetekster i C-sprog.
Panasenko, S. "Moderne metoder til cracking af krypteringsalgoritmer, del 3" . Chief Information Officer - 2006 . Arkiveret 15. januar 2010 på Wayback Machine
Biham E. , Shamir A. Differentiel kryptoanalyse af datakrypteringsstandarden.
Biham E. , Shamir A. Differentiel kryptoanalyse af DES-lignende kryptosystemer (engelsk) . - 1990.