Differentiell kryptoanalys

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

Differentiell kryptoanalys är en metod för kryptoanalys av symmetriska blockchiffer (och andra kryptografiska primitiver , i synnerhet hashfunktioner och strömchiffer ).

Differentiell kryptoanalys baseras på studien av omvandlingen av skillnaderna mellan krypterade värden i olika omgångar av kryptering . Som en skillnad, som regel, används operationen av bitvis summering modulo 2 , även om det finns attacker med beräkningen av skillnaden modulo . Det är en statistisk attack. Tillämplig för att spricka DES , FEAL och några andra chiffer, som regel, utvecklade tidigare än början av 90-talet. Antalet omgångar av moderna chiffer ( AES , Camellia , etc.) beräknades med hänsyn till säkerhet , inklusive differentiell kryptoanalys. $2^{32}$

Historik

Differentiell kryptoanalys föreslogs 1990 av de israeliska experterna Eli Biham och Adi Shamir för att bryta kryptosystem som DES. I sitt arbete visade de att DES-algoritmen visade sig vara ganska resistent mot denna kryptoanalysmetod, och varje minsta förändring i algoritmens struktur gör den mer sårbar.

1994 publicerade IBM :s Don Coppersmith en artikel [1] som påstod att metoden för differentiell kryptoanalys var känd för IBM redan 1974, och ett av målen med att utveckla DES var att skydda mot denna metod. IBM hade sina hemligheter. Coppersmith förklarade:

Designen drog fördel av vissa kryptoanalytiska metoder, särskilt metoden "differentiell kryptoanalys", som inte har publicerats i den öppna litteraturen. Efter diskussioner med NSA beslutades det att avslöjande av designprocessen också skulle avslöja en metod för differentiell kryptoanalys vars kraft kunde användas mot många chiffer. Detta skulle i sin tur minska USA:s fördel gentemot andra länder inom kryptografi.

DES visade sig vara kryptografiskt resistent mot differentiell kryptoanalys, till skillnad från vissa andra chiffer. Så till exempel visade sig FEAL- chifferet vara sårbart . En 4-round FEAL-4 kan knäckas med så lite som 8 valda klartexter , och även en 31-round FEAL är sårbar för attack.

DES Hacking Scheme

År 1990 hittade Eli Biham och Adi Shamir , med hjälp av differentiell kryptoanalys, ett sätt att bryta DES som var mer effektivt än brute force. Genom att arbeta med par av chiffertexter vars klartexter har vissa skillnader, har forskare analyserat utvecklingen av dessa skillnader när klartexterna passerar genom stadierna av DES .

Enkelrunda analys

Den grundläggande metoden för differentiell kryptoanalys är den adaptivt valda klartextattacken , även om den har en förlängning för klartextattack . För att utföra attacken används par av klartexter kopplade med en viss skillnad. För DES och DES-liknande system definieras det som exklusivt ELLER (XOR) . Vid dekryptering behövs endast värdet av motsvarande chiffertextpar.

Diagrammet visar Feistel-funktionen . Låt och vara ett par ingångar som skiljer sig med . De utgångar som motsvarar dem är kända och lika med och , skillnaden mellan dem är . Permutationen med förlängning och -block är därför också kända och är också kända . och är okända, men vi vet att deras skillnad är , eftersom skillnader c och neutraliseras. De enda icke-linjära elementen i kretsen är -block. För varje -block kan du lagra en tabell, vars rader är skillnaderna vid ingången av -blocket, kolumnerna är skillnaderna vid utgången, och vid skärningspunkten - antalet par som har gett input och output skillnader, och någonstans att lagra dessa par själva. $X$ $X'$ $\Delta X$ $Y$ $Y'$ $\Delta Y$ $P$ $\Delta A$ $\Delta C$ $B$ $B'$ $\Delta A$ $XOR\ K_{{i}}$ $A$ $A'$ $S$ $S$ $S$

Att öppna den runda nyckeln är baserad på det faktum att för ett givet värde är inte alla värden lika sannolika, men kombinationen av och låter oss anta värdena och . För känt och detta tillåter oss att bestämma . Med undantag för all nödvändig information för den sista omgången finns i det sista paret av chiffertexter. $\Delta A$ $\Delta C$ $\Delta A$ $\Delta C$ $A\ XOR\ K_{{i}}$ $A'\ XOR\ K_{{i}}$ $A$ $A'$ $K_{{i}}$ $\Delta C$

Efter att ha bestämt rundnyckeln för den sista cykeln blir det möjligt att delvis dekryptera chiffertexterna och sedan använda ovanstående metod för att hitta alla runda nycklar.

Egenskaper

För att bestämma de möjliga skillnaderna mellan de chiffertexter som tas emot vid den i:te omgången, används runda egenskaper .

N-runda karakteristiken är en tupel , sammansatt av skillnader i klartext, chiffertextskillnader och en uppsättning skillnader i mellanliggande krypteringsresultat för varje tidigare omgång. $\Omega \ =\ (\Omega _{{P)),\Omega _({\Lambda )),\Omega _{{T)))$ $\Omega _{{P}}$ $\Omega _{{T}}$ $\Omega _{{\Lambda }}\ =\ (\Lambda _{{1}},\Lambda _{{2}},\ ...\ ,\Lambda _{{n}})$

Karaktäristiken tilldelas en sannolikhet lika med sannolikheten att ett slumpmässigt par klartexter med en skillnad till följd av kryptering med slumpmässiga nycklar har runda skillnader och chiffertextskillnader som matchar de som anges i egenskapen. Ett par öppna texter som motsvarar egenskapen kallas "korrekt" . Par öppna texter som inte motsvarar egenskapen kallas "felaktiga" . $\Omega _{{P}}$

Låt oss ta värdet av skillnaden mellan texter vid utgången av den näst sista cykeln, som används för att bestämma den möjliga undernyckeln för den sista omgången, . I ett sådant fall bestämmer det "rätta" textparet rätt nyckel, medan det "fel" paret bestämmer en slumpmässig nyckel. $\Delta A=\Omega _{{T}}$

Vid en attack används vanligtvis flera egenskaper samtidigt. Strukturer används vanligtvis för att spara minne.

En kvartett är en struktur av fyra texter, som samtidigt innehåller två par texter för två olika egenskaper. Gör att du kan spara 1/2 av minnet för klartext.
Oktett - en struktur av 16 texter som innehåller 8 par, 4 för varje egenskap. Gör att du kan spara 2/3 av minnet för klartext.

Signal-brusförhållande

För alla nyckelalternativ kan du skapa räknare, och om något par föreslår detta alternativ som en giltig nyckel kommer vi att öka motsvarande räknare. Nyckeln som motsvarar den största räknaren har stor sannolikhet att vara korrekt.

För vårt beräkningsschema kommer förhållandet mellan antalet korrekta par S och medelvärdet för räknaren N att kallas signal-brusförhållandet och kommer att betecknas med . $S/N$

För att hitta rätt nyckel och se till att rätt par finns, måste du:

egenskap med tillräcklig sannolikhet;
tillräckligt många par.

Antalet obligatoriska par bestäms av:

sannolikheten för egenskapen;
antalet nyckelbitar (de bitar vi vill definiera);
nivån för identifiering av felaktiga par (par bidrar inte till räknarna, eftersom de kasseras tidigare).

Låt nyckelstorleken vara k bitar, då behöver vi räknare. Om en: $2^k$

m är antalet använda par;
$\alfa$ - det genomsnittliga tillägget till räknarna för ett par;
$\beta$ är förhållandet mellan par som bidrar till räknarna till alla par (inklusive kasserade),

då är medelvärdet för räknaren N :

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

Om är sannolikheten för egenskapen, då är antalet korrekta par S lika med: $sid$

S=m\cdot sid.

Då är signal-brusförhållandet :

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

Observera att för vårt designschema beror signal-brusförhållandet inte på det totala antalet par. Antalet giltiga par som behövs är i allmänhet en funktion av signal-brusförhållandet . Det fastställdes experimentellt att om S/N=1-2 är 20-40 förekomster av korrekta par nödvändiga. Om förhållandet är mycket högre kan till och med 3-4 korrekta par vara tillräckligt. Slutligen, när det är mycket lägre, är antalet par som krävs enormt.

S/N	Antal par krävs
mindre än 1	Veliko
1-2	20-40
mer än 2	3-4

Hack effektivitet

Med en ökning av antalet omgångar ökar komplexiteten för kryptoanalys, men den förblir mindre än komplexiteten i en uttömmande sökning när antalet cykler är mindre än 16.

Beroende på antalet omgångar
Antal omgångar	Attackens komplexitet
$fyra$	$2^{{4}}$
$6$	$2^{{8}}$
$åtta$	$2^{16}$
$9$	$2^{26}$
$tio$	$2^{{35}}$
$elva$	$2^{{36}}$
$12$	$2^{43}$
$13$	$2^{{44}}$
$fjorton$	$2^{{51}}$
$femton$	$2^{{52}}$
$16$	$2^{{58}}$

Utformningen av S-boxar påverkar också avsevärt effektiviteten av differentiell kryptoanalys. DES S-boxar är i synnerhet optimerade för attackmotstånd.

Jämförelse med andra metoder

Se Kända attacker på DES

Differentiell kryptoanalys och DES-liknande system

Medan fullständig 16-runda DES ursprungligen designades för att vara resistent mot differentiell kryptoanalys, visade sig attacken vara framgångsrik mot en bred grupp av DES-liknande chiffer [2] .

Lucifer , förkortad till åtta omgångar, bryter med mindre än 60 chiffertexter.
FEAL -8 är knäckt med mindre än 2000 chiffertexter.
FEAL-4 är knäckt med 8 chiffertexter och en klartext .
FEAL-N och FEAL-NX kan hackas med . $N\leq 31$

Differentiell kryptoanalys är också tillämplig mot hashfunktioner .

Efter publiceringen av arbeten om differentiell kryptoanalys i början av 1990-talet designades efterföljande chiffer för att vara resistenta mot denna attack.

Nackdelar med metoden

Metoden för differentiell kryptoanalys är till stor del en teoretisk prestation. Dess tillämpning i praktiken begränsas av höga krav på tid och datavolym.

Eftersom differentiell kryptoanalys i första hand är en vald-klartext-attackmetod är det svårt att implementera i praktiken. Det kan användas för att attackera med känd klartext, men i fallet med en fullständig 16-runda DES gör detta den ännu mindre effektiv än en brute-force attack.

Metoden kräver en stor mängd minne för att lagra kandidatnycklar. Metodens effektivitet beror också starkt på strukturen hos S-boxarna för den hackade algoritmen.

Se även

Anteckningar

↑ Kopparsmed, Don. Data Encryption Standard (DES) och dess styrka mot attacker // IBM Journal of Research and Development : journal. - 1994. - Maj ( vol. 38 , nr 3 ). — S. 243 . - doi : 10.1147/rd.383.0243 . (prenumeration krävs)
↑ Biham E. , Shamir A. Differentiell kryptoanalys av DES-liknande kryptosystem . - 1990. - P. 7 .

Litteratur

Bruce Schneier. Tillämpad kryptografi. Protokoll, algoritmer, källtexter i C-språk.
Panasenko, S. "Moderne metoder för att knäcka krypteringsalgoritmer, del 3" . Informationschef - 2006 . Arkiverad 15 januari 2010 på Wayback Machine
Biham E. , Shamir A. Differentiell kryptoanalys av Data Encription Standard.
Biham E. , Shamir A. Differentiell kryptoanalys av DES-liknande kryptosystem (engelska) . — 1990.