Vald klartext 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 4 december 2017; kontroller kräver 7 redigeringar .

Vald klartext-attack ( CPA ) är en av de viktigaste metoderna för kryptoanalytiska attacker .  Kryptanalytikern har ett visst antal klartexter och motsvarande chiffertexter , dessutom har han förmågan att kryptera flera förvalda klartexter [1] .

Beskrivning

En kryptoanalytiker , enligt Kerckhoffs princip , har all information om krypteringssystemet som används, förutom en viss uppsättning parametrar som kallas nyckeln . Kryptanalytikerns uppgift är att hitta nyckeln eller skapa en algoritm som gör det möjligt att dekryptera alla meddelanden som krypteras med denna nyckel.

Given:

där den klartext som valts av kryptoanalytikern, chiffertexten, krypteringsfunktionen, nyckeln.

Hämta: Antingen , eller algoritm hur man får från [1]

Möjligheten att utföra en vald-klartext-attack är ganska vanlig. Till exempel kan en angripare muta någon att kryptera ett valt meddelande. Följande situation är också möjlig: angriparen skickar ett meddelande till ambassadören i ett visst land, och han skickar det till sitt hemland i krypterad form [2] .

Utvald klartext-attack hänvisar till aktiva attacker på kryptosystem. Sådana attacker bryter mot integriteten och sekretessen för den överförda informationen [3] .

Figur 1 visar ett diagram över en attack baserat på vald klartext. Angriparen (A) tar emot chiffertexten från användaren (C). Angriparens uppgift är att "gissa" klartexten . Eftersom angriparen har tillgång till krypteringsblocket har han möjlighet att kryptera sina meddelanden och analysera de mottagna chiffertexterna. . Som ett resultat tar angriparen upp meddelandet och vidarebefordrar det till användaren.

Typer av attacker

Det finns två typer av attacker baserat på vald klartext:

Jämförelse med andra typer av attacker

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

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

I historia

Matchad klartext attack användes under andra världskriget .

1942 fångade kryptanalytiker från den amerikanska flottan en krypterad order från det japanska kommandot. Efter att ha dechiffrerat en del av meddelandet fick amerikanska kryptoanalytiker veta om den förestående attacken mot den mystiska "AF", men de lyckades inte ta reda på platsen för attacken. Förutsatt att Midway Island var det mest sannolika målet för japanerna , gick amerikanerna på ett trick. De upprättade en rapport om att ön saknade färskvatten och skickade det genom en oskyddad kanal. Några dagar senare avlyssnade amerikanska underrättelsetjänstemän en japansk chiffertext, som rapporterade att det fanns lite färskvatten på AF. Således visste det amerikanska kommandot i förväg om den kommande attacken mot Midway Atoll [6] .

Brittiska kryptoanalytiker på Bletchley Park använde framgångsrikt en vald-klartextattack för att dekryptera tysk korrespondens. Britterna provocerade fienden att använda vissa ord och namn i meddelandetexterna. Till exempel, om tyskarna nyligen rensade en del av kustvattnet från minor, skulle de brittiska underrättelsetjänsterna kunna meddela att området återigen var minerat. Detta provocerade fram en ström av krypterade meddelanden från det tyska kommandot, inklusive ordet "minor" och namnet på territoriet. Således kunde britterna plocka upp klartext och analysera chiffertexter ganska effektivt för att bryta tyska chiffer. Denna attack kan kvalificeras som en adaptivt vald klartextattack , eftersom brittiska kryptoanalytiker kan välja nästa klartext som ska krypteras baserat på de resultat som redan erhållits [7] .

Exempel på attacker

Privat nyckel kryptosystem

Attack mot affina chiffer

Tänk på ett enkelt exempel på en attack på ett affint chiffer med latinska tecken från A till Ö.

A B C D E F G H jag J K L M N O P F R S T U V W X Y Z
0 ett 2 3 fyra 5 6 7 åtta 9 tio elva 12 13 fjorton femton 16 17 arton 19 tjugo 21 22 23 24 25

Krypteringsfunktion:

Kryptanalytikern utför en attack baserat på den valda klartexten. Den valda klartexten är "HAHAHA", motsvarande chiffertext är "NONONO". Målet för kryptoanalytikern är att hitta den explicita formen av krypteringsfunktionen, det vill säga att beräkna koefficienterna och .

Med hjälp av det resulterande klartext-chiffertextparet kommer vi att komponera ett ekvationssystem:

När vi löser systemet finner vi:

Krypteringsfunktion: [8]

Differentiell kryptoanalys

Den valda klartextattacken används i en differentiell kryptoanalysmetod som föreslogs av de israeliska kryptoanalytikerna Eli Biham och Adi Shamir 1990 för att bryta DES -kryptosystemet . Metoden bygger på studiet av chiffertexter, vars klartexter har vissa skillnader. Genom att analysera utvecklingen av chiffertextskillnader under DES-rundor bestäms en lista över möjliga nycklar och en sannolikhet tilldelas varje möjlig nyckel. I processen att analysera följande par av chiffertexter kommer en av nycklarna att bli den mest troliga [9] . Därefter utvidgades metoden för differentiell kryptoanalys till sådana kryptosystem som FEAL , Khafre , Lucifer , LOKI och andra [10] [11] .

Låt , matchade klartexter, , motsvarande chiffertexter. Skillnaden mellan klartext och chiffertext bestäms av XOR- operationen : För att beskriva möjliga förändringar i värdet under passagen av DES-stadier introduceras konceptet med en rund egenskap, som består av skillnader i klartext , chiffertext och en uppsättning runda skillnader (skillnader i chiffertexter efter varje mellanrunda) . Varje funktion tilldelas sannolikheten att ett slumpmässigt par klartexter med en skillnad kommer att producera runda skillnader och chiffertextskillnader som motsvarar funktionen efter att ha passerat motsvarande krypteringsrunda. Ett par klartexter vars passage genom en DES-runda beskrivs exakt av egenskapen kallas ett "korrekt par" , annars kallas det ett "felaktigt par". [9]

För att bestämma nyckeln utförs en attack baserat på den valda klartexten. Vid datainsamlingsstadiet skickar kryptoanalytikern för kryptering ett stort antal par klartexter med vissa skillnader som motsvarar egenskapen med sannolikhet (det vill säga bland alla klartextpar finns det korrekta par). Sedan, vid dataanalyssteget , bestäms en uppsättning möjliga runda nycklar, för varje möjlig nyckel beräknas skillnaderna mellan motsvarande chiffertexter. Under den sista omgången av kryptering sker en fullständig uppräkning av möjliga nycklar. För felaktiga runda nycklar kommer sannolikheten för en skillnad i chiffertexter som motsvarar karakteristiken att vara mycket liten, för en korrekt rund nyckel blir sannolikheten av storleksordningen eller högre. På så sätt kan du bestämma rätt systemnyckel [9] [12] .

Det bör noteras att metoden för differentiell kryptoanalys är ganska opraktisk på grund av de höga kraven på tid och datavolym. Till exempel, att knäcka en 16-rund DES kräver matchade klartexter och operationer [9] .

Linjär kryptoanalys

1993 föreslog den japanske kryptoanalytikern Mitsuru Matsui en linjär kryptoanalysmetod för att bryta blockchiffer som DES. Metoden bygger på konstruktionen av linjära relationer mellan klartext, chiffertext och nyckel :

var  är de n :te bitarna av texten, chiffertexten respektive nyckeln. Sådana relationer kallas linjära approximationer.

Kärnan i metoden är att beräkna sannolikheten för förekomsten av linjära approximationer. Om sannolikheten skiljer sig från , är det möjligt att extrahera information om nyckeln med hjälp av klartext-chiffertext-par. Inledningsvis, för varje enskild omgång, hittas en linjär approximation med den högsta sannolikheten för bias. Sedan kombineras de runda approximationerna till en generell linjär approximation av kryptosystemet, och med hjälp av klartext-chiffertext-par görs ett antagande om nyckelbitarnas värden [13] .

Inledningsvis använde den linjära kryptoanalysmetoden en känd klartextattack. Till exempel tog det kända klartexter och 50 dagar att knäcka en 16-runda DES [13] . År 2000 föreslog Lars Knudsen en variant av linjär kryptoanalys baserad på utvalda klartexter - det krävdes utvalda klartexter för att öppna 12 bitar av nyckeln [14] .

Public key kryptosystem

Den valda klartextattacken kan användas för att bryta asymmetriska kryptosystem. I sådana system är den publika nyckeln tillgänglig för alla användare, vilket ger kryptoanalytikern fullständig kontroll över krypteringsalgoritmen. Således är det alltid möjligt att organisera en attack mot kryptosystem med offentliga nyckel baserat på vald klartext [15] . Till exempel, om en angripare har snappat upp en chiffertext , för att dekryptera den, räcker det att plocka upp ett annat meddelande och kryptera det med den publika nyckeln . Om , ett försök till görs [16] .

Probabilistisk kryptering

Vanligtvis är asymmetriska kryptosystem utformade för att motstå attacker med utvald klartext [15] . Till exempel är RSA -kryptosystemets försvar mot attacker baserade på vald klartext baserat på svårigheten att beräkna roten av chiffertexten med ett sammansatt heltal modulo [17] . Ett annat sätt att eliminera informationsläckor i kryptosystem med offentliga nyckel är probabilistisk kryptering som föreslagits av Shafi Goldwasser och Silvio Micali . Huvudidén med probabilistisk kryptering är att matcha flera slumpmässigt utvalda chiffertexter till samma klartext . Således, om en kryptoanalytiker försöker gissa klartexten P för att dekryptera , kommer han att få en helt annan chiffertext och kommer inte att kunna kontrollera riktigheten av sin gissning [18] .

Attack mot RSA-kryptosystemet

Trots säkerheten hos RSA-kryptosystemet mot valda textattacker, finns det ett antal sårbarheter som gör att en kryptoanalytiker kan dekryptera chiffertexten. Tänk på följande algoritm för att attackera ett RSA-baserat elektroniskt signatursystem som föreslogs av George David 1982. Attacken görs under antagandet att kryptoanalytikern har snappat upp chiffertexten . Kryptanalytikerns mål är att få ett öppet meddelande . För att utföra en attack måste en kryptoanalytiker kunna signera alla meddelanden han väljer [19] [20] .

  1. I det första skedet av attacken delas chiffertexten upp i faktorer (inte nödvändigtvis enkla): . Härav följer att meddelandet också kan representeras som en produkt av faktorer och jämlikheter är giltiga: , och .
  2. Kryptanalytikern väljer ett öppet meddelande och skickar det för underskrift. Han ber också att få signera meddelanden . Signaturen görs enligt följande: , medan .
  3. Det inversa elementet beräknas .
  4. Genom att multiplicera det resulterande uttrycket med är det möjligt att få : .
  5. Som ett resultat återställs det ursprungliga meddelandet:

Denna metod tillåter dig inte att öppna kryptosystemet i traditionell mening, det vill säga för att få en privat nyckel, men kryptoanalytikern kan dekryptera ett specifikt meddelande. Därför är denna attack svagare än attacken med matchad klartext för symmetriska kryptosystem, vilket gör att du kan få all information om kryptosystemet om den lyckas [20] .

Anteckningar

  1. ↑ 1 2 3 Schneier, 2003 , sid. tjugo.
  2. ↑ Schneier, 2003 , sid. 21.
  3. ↑ Gabidulin , sid. 25-28.
  4. ↑ Schneier, Ferguson, 2002 , sid. 48.
  5. ↑ Schneier, Ferguson, 2002 , sid. 47-49.
  6. ↑ Kahn, 2000 , sid. 106-109.
  7. ↑ Hinsley, 2001 .
  8. ↑ Stinson, 2006 , sid. 27-29.
  9. ↑ 1 2 3 4 Biham, Shamir (DES), 1990 .
  10. ↑ Biham, Shamir (FEAL), 1991 .
  11. ↑ Biham, Shamir (LOKI), 1991 .
  12. ↑ Schneier, 2003 , sid. 212-216.
  13. ↑ 12 Matsui , 1993 .
  14. ↑ Knudsen, 2000 .
  15. ↑ 1 2 Schneier, 2003 , sid. 342.
  16. ↑ Schneier, 2003 , sid. 404.
  17. ↑ Mao, 2005 , sid. 308.
  18. ↑ Schneier, 2003 , sid. 404-406.
  19. ↑ Davida, 1982 .
  20. ↑ 12 Denning , 1984 .

Litteratur