Ciphertext oskiljbar

Ciphertext omöjlig att skilja är en egenskap hos många krypteringssystem . Intuitivt, om ett system har egenskapen omöjlig att särskilja, kommer en angripare inte att kunna särskilja par av chiffertexter baserat på klartexterna de krypterar. Egenskapen omöjlig att särskilja för attacker baserade på vald klartext anses vara ett grundläggande krav för de sannolikt säkraste kryptosystem med offentliga nyckel , även om vissa krypteringssystem också har en egenskap som inte kan urskiljas för attacker baserade på vald klartext och för adaptiva attacker baserade på vald chiffertext. Osärskiljbarhet för attacker med utvald klartext motsvarar den semantiska säkerheten i ett system, så dessa definitioner anses vara utbytbara i många kryptografiska bevis.

Ett kryptosystem anses vara säkert ur synvinkel omöjligt att särskilja [1] om ingen angripare, efter att ha mottagit en chiffertext slumpmässigt vald från ett meddelandeutrymme med två element som definierats av motståndaren, kan identifiera den klartext som motsvarar denna chiffertext med en betydligt bättre sannolikhet än med slumpmässig gissning (1⁄2 ). Om någon angripare kan lyckas urskilja den valda chiffertexten med en sannolikhet som är väsentligt större än 1⁄2, så sägs den angriparen ha en "fördel" i att urskilja chiffertexten, och systemet anses inte vara säkert ur synpunkt om oskiljaktighet . Den här definitionen inkluderar uppfattningen att en angripare i ett säkert system inte ska få någon information genom att se chiffertexten . Därför bör en angripare inte kunna skilja mellan chiffertexter bättre än om han gissade slumpmässigt.

Formella definitioner

Säkerhet när det gäller omöjlighet att särskilja har många definitioner, beroende på antaganden om angriparens förmåga. Följande analogi används vanligtvis. Ett kryptosystem är ett slags spel . Dessutom anses ett kryptosystem säkert om ingen deltagare kan vinna spelet med en betydligt högre sannolikhet än en deltagare som kommer att agera slumpmässigt. De vanligaste begreppen som används i kryptografi är omöjlighet att särskilja för vald-klartext-attacker (förkortat som IND-CPA), omöjlig att särskilja för (icke-adaptiva) vald-chiffertext-attacker (IND-CCA1), och omöjlig att särskilja för adaptiva vald-chiffertextattacker (IND- CPA) CCA2). Säkerhet i betydelsen av var och en av ovanstående definitioner innebär säkerhet i betydelsen av varje föregående: ett kryptosystem som är IND-CCA1 säkert är också IND-CPA säkert, och följaktligen är ett system som är IND-CCA2 säkert både IND-CCA1 och IND-CPA säker . Säkerhet i betydelsen IND-CCA2 är alltså den starkaste av de tre definitionerna.

Ourskiljbarhet för valda klartextattacker (IND-CPA)

För en probabilistisk algoritm för asymmetrisk nyckelkryptering bestäms omöjligheten i betydelsen IND-CPA [2] av följande spel mellan angriparen och testaren. För system baserade på beräkningssäkerhet modelleras angriparen av en probabilistisk polynom Turing-maskin , vilket innebär att han måste slutföra spelet och ge en gissning i ett polynomantal tidssteg. I denna definition representerar E(PK, M ) chiffertexten för meddelandet M , erhållen med nyckeln PK :

Testaren genererar ett nyckelpar PK , SK baserat på någon säkerhetsparameter k (t.ex. nyckelstorlek i bitar) och publicerar PK till angriparen. Testaren räddar SK .
En angripare kan utföra ett polynomiskt begränsat antal krypteringar eller andra operationer.
Så småningom presenterar angriparen två separata klartexter för testaren. ${\displaystyle \scriptstyle M_{0},M_{1))$
Testaren väljer bit b {0, 1} slumpmässigt och skickar den testade chiffertexten C = E(PK, ) tillbaka till angriparen. $\scriptstyle \in$ ${\displaystyle \scriptstyle M_{b))$
En angripare kan utföra valfritt antal ytterligare beräkningar eller krypteringar. Slutligen skriver den bara ut värdet av b .

Ett kryptosystem är säkert i betydelsen IND-CPA om någon trovärdig angripare i polynomtid bara har en liten "fördel" i att särskilja chiffertexter framför slumpmässiga gissningar. Angriparen har en försumbar "fördel" om han vinner spelet ovan med sannolikhet , där är en försumbar funktion för säkerhetsparametern k , det vill säga för alla (icke-noll) polynomfunktioner , som har , sådan att för alla . $\scriptstyle \left({\frac {1}{2}}\right)\,+\,\epsilon (k)$ $\scriptstyle \epsilon (k)$ $\scriptstyle poly()$ ${\displaystyle \scriptstyle k_{0))$ $\scriptstyle |\epsilon (k)|\;<\;\left|{\frac {1}{poly(k)))\right|$ ${\displaystyle \scriptstyle k\;>\;k_{0))$

Även om angriparen känner till , och PK, innebär den sannolikhetsmässiga karaktären hos E att chiffertexten bara kommer att vara en av många giltiga chiffertexter , och därför ger inte angriparen någon betydande fördel att kryptera och jämföra de mottagna chiffertexterna med testarens chiffertext. $\scriptstyle M_{0}$ $\scriptstyle M_{1}$ ${\displaystyle \scriptstyle M_{b))$ $\scriptstyle M_{0}$ $\scriptstyle M_{1}$

Även om definitionen ovan är specifik för asymmetriska nyckelkryptosystem , kan den anpassas till det symmetriska fallet genom att ersätta den offentliga nyckelkrypteringsfunktionen med orakelkryptering , som lagrar den hemliga krypteringsnyckeln och krypterar godtyckliga klartexter på angriparens begäran.

Osärskiljbarhet för valda chiffertextattacker/Adaptiv chiffertextattacker (IND-CCA1, IND-CCA2)

Säkerhet i betydelsen IND-CCA1 och IND-CCA2 [1] definieras på samma sätt som systemtillförlitlighet i betydelsen IND-CPA. Men förutom den publika nyckeln (eller orakelkryptering , i det symmetriska fallet ), ges angriparen åtkomst till orakeldekryptering , som dekrypterar godtyckliga chiffertexter på angriparens begäran och returnerar klartexten . I definitionen av IND-CCA1 får en angripare endast fråga oraklet tills han har fått chiffertexten som testas. I IND-CCA2-definitionen kan angriparen fortsätta att fråga oraklet efter att han fått chiffertexten som testas, med varningen att han inte kan skicka in den för dekryptering (annars skulle definitionen vara trivial).

Testaren genererar ett nyckelpar PK , SK baserat på någon säkerhetsparameter k (t.ex. nyckelstorlek i bitar) och publicerar PK till angriparen. Testaren räddar SK .
En angripare kan utföra valfritt antal krypteringar , dekrypteringssamtal med ett orakel baserat på godtyckliga chiffertexter eller andra operationer.
Så småningom presenterar angriparen två separata klartexter för testaren. $\scriptstyle M_{0},\,M_{1}$
Testaren väljer bit b {0, 1} slumpmässigt och skickar den testade chiffertexten C = E(PK, ) tillbaka till angriparen. $\scriptstyle \in$ ${\displaystyle \scriptstyle M_{b))$
En angripare kan utföra valfritt antal ytterligare beräkningar eller krypteringar.
1. I definitionen av IND-CCA1 kan angriparen inte utföra någon ytterligare dekryptering med oracle .
2. I IND-CCA2-definitionen kan angriparen göra ytterligare orakelanrop , men kan inte använda C -chiffertexten för att göra det .
Slutligen gör angriparen en gissning om värdet av b .

Ett kryptosystem är säkert i betydelsen IND-CCA1 eller IND-CCA2 om ingen av motståndarna har en betydande fördel i det givna spelet.

Kan inte skiljas från slumpmässigt brus

Ibland krävs krypteringssystem där en chiffertextsträng inte kan skiljas från en slumpmässig sträng för en angripare. [3]

Om angriparen inte ens kan avgöra om meddelandet finns, ger detta personen som skrev meddelandet rimlig förnekelse .

Vissa personer som skapar krypterade kommunikationskanaler föredrar att göra innehållet i varje chiffertext omöjligt att skilja från slumpmässiga data för att göra trafikanalys svårare. [fyra]

Vissa människor som bygger system för att lagra krypterad data föredrar att data inte går att skilja från slumpmässiga data för att göra det lättare att dölja det . Till exempel, vissa typer av diskkryptering , som TrueCrypt , försöker dölja data i slumpmässiga data som blir över efter vissa typer av dataförstöring . Som ett annat exempel försöker vissa typer av steganografi att dölja data genom att få dem att matcha de statistiska egenskaperna för "slumpmässigt" bildbrus i digitala fotografier .

För närvarande finns det specialdesignade kryptografiska algoritmer för förnekbara krypteringssystem , där chiffertexter inte går att skilja från slumpmässiga bitsträngar. [5] [6] [7]

Om krypteringsalgoritmen E kan konstrueras på ett sådant sätt att en angripare (generellt definierad som en polynom-tidsobservatör) som känner till klartexten i meddelandet m inte kan skilja mellan E(m) och en nygenererad slumpmässig bitsträng i samma längd, som E(m), så följer att om E(m1) är samma längd som E(m2), kommer dessa två chiffertexter att vara omöjliga att skilja från varandra för en angripare, även om han känner till klartexten m1 och m2 (IND -CPA). [åtta]

De flesta applikationer kräver ingen krypteringsalgoritm för att skapa chiffertexter som inte kan särskiljas från slumpmässiga bitar. Vissa författare tror dock att sådana krypteringsalgoritmer är konceptuellt enklare och lättare att arbeta med, och mer mångsidiga i praktiken - och de flesta IND-CPA- krypteringsalgoritmer verkar producera krypterade meddelanden som inte går att skilja från slumpmässiga bitar. [9]

Ekvivalenter och deras betydelse

Ourskiljbarhet är en viktig egenskap för att upprätthålla konfidentialitet för krypterade meddelanden. Det har dock visat sig att i vissa fall den oskiljaktiga egenskapen innebär andra egenskaper som inte uttryckligen säkerhetsrelaterade. Ibland har sådana likvärdiga definitioner helt olika betydelser. Till exempel är egenskapen omöjlig att särskilja i betydelsen IND-CPA känd för att vara likvärdig med inflexibilitetsegenskapen för liknande scenarioattacker (NM-CCA2). Denna likvärdighet är inte omedelbart uppenbar, eftersom oflexibilitet är en egenskap relaterad till meddelandeintegritet, inte konfidentialitet. Det har också visat sig att oskiljbarhet kan följa av någon annan definition eller vice versa. Följande lista listar några kända konsekvenser, även om de är långt ifrån kompletta:

IND-CPA semantisk säkerhet för CPA. [tio] $\scriptstyle \Leftrightarrow$
NM-CPA (Inflexibility for Chosen Plaintext Attacks ) IND-CPA. [ett] $\scriptstyle \Rightarrow$
NM-CPA (Inflexibility for Chosen Plaintext Attacks ) IND-CCA2 . [ett] $\scriptstyle \not \Rightarrow$
NM-CCA2 (Inflexibility for Adaptive Chiffertext-Based Attacks) IND-CCA2. [ett] $\scriptstyle \Leftrightarrow$

Anteckningar

↑ 1 2 3 4 5 Krohn, Maxwell. Om definitionerna av kryptografisk säkerhet : Attack med vald chiffertext återbesökt . — 1999.
↑ Katz, Jonathan; Lindell, Yehuda. Introduktion till modern kryptografi : principer och protokoll . — Chapman och Hall/CRC, 2007.
↑ Chakraborty, Debrup; Rodriguez-Henriquez., Francisco. Kryptografisk teknik (neopr.) / Çetin Kaya Koç. - 2008. - S. 340. - ISBN 9780387718170 .
↑ iang. Kan inte skiljas från slumpmässigt (20 maj 2006). Hämtad 6 augusti 2014. Arkiverad från originalet 15 augusti 2014. (obestämd)
↑ Bernstein, Daniel J.; Hamburg, Mike; Krasnova, Anna; Lange, Tanja Elligator: Elliptiska kurvor som inte kan skiljas från enhetliga slumpmässiga strängar (28 augusti 2013). Hämtad 23 januari 2015. Arkiverad från originalet 5 november 2014. (obestämd)
↑ Möller, Bodö. Ett krypteringsschema med offentlig nyckel med pseudo-slumpmässiga chiffertexter // Datorsäkerhet - ESORICS 2004 (neopr.) . - 2004. - T. 3193. - S. 335-351. — (Föreläsningsanteckningar i datavetenskap). — ISBN 978-3-540-22987-2 . - doi : 10.1007/978-3-540-30108-0_21 .
↑ Moore, Christopher; Mertens, Stephan. Beräkningens natur (neopr.) . - 2011. - ISBN 9780191620805 .
↑ Reingold, Omar Pseudo-slumpmässiga synthesizers, funktioner och permutationer 4 (november 1998). Hämtad 7 augusti 2014. Arkiverad från originalet 19 februari 2014. (obestämd)
↑ Rogaway, Phillip Nonce-Based Symmetric Encryption 5–6 (1 februari 2004). Hämtad 7 augusti 2014. Arkiverad från originalet 10 maj 2013. (obestämd)
↑ Silvio Micali, Shafi Goldwasser Probabilistisk kryptering (1984). (obestämd)

Litteratur

Katz, Jonathan; Lindell, Yehuda. Introduktion till modern kryptografi : principer och protokoll . - Chapman & Hall / CRC Press , 2007. - ISBN 978-1584885511 .