A titkosított szöveg megkülönböztethetetlensége

A titkosított szöveg megkülönböztethetetlensége számos titkosítási rendszer sajátja . Intuitív módon, ha egy rendszer rendelkezik megkülönböztethetetlenségi tulajdonsággal, akkor a támadó nem fogja tudni megkülönböztetni a titkosított szövegek párjait az általa titkosított egyszerű szövegek alapján . A választott nyílt szövegen alapuló támadások megkülönböztethetetlenségi tulajdonságát alapvető követelménynek tekintik a bizonyíthatóan legbiztonságosabb nyilvános kulcsú kriptorendszereknél , bár egyes titkosítórendszerek megkülönböztethetetlenségi tulajdonsággal is rendelkeznek a választott nyílt szövegen alapuló támadások és a választott titkosított szövegen alapuló adaptív támadások esetében. A választott egyszerű szöveges támadások megkülönböztethetetlensége a rendszer szemantikai biztonságának megfelelője, ezért ezeket a meghatározásokat sok kriptográfiai bizonyításban felcserélhetőnek tekintik.

A titkosítási rendszer a megkülönböztethetetlenség [1] szempontjából biztonságosnak tekinthető, ha az ellenfél által meghatározott kételemes üzenettérből véletlenszerűen kiválasztott titkosított szöveget kapott támadó nem tudja lényegesen jobb valószínűséggel azonosítani az ennek a rejtjelezett szövegnek megfelelő nyílt szöveget . mint véletlenszerű találgatással (1⁄2 ). Ha bármelyik támadónak sikerül felismernie a kiválasztott rejtjelezett szöveget 1⁄2-nél lényegesen nagyobb valószínűséggel, akkor azt mondják, hogy a támadónak "előnye" van a rejtjelezett szöveg felismerésében, és a rendszer nem tekinthető biztonságosnak a megkülönböztethetetlenség szempontjából. . Ez a meghatározás magában foglalja azt az elképzelést, hogy egy biztonságos rendszerben a támadónak nem szabad információhoz jutnia a titkosított szöveg láttán . Ezért a támadónak képesnek kell lennie a titkosított szövegek közötti különbségtételre, mintha véletlenszerűen tippelne.

Formális definíciók

A megkülönböztethetetlenség szempontjából a biztonságnak számos meghatározása van, a támadó képességeivel kapcsolatos feltételezésektől függően. Általában a következő analógiát használják. A kriptorendszer egyfajta játék . Ezenkívül egy kriptorendszer akkor tekinthető biztonságosnak, ha egyik résztvevő sem nyerheti meg a játékot lényegesen nagyobb valószínűséggel, mint egy véletlenszerűen cselekvő résztvevő. A kriptográfiában leggyakrabban használt fogalmak a megkülönböztethetetlenség a választott szöveges támadásoknál (rövidítve IND-CPA), a megkülönböztethetetlenség a (nem adaptív) választott titkosított szöveges támadásoknál (IND-CCA1) és a megkülönböztethetetlenség az adaptív, választott titkosított szöveges támadásoknál (IND- CPA). CCA2). A biztonság a fenti definíciók mindegyikének értelmében magában foglalja az előző definíciók értelmében vett biztonságot is: az IND-CCA1 biztonságos titkosítási rendszer egyben IND-CPA biztonságos is, és ennek megfelelően az IND-CCA2 biztonságos rendszer egyaránt IND-CCA1. és IND-CPA biztonságos. Így a biztonság az IND-CCA2 értelmében a legerősebb a három definíció közül.

Kiválaszthatatlan egyszerű szöveges támadások (IND-CPA)

Az aszimmetrikus kulcsú titkosítás valószínűségi algoritmusa esetén az IND-CPA [2] értelmében vett megkülönböztethetetlenséget a támadó és a tesztelő következő játéka határozza meg. A számítási biztonságon alapuló rendszerek esetében a támadót egy valószínűségi polinomiális Turing-gép modellezi , ami azt jelenti, hogy be kell fejeznie a játékot, és polinomiális számú időlépésben tippelnie kell. Ebben a definícióban az E(PK, M ) az M üzenet titkosított szövegét jelöli, amelyet a PK kulcs használatával kapunk :

A tesztelő valamilyen k biztonsági paraméter (pl. kulcsméret bitben) alapján generál egy PK , SK kulcspárt, és közzéteszi a PK -t a támadónak. A teszter megmenti az SK -t .
A támadó polinomiálisan korlátozott számú titkosítást vagy egyéb műveletet hajthat végre.
Végül a támadó két különálló nyílt szöveget mutat be a tesztelőnek. ${\displaystyle \scriptstyle M_{0},M_{1))$
A tesztelő véletlenszerűen választja ki a b {0, 1} bitet, és visszaküldi a tesztelt C = E(PK, ) titkosított szöveget a támadónak. $\scriptstyle \in$ ${\displaystyle \scriptstyle M_{b))$
A támadó tetszőleges számú további számítást vagy titkosítást végezhet. Végül csak a b értékét írja ki .

Egy kriptorendszer biztonságos az IND-CPA értelmében, ha bármely hiteles támadó polinomiális időben csak csekély "előnnyel" rendelkezik a rejtjelezett szövegek megkülönböztetésében a véletlenszerű találgatásokkal szemben. A támadónak elhanyagolható "előnye" van, ha a fenti játékot valószínűséggel megnyeri , ahol elhanyagolható függvény a k biztonsági paraméterre , azaz bármely (nullatól eltérő) polinomfüggvényre , amelynek van , úgy, hogy az összes esetében . $\scriptstyle \left({\frac {1}{2}}\right)\,+\,\epsilon (k)$ $\scriptstyle \epsilon (k)$ $\scriptstyle poly()$ $\scriptstyle k_{0}$ $\scriptstyle |\epsilon (k)|\;<\;\left|{\frac {1}{poly(k)))\right|$ ${\displaystyle \scriptstyle k\;>\;k_{0))$

Annak ellenére, hogy a támadó ismeri a PK -t , az E valószínűségi természete azt jelenti, hogy a rejtjelezett szöveg csak egy lesz a sok érvényes rejtjelezett szöveg közül, ezért a kapott rejtjelezett szövegek titkosítása és összehasonlítása a tesztelő titkosításával nem jelent jelentős előnyt a támadónak. $\scriptstyle M_{0}$ $\scriptstyle M_{1}$ ${\displaystyle \scriptstyle M_{b))$ $\scriptstyle M_{0}$ $\scriptstyle M_{1}$

Bár a fenti meghatározás az aszimmetrikus kulcsú titkosítási rendszerekre vonatkozik, a szimmetrikus esethez igazítható, ha a nyilvános kulcsú titkosítási funkciót az oracle titkosítással helyettesítjük , amely tárolja a titkosítási titkos kulcsot, és a támadó kérésére tetszőleges nyílt szövegeket titkosít.

A kiválasztott titkosított szöveges támadások/adaptív titkosított szöveges támadások megkülönböztethetősége (IND-CCA1, IND-CCA2)

Az IND-CCA1 és IND-CCA2 [1] értelmében vett biztonság az IND-CPA értelmében vett rendszermegbízhatósághoz hasonlóan definiálható. A nyilvános kulcson (vagy szimmetrikus esetben az oracle titkosításon ) kívül azonban a támadó hozzáférést kap az oracle decryption szolgáltatáshoz, amely a támadó kérésére tetszőleges titkosított szöveget fejt vissza, visszaadva a sima szöveget . Az IND-CCA1 definíciójában a támadó csak addig kérdezheti le az orákulumot, amíg meg nem kapja a tesztelés alatt álló rejtjelezett szöveget. Az IND-CCA2 definícióban a támadó továbbra is lekérdezheti az orákulumot , miután megkapta a tesztelt rejtjelezett szöveget, azzal a kitétellel, hogy nem küldheti be visszafejtésre (különben a definíció triviális lenne).

A tesztelő valamilyen k biztonsági paraméter (pl. kulcsméret bitben) alapján generál egy PK , SK kulcspárt, és közzéteszi a PK -t a támadónak. A teszter megmenti az SK -t .
A támadó tetszőleges számú titkosítást , dekódolási hívást végrehajthat egy orákulum segítségével tetszőleges rejtjelezett szövegek alapján vagy egyéb műveleteket.
Végül a támadó két különálló nyílt szöveget mutat be a tesztelőnek. ${\displaystyle \scriptstyle M_{0},\,M_{1))$
A tesztelő véletlenszerűen választja ki a b {0, 1} bitet, és visszaküldi a tesztelt C = E(PK, ) titkosított szöveget a támadónak. $\scriptstyle \in$ ${\displaystyle \scriptstyle M_{b))$
A támadó tetszőleges számú további számítást vagy titkosítást végezhet.
1. Az IND-CCA1 definíciójában a támadó nem hajthat végre további visszafejtést az oracle segítségével .
2. Az IND-CCA2 definícióban a támadó további oracle hívásokat indíthat, de nem használhatja a C rejtjelezett szöveget erre .
Végül a támadó kitalálja b értékét .

Egy kriptorendszer biztonságos az IND-CCA1 vagy IND-CCA2 értelmében, ha egyik ellenfél sem rendelkezik jelentős előnnyel az adott játékban.

Megkülönböztethetetlen a véletlenszerű zajtól

Néha olyan titkosítási rendszerekre van szükség , amelyekben a titkosított szöveget a támadó nem tudja megkülönböztetni a véletlenszerű karakterlánctól. [3]

Ha a támadó még azt sem tudja megmondani, hogy létezik-e az üzenet, ez elfogadható tagadhatóságot ad az üzenetet író személynek .

Vannak, akik titkosított kommunikációs csatornákat hoznak létre, a forgalomelemzés megnehezítése érdekében az egyes titkosított szövegek tartalmát a véletlenszerű adatoktól megkülönböztethetetlenné teszik. [négy]

Néhányan, akik titkosított adatok tárolására rendszereket építenek, jobban szeretik, ha az adatok nem különböztethetők meg a véletlenszerű adatoktól, hogy megkönnyítsék az elrejtést . Például egyes lemeztitkosítási típusok , mint például a TrueCrypt , megkísérlik elrejteni az adatokat a bizonyos típusú adatmegsemmisítésekből visszamaradt véletlenszerű adatokban . Egy másik példaként a szteganográfia bizonyos típusai megpróbálják elrejteni az adatokat azáltal, hogy megfelelnek a digitális fényképek "véletlenszerű" képzajának statisztikai jellemzőinek .

Jelenleg speciálisan kifejlesztett kriptográfiai algoritmusok léteznek a tagadható titkosítási rendszerekhez , amelyekben a rejtjelezett szövegek megkülönböztethetetlenek a véletlenszerű bitláncoktól. [5] [6] [7]

Ha az E titkosítási algoritmus megszerkeszthető úgy, hogy egy támadó (általában polinomiális idejű megfigyelőként definiálva) az m üzenet nyílt szövegét ismerve nem tud különbséget tenni E(m) és az üzenet frissen generált véletlenszerű bitsora között. azonos hosszúságú, mint E(m), akkor ebből az következik, hogy ha E(m1) azonos hosszúságú E(m2)-vel, akkor ez a két rejtjelezett szöveg megkülönböztethetetlen lesz egymástól a támadó számára, még akkor sem, ha ismeri az m1 és m2 nyílt szöveget. (IND -CPA). [nyolc]

A legtöbb alkalmazás nem igényel titkosítási algoritmust olyan rejtjelezett szövegek létrehozásához , amelyek nem különböztethetők meg a véletlenszerű bitektől. Egyes szerzők azonban úgy vélik, hogy az ilyen titkosítási algoritmusok fogalmilag egyszerűbbek és könnyebben kezelhetők, a gyakorlatban pedig sokoldalúbbak – és úgy tűnik, hogy a legtöbb IND-CPA titkosítási algoritmus olyan titkosított üzeneteket állít elő , amelyek megkülönböztethetetlenek a véletlenszerű bitektől. [9]

Egyenértékűek és jelentésük

A kiismerhetetlenség fontos tulajdonság a titkosított üzenetek titkosságának megőrzéséhez. Azonban azt találták, hogy bizonyos esetekben a megkülönböztethetetlen tulajdonság más, nem kifejezetten biztonsággal kapcsolatos tulajdonságokat is jelent. Néha az ilyen ekvivalens definícióknak teljesen más jelentése van. Például az IND-CPA értelmében vett megkülönböztethetetlenségi tulajdonságról ismert, hogy egyenértékű a hasonló forgatókönyvű támadások rugalmatlansági tulajdonságával (NM-CCA2). Ez az egyenértékűség nem azonnal nyilvánvaló, mivel a rugalmatlanság az üzenet integritásához, nem pedig a bizalmassághoz kapcsolódó tulajdonság. Azt is kimutatták, hogy a megkülönböztethetetlenség következhet más definíciókból, vagy fordítva. Az alábbi lista felsorol néhány ismert következményt, bár ezek messze nem teljesek:

IND-CPA szemantikai biztonság a CPA-hoz. [tíz] $\scriptstyle \Leftrightarrow$
NM-CPA (rugalmasság a választott egyszerű szöveges támadásokhoz ) IND-CPA. [egy] $\scriptstyle \Rightarrow$
NM-CPA (rugalmasság a választott egyszerű szöveges támadásokhoz ) IND-CCA2 . [egy] $\scriptstyle \not \Rightarrow$
NM-CCA2 (rugalmasság az adaptív titkosított szöveg alapú támadásokhoz) IND-CCA2. [egy] $\scriptstyle \Leftrightarrow$

Jegyzetek

↑ 1 2 3 4 5 Krohn, Maxwell. A kriptográfiai biztonság definícióiról : A választott titkosított szövegű támadás újralátogatása . – 1999.
↑ Katz, Jonathan; Lindell, Yehuda. Bevezetés a modern kriptográfiába : alapelvek és protokollok . – Chapman és Hall/CRC, 2007.
↑ Chakraborty, Debrup; Rodriguez-Henriquez, Francisco. Cryptographic Engineering (neopr.) / Çetin Kaya Koç. - 2008. - S. 340. - ISBN 9780387718170 .
↑ iang. Nem különböztethető meg a véletlentől (2006. május 20.). Letöltve: 2014. augusztus 6. Az eredetiből archiválva : 2014. augusztus 15.. (határozatlan)
↑ Bernstein, Daniel J.; Hamburg, Mike; Krasznova, Anna; Lange, Tanja Elligator: Elliptikus görbe pontok megkülönböztethetetlenek az egységes véletlenszerű húroktól (2013. augusztus 28.). Letöltve: 2015. január 23. Az eredetiből archiválva : 2014. november 5.. (határozatlan)
↑ Möller, Bodo. Nyilvános kulcsú titkosítási séma pszeudo-véletlen titkosított szövegekkel // Számítógép-biztonság - ESORICS 2004 (újj.) . - 2004. - T. 3193. - S. 335-351. — (Számítástechnikai előadásjegyzetek). — ISBN 978-3-540-22987-2 . - doi : 10.1007/978-3-540-30108-0_21 .
↑ Moore, Christopher; Mertens, Stephan. A számítás természete (neopr.) . - 2011. - ISBN 9780191620805 .
↑ Reingold, Omar Álvéletlen szintetizátorok, függvények és permutációk 4 (1998. november). Letöltve: 2014. augusztus 7. Az eredetiből archiválva : 2014. február 19. (határozatlan)
↑ Rogaway, Phillip Nonce-Based Symmetric Encryption 5–6 (2004. február 1.). Letöltve: 2014. augusztus 7. Az eredetiből archiválva : 2013. május 10. (határozatlan)
↑ Silvio Micali, Shafi Goldwasser Valószínűségi titkosítás (1984). (határozatlan)

Irodalom

Katz, Jonathan; Lindell, Yehuda. Bevezetés a modern kriptográfiába : alapelvek és protokollok . - Chapman & Hall / CRC Press , 2007. - ISBN 978-1584885511 .