Választott titkosított szöveges támadás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. december 21-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A választott – rejtjelezett szöveges támadás olyan kriptográfiai támadás , amelyben a kriptaelemző információkat gyűjt a rejtjelről úgy, hogy kitalálja a rejtjelezett szöveget, és egy ismeretlen kulccsal visszafejti. A kriptoanalizátor általában egy vagy több alkalommal használhatja a visszafejtőt a visszafejtett rejtjelezett szöveg megszerzéséhez. A kapott adatok felhasználásával megpróbálhatja visszaállítani a titkos kulcsot a visszafejtéshez. Vannak olyan titkosítások, amelyeknél ez a fajta támadás sikeres lehet. Ezek a következők: ElGamal-séma ; RSA , az SSL protokollban használatos ; NTRU . A védelem érdekében RSA-OAEP és Cramer-Showe titkosításokat használnak .

A titkosított szöveges támadás lehet adaptív vagy nem adaptív.

Támadás rosszul alkalmazkodó rejtjelezett szövegen

Nem adaptív támadásnál a kriptoanalizátor nem használja fel a korábbi visszafejtések eredményeit, vagyis a titkosított szövegeket előre kiválasztja. Az ilyen támadásokat ebédidős támadásoknak nevezik ( ebédidő vagy CCA1 ).

Támadás adaptívan választott rejtjelezett szöveg alapján

Ellenkező esetben a titkosítási elemző adaptív módon választ ki egy rejtjelezett szöveget, amely a korábbi visszafejtések ( CCA2 ) eredményeitől függ.

Támadás az RSA PKCS#1 titkosítási szabványon alapuló protokollok ellen

Az RSA PKCS#1 szabvány rövid leírása

A nyilvános kulcsú kriptorendszerek ( Public Key Cryptography Standards ) egyik képviselője, az RSA algoritmus alapján. Legyen k az RSA modul bájthossza, n. A PKCS#1 szabványnak számos változata létezik. Ebben a példában az RSAES-PKCS1-v1_5 verziót digitális aláírás nélkül vesszük figyelembe, az üzenetblokk második bájtja 00 vagy 01. A szabvány maximum k-11 hosszúságú üzenetekkel tud működni. A PKCS#1 szabványos blokk, az EB, k bájtból áll. Alakja EB = 00||02||PS||00||D. Az első két bájt állandó és egyenlő 00-val, illetve 02-val.. A PS egy kitöltési karakterlánc, egy generált pszeudovéletlen szám, amely nem nulla bájtokból áll. A biztonsági szint növelése érdekében ajánlott minden egyes titkosításhoz új PS blokkot generálni. Ennek hossza rendre k-3-|D|, ahol D az adatblokk, |D| a bájt hossza. A PS blokk hosszának legalább 8 bájtnak kell lennie. A PS és D blokkokat null byte-tal kell elválasztani. A kényelem kedvéért a jövőben nem adjuk meg az RSAES-PKCS1-v1_5 szabványt, hanem PKCS#1-ként fogjuk megjelölni. Legyen n, e a nyilvános kulcs és p, q, d a titkos kulcs. Az R.S.A. Az EB blokkot x egész számmá alakítjuk, és az RSA algoritmussal titkosítjuk . A vevő ellenőrzi a titkosított szöveg hosszát , dekódolja , blokkolja, és ellenőrzi a helyes első két bájtot, amelyek elválasztják a null byte-ot és a PS blokk hosszát. Ha az ellenőrzés sikertelen, hibaüzenet jelenik meg. $n=pq,d=e^{-1}\operátornév {mod} (\phi (n))$ $c=x^{e}\operátornév {mod} (n)$ $c\leqslant n$ $m=c^{d}\operátornév {mod} (n)$

A támadás leírása

Ez a példa egy sikeres támadás lehetőségét szemlélteti egy adaptívan választott rejtjelezett szöveg alapján. Engedje meg, hogy a rejtjelelemző hozzáférjen egy olyan eszközhöz, amely bármely kiválasztott rejtjelezett szöveg esetén jelzi, hogy a megfelelő nyílt szöveg a PKCS#1 szabványos formátumban van-e, és a C rejtjelezett szöveg visszafejtésének feladatával kell szembenéznie. Ily módon az elemző különféle rejtjelezett szövegeket választhat ki. és küldje el őket a készülékre. Miután megkapta a választ, az előzőek eredményei alapján összeállítja a következő rejtjelezett szöveget. Így az eszköztől kapott válaszok és a szabványnak megfelelő nyílt üzenetformátum ismerete alapján a kriptoanalitikus kiszámíthatja a . A támadásban a döntő tényező a nyitott üzenet első két bájtja, amelyek konstansok. Ebben a példában egy olyan algoritmust veszünk figyelembe, amely minimalizálja a nyitott üzenet fogadásához szükséges titkosított szövegek számát. A támadás 3 szakaszra osztható: $m=c^{d}\operátornév {mod} (n)$

Az üzenetnek megfelelő titkosított szöveg lekérése $c_{0}$ $m_{0}$
Olyan kis számok keresése , amelyekre az űrlap rejtjelezett szövegei megfelelnek a PKCS szabványnak. Az elemző minden sikeresen talált esetre a korábbi ismeretek felhasználásával kiszámol egy intervallumsorozatot, amelynek tartalmaznia kell . $s_{i}$ $c_{0}\cdot (s_{i})^{e}\operátornév {mod} (n)$ $s_{i}$ $m_{0}$ $m_{0}$
Csak egy intervallumból álló sorozat keresése. Ebben az esetben az elemző elegendő információval rendelkezik a -ról , hogy kiválassza a kívánt , amelyre az megfelel a PKCS szabványnak. Az érték fokozatosan növekszik, amíg az intervallum egy lehetséges számra nem csökken. $m_{0}$ $s_{i}$ $c_{0}\cdot (s_{i})^{e}\operátornév {mod} (n)$ $s_{i}$

A támadás matematikai leírása

Tegyük fel, hogy a kriptoanalitikus célja az, hogy kiderítse . Mivel k az n bájthossza, akkor . Az elemző kiválasztja az s számot, kiszámolja és elküldi a készüléknek. Ha a készülék üzenetet kap, akkor biztosan tudjuk, hogy az első két bájt 00 és 02. A kényelem kedvéért jelöljük . Tegyük fel, hogy s megfelelő, akkor a becslés igaz . Az ilyen típusú információkat összegyűjtve megtalálhatjuk a m. A titkosított szövegek általában elegendőek, de ez a szám nagymértékben ingadozhat. Írjuk le lépésről lépésre a támadást. $m=c^{d}\operátornév {mod} (n)$ ${\displaystyle 2^{8(k-1)}\leqslant n<2^{8k))$ $c'=c\cdot s^{e}\operátornév {mod} (n)$ $c'$ ${\displaystyle B=2^{8(k-2)))$ $2B\leqslant m\cdot s\operátornév {mod} (n)<3B$ $2^{20}$

Megtalálás $s_{0}$ . Adott egy c egész szám, különböző véletlenszerű egészeket választunk , majd az eszközzel ellenőrizzük, hogy a kifejezés megfelel -e a PKCS szabványnak. Az ily módon sikeresen megtalált első számra , , . $s_{0}$ $c\cdot s_{0}^{e}\operátornév {mod} (n)$ $s_{0}$ $c_{0}=c\cdot (s_{0})^{e}\operátornév {mod} (n)$ $M_{0}={[2B,3B-1]}$ $i=1$
A megfelelő üzenetek megtalálása
1. Keresés indítása. Ha i=1, akkor a legkisebb pozitív számot keressük , amelyre a rejtjelezett szöveg megfelel a PKCS szabványnak. $s_{1}\geqslant {\frac {n}{3B))$ $c_{0}\cdot (s_{1})^{e}\operátornév {mod} (n)$
2. Ellenkező esetben, ha és az intervallumok száma legalább 2, akkor azt a legkisebb egész számot keressük, amelyre a rejtjelezett szöveg megfelel a PKCS szabványnak. $i>1$ $M_{{i-1}}$ $s_{i}>s_{i-1}$ $c_{0}\cdot (s_{i})^{e}\operátornév {mod} (n)$
3. Ellenkező esetben, ha pontosan egy intervallumot (azaz ) tartalmaz, akkor válasszon olyan egész számokat , amelyek kielégítik az és kifejezéseket , amíg a rejtjelezett szöveg nem felel meg a PKCS szabványnak. $M_{{i-1}}$ $M_{i-1}={[a,b]}$ ${\displaystyle s_{i}r_{i))$ $r_{i}\geqslant 2{\frac {bs_{i-1}-2B}{n))$ ${\frac {2B+r_{i}n}{b}}\leqslant s_{i}\leqslant {\frac {3B+r_{i}n}{a}}$ $c_{0}\cdot (s_{i})^{e}\operátornév {mod} (n)$
A megoldáskészlet szűkítése . Ha megtalálta, a rendszer kiszámol egy intervallumsorozatot mind az összesre, mind a . $s_{i}$ $M_{i}$ $M_{i}=\bigcup _{(a,b,r)}[\operátornév {max} (a,[{\frac {2B+rn}{s_{i}}}]),\operátornév {min} (b,[{\frac {3B-1+rn}{s_{i))}])]$ $[a,b]\in M_{i-1}$ ${\frac {as_{i}-3B+1}{n}}\leqslant r\leqslant {\frac {bs_{i}-2B}{n}}$
Megoldás kiszámítása . Ha csak egy intervallumot tartalmaz az űrlap , akkor állítsa be és adja vissza az m-t megoldásként . Ellenkező esetben a 2. lépésre lépünk. $M_{i}$ $M_{i}={[a,a]}$ $m=a(s_{0})^{-1}\operátornév {mod} (n)$ $m=c^{d}\operátornév {mod} (n)$ $i=i+1$

Az első lépés kihagyható, ha C a PKCS szabványnak megfelelő titkosított üzenet. A második lépésben az egyezés a -val kezdődik , mivel kisebb értékek esetén az üzenet nem felel meg a PKCS szabványnak. A szám arra szolgál, hogy az intervallumot minden iterációnál körülbelül a felére osztja. $s_{1}$ ${\frac {n}{3B))$ ${\displaystyle m_{0}s_{1))$ $r_{i}\geqslant 2{\frac {bs_{i-1}-2B}{n))$

Támadáselemzés

A PKCS szabványnak megfelelő üzenet valószínűségének becslése

Legyen annak a valószínűsége, hogy egy véletlenszerűen kiválasztott rejtjelezett szövegnek megfelelő egyszerű szöveges formátuma van , és legyen annak a valószínűsége, hogy bármely véletlenszerűen kiválasztott egész szám első 2 bájtja 00 és 02. Mivel , ebből következik, hogy . Az RSA modulust általában 8 többszöröseként választják. Tehát általában közel . Annak a valószínűsége, hogy egy PS-blokk legalább 8 nullától eltérő bájtot tartalmaz, amelyek egy nullbájttal végződnek, . Feltételezve, hogy n legalább 512 bit (k > 64), akkor . Szóval . $\Pr(P\cap A)$ $\Pr(A)={\frac {B}{n))$ $2^{8}B<n<2^{16}B$ ${\displaystyle 2^{-16}<\Pr(A)<2^{-8))$ $\Pr(A)$ $2^{-16}$ $\Pr(P|A)=({\frac {255}{256)))^{8}\cdot (1-({\frac {255}{256)))^{k-10} )$ $0,18<\Pr(P|A)<0,97$ $0,18\cdot 2^{-16}<\Pr(P\cap A)<0,97\cdot 2^{-8}$

Becslő intervallumok

M_{i}

Bizonyítsuk be . Mivel megfelel a PKCS szabványnak, ebből következik, hogy . Tegyük fel, hogy . Tehát van egy intervallum -val . Mivel megfelel a PKCS szabványnak, van egy olyan r, amely ezért , , azaz az egyik intervallumban benne van. ${\displaystyle m_{0}\in M_{i))$ $m_{0}$ $2B\leqslant m_{0}\leqslant 3B-1$ $m_{0}\in M_{0}$ $m_{0}\in M_{i-1}$ $[a,b]\in M_{i-1}$ $a\leqslant m_{0}\leqslant b$ $m_{0}s_{i}$ $2B\leqslant m_{0}s_{i}-rn\leqslant 3B-1$ $as_{i}-(3B-1)\leqslant rn\leqslant bs_{i}-2B$ ${\frac {2B+rn}{s_{i}}}\leqslant m_{0}\leqslant {\frac {3B-1+rn}{s_{i}}}$ $m_{0}$

Egy támadás összetettségének becslése

Az 1. lépésben az üzenetet véletlenszerűen választja ki, ami azt jelenti, hogy el kell küldenie az üzenetek közelében lévő eszközre, hogy megtalálja . Hasonlóan a 2.1. és 2.2. lépéshez a . Legyen az intervallumok száma -ben . Akkor azért . Az intervallum hosszát felülről az érték határolja . Tudva, hogy a PKCS formátum, az űrlap intervallumait kapjuk . körülbelül intervallumokat fog tartalmazni. Ha , akkor minden intervallum vagy annak egy része benne van, ha átfedésben van az egyik intervallumtal . Egyik intervallum sem fedhet át két intervallumot . Ha az intervallumok véletlenszerű eloszlásúak, akkor annak a valószínűsége, hogy egy metszéspontba kerül, a fenti értékkel határos . Így a for egyenletet azzal a feltételezéssel kapjuk meg, hogy egy intervallumnak tartalmaznia kell az értéket . A mi esetünkben azt várjuk, hogy kb and have . Ezért nagy valószínűséggel egyetlen értéket vesz fel. Ezért a 2.2 lépés várhatóan csak egyszer történik meg. Elemezzük a 2.3 lépést. Létezik tehát tehát . Intervallum hossza . Ezért minden harmadik értékre találhatunk olyan párt , amely kielégíti a 2.3 lépésben szereplő egyenlőtlenségeket . Annak a valószínűsége, hogy kb . Ezért találhatunk , ami nagyjából megfelel a szabványnak rejtjelezett szövegek segítségével. Mivel az in intervallum többi része a 2.3 lépésben felére csökken, várhatóan közel rejtjelezett szövegeket használunk. A sikeres támadáshoz körülbelül titkosított szövegekre lesz szükség . Az összes fent jelzett valószínűséget úgy határoztuk meg, hogy feltételeztük, hogy mindegyik független. Legyen és feleljen meg a PKCS szabványnak, és azonos PS blokkhosszú legyen. Ekkor valamilyen egész számra megkapjuk és . Akkor nagy valószínűséggel megfelelnek a PKCS szabványnak, hiszen gyakran megfelelnek a szabványnak is. Általában n-t 8 többszörösének választják, mivel ennek kicsi a valószínűsége. A , bithosszúságú modul kényelmes az elemző számára, mivel ebben az esetben körülbelül titkosított szövegek szükségesek a sikeres támadáshoz. ${\frac {1}{\Pr(P\cap A)))$ $s_{0}$ $i\geqslant 1$ $w_{i}$ $M_{i}$ ${\displaystyle w_{i}\leqslant 1+2^{i-1}s_{i}({\frac {B}{n)))^{i))$ $i\geqslant 1$ $M_{i}$ ${\displaystyle {\frac {B}{s_{i))))$ $m_{0}s_{i}$ ${\frac {Bs_{i}}{n}}$ $I_{r}=[[{\frac {2B+rn}{s_{i}}}],[{\frac {3B-1+rn}{s_{i}}}]]$ $M_{1}$ ${\frac {Bs_{i}}{n}}$ $i>1$ $I_r$ $M_{i}$ $I_r$ $M_{{i-1}}$ $I_r$ $M_{{i-1}}$ $I_r$ $M_{{i-1}}$ $({\frac {1}{s_{i}}}+{\frac {1}{s_{i-1}}})w_{i-1}$ $w_{i}$ $m_{0}$ $s_{2}$ ${\frac {2}{\Pr(P\cap A)))$ $2{\frac {({\frac {B}{n)))^{2}}{\Pr(P\cap A)))={\frac {2B}{n\Pr(P| A)))<{\frac {2B}{0.18n}}<{\frac {1}{20}}$ ${\displaystyle w_{2))$ $M_{i-1}={[a,b]}$ $a\leqslant m_{0}\leqslant b$ ${\frac {2B+r_{i}n}{b}}\leqslant {\frac {2B+r_{i}n}{m_{0))}\leqslant s_{i}\leqslant {\ frac {3B-1+r_{i}n}{m_{0}}}\leqslant {\frac {3B-1+r_{i}n}{a}}$ ${\frac {3B-1+r_{i}n}{a}}-{\frac {2B+r_{i}n}{b}}\geqslant {\frac {3B-1+r_{ i}n}{m_{0))}-{\frac {2B+r_{i}n}{m_{0))}\geqslant {\frac {B-1}{m_{0))}\geqslant {\frac {B-1}{3B}}$ ${\displaystyle r_{i}s_{i))$ $r_{i}$ $s_{i}\in [{\frac {2B+r_{i}n}{m_{0}}},{\frac {3B-1+r_{i}n}{m_{0}} }]$ ${\frac {1}{2))$ $s_{i}$ ${\frac {2}{\Pr(P|A)))$ $M_{i}$ $m_{0}$ ${\frac {3}{\Pr(P\cap A)))+{\frac {16k}{\Pr(P|A)))$ $\Pr(P\cap A)=0,18\cdot 2^{-16}$ $k=128$ $2^{20}$ $s_{i}$ $m_{0}$ $m_{0}s_{i}$ $j$ $m_{0}=2\cdot 2^{8(k-2)}+2^{8j}PS+D$ $s_{i}m_{0}=2\cdot 2^{8(k-2)}+2^{8j}PS'+D'$ ${\displaystyle (2s_{i}-1)m_{0))$ $(2s_{i}-1)m_{0}=2\cdot 2^{8(k-2)}+2^{8j}(2PS'-PS)+2D'-D$ $\Pr(P\cap A)$ $8k-7$ $2^{13}$

Hozzáférés a visszafejtőhöz

Vegyünk 3 olyan helyzetet, amikor az elemző hozzáférhet egy eszközhöz.

Rendszeres titkosítás . Alice létrehoz egy üzenetet, a PKCS#1 szabvány szerint titkosítja, integritásellenőrzés nélkül, és elküldi Bobnak. Bob visszafejti, és ha a visszafejtett üzenet formátuma nem felel meg a szabványnak, akkor hibát dob, ellenkező esetben a protokoll szerint jár el. Így az elemző Aliceként viselkedhet, és ellenőrizheti, hogy az üzenetek megfelelnek-e a szabványnak. Vegye figyelembe, hogy az elemző támadása akkor is működik, ha a következő lépésben hitelesítést használnak, mivel az elemző megkapja a szükséges információkat, mielőtt a felhasználót hitelesíteni kellene.
Részletes hibaüzenetek . Az integritás-ellenőrzés az RSA-titkosítás fontos része. Ennek egyik módja, hogy aláírja az üzenetet a privát kulccsal, mielőtt a feladó titkosítaná a nyilvános kulccsal. Ekkor a támadó nem tudja véletlenül a megfelelő üzenetet létrehozni. A támadás azonban sikeres lehet. Sikertelen érvényesítés esetén a címzett üzenetet küld, amelyben megadja, hogy hol nem sikerült az érvényesítés. Különösen veszélyezteti a biztonságot azáltal, hogy különböző hibaüzeneteket ad vissza a szabványnak nem megfelelő és az aláírás-ellenőrzési hibát tartalmazó üzenetekhez.
Idő támadás . Egyes üzenetgenerálási lehetőségek a titkosítást és az aláírást egyaránt tartalmazzák. Fontolja meg a műveletek sorrendjét.
1. Az üzenet visszafejtésre kerül.
2. Ha nem felel meg a szabványnak, hibaüzenetet küld.
3. Ellenkező esetben az aláírás ellenőrzésre kerül.
4. Ha az aláírás hibás, akkor hibaüzenet jelenik meg, ellenkező esetben hozzáférés.

Így a vevő válaszidejének mérésével megállapítható, hogy van-e formázási hiba vagy sem.

Irodalom

Bleichenbacher D. Választott titkosított szöveges támadások az RSA titkosítási szabványon alapuló PKCS #1 protokollok ellen // Advances in Cryptology — CRYPTO '98 :18th Annual International Cryptology Conference Santa Barbara, California, USA, 1998. augusztus 23–27. Proceedings / Krawczyk - H. Berlin , Heidelberg , New York, NY , London [stb.] : Springer Berlin Heidelberg , 1998. - 1-12. o. — 524 p. - ( Számítástechnikai előadások jegyzetei ; 1462. kötet) - ISBN 978-3-540-64892-5 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/BFB0055716

Linkek

RSA Data Security Inc. PKCS #1: RSA titkosítási szabvány. – Redwood City, Kalifornia, nov. 1993. 1.5-ös verzió – ftp://ftp.rsa.com/pub/pkcs/ascii/pkcs-1.asc
Bleichenbacher's Attack // Hitelesített kulcscsere (TLS-ben), Kenny Paterson, 2015, 32-41 .