Salatekstin erottamattomuus

Salatekstin erottamattomuus on monien salausjärjestelmien ominaisuus . Intuitiivisesti, jos järjestelmällä on erottamattomuusominaisuus, hyökkääjä ei pysty erottamaan salatekstien pareja salaamiensa selkeiden tekstien perusteella . Valittuun selkeään tekstiin perustuvien hyökkäysten erottamattomuusominaisuutta pidetään perusedellytyksenä todistetusti turvallisimmille julkisen avaimen salausjärjestelmille , vaikka joissakin salausjärjestelmissä on myös erottamattomuusominaisuus valittuun selkeään tekstiin perustuville hyökkäyksille ja valittuun salatekstiin perustuville mukautuville hyökkäyksille. Valittujen selkokielisten hyökkäysten erottamattomuus vastaa järjestelmän semanttista turvallisuutta, joten näitä määritelmiä pidetään keskenään vaihdettavissa monissa salaustodistuksissa.

Salausjärjestelmää pidetään erottamattomuuden kannalta turvallisena [1] , jos yksikään hyökkääjä, joka on vastaanottanut vastustajan määrittelemästä kaksielementtistä viestiavaruudesta satunnaisesti valitun salatekstin , ei pysty tunnistamaan tätä salatekstiä vastaavaa selkeää tekstiä huomattavasti paremmin todennäköisyydellä . kuin satunnaisella arvauksella (1⁄2 ). Jos joku hyökkääjä pystyy tunnistamaan valitun salatekstin todennäköisyydellä, joka on huomattavasti suurempi kuin 1⁄2, hyökkääjällä sanotaan olevan "etu" salatekstin tunnistamisessa, eikä järjestelmää pidetä turvallisena erottamattomuuden kannalta. . Tämä määritelmä sisältää ajatuksen, että suojatussa järjestelmässä hyökkääjän ei pitäisi saada mitään tietoa näkemällä salatekstin . Siksi hyökkääjän pitäisi pystyä erottamaan salatekstit paremmin kuin jos hän arvasi satunnaisesti.

Muodolliset määritelmät

Tietoturvalla erottamattomuuden kannalta on monia määritelmiä, jotka riippuvat hyökkääjän kykyjä koskevista oletuksista. Yleensä käytetään seuraavaa analogiaa. Salausjärjestelmä on eräänlainen peli . Lisäksi kryptosysteemiä pidetään turvallisena, jos kukaan osallistuja ei voi voittaa peliä huomattavasti suuremmalla todennäköisyydellä kuin satunnaisesti toimiva osallistuja. Yleisimmät kryptografiassa käytetyt käsitteet ovat valittujen selkotekstihyökkäysten erottamattomuus (lyhenne IND-CPA), erottomuus (ei-adaptiivisille) valituille salatekstihyökkäyksille (IND-CCA1) ja erottumattomuus adaptiivisille valitun salakirjoituksen hyökkäyksille (IND- CPA). CCA2). Turvallisuus kunkin yllä olevan määritelmän merkityksessä merkitsee turvallisuutta jokaisen edellisen määritelmän merkityksessä: IND-CCA1-suojattu kryptojärjestelmä on myös IND-CPA-suojattu, ja vastaavasti IND-CCA2-suojattu järjestelmä on molemmat IND-CCA1. ja IND-CPA suojattu. Näin ollen turvallisuus IND-CCA2:n merkityksessä on vahvin kolmesta määritelmästä.

Valittujen selkokielisten hyökkäysten havaitsemattomuus (IND-CPA)

Epäsymmetrisen avaimen salauksen todennäköisyyspohjaisessa algoritmissa erottamattomuus IND-CPA:n [2] merkityksessä määräytyy seuraavan hyökkääjän ja testaajan välisen pelin perusteella. Laskennalliseen tietoturvaan perustuvissa järjestelmissä hyökkääjä mallinnetaan todennäköisyyspohjaisella polynomilla Turingin koneella , mikä tarkoittaa, että hänen on suoritettava peli loppuun ja annettava arvaus polynomimääräisenä aikaaskeleena. Tässä määritelmässä E(PK, M ) edustaa viestin M salatekstiä , joka on saatu avaimella PK :

Testauslaite luo avainparin PK , SK jonkin suojausparametrin k perusteella (esim. avaimen koko bitteinä) ja julkaisee PK :n hyökkääjälle. Testeri säästää SK :n .
Hyökkääjä voi suorittaa polynomisesti rajoitetun määrän salauksia tai muita toimintoja.
Lopulta hyökkääjä esittää testaajalle kaksi erillistä selkeää tekstiä . ${\displaystyle \scriptstyle M_{0},M_{1))$
Testaaja valitsee bitin b {0, 1} satunnaisesti ja lähettää testatun salatekstin C = E(PK, ) takaisin hyökkääjälle. $\scriptstyle \in$ ${\displaystyle \scriptstyle M_{b))$
Hyökkääjä voi suorittaa minkä tahansa määrän lisälaskelmia tai salauksia. Lopuksi se tulostaa vain b :n arvon .

Salausjärjestelmä on turvallinen IND-CPA:n merkityksessä, jos jollakin uskottavalla polynomiajassa hyökkääjällä on vain pieni "etu" salatekstien erottamisessa satunnaiseen arvaukseen verrattuna. Hyökkääjällä on mitätön "etu", jos hän voittaa yllä olevan pelin todennäköisyydellä , jossa on merkityksetön funktio turvaparametrille k , eli mille tahansa (nollasta poikkeavalle) polynomifunktiolle , jolla on , niin että kaikille . $\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))$

Vaikka hyökkääjä tietää , ja PK:n, E:n todennäköisyys tarkoittaa, että salateksti on vain yksi monista kelvollisista salateksteistä , ja siksi vastaanotettujen salatekstien salaaminen ja vertaaminen testaajan salatekstiin ei anna hyökkääjälle merkittävää etua. $\scriptstyle M_{0}$ $\scriptstyle M_{1}$ ${\displaystyle \scriptstyle M_{b))$ $\scriptstyle M_{0}$ $\scriptstyle M_{1}$

Vaikka yllä oleva määritelmä koskee vain epäsymmetrisen avaimen salausjärjestelmiä , se voidaan mukauttaa symmetriseen tapaukseen korvaamalla julkisen avaimen salaustoiminto oraakkelin salauksella , joka tallentaa salauksen salaisen avaimen ja salaa mielivaltaiset selkeät tekstit hyökkääjän pyynnöstä.

Valittujen salatekstihyökkäysten/adaptiivisten salatekstihyökkäysten erottamattomuus (IND-CCA1, IND-CCA2)

Turvallisuus IND-CCA1:n ja IND-CCA2:n [1] merkityksessä määritellään samalla tavalla kuin järjestelmän luotettavuus IND-CPA:n merkityksessä. Kuitenkin julkisen avaimen (tai symmetrisessä tapauksessa oraakkelisalauksen ) lisäksi hyökkääjälle annetaan pääsy oraakkelin salauksenpurkuun , joka purkaa mielivaltaiset salatekstit hyökkääjän pyynnöstä ja palauttaa puhtaan tekstin . IND-CCA1:n määritelmässä hyökkääjä saa tehdä kyselyn oraakkelille vain, kunnes hän on vastaanottanut testattavan salatekstin. IND-CCA2-määritelmässä hyökkääjä voi jatkaa kyselyä oraakkelilta saatuaan testattavan salatekstin sillä varauksella, että hän ei voi lähettää sitä salauksen purkamiseen (muuten määritelmä olisi triviaali).

Testauslaite luo avainparin PK , SK jonkin suojausparametrin k perusteella (esim. avaimen koko bitteinä) ja julkaisee PK :n hyökkääjälle. Testeri säästää SK :n .
Hyökkääjä voi suorittaa minkä tahansa määrän salauksia , salauksen purkukutsuja oraakkelilla mielivaltaisten salatekstien perusteella tai muita toimintoja.
Lopulta hyökkääjä esittää testaajalle kaksi erillistä selkeää tekstiä . $\scriptstyle M_{0},\,M_{1}$
Testaaja valitsee bitin b {0, 1} satunnaisesti ja lähettää testatun salatekstin C = E(PK, ) takaisin hyökkääjälle. $\scriptstyle \in$ ${\displaystyle \scriptstyle M_{b))$
Hyökkääjä voi suorittaa minkä tahansa määrän lisälaskelmia tai salauksia.
1. IND-CCA1:n määritelmässä hyökkääjä ei voi suorittaa enempää salauksen purkamista oraclella .
2. IND-CCA2-määritelmässä hyökkääjä voi tehdä lisää oraakkelikutsuja , mutta ei voi käyttää C -salatekstiä tehdäkseen niin .
Lopuksi hyökkääjä arvaa b :n arvon .

Salausjärjestelmä on turvallinen IND-CCA1:n tai IND-CCA2:n mielessä, jos kummallakaan vastustajalla ei ole merkittävää etua kyseisessä pelissä.

Ei erotu satunnaisesta melusta

Joskus tarvitaan salausjärjestelmiä , joissa hyökkääjä ei voi erottaa salatekstijonoa satunnaisesta merkkijonosta. [3]

Jos hyökkääjä ei voi edes sanoa, onko viesti olemassa, tämä antaa viestin kirjoittajalle uskottavan kielteisyyden .

Jotkut salattuja viestintäkanavia luovat ihmiset haluavat mieluummin tehdä jokaisen salatekstin sisällön erottumattomaksi satunnaisista tiedoista, mikä vaikeuttaa liikenteen analysointia. [neljä]

Jotkut ihmiset, jotka rakentavat järjestelmiä salatun tiedon tallentamiseen, pitävät parempana, että tiedot eivät eroa satunnaisista tiedoista, jotta ne on helpompi piilottaa . Esimerkiksi tietyntyyppiset levysalaukset , kuten TrueCrypt , yrittävät piilottaa tietoja satunnaisista tiedoista, jotka jäävät jäljelle tietyntyyppisten tietojen tuhoamisesta . Toisena esimerkkinä jotkin steganografiatyypit yrittävät piilottaa tietoja saattamalla ne vastaamaan digitaalisten valokuvien "satunnaisen" kuvakohinan tilastollisia ominaisuuksia .

Tällä hetkellä on olemassa erityisesti suunniteltuja salausalgoritmeja kiellettäville salausjärjestelmille , joissa salatekstejä ei voi erottaa satunnaisista bittijonoista. [5] [6] [7]

Jos salausalgoritmi E voidaan rakentaa siten, että viestin m selkeän tekstin tunteva hyökkääjä (yleensä määritelty polynomiaikaiseksi havainnoijaksi) ei pysty erottamaan E(m):n ja juuri luodun satunnaisen bittijonon välillä. sama pituus kuin E(m), niin tästä seuraa, että jos E(m1) on yhtä pitkä kuin E(m2), nämä kaksi salatekstiä ovat hyökkääjälle mahdottomia erottaa toisistaan, vaikka hän tietäisi selkeät tekstit m1 ja m2 (IND -CPA). [kahdeksan]

Useimmat sovellukset eivät vaadi salausalgoritmia luodakseen salatekstejä , joita ei voida erottaa satunnaisista biteista. Jotkut kirjoittajat kuitenkin uskovat, että tällaiset salausalgoritmit ovat käsitteellisesti yksinkertaisempia ja helpompia työstää ja monipuolisempia käytännössä - ja useimmat IND-CPA- salausalgoritmit näyttävät tuottavan salattuja viestejä , joita ei voi erottaa satunnaisista bitteistä. [9]

Ekvivalentit ja niiden merkitys

Tuntemattomuus on tärkeä ominaisuus salattujen viestien luottamuksellisuuden ylläpitämisessä. On kuitenkin havaittu, että joissakin tapauksissa erottamattomuusominaisuus tarkoittaa muita ominaisuuksia, jotka eivät ole eksplisiittisesti turvallisuuteen liittyviä. Joskus tällaisilla vastaavilla määritelmillä on täysin erilaiset merkitykset. Esimerkiksi erottamattomuusominaisuuden IND-CPA:n merkityksessä tiedetään vastaavan joustamattomuusominaisuutta vastaaville skenaariohyökkäyksille (NM-CCA2). Tämä vastaavuus ei ole heti ilmeinen, koska joustamattomuus on viestin eheyteen liittyvä ominaisuus, ei luottamuksellisuus. On myös osoitettu, että erottamattomuus voi seurata jostain muusta määritelmästä tai päinvastoin. Seuraavassa luettelossa on joitain tunnettuja seurauksia, vaikka ne eivät olekaan täydellisiä:

IND-CPA :n semanttinen suojaus CPA:lle. [kymmenen] $\scriptstyle \Leftrightarrow$
NM-CPA (joustamattomuus valituille selkokielisille hyökkäyksille ) IND-CPA. [yksi] $\scriptstyle \Rightarrow$
NM-CPA (joustamattomuus valituille selkokielisille hyökkäyksille ) IND-CCA2 . [yksi] $\scriptstyle \not \Rightarrow$
NM-CCA2 (joustamattomuus mukautuville salakirjoituspohjaisille hyökkäyksille) IND-CCA2. [yksi] $\scriptstyle \Leftrightarrow$

Muistiinpanot

↑ 1 2 3 4 5 Krohn, Maxwell. Salausturvallisuuden määritelmistä : Valitun salakirjoituksen hyökkäys uudelleen . – 1999.
↑ Katz, Jonathan; Lindell, Yehuda. Johdatus nykyaikaiseen kryptografiaan : periaatteet ja protokollat . – Chapman ja Hall/CRC, 2007.
↑ Chakraborty, Debrup; Rodriguez-Henriquez, Francisco. Cryptographic Engineering (uuspr.) / Çetin Kaya Koç. - 2008. - S. 340. - ISBN 9780387718170 .
↑ iang. Ei erotettavissa satunnaisesta (20. toukokuuta 2006). Haettu 6. elokuuta 2014. Arkistoitu alkuperäisestä 15. elokuuta 2014. (määrätön)
↑ Bernstein, Daniel J.; Hampuri, Mike; Krasnova, Anna; Lange, Tanja Elligator: Elliptisen käyrän pisteet, joita ei voi erottaa yhtenäisistä satunnaisista merkkijonoista (28. elokuuta 2013). Haettu 23. tammikuuta 2015. Arkistoitu alkuperäisestä 5. marraskuuta 2014. (määrätön)
↑ Möller, Bodo. Julkisen avaimen salausjärjestelmä näennäissatunnaisilla salakirjoituksilla // Computer Security - ESORICS 2004 (uus.) . - 2004. - T. 3193. - S. 335-351. — (Luentomuistiinpanot tietojenkäsittelytieteestä). — ISBN 978-3-540-22987-2 . - doi : 10.1007/978-3-540-30108-0_21 .
↑ Moore, Christopher; Mertens, Stephan. Laskennan luonne (uuspr.) . - 2011. - ISBN 9780191620805 .
↑ Reingold, Omar Pseudosatunnaissyntetisaattorit, funktiot ja permutaatiot 4 (marraskuu 1998). Haettu 7. elokuuta 2014. Arkistoitu alkuperäisestä 19. helmikuuta 2014. (määrätön)
↑ Rogaway, Phillip Nonce-Based Symmetric Encryption 5–6 (1. helmikuuta 2004). Haettu 7. elokuuta 2014. Arkistoitu alkuperäisestä 10. toukokuuta 2013. (määrätön)
↑ Silvio Micali, Shafi Goldwasser Probabilistinen salaus (1984). (määrätön)

Kirjallisuus

Katz, Jonathan; Lindell, Yehuda. Johdatus nykyaikaiseen kryptografiaan : periaatteet ja protokollat . - Chapman & Hall / CRC Press , 2007. - ISBN 978-1584885511 .