Valgt almindeligt tekstangreb - Chosen-plaintext attack

Et valgt angreb med almindelig tekst ( CPA ) er en angrebsmodel til kryptanalyse, der antager, at angriberen kan opnå ciphertexts til vilkårlige almindelige tekster . Målet med angrebet er at få oplysninger, der reducerer sikkerheden ved krypteringsordningen .

Moderne cifre sigter mod at tilvejebringe semantisk sikkerhed, også kendt som krypteringsteknisk skelnen mellem valgt angreb med almindelig tekst , og de er derfor ved design generelt immune over for valgte almindelige tekstangreb, hvis de implementeres korrekt.

Introduktion

I et valgt almindeligt tekstangreb kan modstanderen (muligvis adaptivt ) bede om krypteringstekster for vilkårlige almindelige tekstbeskeder. Dette er formaliseret ved at tillade modstanderen at interagere med en kryptering Oracle , ses som en sort boks . Angriberens mål er at afsløre hele eller en del af den hemmelige krypteringsnøgle.

I praksis kan det virke umuligt, at en angriber kunne få ciphertexts til givne plaintexts. Imidlertid er moderne kryptografi implementeret i software eller hardware og bruges til en række applikationer; i mange tilfælde er et valgt angreb med almindelig tekst ofte meget gennemførligt (se også i praksis ). Valgte almindelige tekstangreb bliver ekstremt vigtige i forbindelse med kryptografi med offentlig nøgle, hvor krypteringsnøglen er offentlig, og så angribere kan kryptere enhver almindelig tekst, de vælger.

Forskellige former

Der er to former for valgte angreb i almindelig tekst:

  • Batch valgt-almindeligt tekstangreb , hvor modstanderen vælger alle almindelige tekster, før han ser nogen af ​​de tilsvarende krypteringstekster. Dette er ofte meningen med "valgt-angreb med almindelig tekst", når dette ikke er kvalificeret.
  • Adaptivt valgt angreb med almindelig tekst ( CPA2 ), hvor modstanderen kan anmode om ciphertexts for yderligere plaintexts efter at have set ciphertexts for nogle plaintexts.

Generel metode til et angreb

Et generelt batch valgt-almindeligt tekstangreb udføres som følger:

  1. Angriberen kan vælge n almindelige tekster. (Denne parameter n er specificeret som en del af angrebsmodellen , den kan eller ikke være afgrænset.)
  2. Angriberen sender derefter disse n almindelige tekster til krypteringsoraklet.
  3. Krypteringsoraklet krypterer derefter angriberens almindelige tekster og sender dem tilbage til angriberen.
  4. Angriberen modtager n ciphertexts tilbage fra oraklet på en sådan måde, at angriberen ved, hvilken ciphertext der svarer til hver almindelig tekst.
  5. Baseret på parret med almindelig tekst - krypteringstekst kan angriberen forsøge at udtrække den nøgle, der bruges af oraklet til at kode almindelige tekster. Da angriberen i denne type angreb frit kan udarbejde almindelig tekst til at matche hans behov, kan angrebskompleksiteten reduceres.

Overvej følgende udvidelse af ovenstående situation. Efter det sidste trin,

  1. Modstanderen udsender to almindelige tekster m 0 og m 1 .
  2. En bit b vælges tilfældigt tilfældigt .
  3. Modstanderen modtager krypteringen af m b og forsøger at "gætte", hvilken almindelig tekst den har modtaget, og udsender lidt b ' .

En kryptering kan ikke skelnes mellem kryptering under et valgt angreb med almindelig tekst, hvis modstanderen efter kørsel af ovenstående eksperiment med n = 1 ikke kan gætte korrekt ( b = b ' ) med sandsynligheden ikke ubetydeligt bedre end 1/2.

Eksempler

Følgende eksempler viser, hvordan nogle chifre, der opfylder andre sikkerhedsdefinitioner, kan brydes med et valgt angreb med almindelig tekst.

Caesar-kryptering

Følgende angreb på Caesar-krypteringen muliggør fuld gendannelse af den hemmelige nøgle:

  1. Antag modstanderen sender beskeden: Attack at dawn,
  2. og oraklet vender tilbage Nggnpx ng qnja.
  3. Modstanderen kan derefter arbejde igennem for at gendanne nøglen på samme måde som du ville dekryptere en Caesar-chiffer. Modstanderen kunne udlede udskiftningerne A→N , T→G og så videre. Dette ville få modstanderen til at bestemme, at 13 var nøglen, der blev brugt i Cæsar-krypteringen.

Med mere indviklede eller komplekse krypteringsmetoder bliver dekrypteringsmetoden mere ressourceintensiv, men kernekonceptet er stadig relativt det samme.

Engangspuder

Følgende angreb på en engangspude muliggør fuld gendannelse af den hemmelige nøgle. Antag, at meddelelsens længde og nøgellængde er lig med n .

  1. Modstanderen sender en streng, der består af n nuller til Oracle.
  2. Oraklet returnerer den bitvise eksklusive-eller af nøglen med nullen.
  3. Strengen, der returneres af oraklet, er den hemmelige nøgle.

Mens engangspuden bruges som et eksempel på et informationsteoretisk sikkert kryptosystem, gælder denne sikkerhed kun under sikkerhedsdefinitioner svagere end CPA-sikkerhed. Dette skyldes, at krypteringsoraklet under den formelle definition af CPA-sikkerhed ikke har nogen tilstand. Denne sårbarhed er muligvis ikke gældende for alle praktiske implementeringer - engangspuden kan stadig gøres sikker, hvis genbrug af nøgler undgås (deraf navnet "engangspude").

I praksis

I 2. verdenskrig opdagede kryptoanalytikere i den amerikanske flåde, at Japan planlagde at angribe et sted kaldet "AF". De troede, at "AF" måske var Midway Island , fordi andre steder på Hawaii-øerne havde kodeord, der begyndte med "A". For at bevise deres hypotese om, at "AF" svarede til "Midway Island", bad de de amerikanske styrker ved Midway om at sende en almindelig tekstbesked om lave forsyninger. Japanerne aflyttede beskeden og rapporterede straks til deres overordnede, at "AF" var lavt vand, hvilket bekræftede flådens hypotese og tillod dem at placere deres styrke for at vinde kampen .

Også under Anden Verdenskrig bad allierede kodebrydere på Bletchley Park undertiden Royal Air Force om at lægge miner på en position, der ikke havde nogen forkortelser eller alternativer i det tyske flådesystems netreference. Håbet var, at tyskerne, der så minerne, ville bruge en Enigma-maskine til at kryptere en advarselsmeddelelse om minerne og en "helt klar" besked, efter at de blev fjernet, hvilket gav de allierede tilstrækkelig information om meddelelsen til at bryde den tyske flåde Enigma . Denne proces med at plante en kendt tekst blev kaldt havearbejde . Allierede kodebrydere hjalp også med at skabe meddelelser sendt af dobbeltagenten Juan Pujol García , hvis krypterede radiorapporter blev modtaget i Madrid, manuelt dekrypteret og derefter krypteret igen med en Enigma-maskine til transmission til Berlin. Dette hjalp kodebrydere med at dekryptere den kode, der blev brugt på det andet ben, efter at have leveret den originale tekst .

I moderne tid bruges CPA'er (valgt almindelig tekst) ofte til at bryde symmetriske cifre . For at blive betragtet som CPA-sikker, må den symmetriske chiffer ikke være sårbar over for angreb med valgt almindelig tekst. Det er således vigtigt for symmetriske chifferimplementatorer at forstå, hvordan en angriber vil forsøge at bryde deres chiffer og foretage relevante forbedringer.

For nogle valgte angreb med almindelig tekst behøver kun en lille del af almindelig tekst at blive valgt af angriberen; sådanne angreb er kendt som almindelig tekstinjektionsangreb.

Forhold til andre angreb

Et valgt angreb med almindelig tekst er mere kraftfuldt end kendt angreb med almindelig tekst , fordi angriberen direkte kan målrette mod bestemte udtryk eller mønstre uden at skulle vente på, at disse vises naturligt, hvilket muliggør hurtigere indsamling af data, der er relevante for kryptanalyse. Derfor er enhver kryptering, der forhindrer valgte almindelig tekstangreb, også sikker mod kendt angreb med almindelig tekst og kun krypteringstekst .

Imidlertid er et valgt angreb med almindelig tekst mindre kraftfuldt end et valgt ciffertekstangreb , hvor angriberen kan få almindelig tekst til vilkårlige krypteringstekster. En CCA-angriber kan undertiden bryde et CPA-sikkert system. For eksempel er El Gamal-chiffer sikker mod valgte almindelige tekstangreb, men sårbar over for valgte chiffertekstangreb, fordi den ubetinget kan formes .

Referencer