Nyckelgissad attack

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 21 mars 2015; kontroller kräver 24 redigeringar .

Vald-nyckel attack är en av metoderna för kryptoanalytisk attack , som övervakar driften av en krypteringsalgoritm som använder flera hemliga nycklar . En kryptoanalytiker har till en början bara information om ett visst matematiskt förhållande som länkar ihop nycklarna.

Beskrivning

Enligt Kerckhoffs princip har kryptoanalytikern all nödvändig information om krypteringssystemet som används, förutom en viss uppsättning hemliga parametrar som kallas nyckeln. En kryptoanalytiker känner bara till förhållandet mellan ett par nycklar. Den använder chiffertexten och det givna förhållandet för att gissa båda nycklarna. Två typer av valda nyckelattacker är kända: den valda nyckeln och den kända klartextattacken, där endast relationen mellan nyckelparet specificeras av kryptoanalytikern, och den valda nyckel- och klartextattacken, där kryptoanalytikern ställer in både relationen mellan nyckelpar och och själva klartexten, som ska krypteras. [ett]

En attack baserad på en utvald nyckel utförs på samma sätt på alla kryptosystem, inklusive den så kallade "svarta lådan", där alla egenskaper är okända. Denna "svarta låda" använder krypteringsfunktionen , som väljs på samma sätt för slumpmässiga permutationer av meddelanden. Bitarna i nyckeln väljs slumpmässigt, så att kunskap om chiffertexten inte kan berätta något om chiffertexten för nyckeln . ${\displaystyle E_{k))$ $k$ $E_{k}(m)$ $E_{h}(m')$ $h\neq k$

Attackalgoritmen baserad på den valda nyckeln på den "svarta lådan", förutom standardoperationer, kan när som helst för beräkningen kräva:

kryptera eller dekryptera med den hemliga nyckeln och det matchade meddelandet och inversionsvektorn , $E_{k\oplus l}(m)$ $E_{k\oplus l}^{-1}(m)$ $k$ $m$ $l$
använd den "svarta rutan" för beräkning eller med hjälp av en nyckel (som inte är en funktion ) genom att plocka upp ett meddelande . $E_{h}(m)$ $E_{h}^{-1}(m)$ $h$ $k$ $m$

Algoritmen kan också ha tillgång till en slumpmässig bitgenerator. I slutet av beräkningen matas den uppskattade nyckeln ut . [2] $k$

Således, om användaren använder en hemlig nyckel och ett offentligt kryptosystem ( public key cryptosystem ), kan kryptoanalytikern när som helst välja ett meddelande och en inversionsvektor och utföra kryptering eller dekryptering . Huvudapplikationen för en gissad nyckelattack är att verifiera system, men under vissa omständigheter kan denna attack tillämpas i praktiken. Om ett strömchiffer används för att överföra en sessionsnyckel från användare till användare , och kryptoanalytikern får kontroll över transmissionslinjen, kan han ändra vilka bitar av nyckeln som helst efter eget tycke och kommer att få den ändrade nyckeln istället för . Sedan, när den börjar sända med fel nyckel, kommer den att få ett förvrängt meddelande och påbörja återställningsproceduren. Under tiden kommer kryptoanalytikern att få texten krypterad med nyckeln. (Bra kryptoskydd kan avvärja sådana attacker genom att använda nya oberoende sessionsnycklar eller genom att lägga till icke-linjära feldetekteringsbitar till sessionsnyckeln närhelst en återställningsprocedur behövs. Historien visar dock att bra kryptoskydd inte alltid följer detta och det är önskvärt att ha ett system som inte kraschar under sådan attack) [3] . $k$ $E$ $m$ $l$ $E_{{k\oplus l}}$ $E_{{k\oplus l}}^{{-1}}$ $k$ $A$ $B$ $B$ $k\oplus l$ $k$ $B$ $A$ $k\oplus l$

Den huvudsakliga typen av attack baserat på en vald nyckel

I denna del kommer vi att överväga en attack som inte beror på en specifik svaghet i krypteringsfunktionen. Det är en man-i-mitten-attack ( MITM ). Denna typ av attack gör att du kan minska tiden för den avancerade sökningen, beroende på antalet tillåtna nyckelinversioner [4] .

Sats. Låta vara ett blockchiffer med en n-bitars nyckel. Antag att kryptoanalytikern kan utföra inversioner och har minnesord. Då kommer han att kunna knäcka chifferet i extra steg [4] . $E$ $2^{p}$ $2^{p}$ $E$ $2^{{np}}$

Bevis:

Analytikern ersätter de sista bitarna i nyckeln på alla möjliga sätt. Till exempel krypterar den värdena $sid$ $2^{p}$

E_{k}(m),E_{{k\oplus (00\dots 01)}}(m),\dots ,E_{{k\oplus j}}(m),\ldots ,E_{{k\ oplus (00\dots 011\dots 1)}}(m)

var är användarens privata nyckel och eventuellt lämpligt meddelande. Den skapar en hashtabell från värdena [4] . $k$ $m$ $2^{p}$ $(E_{{k\oplus j}},j)$

Den utför sedan kryptering genom att ändra de första bitarna i nyckeln och återställa de sista bitarna: $2^{{np}}$ $np$ $sid$

E_{{(00\dots 0)}}(m),E_{{(00\dots 10\dots )}}(m),\dots ,E_{{(11\dots 10\ldots 0)}}( m)

Efter alla beräkningar kontrolleras varje värde mot hashtabellen [4] .

Om den ursprungliga nyckeln är knäckt genom , där består av de sista bitarna, kommer posten att matcha resultatet genom kryptering i det andra steget. När en matchning hittas kommer det att vara en kandidatnyckel. Flera falska larm är möjliga om flera nycklar matchar meddelandet , men som i en matchad textattack kommer ett eller två ytterligare block av känd klartext nästan säkert att utesluta dem, med liten inverkan på körtiden [4] . $k$ $(a,b)$ $b$ $sid$ $(E_{{k\oplus b}},b)$ $a^{{th}}$ $(a,b)$ $m$

Slutsats: Genom att använda ett obegränsat antal attacker med utvalda nyckel, kan alla blockchiffer med en n-bitars nyckel brytas genom att inte använda mer än beräkningar i minnet [4] . $O(2^{{n/2}})$

Bevis: Låt oss välja . $p=n/2$

Obs: För ett stort antal exempel och en stor mängd tillgängligt minne kommer det att vara mycket effektivare att byta ut de två stegen i beviset på satsen. Beräkna och lagra krypteringar i minnet. För varje uppgift, utför inversioner och kontrollera tabellen för efterlevnad. Således kommer iterationer att spenderas på varje ytterligare uppgift [4] . $2^{{np}}$ $2^{p}$ $2^{p}$

Sårbarhet för blockkod för attack baserat på vald nyckel

Vi kommer att demonstrera förmågan hos denna typ av attack mot ett kryptosystem, som har visat sig vara extremt motståndskraftigt mot en matchad textattack [3] .

Låt vara ett hemligt blockchiffer med en nyckelstorlek av bitar. Låt oss definiera ett nytt blockchiffer . $E$ $n$ $F$

F_{k}(m)=E_{k}(m)

om den första biten är 0

k

F_{k}(m)=E_{{k'}}(m)\oplus k

i andra fall, där resultatet av inverteringen av den första biten är till exempel .

k'

k

k'=k\oplus(1,0,\ldots ,0)

F

legitimt blockchiffer:

F_{k}^{{-1}}(m)=E_{k}^{{-1}}(m)

om den första biten i nyckeln är 0

k

F_{k}^{{-1}}(m)=E_{{k'}}^{{-1}}(m\oplus k)

, i andra fall

Om huvudchifferet har bra n-bitars skydd, kräver brytning av chifferet med en textanalysattack en avancerad sökning i nyckelbitsutrymmet . Med andra ord, om analytikern inte har information om chifferet , då kan han få den nödvändiga informationen om han krypterar eller dekrypterar med nycklarna eller [3] . $E$ $F$ $n-1$ $E$ $k$ $k'$

Även om chiffret är svårt att bryta med en vald textattack, är det väldigt lätt att bryta med en vald nyckelattack. Analytikern behöver två chiffer: och för något lämpligt meddelande . Om den första biten är noll, då $F$ $F_{k}(m)$ $F_{{k'}}(m)$ $m$ $k$

F_{k}(m)\oplus F_{{k'}}(m)=E_{k}(m)\oplus (E_{{k''}}(m)\oplus k')=k'

I andra fall,

F_{k}(m)\oplus F_{{k'}}(m)=(E_{{k'}}(m)\oplus k)\oplus (E_{{k'}}(m)=k

[3] .

Således får analytikern omedelbart alla bitar av nyckeln , förutom den första, och kan slutföra operationen, eftersom han kan klartexten [4] . $k$

Exempel på attacker

Attack på LOKI89

I LOKI89-chifferet har varje val av två undernycklar , en från en jämn cykel och en från en udda cykel, en motsvarande 64-bitars nyckel. Eftersom alla algoritmer för att erhålla två undernycklar från de två föregående är desamma, påverkar inte placeringen av cyklerna i vilka de två aktuella undernycklarna är utmatningen av följande undernycklar. Om vi fixar två undernycklar och nycklar och definierar den andra nyckeln genom att välja och , då kommer värdena för nyckelns undernycklar att vara desamma som följande undernycklar till nyckeln . I så fall . Detta förhållande bevaras för alla två nycklar som väljs på detta sätt: om informationen före den andra krypteringscykeln med nyckeln är densamma som informationen före den första krypteringen med nyckeln , då är informationen och indata för funktionen desamma i båda operationerna förskjuts med en cykel. I det här fallet, om klartexten är krypterad med nyckeln , kommer chiffertexten före den andra cykeln att vara . Den mottagna informationen är densamma som den som hittades före den första krypteringscykeln med nyckeln , vars värde kommer att vara , och därmed i detta par $K2$ $K3$ $K$ $K^{*}$ $K1^{*}=K2$ $K2^{*}=K3$ $Ki^{*}$ $K^{*}$ $K(i+1)$ $K$ $K^{*}=(K2,K3)=(K_{R},ROL12(K_{L}))$ $K$ $K^{*}$ $F$ $P$ $K$ $(P_{R}\oplus K_{R},P_{L}\oplus K_{L}\oplus F(P_{R}\oplus K_{R},K_{L}))$ $K^{*}$ $P^{*}\oplus K^{*}=(P_{R}^{*}\oplus K_{L},P_{R}^{*}\oplus ROL12(K_{L}))$

P ∗ = ( P R , P L ⊕ K L ⊕ R O L 12 ( K L ) ⊕ F ( P R ⊕ K R , K L ) ) {\displaystyle P^{*}=(P_{R},P_{L}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{R}\oplus K_{R},K_ {L}))}

P^{*}=(P_{R},P_{L}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{R}\oplus K_{R},K_ {L}))

Du kan se att den högra sidan av uttrycket är densamma som den vänstra sidan av uttrycket och förhållandet mellan de två andra delarna beror på tangenten. I ett sådant par finns det ett liknande förhållande mellan chiffertexter:

P

P^{{*}}

C ∗ = ( C R ⊕ K L ⊕ R O L 12 ( K L ) ⊕ F ( C L ⊕ K R , K L ) , C L ) . {\displaystyle C^{*}=(C_{R}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(C_{L}\oplus K_{R},K_{L}), C_{L}).}

C^{*}=(C_{R}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(C_{L}\oplus K_{R},K_{L}), C_{L}).

Graferna beskriver förhållandet mellan undernycklarna till de två nycklarna och förhållandet mellan värdena under krypteringsprocessen.

SCHEMA

En key-matched-plaintext-attack som förlitar sig på dessa egenskaper väljer ett 32-bitars värde , klartexter vars högra sidor är , och vars 32-bitars vänsterhalvor väljs slumpmässigt, och klartexter vars vänstra sidor är , och vars höger sidor väljs slumpmässigt. Två okända associerade nycklar används för att kryptera klartextdata på systemet som studeras: nyckeln används för att kryptera de första klartexterna, och nyckeln används för att kryptera de återstående klartexterna. För varje par klartexter och det är garanterat att , och med hög sannolikhet finns det två klartexter så att . För ett sådant par förblir data densamma om båda exekveringarna skiftas med en cykel. Ett sådant par kan lätt väljas ut, om det finns, genom att kontrollera likheten. Sannolikheten att klara detta test slumpmässigt är , så endast ett fåtal par kommer att klara det. $P_{R}$ $2^{16}$ $P_{0},...,P_{65535}$ $P_{R}$ $2^{16}$ $P_{0}^{*},...,P_{65535}^{*}$ $P_{R}$ $K$ $2^{16}$ $K^{*}=(K_{R},ROL12(K_{L}))$ $2^{16}$ $Pi}}$ $P_{j}^{*}$ ${\displaystyle P_{jL}^{*}=P_{iR))$ $P_{jR}^{*}=P_{iL}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{iR}\oplus K_{R},K_{L} )$ $C_{R}^{*}=C_{L}.$ $2^{-32}$

Par som har dessa klartext- och chiffertextegenskaper uppfyller nyckelkraven (1) och (2). Således, för detta par, är relationen uppfylld , där värdet är det enda okända . Av alla möjliga värden är det bara ett fåtal som uppfyller ekvationen. Genom att använda differentiell kryptoanalys och optimeringstekniker kan man hitta ett värde i ett fåtal operationer. När värdet har hittats är det lätt att beräkna med formlerna (1) och (2) för att få och . $F(P_{R}\oplus K_{R},K_{L})\oplus F(C_{L}\oplus K_{R},K_{L})=P_{R}^{*} \oplus P_{L}\oplus C_{L}^{*}\oplus C_{R}$ $K_{L}\oplus K_{R}$ $2^{32}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus ROL12(K_{L})$ $K$ $K^{*}$

En liknande attack med vald-nyckel-känd-klartext använder känd klartext krypterad med en okänd nyckel och klartext krypterad med en relaterad nyckel . Ett par med dessa egenskaper kan lätt identifieras av 32 vanliga bitar av klartext och 32 vanliga bitar av chiffertext. Detta par kan användas för att söka efter nycklar på samma sätt som i en vald nyckel och vald klartextattack. [ett] $2^{32}$ $Pi}}$ $K$ $2^{32}$ $P_{j}^{*}$ $K^{*}=(K_{R},ROL12(K_{L}))$

Jämförelse med andra typer av attacker

Enligt Bruce Schneier finns det 7 huvudsakliga sätt för kryptoanalytisk attack [5] :

Vid en chiffertextbaserad attack har kryptoanalytikern bara tillgång till chiffertexten. Detta är den svåraste typen av attack på grund av den lilla mängd information som finns tillgänglig.

I en attack med känd klartext känner kryptanalytikern både klartexten och chiffertexten. Denna typ av attack är mer effektiv än en chiffertextbaserad attack på grund av den större mängden känd information om kryptosystemet.

En vald klartextattack är en kraftfullare typ av attack än en känd klartextattack. Möjligheten att förvälja klartext ger fler alternativ för att extrahera systemnyckeln. Det är också sant att om ett kryptosystem är sårbart för en känd klartextattack, så är det också sårbart för en vald klartextattack. [ett]

En matchad nyckelattack är starkare än en matchad textattack. Det knäcker omedelbart ett specialtillverkat blockchiffer som är säkert mot andra attacker. För alla blockchiffer kan en vald nyckelattack påskynda den avancerade sökprocessen beroende på antalet tillåtna nyckelinversioner. För en obegränsad gissad nyckelattack kan mängden arbete minskas som en kvadratrot. Dessa resultat är de bästa möjliga för en allmän attack som inte förlitar sig på något speciellt blockchiffer.

Anteckningar

↑ 1 2 3 Biham, 1993 .
↑ Winternitz & Hellman, 1987 .
↑ 1 2 3 4 Winternitz & Hellman, 1987 , sid. 17
↑ 1 2 3 4 5 6 7 8 Winternitz & Hellman, 1987 , sid. arton
↑ Schneier, 2003 .

Litteratur

Robert Winternitz, Martin Hellman . Valda nyckelattacker på ett blockchiffer // Cryptologia : journal. - 1987. - Nej . 11:1 . - S. 16-20 . - doi : 10.1080/0161-118791861749 .
Eli Biham. Nya typer av kryptoanalytiska attacker med relaterade nycklar // Helleseth T. (red) Advances in Cryptology . — EUROCRYPT '93. EUROCRYPT 1993. Lecture Notes in Computer Science, vol 765. Springer, Berlin, Heidelberg, 1993. doi : 10.1007/3-540-48285-7_34 .
B. Schneier. Tillämpad kryptografi. - Triumph, 2003. - 816 sid. - ISBN 5-89392-055-4 .